int levenshtein ( string $str1 , string $str2 , int $cost_ins , int $cost_rep , int $cost_del )
Oblicza relatywny odległości między dwoma ciągami.
Odległość Levenshtein definiowana jest jako minimalna liczba znaków, którą trzeba zastąpić, wstawić lub usunąć, aby przekształcić $str1 do $str2. Złożoność tego algorytmu jest O (m * n), gdzie n i m są długości $str1 i $str2 (dość dobry w porównaniu do similar_text (), która jest O (max (n, m) ** 3), ale nadal bardzo kosztowne).
W najprostszej postaci funkcja przyjmować będzie tylko dwa ciągi jako parametry i będzie po prostu obliczyć liczbę, aby wstawić, usunąć i zastąpi czynności potrzebne do przekształcenia $str1 do $str2.
Drugi wariant będzie miał trzy dodatkowe parametry, które określają koszt wstawiania, usunięcia i zastąpięnia operacji. Jest to bardziej ogólne oraz adaptacyjny wariant niż jeden, ale nie tak skuteczny.
Kompatybilność: PHP4, PHP5.
Listing
// słowo źle przeliterowane
$input = 'carrrot';
// array do sprawdzania poprawności
$words = array('apple','pineapple','banana','orange',
'radish','carrot','pea','bean','potato');
// brak najkrótszej odległości
$shortest = -1;
// pętla do arraya aby sprawdzić poprawność i porównać
foreach ($words as $word) {
// liczymy dystans między 1 a 2 stringiem,
$lev = levenshtein($input, $word);
// zacieśniamy wyszukiwanie
if ($lev == 0) {
// najbliższe słowo jest to:
$closest = $word;
$shortest = 0;
// jeśli znaleźliśmy wynik to zamykamy pętlę
break;
}
// jeśli dystans jest mniejszy niż znaleziony najmniejszy
// dystans, lub jesli następnego najmniejszego słowa nie znaleziono
if ($lev <= $shortest || $shortest < 0) {
// ustaw najbliższe wyniki i najmniejsze dustanse
$closest = $word;
$shortest = $lev;
}
}
echo "Input word: $input\n";
if ($shortest == 0) {
echo "Exact match found: $closest\n";
} else {
echo "Did you mean: $closest?\n";
}
?>
//zwróci:
Input word: carrrot
Did you mean: carrot?
Ranga: Administrator serwisu Punktów: 0
-
-
Tre¶æ komentarza
-
