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

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 грамм

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 (равно).
   
   

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

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

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

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

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

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

Я применяю 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].... 

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

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

 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, но для сопоставления с одним словом это та же идея. Вы работаете с веткой и привязкой, и в любой момент вы можете сделать любое изменение, которое вам нравится, если вы дадите ему стоимость.

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

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

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

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

Если первая строка 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 *, а затем меньше близких совпадений и т. Д.