|
7.101.27 levenshtein()
Calcule la distance Levenshtein entre deux chaînes
[ Exemples avec levenshtein ] PHP 3>= 3.0.17, PHP 4 >= 4.0.1
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 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ètres, 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
prendre 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
.
|
