Недавно мы столкнулись с интересной проблемой, когда в нашей базе данных были обнаружены дублированные пользовательские данные. Мы поняли, что расстояние Левенштейна между большей частью этих данных было просто разницей между двумя указанными строками. Это указывает на то, что если мы просто добавим символы из одной строки в другую, то мы получим одну и ту же строку, и для большинства вещей это кажется лучшим способом для нас учитывать элементы, которые дублируются.
Мы также хотим учитывать опечатки. Поэтому мы начали задумываться о том, как часто люди делают опечатки онлайн за слово и пытаются использовать эти данные на этом расстоянии. Мы не смогли найти такую статистику.
Есть ли способ учета опечаток при создании такого порога для сопоставления данных?
Дайте мне знать, если я смогу прояснить!
Во-первых, расстояние Левенштейна определяется как минимальное количество изменений, необходимых для преобразования строки A в строку B, где редактирование является вставкой или удалением одного символа или заменой символа другим символом. Так что это очень «разница между двумя строками», для определенного определения расстояния. знак равно
Похоже, вы ищете функцию расстояния F (A, B), которая дает расстояние между строками A и B и порогом N, где строки с расстоянием меньше N друг от друга являются кандидатами на опечатки. В дополнение к расстоянию Левенштейна вы также можете рассмотреть Needleman-Wunsch . Это в основном то же самое, но оно позволяет вам предоставить функцию того, насколько близко данный персонаж к другому персонажу. Вы можете использовать этот алгоритм с набором весов, которые отражают позиции клавиш на QWERTY-клавиатуре, чтобы сделать довольно хорошую работу по поиску опечаток. Тем не менее, это имело бы проблемы с международными клавиатурами.
Если у вас есть k строк и вы хотите найти потенциальные опечатки, количество сравнений, которые вам нужно сделать, равно O (k ^ 2). Кроме того, каждое сравнение представляет собой O (len (A) * len (B)). Поэтому, если у вас есть миллион строк, вы столкнетесь с неприятностями, если будете делать что-то наивно. Вот несколько советов о том, как ускорить процесс:
Одна проблема, с которой вы столкнетесь, – это то, что «1-я Санкт-Петербург» имеет довольно большое расстояние от «Первой улицы», хотя вы, вероятно, захотите считать, что они идентичны. Самый простой способ справиться с этим – это, вероятно, преобразовать строки в каноническую форму, прежде чем выполнять сравнения. Таким образом, вы можете сделать все строки строчными, использовать словарь, который отображает «1-й» на «первый» и т. Д. Этот словарь может стать довольно большим, но я не знаю, как лучше справиться с этими проблемами.
Поскольку вы отметили этот вопрос php, я предполагаю, что вы хотите использовать php для этого. PHP имеет встроенную функцию levenshtein (), но обе строки должны содержать не более 255 символов. Если это не достаточно долго, вам придется сделать свой собственный. Кроме того, вы изучаете использование difflib на Python.
Вы должны проверить эту книгу:
http://nlp.stanford.edu/IR-book/pdf/irbookonlinereading.pdf
Имеет хорошую главу (3.3) о проверке орфографии
В ссылках в конце главы перечислены некоторые документы, в которых обсуждаются вероятностные модели
Удачи