levenshtein

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().