6.95.21 levenshtein[ Exemples avec levenshtein ] PHP 3>= 3.0.17, PHP 4 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 retourne la distance Levenshtein
entre les deux chaînes str1 et
str1 ou -1 si un des arguments excède
la limite de 255 caractères.
La distance Levenshtein est définie comme le nombre
minimal de caractères qu'il faut
remplacer, insérer ou effacer pour transformer la
chaîne str1 en str2.
La complexité de l'algorithme est en O(m*n),
où n et m sont les
longueurs respectives de str1 et
str2 (ceci est plutôt un bon
résultat, comparé à similar_text,
qui est en O(max(n,m)**3), mais cela reste coûteux en terme de ressources).
Dans sa forme la plus simple, la fonction va prendre uniquement
deux chaînes en paramètres, et calculer uniquement le nombre
d'insertions, remplacements et effacements nécessaires pour transformer
la chaîne str1 en str2.
Une variante prend trois paramètres additionnels, qui définissent
le coût des insertions, des remplacements et des effacement.
C'est une version plus générale et plus souple que la version
simple, mais qui n'est pas aussi efficace.
La deuxième variante n'est pas encore implémentée.
Elle est encore plus générale, et plus souple, mais plus lente.
Elle appellera une fonction utilisateur qui déterminera le coût
de chaque opération.
La fonction utilisateur sera appelée avec les arguments suivants :
opération a appliquer : 'I', 'R' or 'D'
caractère courant de la chaîne str1
caractère courant de la chaîne str2
position courante de la chaîne str1
position courante de la chaîne str2
caractères restants dans la chaîne str1
caractères restants dans la chaîne str2
La fonction utilisateur doit retourner un entier positif, qui
décrira le coût de cette opération particulière. Elle peut ne
prendre en compte que certains arguments, et non leur
totalité.
L'utilisation d'une fonction utilisateur permet de prendre en
compte la différence entre certains caractères, ou
leur contexte pour déterminer le coût d'une opération
d'insertion, remplacement ou effacement. Elle accroît la charge de calcul
demandée au CPU, et annule l'optimisation des autres variantes.
Voir aussi
soundex,
similar_text et
metaphone.
|