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;
    }

    // если это расстояние меньше следующего наименьшего расстояния

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

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

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

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