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