A função levenshtein(): Você quis dizer…

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

A função levenshtein, é uma função bastante interessante do PHP. Ela é capaz de calcular o numero de inserções, remoções e substituições necessárias para tornar a str1 na str2.

A função serviu como base de inspiração para várias ferramentas e serviços vistos e utilizados de maneira frequente na Internet; corretores ortográficos, o famoso “Did you mean” ou “Você quis dizer” do Google estão todos inclusos nesta lista.

Abaixo segue um exemplo da implementação do famoso “Did you mean” encontrado no próprio manual, utilizando a dita-cuja:

[php]
<?php
// input misspelled word
$input = ‘carrrot’;

// array of words to check against
$words = array(‘apple’,’pineapple’,’banana’,’orange’,
‘radish’,’carrot’,’pea’,’bean’,’potato’);

// no shortest distance found, yet
$shortest = -1;

// loop through words to find the closest
foreach ($words as $word) {
// calculate the distance between the input word,
// and the current word
$lev = levenshtein($input, $word);

// check for an exact match
if ($lev == 0) {
// closest word is this one (exact match)
$closest = $word;
$shortest = 0;

// break out of the loop; we’ve found an exact match
break;
}

// if this distance is less than the next found shortest
// distance, OR if a next shortest word has not yet been found
if ($lev <= $shortest || $shortest < 0) {
// set the closest match, and shortest distance
$closest = $word;
$shortest = $lev;
}
}

echo &quot;Input word: $input\n&quot;;
if ($shortest == 0) {
echo "Exact match found: $closest\n"";
} else {
echo "Did you mean: $closest?\n";
}
?>
[/php]

Saída

Input word: carrrot
Did you mean: carrot?

Espero que um dia seja útil para alguém!

Igor,
[]’s

One thought on “A função levenshtein(): Você quis dizer…

  1. Tem um trecho errado no codigo:

    if ($lev 0) {

    seria:

    if ($lev <= $shortest || $shortest < 0) {

    ou

    if ($lev <= $shortest || $shortest == -1) {

    Valeu

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: