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


(PHP 4 >= 4.0.1, PHP 5)

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

Описание

int levenshtein ( string $str1 , string $str2 )
int levenshtein ( string $str1 , string $str2 , int $cost_ins , int $cost_rep , int $cost_del )

Расстояние Левенштейна - это минимальное количество вставок, замен и удалений символов, необходимое для преобразования str1 в str2. Сложность алгоритма равна O(m*n), где n и m - длины строк str1 и str2 (неплохо по сравнению с similar_text(), имеющей сложность O(max(n,m)**3), но все же довольно много).

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

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

Список параметров

str1

Одна из строк, для которых вычисляется расстояние Левенштейна.

str2

Одна из строк, для которых вычисляется расстояние Левенштейна.

cost_ins

Определяет стоимость вставки.

cost_rep

Определяет стоимость замены.

cost_del

Определяет стоимость удаления.

Возвращаемые значения

Эта функция возвращает расстояние Левенштейна между двумя строками, или -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) {
        
// set the closest match, and shortest distance
        
$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 для строки