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