array ( 0 => 'index.php', 1 => 'PHP Manual', ), 'head' => array ( 0 => 'UTF-8', 1 => 'ru', ), 'this' => array ( 0 => 'function.levenshtein.php', 1 => 'levenshtein', 2 => 'Вычисляет расстояние Левенштейна между двумя строками', ), 'up' => array ( 0 => 'ref.strings.php', 1 => 'Функции для работы со строками', ), 'prev' => array ( 0 => 'function.lcfirst.php', 1 => 'lcfirst', ), 'next' => array ( 0 => 'function.localeconv.php', 1 => 'localeconv', ), 'alternatives' => array ( ), 'source' => array ( 'lang' => 'ru', 'path' => 'reference/strings/functions/levenshtein.xml', ), 'history' => array ( ), ); $setup["toc"] = $TOC; $setup["toc_deprecated"] = $TOC_DEPRECATED; $setup["parents"] = $PARENTS; manual_setup($setup); contributors($setup); ?>

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?

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