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

Question

Я добился некоторого успеха, сравнивая строки с помощью PHP левенштейн функция.

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

Например:

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

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

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

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

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

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

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

Answer 1

N-граммы

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

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

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

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

A и B делят 18 2 грамма

А и С делят только 8 2 грамма

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

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

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

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

Алгоритм:

<Ол>

Рассчитайте 2-символьную частоту токена (tf) для каждого предложения.

Рассчитайте частоты обратных предложений (idf), которые представляют собой логарифм отношения числа всех предложений в корпусе (в данном случае 3), деленного на количество раз, когда конкретный токен появляется во всех предложениях. В этом случае th находится во всех предложениях, поэтому у него нулевое информационное содержание (log (3/3) = 0).

Создайте матрицу tf-idf, умножив соответствующие ячейки в таблицах tf и idf.

Наконец, вычислите матрицу сходства косинусов для всех пар предложений, где A и B - веса из таблицы tf-idf для соответствующих токенов. Диапазон составляет от 0 (не похоже) до 1 (равно).

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

По поводу других ответов. Damerau & # 8211; Левенштейн поддерживает только транспонирование двух двух соседние символы. Метафон был разработан для соответствия словам, которые звучат одинаково и не для сопоставления сходства.

Answer 2

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

Answer 3

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

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

Answer 5

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

Вы просите считать транспозиции как 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 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]);
  }
}

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

Answer 7

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

Answer 8

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

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

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

Answer 9

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

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

Пример:

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

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