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

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

Второй вариант принимает три дополнительных аргумента, задающих стоимость операций вставки, замены и удаления. Этот вариант универсальнее первого, но не так эффективен.

Список параметров

str1: Одна из строк, для которых вычисляется расстояние Левенштейна.
str2: Одна из строк, для которых вычисляется расстояние Левенштейна.
cost_ins: Определяет стоимость вставки.
cost_rep: Определяет стоимость замены.
cost_del: Определяет стоимость удаления.

Возвращаемые значения

Эта функция возвращает расстояние Левенштейна между двумя строками, или -1, если хотя бы одна из строк длиннее 255 символов.

Примеры

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


<?php
// введенное слово с опечаткой
$input = 'carrrot';

// массив сверяемых слов
$words  = array('apple','pineapple','banana','orange',
                'radish','carrot','pea','bean','potato');

// кратчайшее расстояние пока еще не найдено
$shortest = -1;

// проходим по словам для нахождения самого близкого варианта
foreach ($words as $word) {

    // вычисляем расстояние между входным словом и текущим
    $lev = levenshtein($input, $word);

    // проверяем полное совпадение
    if ($lev == 0) {

        // это ближайшее слово (точное совпадение)
        $closest = $word;
        $shortest = 0;

        // выходим из цикла - мы нашли точное совпадение
        break;
    }

    // если это расстояние меньше следующего наименьшего расстояния
    // ИЛИ если следующее самое короткое слово еще не было найдено
    if ($lev <= $shortest || $shortest < 0) {
        // set the closest match, and shortest distance
        $closest  = $word;
        $shortest = $lev;
    }
}

echo "Вы ввели: $input\n";
if ($shortest == 0) {
    echo "Найдено точное совпадение: $closest\n";
} else {
    echo "Вы не имели в виду: $closest?\n";
}

?>

Результат выполнения данного примера:

Вы ввели: carrrot
Вы не имели в виду: carrot?

Смотрите также

soundex() - Возвращает ключ soundex для строки
similar_text() - Вычисляет степень похожести двух строк
metaphone() - Возвращает ключ metaphone для строки

Вернуться к: Обработка строк