Во-первых, расстояние Левенштейна определяется как минимальное количество правок, необходимых для преобразования строки 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. Таким образом, вы можете пропустить проверку строк, длина которых слишком различна.
Одна из проблем, с которой вы можете столкнуться, заключается в том, что "1-я улица"имеет довольно большое расстояние от «Первой улицы», даже если вы, вероятно, хотите считать их идентичными.Самый простой способ справиться с этим - это, вероятно, преобразовать строки в каноническую форму перед выполнением сравнений.Таким образом, вы можете сделать все строки строчными, использовать словарь, который отображает «1-й» на «первый» и т. Д. Этот словарь может стать довольно большим, но я не знаю лучшего способа решения этих проблем.
Поскольку вы пометили этот вопрос php, я предполагаю, что вы хотите использовать php для этого.В PHP есть встроенная функция levenshtein (), но обе строки должны содержать не более 255 символов.Если это не достаточно долго, вам придется сделать свой собственный.Кроме того, вы исследуете с использованием difflib Python.