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 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 couteux 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'insertion, replacmenet et effacement nécessaire pour transformer la chaîne str1 en str2.
Une variante prend trois paramètres additionnels, qui définissent le cout 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 troisième variante n'est pas encore implémentée. Elle est encore plus générale, et plus souple, mais plus lente. Elle appelera 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
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 accroit la charge de calcul demandée au CPU, et annule l'optimisation des autres variantes.
Voir aussi soundex(), similar_text() et metaphone().
| Précédent | Sommaire | Suivant |
| join | Niveau supérieur | localeconv |