levenshtein()

La función levenshtein() calcula la distancia de Levenshtein entre dos cadenas — el número mínimo de ediciones de un solo carácter (inserciones, eliminaciones o sustituciones) necesarias para transformar una cadena en la otra. Una distancia menor significa que las cadenas se parecen más, por lo que levenshtein() es la herramienta ideal para la coincidencia aproximada: correctores ortográficos, sugerencias del tipo "¿quisiste decir…?", deduplicación de registros casi idénticos y clasificación de resultados de búsqueda por similitud.

Este capítulo cubre la sintaxis, los pesos de coste opcionales, las diferencias con funciones relacionadas, errores comunes y ejemplos ejecutables.

Sintaxis

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

O bien, con costes de edición personalizados:

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

Parámetros

• $string1 — la primera cadena a comparar.
• $string2 — la segunda cadena a comparar.
• $insertion_cost (opcional) — coste de insertar un carácter. Por defecto 1.
• $replacement_cost (opcional) — coste de reemplazar un carácter. Por defecto 1.
• $deletion_cost (opcional) — coste de eliminar un carácter. Por defecto 1.

La función devuelve la distancia de Levenshtein como un int. Con los pesos por defecto, esa distancia es simétrica — levenshtein($a, $b) es igual a levenshtein($b, $a).

Ejemplo básico

La salida de este código es:

4

La función devuelve 4: transformar "Hello" en "World" requiere cuatro sustituciones (H→W, e→o, l→r, o→d); solo la segunda l permanece en su lugar.

Cómo se construye la distancia

Cada operación de edición cuenta como un paso (con los pesos por defecto). El par clásico de los libros de texto "kitten" → "sitting" necesita tres ediciones:

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

Salida:

3

levenshtein() distingue mayúsculas de minúsculas

Las diferentes capitalizaciones cuentan como una edición, lo que suele sorprender a la gente:

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

Salida:

1
0

Para una comparación sin distinción entre mayúsculas y minúsculas, normaliza ambas cadenas con strtolower() (o mb_strtolower() para texto multibyte) antes de llamar a levenshtein().

Ponderación diferente de ediciones

Cuando las inserciones, eliminaciones y sustituciones no deben tener el mismo coste, pasa los tres argumentos de coste. Aquí se hace que una eliminación sea costosa:

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

Salida:

5

Eliminar la s final es una única eliminación, pero con un coste de 5 la distancia reportada es 5. Esto es útil cuando un tipo de error tipográfico debe penalizarse más que otro.

Uso práctico: sugerencias del tipo "¿quisiste decir?"

Una tarea común en el mundo real es encontrar la palabra conocida más cercana a la entrada de un usuario:

<?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})";
?>

Salida:

Did you mean: commit? (distance 1)

Errores comunes

• Bytes, no caracteres. levenshtein() opera sobre bytes individuales, por lo que los caracteres UTF-8 multibyte (acentos, emoji, escrituras no latinas) pueden contarse incorrectamente. Para resultados precisos con ese tipo de texto, translitéralos o compara ASCII normalizado.
• Las cadenas largas consumen memoria y tiempo. La complejidad es aproximadamente proporcional al producto de las longitudes de las dos cadenas, así que evita usarla con entradas muy grandes.
• Las mayúsculas y los espacios en blanco cuentan. Recorta y convierte a minúsculas primero si esas diferencias deben ignorarse.

Funciones relacionadas

• similar_text() — devuelve el número de caracteres coincidentes (y un porcentaje opcional) en lugar de una distancia de edición.
• soundex() y metaphone() — comparan cadenas por cómo suenan en lugar de por cómo se escriben.
• strcmp() — una comparación estricta y segura para binarios que solo indica si las cadenas son iguales o cuál va primero al ordenar.

Práctica