levenshtein

(PHP 3 >= 3.0.17, PHP 4 >= 4.0.1, PHP 5)

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 )

Функция возвращает расстояние Левенштейна между двумя строками, или -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

Пользовательская функция должна возвращать положительное целое, определяющее стоимость конкретной операции.

Использование пользовательской функции позволяет учитывать различия между символами и даже контекст символов при вычислении стоимости операций вставки, замены и удаления, но ценой потери скорости по сравнению с двумя первыми вариантами.

Проверить работу функции levenshtein:

str1=
str2=

Пример использования levenshtein()

// input misspelled word
$input = 'carrrot';

// array of words to check against
$words  = array('apple','pineapple','banana','orange',
                'radish','carrot','pea','bean','potato');

// no shortest distance found, yet
$shortest = -1;

// loop through words to find the closest
foreach ($words as $word) {

    // calculate the distance between the input word,
    // and the current word
    $lev = levenshtein($input, $word);

    // check for an exact match
    if ($lev == 0) {

        // closest word is this one (exact match)
        $closest = $word;
        $shortest = 0;

        // break out of the loop; we've found an exact match
        break;
    }

    // if this distance is less than the next found shortest
    // distance, OR if a next shortest word has not yet been found
    if ($lev <= $shortest || $shortest < 0) {
        // set the closest match, and shortest distance
        $closest  = $word;
        $shortest = $lev;
    }
}

echo "Input word: $inputn";
if ($shortest == 0) {
    echo "Exact match found: $closestn";
} else {
    echo "Did you mean: $closest?n";
}

Смотрите также описание функций soundex(), similar_text() и metaphone().

Описание на ru2.php.net
Описание на php.ru