Description
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)
levenshtein(
)
calcule
la
distance
Levenshtein
entre
deux
chaînes
de
caractères
.
Elle
retournera
-1
si
l'
un
des
deux
arguments
contient
plus
de
255
caractères
(cela
devrait
être
plus
que
suffisant
pour
faire
des
comparaisons
dans
un
dictionnaire
ou
annuaire
,
et
personne
de
sérieux
ne
fera
de
comparaison
génétique
en
PHP
)
.
La
distance
Levenshtein
distance
est
définie
comme
le
nombre
minimal
de
caractères
qu
'
il
faut
remplacer
,
insérer
ou
modifier
pour
transformer
la
chaîne
str1
en
str2
.
La
complexité
de
l'
algorithme
est
en
O(m*n
)
,
où
n
et
m
sont
les
tailles
respectives
de
str1
et
str2
:
c'est
plutôt
bien
,
en
comparaison
de
similar_text(
)
,
qui
est
en
O(max(n,m)**3
)
,
mais
cela
reste
très
coûteux
.
Dans
sa
forme
la
plus
simple
,
levenshtein(
)
va
prendre
uniquement
deux
chaînes
de
caractères
comme
paramèters
,
et
calculer
simplement
le
nombre
d'insertions
,
de
remplacements
et
d
'effacements
nécessaires
pour
tranformer
str1
en
str2
.
La
deuxième
variante
de
la
fonction
prend
trois
paramètres
supplémentaires
qui
représentent
les
coûts
d'
insertions
,
de
remplacements
et
d
'effacements
.
C
'
est
une
version
plus
générale
de
la
première
fonction
,
mais
qui
est
un
peu
moins
efficace
.
La
troisième
variante
(
qui
n'est
pas
implémentée
actuellement
)
,
est
la
version
la
plus
générale
,
mais
la
plus
lente
.
Elle
appelera
une
fonction
utilisateur
qui
déterminera
le
coût
de
chaque
opération
.
La
fonction
utilisateur
qui
sera
appelée
reçoit
les
arguments
suivants
:
-
Opération
à
réaliser
:
'
I'
,
'R
'
ou
'D
'
-
Caractère
dans
str1
-
Caractère
dans
str2
-
Position
dans
str1
-
Position
dans
str2
-
Caractères
restants
dans
str1
-
Caractères
restants
dans
str2
Cette fonction doit retourner un entier positif, qui représente
le coût de cette opération particulière. Il peut ne prendre en
compte que certains des paramètres fournis.
Grâce
à
cette
fonction
utilisateur
,
il
est
possible
de
prendr
en
compte
la
pertinence
ou
la
valeur
des
caractères
eux-mêmes
,
ou
encore
le
contexte
,
pour
définir
le
coûts
d'
une
insertion
,
d'un
effacement
ou
d
'un
remplacement
.
Cela
se
fait
en
perdant
toutes
les
optimisations
faîtes
en
terme
d
'
exploitation
du
CPU
et
des
buffers
.
Voir
aussi
soundex(
)
,
similar_text(
)
et
metaphone(
)
.