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: 38473

