Distance de Levenshtein

Description

La distance de Levenshtein mesure la similarité entre deux chaînes de caractères.
Elle est égale au nombre minimal de caractères qu'il faut supprimer, insérer ou remplacer pour passer d'une chaîne à l'autre.
(voir http://fr.wikipedia.org/wiki/Distance_de_Levenshtein )

Ce script pourvoit l'eggdrop du package Levenshtein :
Package provide Levenshtein 1.0

Intérêts

Permet à un correcteur orthographique de faire des suggestions pour tel mot mal orthographié, en proposant d'autres mots dont la distance de Levenshtein par rapport au premier est faible.
Permet à une pseudo-IA de type chatterbot d'avoir une tolérance orthographique : si tel mot comparé à tel autre a une distance inférieure à une tolérance donnée, on peut décider qu'il est équivalent.
...

Syntaxe

::levenshtein::distance <string 1> <string 2>

Exemples :

levenshtein::distance "bonjour" "bougeoir"

			-> 4

Il faut manipuler 4 caractères pour passer du mot "bonjour" au mot "bougeoir" :

BONJOUR
BOUJOUR -> on remplace le N par un U
BOUGOUR -> on remplace le J par un G
BOUGEOUR -> on insère un E
BOUGEOIR -> on remplace le U par un I

levenshtein::distance "antiquaire" "antikaire"

			-> 2

On peut conclure de cet exemple de 10 lettres qu'il est très similaire avec le 2ème mot avec une distance de 2 seulement.

Il est important d'avoir à l'esprit qu'une distance de 2 entre deux mots de 10 lettres dénote une ressemblance, tandis qu'une distance de 2 entre deux mots de 3 lettres signifie qu'ils sont très différents comme le montre l'exemple suivant :

levenshtein::distance "pin" "pas"

			-> 2

Comme vous le voyez, une distance de 2 ne permet pas de faire beaucoup de modifications dans un mot de 10 lettres mais elle représente un changement radical pour un mot de 3 lettres.

Afin de préserver la pertinence des résultats, vous prendrez soin de toujours lier la tolérance à la longueur, proportionnellement.

levenshtein::distance "antiquaire" "dimanche"

			-> 8

Sur ce dernier exemple, on peut voir qu'il y a une distance de 8 entre le 1er mot et le second qui est très différent.

Téléchargement

Distance de Levenshtein v1.0

Laissez vos commentaires / questions / suggestions / rapports de bugs ici.