Beschrijving
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)
Deze
functie
geeft
de
Levenshtein-afstand
tussen
de
twee
argument
strings
of
-1
weer
,
als
een
van
de
argumenten
is
langer
dan
de
grens
van
255
karakters
(
255
zou
meer
dan
genoeg
moeten
zijn
voor
naam
of
dictionary
vergelijking
,
en
een
serieus
persoon
zou
geen
genetische
analyses
gaan
doen
met
PHP
)
.
De
Levenshtein
afstand
is
gedefnieerd
als
het
minimum
aantal
karakters
die
vervangen
,
ingevoegd
of
verwijderd
moeten
worden
om
str1
naar
str2
te
transformeren
.
De
complexiteit
van
het
algoritme
is
O(
m*n
)
,
waar
n
en
m
de
lengte
zijn
van
str1
en
str2
(vrij
goed
vergeleken
met
similar_text(
)
,
wat
O(max(n,m)**3
)
is
,
maar
nog
vrij
kostbaar
)
.
In
haar
meest
simpele
vorm
neemt
de
functie
alleen
de
twee
strings
als
parameter
en
zal
het
alleen
het
aantal
invoeg
-
vervang
-
en
verwijderbewerkingen
berekenen
die
nodig
zijn
voor
het
transformeren
van
str1
in
str2
.
Een
tweede
variant
neemt
3
parameters
die
de
kosten
van
de
invoeg
-
vervang
-
en
verwijderbewerkingen
definieren
.
Dit
is
meer
algemeen
en
aanpasbaar
dan
de
eerste
variant
,
maar
minder
efficient
.
De
derde
variant
(
welke
nog
niet
geimplementeerd
is
)
zal
de
meest
algemene
en
aanpasbare
,
maar
ook
het
meest
trage
alternatief
worden
.
Deze
zal
een
user-voorziene
functie
aanspreken
die
zal
bepalen
wat
de
kost
zal
zijn
voor
elke
mogelijke
bewerking
.
De
uservoorziene
functie
zal
worden
aangesproken
met
de
volgende
argumenten
:
-
uit
te
voeren
bewerking
:
'
I'
,
'R
'
or
'D
'
-
betreffende
karakter
in
string
1
-
betreffende
karakter
in
string
2
-
positie
in
string
1
-
positie
in
string
2
-
overblijvende
karakters
in
string
1
-
overblijvende
karakters
in
string
2
De user-voorziene functie moet een positieve integer teruggeven,
die de kost voor deze bewerking beschrijft, maar het mag alleen
maar sommige van de meegegeven argumenten gebruiken.
De
user-voorziene
functie
aanpak
biedt
de
mogelijkheid
om
op
te
nemen
de
relevantie
van
en
/
of
de
mogelijkheid
tot
het
opnemen
van
verschil
tussen
bepaalde
symbolen
(
karakters
)
of
zelfs
de
context
waarin
deze
symbolen
verschijnen
om
de
kost
van
de
invoeg
-
vervang
-
en
verwijderbewerkingen
te
bepalen
,
maar
tegen
de
kost
van
het
verliezen
van
alle
optimalisatie
de
gedaan
wordt
met
betrekking
tot
cpu
register
utilisatie
en
cache
missingen
die
in
de
andere
varianten
opgenomen
zijn
.
Zie
ook
soundex(
)
,
similar_text(
)
en
metaphone(
)
.