levenshtein

(PHP 4 >= 4.0.1, PHP 5, PHP 7, PHP 8)

levenshtein — Вычисляет расстояние Левенштейна между двумя строками

Описание

levenshtein(
    string $string1,
    string $string2,
    int $insertion_cost = 1,
    int $replacement_cost = 1,
    int $deletion_cost = 1
): int

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

Если insertion_cost, replacement_cost и/или deletion_cost не равны 1, алгоритм адаптируется для выбора самых дешёвых преобразований. Например. если $insertion_cost + $deletion_cost < $replacement_cost, замены не будут выполняться, вместо этого будут выполняться вставки и удаления.

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

string1: Одна из строк, для которых вычисляется расстояние Левенштейна.
string2: Одна из строк, для которых вычисляется расстояние Левенштейна.
insertion_cost: Определяет стоимость вставки.
replacement_cost: Определяет стоимость замены.
deletion_cost: Определяет стоимость удаления.

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

Эта функция возвращает расстояние Левенштейна между двумя строками.

Список изменений

Версия	Описание
8.0.0	До этой версии levenshtein() нужно было вызывать с двумя или пятью аргументами.
8.0.0	До этой версии, levenshtein() возвращала значение `-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) {
        // устанивливаем ближайшее совпадение и кратчайшее расстояние
        $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 для строки