Source Wikipedia. La distance de Levenshtein une distance mathematique donnant une mesure de la similarite entre deux chaines de caracteres. Elle est egale au nombre minimal de caracteres qu il faut supprimer, inserer ou remplacer pour passer d une chaine a l autre. Elle a ete proposee par Vladimir Levenshtein en 1965. Elle est egalement connue sous les noms de distance d edition ou de deformation dynamique temporelle, notamment en reconnaissance de formes et particulierement en reconnaissance vocale1,2.Cette distance est d autant plus grande que le nombre de differences entre les deux chaines est grand. La distance de Levenshtein peut etre consideree comme une generalisation de la distance de Hamming. On peut montrer en particulier que la distance de Hamming est un majorant de la distance de Levenshtein.Definition : on appelle distance de Levenshtein entre deux mots M et P le cout minimal pour aller de M a P en effectuant les operations elementaires suivantes : i) substitution d un caractere de M en un caractere de P ; ii) ajout dans M d un caractere de P ; iii) suppression d un caractere de M. On associe ainsi a chacune de ces operations un cout. Le cout est toujours egal a 1, sauf dans le cas d une substitution de caracteres identiques. Exemples : si M = "examen" et P = "examen", alors LD (M, P) = 0, parce qu aucune operation n a ete realisee. Si M = "examen" et P = "examan", alors LD (M, P) = 1, parce qu il y a eu un remplacement (changement du e en a), et que l on ne peut pas en faire moins.