Расстояние Левенштейна: как лучше обработать слова, подкачивающие положения?

Its easy. Just use the Damerau-Levenshtein distance on the words instead of letters.

Взрываться на пространствах, сортировать массив, взрываться, а затем Левенштейн.

Вы также можете попробовать это. (просто дополнительное предложение)

$one = metaphone("The quick brown fox"); // 0KKBRNFKS
$two = metaphone("brown quick The fox"); // BRNKK0FKS
$three = metaphone("The quiet swine flu"); // 0KTSWNFL

similar_text($one, $two, $percent1); // 66.666666666667
similar_text($one, $three, $percent2); // 47.058823529412
similar_text($two, $three, $percent3); // 23.529411764706

Это покажет, что 1-й и 2-й больше похожи, чем один и три, два и три.

Возьмите этот ответ и внесите следующее изменение:

void match(trie t, char* w, string s, int budget){
  if (budget < 0) return;
  if (*w=='\0') print s;
  foreach (char c, subtrie t1 in t){
    /* try matching or replacing c */
    match(t1, w+1, s+c, (*w==c ? budget : budget-1));
    /* try deleting c */
    match(t1, w, s, budget-1);
  }
  /* try inserting *w */
  match(t, w+1, s + *w, budget-1);
  /* TRY SWAPPING FIRST TWO CHARACTERS */
  if (w[1]){
    swap(w[0], w[1]);
    match(t, w, s, budget-1);
    swap(w[0], w[1]);
  }
}

Это для поиска по словарю в дереве, но для сопоставления с одним словом, это та же идея. Вы делаете ветвление и ограничение, и в любой момент вы можете вносить любые изменения, которые вам нравятся, если вы платите за это.

Удалите повторяющиеся слова между двумя строками, а затем используйте Левенштейна.

I've been implementing levenshtein in a spell checker.

What you're asking for is counting transpositions as 1 edit.

This is easy if you only wish to count transpositions of one word away. However for transposition of words 2 or more away, the addition to the algorithm is worst case scenario !(max(wordorder1.length(), wordorder2.length())). Adding a non-linear subalgorithm to an already quadratic algorithm is not a good idea.

This is how it would work.

if (wordorder1[n] == wordorder2[n-1])
{
  min(workarray[x-1, y] + 1, workarray[x, y-1] + 1, workarray[x-2, y-2]);
}
  else
{
  min(workarray[x-1, y] + 1, workarray[x, y-1] + 1);
}

JUST for touching transpositions. If you want all transpositions, you'd have to for every position work backwards from that point comparing

1[n] == 2[n-2].... 1[n] == 2[0]....

So you see why they don't include this in the standard method.

Я считаю, что это лучший пример использования поисковой машины в векторном пространстве .

в этом методе каждый документ по существу становится вектором с таким количеством измерений, сколько разных слов во всем корпусе; подобные документы затем занимают соседние области в этом векторном пространстве. Одним из хороших свойств этой модели является то, что запросы также являются просто документами: чтобы ответить на запрос, вы просто вычисляете их положение в векторном пространстве, и ваши результаты являются ближайшими документами, которые вы можете найти. я уверен, что есть готовые решения для PHP.

для нечеткого определения результатов из векторного пространства вы можете рассмотреть возможность применения методики обработки стемминга / аналогичной обработки естественного языка и использования levenshtein для построения вторичных запросов для похожих слов, которые встречаются в вашем общем словарном запасе.