|
(PHP 3>= 3.0.17, PHP 4 >= 4.0.1)
levenshtein - высчитывает расстояние Левенштайна/Levenshtein между двумя строками.
Описание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)
Эта функция возвращает Levenshtein-дистанцию между двумя строками-аргументами или -1, если одна из строк-аргументов длиннее предела в 255
символов (255 должно быть более чем достаточно для имени или словарного
сравнения, и никто в здравом уме не будет делать генетический анализ с помощью PHP).
Levenshtein-дистанция определяется как минимальное количество символов, которые вы должны заместить, вставить или удалить, чтобы трансформировать
str1 в str2. Сложность алгоритма равна O(m*n), где n и m это длины строк
str1 и str2 (несколько лучше по сравнению с
similar_text(), которая имеет O(max(n,m)**3), но всё же затратно).
В простейшем случае функция принимает в качестве параметров только две строки и вычисляет только количество операций вставки, замены или удаления,
необходимых для трансформации str1 в str2.
Во втором варианте функция принимает три дополнительных параметра, определяющих цену операций вставки, замены или удаления. Это более общо и
адаптивно, чем первый вариант, но не так эффективно. Третий вариант (ещё не реализованный) будет самым общим и адаптивным, но
также и самым медленным. В нём будет вызываться пользовательская функция, которая определит стоимость каждой возможной операции.
Пользовательская функция будет вызвана со следующими аргументами:
применяемая операция: 'I', 'R' или 'D' фактический символ в строке 1 фактический символ в строке 2 позиция в строке 1 позиция в строке 2 оставшиеся символы в строке 1 оставшиеся символы в строке 2
Пользовательская функция должна возвратить положительное целое число, описывающее цену это конкретной операции, но она может определить использование
только нескольких из предоставленных аргументов. Подход с пользовательской функцией предоставляет возможность учесть
соотношение и/или разницу между определёнными символами, или даже контекст, в котором эти символы появляются, чтобы определить цену операций вставки,
замены и удаления, но ценой потери всей оптимизации, достигнутой для регистров cpu и кэша, которая работала в двух других вариантах.
См. также soundex(), similar_text() и
metaphone(). | 