array ( 0 => 'index.php', 1 => 'PHP Manual', ), 'head' => array ( 0 => 'UTF-8', 1 => 'es', ), 'this' => array ( 0 => 'function.levenshtein.php', 1 => 'levenshtein', 2 => 'Calcula la distancia Levenshtein entre dos strings', ), 'up' => array ( 0 => 'ref.strings.php', 1 => 'Funciones de strings', ), 'prev' => array ( 0 => 'function.lcfirst.php', 1 => 'lcfirst', ), 'next' => array ( 0 => 'function.localeconv.php', 1 => 'localeconv', ), 'alternatives' => array ( ), 'source' => array ( 'lang' => 'es', '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 — Calcula la distancia Levenshtein entre dos strings

Descripción

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

La distancia Levenshtein se define como el número mínimo de caracteres que deben ser reemplazados, insertados o eliminados para transformar el string string1 en string2. La complejidad del algoritmo es de O(m*n), donde n y m son los tamaños respectivos de string1 y string2: es bastante buena, en comparación con similar_text(), que es de O(max(n,m)**3), pero sigue siendo muy costosa.

Si insertion_cost, replacement_cost y/o deletion_cost son diferentes de 1, el algoritmo se adapta para elegir la transformación menos costosa. Por ejemplo, si $insertion_cost + $deletion_cost < $replacement_cost, no se realizará ningún reemplazo, sino inserciones y eliminaciones.

Parámetros

string1

Uno de los strings a evaluar.

string2

Uno de los strings a evaluar.

insertion_cost

Define el costo de la inserción.

replacement_cost

Define el costo del reemplazo.

deletion_cost

Define el costo de la eliminación.

Valores devueltos

Esta función devuelve la distancia Levenshtein entre dos strings.

Historial de cambios

Versión Descripción
8.0.0 Antes de esta versión, levenshtein() debía ser llamada con dos o cinco argumentos.
8.0.0 Antes de esta versión, levenshtein() devolvía -1 si alguno de los strings de los argumentos superaba los 255 caracteres.

Ejemplos

Ejemplo #1 Ejemplo con levenshtein()

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

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

// ninguna distancia encontrada por el momento
$shortest = -1;

// bucle sobre las palabras para encontrar la más cercana
foreach ($words as $word) {

// calcula la distancia con la palabra ingresada,
// y la palabra actual
$lev = levenshtein($input, $word);

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

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

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

// Si la distancia es más pequeña que la siguiente distancia encontrada
// O, si la siguiente palabra más cercana aún no ha sido encontrada
if ($lev <= $shortest || $shortest < 0) {
// definición de la palabra más cercana y la distancia
$closest = $word;
$shortest = $lev;
}
}

echo "Palabra ingresada: $input\n";
if ($shortest == 0) {
echo "Coincidencia exacta encontrada: $closest\n";
} else {
echo "¿Quiso decir: $closest?\n";
}

?>

El ejemplo anterior mostrará:

Palabra ingresada: carrrot
¿Quiso decir: carrot?

Ver también