Как я могу создать порог для подобных строк, используя расстояние Левенштейна и учет опечаток?

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

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

Есть ли способ учесть опечатки при создании такого рода порога для сопоставления данных?

Дайте мне знать, если я могу уточнить!

2 3
mysql php levenshtein-distance puzzle

2 ответа:

Во-первых, расстояние Левенштейна определяется как минимальное число правок, требуемых для преобразования строки A в строку B, где правка-это вставка, удаление одного символа или замена символа другим символом. Так что это очень большая "разница между двумя струнами", для определенного определения расстояния. =)

Похоже, что вы ищете функцию расстояния F (A, B), которая дает расстояние между строками A и B и порог N, где строки на расстоянии менее N друг от друга находятся кандидаты на опечатки. В дополнение к расстоянию Левенштейна вы можете также рассмотретьNeedleman–Wunsch . Это в основном одно и то же, но оно позволяет вам предоставить функцию для определения того, насколько близок данный символ к другому символу. Вы можете использовать этот алгоритм с набором весов, которые отражают положение клавиш на клавиатуре QWERTY, чтобы сделать довольно хорошую работу по поиску опечаток. Это будет иметь проблемы с международными клавиатурами хотя.

Если у вас есть k строк и вы хотите найти потенциальные опечатки, число сравнений, которые вам нужно сделать, равно O(k^2). Кроме того, каждое сравнение равно O(len(A)*len(B)). Так что если у вас есть миллион ниточек, вы попадете в беду, если будете делать вещи наивно. Вот несколько советов о том, как ускорить процесс:

  • извиняюсь, если это очевидно, но расстояние Левенштейна симметрично, поэтому убедитесь, что вы не вычисляете F (A, B) и F(B, Ля).
    • Abs (len (A) - len(B)) - это нижняя граница расстояния между строками A и B. Поэтому вы можете пропустить проверку строк, длина которых слишком различна.

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

Поскольку вы отметили этот вопрос php, я предполагаю, что вы хотите использовать php для этого. PHP имеет встроенную функцию levenstein (), но обе строки должны содержать не более 255 символов. Если этого будет недостаточно, вам придется сделать свой собственный. Кроме того, вы исследуете с помощью difflib Python.

7

Вы должны проверить эту книгу:

Http://nlp.stanford.edu/IR-book/pdf/irbookonlinereading.pdf

Есть хорошая глава (3.3) о проверке орфографии

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

Удачи

0