levenshtein

levenshtein -- Calcule la distance Levenshtein entre deux chaînes

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( ) 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 distance 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 ) , 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èters , 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 :

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