Описание
int levenshtein (string str1, string str2)int levenshtein (string str1, string str2, int cost_ins, int cost_rep, int cost_del)
int levenshtein (string str1, string str2, function cost)
- Функция возвращает расстояние Левенштейна между двумя строками, или
-1, если хотя бы одна из строк длиннее 255 символов (этого более чем
достаточно для сравнения имен или поиска по словарю, а проводить
генетический анализ на PHP просто несерьезно).
- Расстояние Левенштейна - это минимальное количество вставок, замен и
удалений символов, необходимое для преобразования
str1 в str2.
Сложность алгоритма равна O(m*n),
где n и m - длины строк
str1 и str2 (неплохо по
сравнению с similar_text(), имеющей сложность O(max(n,m)**3),
но все же довольно много).
- В простейшей форме функция принимает в качестве аргументов две строки
и возвращает минимальное количество вставок, замен и
удалений символов, необходимое для преобразования
str1 в str2.
Второй вариант принимает три дополнительных аргумента, задающих
стоимость операций вставки, замены и удаления. Этот вариант
универсальнее первого, но не так эффективен.
Третий вариант (который еще не реализован) будет наиболее
универсальным, но и самым медленным. Он будет принимать в качестве
третьего аргумента пользовательскую функцию, которая будет вычислять
стоимость каждой возможной операции.
- Пользовательская функция будет иметь следующие аргументы:
- тип операции: 'I', 'R' or 'D'
- текущий символ в строке 1
- текущий символ в строке 2
- текущая позиция символа в строке 1
- текущая позиция символа в строке 2
- количество символов, оставшихся в строке 1
- количество символов, оставшихся в строке 2
Пользовательская функция должна возвращать положительное целое,
определяющее стоимость конкретной операции.
- Использование пользовательской функции позволяет учитывать различия
между символами и даже контекст символов при вычислении стоимости
операций вставки, замены и удаления, но ценой потери скорости по
сравнению с двумя первыми вариантами.
- См. также описание функций soundex(),
join
localeconv
22222
