levenshtein

levenshtein -- Spočítat XXX Levenshteinovu vzdálenost mezi dvěma řetězci

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 :

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( ) .