Principes de la recherche de Levenshtein.

L'algorythme de Levenshtein permet de mesurer la similarité entre deux chaines de caractères. Son résultat est égal au nombre minimal de caractères qu'il faut supprimer, insérer, ou remplacer pour passer d'une chaîne à l'autre.

Dans le cadre d'une recherche sur une base de données de nom, cette recherche s'avère particulièrement utile pour s'affranchir des fautes de transcriptions réalisées aussi bien par les personnes qui ont rédigé l'acte que par les personnes qui l'ont décrypté.

Elle permet aussi de retrouver des noms dont la variablité au fil du temps est importante et imprévisible.

Prenons un exemple :

Lors d'une recherche classique, si l'on tape DURAND on ne trouvera qu'une occurrence dans la liste des 6 noms.

On peut améliorer la chose en ne recherchant qu'une partie du nom : URAN nous retrouvera 3 noms de la liste, plus d'autre contenant ces 4 lettres : BOURAN, FAURAN , URANUS etc..

On peut aussi chercher sur le début du nom : DUR nous donneras 4 noms plus tous les DURAS, DURIVE etc..

Avec la méthode de Levenshtein, on va rechercher les noms dans la base qui varient de une, deux différences ou plus avec notre nom.

Reprenons notre DURAND : DUREND présente une différence, il en est de même pour DURAN, RURAND et DUBAND.

DUREN présente deux différences

Donc si nous faisons une recherche avec deux différence, le programme va aller piocher dans la base de données tous les noms qui ressemblent à deux différences près à notre DURAND : nous retrouverons bien nos 6 noms.

Certains pourront dire que l'on peut faire une recherche sur la prononciation. Dans le cas ci dessus elle marcherait probablement. Le problème est que les recherches sur les prononciations sont basées dans le meilleur des cas sur le Français moderne, souvent sur l'anglosaxon et jamais sur les dialectes pratiqués dans les campagnes juqu'au 19ème siècle. En outre elles ne trouveront jamais les fautes de saisie : notre RURAND ne sera jamais trouvé.

J'espère vous avoir convaincu sur l'intêret de ce type de recherche.