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