Levenshtein: примеры (PHP)

Простые примеры использования

<?
echo levenshtein('кот', 'скат');
?>

2

<?
// Делаем замену более дорогой операцией
echo levenshtein('кот', 'котёнок', 1, 3, 1);
?>

5

<?
$str1 = str_repeat('a', 300);
$str2 = 'test';
echo levenshtein($str1, $str2);
?>

-1

Альтернативные функции в PHP

В PHP существуют несколько функций для сравнения строк:

• similar_text() - вычисляет степень похожести двух строк в процентах. Работает медленнее, но даёт более интуитивно понятный результат. Полезна при необходимости процентного совпадения.
• soundex() и metaphone() - создают phonetic ключи строк. Сравнивают строки на основе их звучания, что полезно для поиска омофонов. Не учитывают опечатки.
• strcmp(), strcasecmp() - бинарно безопасное сравнение строк. Используются для точного сравнения, а не для нахождения схожести.

Выбор функции зависит от задачи: levenshtein() оптимальна для исправления опечаток, similar_text() - для оценки схожести текстов, phonetic функции - для поиска по произношению.

Типичные ошибки

<?
$result = levenshtein(str_repeat('a', 300), 'test');
if ($result === -1) {
    echo 'Слишком длинная строка';
}
?>

Слишком длинная строка

<?
// Использование нулевой стоимости может привести к неожиданным результатам
echo levenshtein('кот', 'котёнок', 0, 0, 0);
?>

0

<?
// Расстояние Левенштейна симметрично, но стоимости операций могут быть разными
$dist1 = levenshtein('кот', 'скат', 2, 1, 1);
$dist2 = levenshtein('скат', 'кот', 2, 1, 1);
echo $dist1 === $dist2 ? 'Равны' : 'Не равны';
?>

Равны

Изменения в современных версиях PHP

В PHP 8.0 не было внесено значительных изменений в функцию levenshtein(). Однако в PHP 7.0 была изменена обработка ошибок: ранее функция возвращала -1 при любой ошибке, теперь при неверном количестве аргументов генерируется предупреждение. Ограничение длины строк в 255 символов сохраняется для всех версий.

В PHP 8.1 улучшена общая производительность интерпретатора, что косвенно влияет на скорость работы функции. Специфических изменений сигнатуры или поведения не производилось.

Расширенные примеры

<?
function autoCorrect($input, $dictionary, $threshold = 3) {
    $minDist = PHP_INT_MAX;
    $closest = '';
    
    foreach ($dictionary as $word) {
        $dist = levenshtein($input, $word);
        if ($dist < $minDist) {
            $minDist = $dist;
            $closest = $word;
        }
    }
    
    return $minDist <= $threshold ? $closest : $input;
}

$words = ['яблоко', 'апельсин', 'банан', 'мандарин'];
echo autoCorrect('яблко', $words);
?>

яблоко

<?
// Делаем опечатки в гласных менее значимыми
function nameDistance($name1, $name2) {
    $vowels = ['a', 'e', 'i', 'o', 'u', 'а', 'е', 'ё', 'и', 'о', 'у', 'ы', 'э', 'ю', 'я'];
    $name1_lower = mb_strtolower($name1);
    $name2_lower = mb_strtolower($name2);
    
    // Упрощённый пример: заменяем стоимость операции для гласных
    // В реальности потребуется более сложная реализация
    return levenshtein($name1_lower, $name2_lower, 1, 2, 1);
}

echo nameDistance('Анна', 'Анно');
?>

1

<?
function findClosestArray($inputArray, $referenceArrays) {
    $bestMatch = '';
    $minAvgDist = PHP_INT_MAX;
    
    foreach ($referenceArrays as $name => $refArray) {
        $totalDist = 0;
        $count = 0;
        
        foreach ($inputArray as $inputWord) {
            foreach ($refArray as $refWord) {
                $totalDist += levenshtein($inputWord, $refWord);
                $count++;
            }
        }
        
        $avgDist = $totalDist / $count;
        if ($avgDist < $minAvgDist) {
            $minAvgDist = $avgDist;
            $bestMatch = $name;
        }
    }
    
    return $bestMatch;
}

$category1 = ['яблоко', 'банан', 'апельсин'];
$category2 = ['помидор', 'огурец', 'морковь'];
$test = ['яблко', 'банан', 'апльсин'];

echo findClosestArray($test, ['фрукты' => $category1, 'овощи' => $category2]);
?>

фрукты

Реализации в других языках

import Levenshtein
print(Levenshtein.distance('кот', 'скат'))

2

function levenshtein(a, b) {
  const matrix = [];
  for (let i = 0; i <= b.length; i++) matrix[i] = [i];
  for (let j = 0; j <= a.length; j++) matrix[0][j] = j;
  for (let i = 1; i <= b.length; i++) {
    for (let j = 1; j <= a.length; j++) {
      matrix[i][j] = b[i-1] === a[j-1] ? matrix[i-1][j-1] : Math.min(
        matrix[i-1][j-1] + 1,
        matrix[i][j-1] + 1,
        matrix[i-1][j] + 1
      );
    }
  }
  return matrix[b.length][a.length];
}
console.log(levenshtein('кот', 'скат'));

2

SELECT LEVENSHTEIN('кот', 'скат');