levenshtein

Расстояние Левенштейна - это минимальное количество вставок, замен и удалений символов, необходимое для преобразования $str1 в $str2. Сложность алгоритма равна O(m*n), где n и m - длины строк $str1 и $str2 (неплохо по сравнению с similar_text(), имеющей сложность O(max(n,m)**3), но все же довольно много).

В простейшей форме функция принимает в качестве аргументов две строки и возвращает минимальное количество вставок, замен и удалений символов, необходимое для преобразования $str1 в $str2.