levenshtein

(PHP 4 >= 4.0.1, PHP 5, PHP 7, PHP 8)

levenshteinCálculo de la distancia Levenshtein entre dos strings

Descripción

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

La distancia Levenshtein se define como el número mínimo de caracteres que se tienen que sustituir, insertar o borrar para transformar str1 en str2. La complejidad del algoritmo es O(m*n), donde n y m son la longitud de str1 y str2 (bastante bueno en comparación con similar_text(), la cual es O(max(n,m)**3), pero sigue siendo costoso).

En su forma más simple la función tomará sólo los dos strings como parámetros y calculará sólo el número de operaciones de insertar, reemplazar y eliminar, necesarias para transformar str1 en str2.

Una segunda variante tomará tres parámetros adicionales que definen el costo de las operaciones de insertar, reemplazar y eliminar. Esto es más general y adaptable que la primera variante, pero no tan eficiente.

Parámetros

str1

Uno de los strings a ser evaluados para la distancia Levenshtein.

str2

Uno de los strings a ser evaluados para la distancia Levenshtein.

cost_ins

Define el costo de inserción.

cost_rep

Define el costo de reemplazo.

cost_del

Define el costo de eliminación.

Valores devueltos

Esta función devuelve la distancia Levenshtein entre los dos strings argumentos ó -1, si uno de los strings argumentos es mayor que el límite de 255 caracteres.

Ejemplos

Ejemplo #1 Ejemplo de levenshtein()

<?php
// palabra de entrada mal escrita
$input 'carrrot';

// array de palabras contra las cuales verificar
$words  = array('apple','pineapple','banana','orange',
                
'radish','carrot','pea','bean','potato');

// no se ha encontrado la distancia más corta, aun
$shortest = -1;

// bucle a través de las palabras para encontrar la más cercana
foreach ($words as $word) {

    
// calcula la distancia entre la palabra de entrada
    // y la palabra actual
    
$lev levenshtein($input$word);

    
// verifica por una coincidencia exacta
    
if ($lev == 0) {

        
// la palabra más cercana es esta (coincidencia exacta)
        
$closest $word;
        
$shortest 0;

        
// salir del bucle, se ha encontrado una coincidencia exacta
        
break;
    }

    
// si esta distancia es menor que la siguiente distancia
    // más corta o si una siguiente palabra más corta aun no se ha encontrado
    
if ($lev <= $shortest || $shortest 0) {
        
// establece la coincidencia más cercana y la distancia más corta
        
$closest  $word;
        
$shortest $lev;
    }
}

echo 
"Input word: $input\n";
if (
$shortest == 0) {
    echo 
"Exact match found: $closest\n";
} else {
    echo 
"Did you mean: $closest?\n";
}

?>

El resultado del ejemplo sería:

Input word: carrrot
Did you mean: carrot?

Ver también