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

Question

У меня был некоторый успех при сравнении строк с использованием функции PHP levenshtein .

Однако для двух строк, которые содержат подстроки, которые поменялись местами, алгоритм считает их как целые новые подстроки.

Например:

levenshtein("The quick brown fox", "brown quick The fox"); // 10 differences

рассматриваются как имеющие общего чем:

levenshtein("The quick brown fox", "The quiet swine flu"); // 9 differences

Я бы предпочел алгоритм, который видел, что первые два были более похожи.

Как я могу придумать функцию сравнения, которая может идентифицировать подстроки, у которых положение переключателя отличается от правок?

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

То, чего я пытаюсь добиться, - это сравнить два факта о людях, которые являются строками свободного текста, и решить, насколько вероятно, что эти факты указывают на тот же факт. Фактами могут быть школа, которую кто-то посещал, например, имя их работодателя или издателя. В двух записях одна и та же школа может быть написана по-разному, слова в другом порядке, дополнительные слова и т. Д., Поэтому совпадение должно быть несколько нечетким, если мы хотим сделать предположение, что они относятся к одной и той же школе. До сих пор это работает очень хорошо для орфографических ошибок (я использую фенетический алгоритм, похожий на метафон поверх всего этого), но очень плохо, если вы переключаете порядок слов, которые обычно встречаются в школе: «ххх колледж» против "колледж ххх".

Answer 1

N-грамм

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

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

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

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

А и В делят 18 2 грамма

Только доля A и C 8 2 грамма

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

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

TF-IDF и косинус сходство

Не столь тривиальная альтернатива, но основанная на теории информации, будет использовать термин термин «частота - обратная частота документа» (tf-idf) , чтобы взвесить токены, построить векторы предложений и затем использовать косинусное сходство как показатель сходства.

Алгоритм:

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

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

Относительно других ответов. модификация Дамерау – Левенштейна поддерживает только транспонирование двух соседних символов. Метафон был разработан, чтобы соответствовать словам, которые звучат одинаково и не для сопоставления сходства.

Answer 2

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

Answer 3

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

Answer 4

Я внедрял Левенштейна в проверку орфографии.

То, что вы просите, это считать транспонирование как 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]....

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

Answer 5

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

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

Answer 6

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

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

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

Answer 7

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

Answer 8

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

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

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

Answer 9

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

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

Пример:

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

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