levenshtein

Popis

int levenshtein ( string str1, string str2)

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

int levenshtein ( string str1, string str2, function cost)

Tato funkce vrací XXX Levenshtein-Distance mezi předanými řetězci nebo -1, pokud délka jednoho z předaných řetězců přesáhne omezení 255 znaků (255 by mělo být pro běžná porovnání víc než dost, a nikdo se zdravým rozumem nebude v PHP dělat genetickou analýzu).

Levenshteinova vzdálenost se definuje jako minimální počet znaku, které musíte nahradit, vložit nebo smazat, abyste změnili str1 na str2. Složitost tohoto algoritmu je O(m*n), kde n a m jsou délky str1 a str2 (celkem slušné v porovnání se similar_text(), který je O(max(n,m)**3), ale i tak drahé).

Ve své nejjednodušší podobě tato funkce pouze vezme dva řetězce jako argumenty a spočítá počet vložení, nahrazení a smazání nutných k transformaci str1 na str2.

Druhá varianta přijme tři další argumenty, které definují náklady na operace vložení, nahrazeni a smazání. Tato varianta je všeobecnější a přizpůsobivější než varianta první, ale ne tak výkonná.

Třetí varianta (zatím neimplementovaná) bude nejvšeobecnější a nejpřizpůsobivější, ale také nejpomalejší alternativou. Bude volat uživatelskou funkci, která určí náklady na všechny možné operace.

Tato uživatelská funkce se bude volat s následujícími argumenty:

• operatce, která se má provést: 'I', 'R' or 'D'

• původní znak v řetězci 1

• původní znak v řetězci 2

• pozice v řetězci 1

• pozice v řetězci 2

• znaky zbývající v řetězci 1

• znaky zbývající v řetězci 2

Tato uživatelská funkce musí vrátit kladné celé číslo vyčíslující náklady na tuto konkrétní operaci, ale může se rozhodnout použít pouze některé z přijatých argumentů.

Tento přístup nabízí možnost zohlednit důležitost určitých symbolů (znaků) a/nebo rozdíly mezi nimi, či dokonce kontext, ve kterém se vyskytují při určování nákladů na vložení, změnu nebo smazání, ale za cenu ztráty všech optimalizací využití CPU registru a XXX cache misses, které byly zapracovány do předchozích dvou variant.

Viz také: soundex(), similar_text() a metaphone().