levenshtein()

Функция levenshtein() вычисляет расстояние Левенштейна между двумя строками — минимальное количество односимвольных правок (вставок, удалений или замен), необходимых для преобразования одной строки в другую. Чем меньше расстояние, тем больше сходство строк, поэтому levenshtein() — незаменимый инструмент для нечёткого поиска: проверки орфографии, подсказок «вы имели в виду…?», дедупликации почти одинаковых записей и ранжирования результатов поиска по близости.

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

Синтаксис

levenshtein(string $string1, string $string2): int

Или с пользовательскими стоимостями правок:

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

Параметры

• $string1 — первая строка для сравнения.
• $string2 — вторая строка для сравнения.
• $insertion_cost (необязательный) — стоимость вставки символа. По умолчанию 1.
• $replacement_cost (необязательный) — стоимость замены символа. По умолчанию 1.
• $deletion_cost (необязательный) — стоимость удаления символа. По умолчанию 1.

Функция возвращает расстояние Левенштейна в виде int. При стандартных весах расстояние симметрично — levenshtein($a, $b) равно levenshtein($b, $a).

Базовый пример

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

4

Функция возвращает 4: чтобы превратить «Hello» в «World», нужно четыре замены (H→W, e→o, l→r, o→d); только вторая l остаётся на месте.

Как формируется расстояние

Каждая операция правки считается за один шаг (при стандартных весах). Классическая учебная пара «kitten» → «sitting» требует трёх правок:

<?php
echo levenshtein("kitten", "sitting"); // 3
// k → s   (substitution)
// e → i   (substitution)
// (append) g   (insertion)
?>

Результат:

3

levenshtein() чувствительна к регистру

Различие в регистре букв считается правкой, что нередко удивляет:

<?php
echo levenshtein("Hello", "hello"), "\n"; // 1  (H vs h)
echo levenshtein(strtolower("Hello"), strtolower("hello")), "\n"; // 0
?>

Результат:

1
0

Для сравнения без учёта регистра нормализуйте обе строки с помощью strtolower() (или mb_strtolower() для многобайтового текста) перед вызовом levenshtein().

Разные веса для правок

Если вставки, удаления и замены должны стоить по-разному, передайте три аргумента стоимости. В примере удаление сделано дорогим:

<?php
// $insertion_cost = 1, $replacement_cost = 1, $deletion_cost = 5
echo levenshtein("cats", "cat", 1, 1, 5); // 5
?>

Результат:

5

Удаление завершающей s — это одно удаление, но при стоимости 5 возвращаемое расстояние равно 5. Это удобно, когда один вид опечатки должен штрафоваться сильнее другого.

Практический пример: подсказки «вы имели в виду?»

Типичная задача — найти ближайшее известное слово к введённому пользователем:

<?php
$input = "comit";
$dictionary = ["commit", "command", "comment", "compile"];

$best = null;
$bestDistance = PHP_INT_MAX;

foreach ($dictionary as $word) {
    $d = levenshtein($input, $word);
    if ($d < $bestDistance) {
        $bestDistance = $d;
        $best = $word;
    }
}

echo "Did you mean: {$best}? (distance {$bestDistance})";
?>

Результат:

Did you mean: commit? (distance 1)

Типичные ловушки

• Байты, а не символы. levenshtein() работает с отдельными байтами, поэтому многобайтовые UTF-8 символы (знаки с диакритикой, эмодзи, нелатинские шрифты) могут считаться неверно. Для точных результатов с таким текстом транслитерируйте или сравнивайте нормализованный ASCII.
• Длинные строки требуют памяти и времени. Сложность примерно пропорциональна произведению длин двух строк, поэтому не используйте функцию на очень больших входных данных.
• Регистр и пробелы учитываются. Обрезайте и переводите в нижний регистр заранее, если эти различия нужно игнорировать.

Связанные функции

• similar_text() — возвращает количество совпадающих символов (и необязательный процент) вместо расстояния правок.
• soundex() и metaphone() — сравнивают строки по звучанию, а не по написанию.
• strcmp() — строгое побайтовое сравнение, которое лишь сообщает, равны ли строки или какая из них идёт первой.

Практика