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

# levenshtein

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

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

### Описание

function 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 для строки

`↑` and `↓` to navigate • `Enter` to select • `Esc` to close • `/` to open