Во-первых, расстояние Левенштейна определяется как минимальное количество правок, необходимых для преобразования строки 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, A).
- abs(len(A) - len(B)) — это нижняя граница расстояния между строками A и B. Таким образом, вы можете пропустить проверку строк, длина которых слишком различается.
Одна проблема, с которой вы можете столкнуться, заключается в том, что «1st St.» находится довольно далеко от «Первой улицы», хотя вы, вероятно, захотите считать их идентичными. Самый простой способ справиться с этим, вероятно, состоит в том, чтобы преобразовать строки в каноническую форму перед выполнением сравнений. Таким образом, вы можете сделать все строки строчными, использовать словарь, который отображает «1-й» на «первый» и т. д. Этот словарь может стать довольно большим, но я не знаю лучшего способа справиться с этими проблемами.
Поскольку вы отметили этот вопрос как php, я предполагаю, что вы хотите использовать для этого php. В PHP есть встроенная функция levenshtein(), но обе строки должны содержать не более 255 символов. Если этого недостаточно, вам придется сделать свой собственный. В качестве альтернативы вы исследуете с помощью difflib Python.
person
David Alves
schedule
27.07.2010
