8.21.21 levenshtein
[Notes en ligne] [Exemples]

Calcule la distance Levenshtein entre deux chaînes

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 : @itemize @bullet