levenshtein()

La funzione levenshtein() calcola la distanza di Levenshtein tra due stringhe — il numero minimo di modifiche su singolo carattere (inserimenti, eliminazioni o sostituzioni) necessarie per trasformare una stringa nell'altra. Una distanza minore indica che le stringhe sono più simili, quindi levenshtein() è lo strumento ideale per il fuzzy matching: correttori ortografici, suggerimenti del tipo "volevi dire…?", deduplicazione di record quasi identici e classificazione dei risultati di ricerca per somiglianza.

Questo capitolo tratta la sintassi, i pesi di costo opzionali, le differenze rispetto a funzioni correlate, i problemi comuni e degli esempi eseguibili.

Sintassi

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

Oppure, con costi di modifica personalizzati:

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

Parametri

• $string1 — la prima stringa da confrontare.
• $string2 — la seconda stringa da confrontare.
• $insertion_cost (opzionale) — costo dell'inserimento di un carattere. Predefinito 1.
• $replacement_cost (opzionale) — costo della sostituzione di un carattere. Predefinito 1.
• $deletion_cost (opzionale) — costo dell'eliminazione di un carattere. Predefinito 1.

La funzione restituisce la distanza di Levenshtein come int. Con i pesi predefiniti, la distanza è simmetrica — levenshtein($a, $b) è uguale a levenshtein($b, $a).

Esempio base

L'output di questo codice è:

4

La funzione restituisce 4: trasformare "Hello" in "World" richiede quattro sostituzioni (H→W, e→o, l→r, o→d); solo la seconda l rimane al suo posto.

Come viene calcolata la distanza

Ogni operazione di modifica conta come un passo (con i pesi predefiniti). La classica coppia "kitten" → "sitting" richiede tre modifiche:

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

Output:

3

levenshtein() è sensibile alle maiuscole

Le differenze di maiuscole/minuscole contano come una modifica, il che spesso sorprende:

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

Output:

1
0

Per un confronto senza distinzione tra maiuscole e minuscole, normalizzare entrambe le stringhe con strtolower() (o mb_strtolower() per il testo multibyte) prima di chiamare levenshtein().

Ponderare le modifiche in modo diverso

Quando inserimenti, eliminazioni e sostituzioni non devono avere lo stesso costo, passare i tre argomenti di costo. In questo esempio l'eliminazione viene resa costosa:

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

Output:

5

Rimuovere la s finale è una singola eliminazione, ma con un costo di 5 la distanza restituita è 5. Questo è utile quando un certo tipo di errore tipografico deve essere penalizzato più degli altri.

Uso pratico: suggerimenti "volevi dire?"

Un caso d'uso comune è trovare la parola conosciuta più vicina all'input dell'utente:

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

Output:

Did you mean: commit? (distance 1)

Problemi comuni

• Byte, non caratteri. levenshtein() opera su singoli byte, quindi i caratteri UTF-8 multibyte (accenti, emoji, scritture non latine) possono essere conteggiati in modo errato. Per risultati accurati con tali testi, traslitterare o confrontare ASCII normalizzato.
• Le stringhe lunghe richiedono memoria/tempo. La complessità è approssimativamente proporzionale al prodotto delle lunghezze delle due stringhe, quindi evitare di usarla su input molto grandi.
• Maiuscole e spazi bianchi contano. Rimuovere gli spazi iniziali/finali e convertire in minuscolo prima se tali differenze devono essere ignorate.

Funzioni correlate

• similar_text() — restituisce il numero di caratteri corrispondenti (e una percentuale opzionale) invece di una distanza di modifica.
• soundex() e metaphone() — confrontano le stringhe in base a come suonano piuttosto che come vengono scritte.
• strcmp() — un confronto rigoroso e binary-safe che indica solo se le stringhe sono uguali o quale viene prima in ordine alfabetico.

Esercitazione