Manuel PHP
Précédent |  | Suivant

# levenshtein

(PHP 3>= 3.0.17, PHP 4 >= 4.0.1, PHP 5)

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 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)`, où `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ètres, 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 :

- Opération à réaliser : 'I', 'R' ou 'D'

- Caractère dans `str1`

- Caractère dans `str2`

- Position dans `str1`

- Position dans `str2`

- Caractères restants dans `str1`

- Caractères restants dans `str2`

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

Précédent | Sommaire | Suivant
join | Niveau supérieur | localeconv