levenshtein()

A função levenshtein() calcula a distância de Levenshtein entre duas strings — o número mínimo de edições de um único caractere (inserções, exclusões ou substituições) necessárias para transformar uma string na outra. Uma distância menor significa que as strings são mais parecidas, portanto levenshtein() é a ferramenta ideal para correspondência aproximada: verificadores ortográficos, sugestões de "você quis dizer…?", deduplicação de registros quase idênticos e classificação de resultados de pesquisa por proximidade.

Este capítulo aborda a sintaxe, os pesos de custo opcionais, como ela difere de funções relacionadas, armadilhas comuns e exemplos executáveis.

Sintaxe

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

Ou, com custos de edição personalizados:

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

Parâmetros

• $string1 — a primeira string a comparar.
• $string2 — a segunda string a comparar.
• $insertion_cost (opcional) — custo de inserir um caractere. Padrão 1.
• $replacement_cost (opcional) — custo de substituir um caractere. Padrão 1.
• $deletion_cost (opcional) — custo de excluir um caractere. Padrão 1.

A função retorna a distância de Levenshtein como um int. Com os pesos padrão, essa distância é simétrica — levenshtein($a, $b) é igual a levenshtein($b, $a).

Exemplo básico

A saída deste código é:

4

A função retorna 4: transformar "Hello" em "World" requer quatro substituições (H→W, e→o, l→r, o→d); apenas o segundo l permanece no lugar.

Como a distância é construída

Cada operação de edição conta como um passo (com pesos padrão). O par clássico dos livros "kitten" → "sitting" requer três edições:

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

Saída:

3

levenshtein() diferencia maiúsculas de minúsculas

Diferenças na capitalização de letras contam como uma edição, o que frequentemente surpreende as pessoas:

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

Saída:

1
0

Para comparação sem distinção entre maiúsculas e minúsculas, normalize ambas as strings com strtolower() (ou mb_strtolower() para texto multibyte) antes de chamar levenshtein().

Ponderando edições de forma diferente

Quando inserções, exclusões e substituições não devem ter o mesmo custo, passe os três argumentos de custo. Aqui uma exclusão é tornada mais cara:

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

Saída:

5

Remover o s final é uma única exclusão, mas com um custo de 5 a distância reportada é 5. Isso é útil quando um tipo de erro de digitação deve ser penalizado mais do que outro.

Uso prático: sugestões de "você quis dizer?"

Uma tarefa comum no mundo real é encontrar a palavra conhecida mais próxima da entrada de um usuário:

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

Saída:

Did you mean: commit? (distance 1)

Armadilhas

• Bytes, não caracteres. levenshtein() trabalha com bytes únicos, portanto caracteres UTF-8 multibyte (acentos, emoji, scripts não-latinos) podem ser contados incorretamente. Para resultados precisos com esse tipo de texto, translitere ou compare ASCII normalizado.
• Strings longas custam memória/tempo. A complexidade é aproximadamente proporcional ao produto dos comprimentos das duas strings, portanto evite usá-la em entradas muito grandes.
• Maiúsculas/minúsculas e espaços em branco contam. Remova espaços e converta para minúsculas primeiro se essas diferenças devem ser ignoradas.

Funções relacionadas

• similar_text() — retorna o número de caracteres correspondentes (e uma porcentagem opcional) em vez de uma distância de edição.
• soundex() e metaphone() — comparam strings pela forma como soam em vez de como são escritas.
• strcmp() — uma comparação estrita e segura para binários que apenas informa se as strings são iguais ou qual vem primeiro na ordenação.

Prática