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

Ответ 1

N-граммы

Используйте N-grams, которые поддерживают многосимвольные транспозиции по всему тексту.

Общая идея состоит в том, что вы разбиваете две указанные строки на все возможные 2-3 символьные подстроки (n-граммы) и обрабатываете количество общих n-граммов между двумя строками как их метрику подобия. Это можно затем нормализовать, разделив общее число на общее число n-граммов в более длинной строке. Это тривиально для вычисления, но довольно мощного.

Для примерных предложений:

A. The quick brown fox
B. brown quick The fox
C. The quiet swine flu

Доля A и B 18 2 грамма

A и C используют только 8 2 грамма

из 20 всего возможного.

Это более подробно обсуждалось в Gravano et al. бумага.

tf-idf и сходство с косинусом

Не столь тривиальная альтернатива, но основанная на теории информации, заключалась бы в использовании термина сходство с косинусом как метрику подобия.

Алгоритм:

• Вычислить 2-символьные частоты токенов (tf) за предложение.
• Вычислить частоты обратного предложения (idf), который является логарифмом частного числа всех предложений в корпусе (в этом случае 3), деленного на количество раз, когда конкретный токен появляется во всех предложениях. В этом случае th во всех предложениях, поэтому он имеет нулевой информационный контент (log (3/3) = 0).
• Произведите матрицу tf-idf, умножив соответствующие ячейки в таблицах tf и idf.
• Наконец, вычислить матрицу подобия косинуса для всех пар предложений, где A и B - веса из таблицы tf-idf для соответствующих токенов. Диапазон от 0 (не похоже) до 1 (равный).
  
  

модификации Левенштейна и Метафон

Относительно других ответов. модификация Damerau-Levenshtein поддерживает только транспонирование двух смежных символов. Metaphone был разработан для соответствия словам, которые звучат одинаково, а не для соответствия подобия.

Ответ 2

Легко. Просто используйте Damerau-Levenshtein расстояние от слов вместо букв.

Ответ 3

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

Ответ 4

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

$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-й более похожи, чем один, три, два и три.

Ответ 5

Я использую levenshtein в проверке орфографии.

То, о чем вы просите, это подсчет транспозиций как 1 редактирование.

Это легко, если вы хотите просто пересчитать перестановки одного слова. Однако для переноса слов 2 или более, дополнение к алгоритму является наихудшим сценарием !(max(wordorder1.length(), wordorder2.length())). Добавление нелинейного субалгоритма к уже квадратичному алгоритму не является хорошей идеей.

Вот как это будет работать.

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);
}

ТОЛЬКО для касания транспозиций. Если вам нужны все транспозиции, вам нужно будет для каждой позиции работать назад с этой точки, сравнивая

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

Итак, вы понимаете, почему они не включают это в стандартный метод.

Ответ 6

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

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]);
  }
}

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

Ответ 7

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

Ответ 8

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

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

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

Ответ 9

Если первая строка A, а вторая - B:

• Разделить A и B на слова
• Для каждого слова в найдите наилучшее совпадающее слово в B (используя levenshtein)
• Удалите это слово из B и поместите его в B * с тем же индексом, что и соответствующее слово в A.
• Теперь сравните A и B *

Пример:

A: The quick brown fox
B: Quick blue fox the
B*: the Quick blue fox

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