Calculatrice Distance de Levenshtein

Calculez la distance de Levenshtein (edit distance) entre chaînes, similarité en %, Damerau avec transposition et recherche du mot le plus proche.

Paramètres de calcul
Scegli il tipo di calcolo.
Prima stringa da confrontare.
Seconda stringa. Per 'closest_word' è la parola di riferimento.
Per modo closest_word: dizionario in cui cercare la parola più vicina a s1.
Ce calculateur vous a-t-il été utile ?

La distance de Levenshtein

La distance de Levenshtein, introduite par Vladimir Levenshtein en 1965, compte le nombre minimal d'opérations élémentaires (insertion, suppression ou substitution) nécessaires pour transformer une chaîne en une autre.

Opérations élémentaires

  1. Insertion.
  2. Suppression.
  3. Substitution.

Distance entre « kitten » et « sitting » = 3.

Les quatre modes

  1. Distance classique avec matrice DP.
  2. Similarité normalisée (0-100 %).
  3. Damerau-Levenshtein avec transposition.
  4. Mot le plus proche dans une liste.

Algorithme DP Wagner-Fischer

d[i][j] = min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1]+c), c = 0 si égaux, 1 sinon. Complexité O(m·n).

Damerau-Levenshtein

Ajoute la transposition : d[i][j] ≤ d[i-2][j-2]+1 si a[i-1]=b[j-2] et a[i-2]=b[j-1]. « teh » → « the » = 1 en Damerau.

Variantes

  • Hamming : substitutions uniquement, même longueur.
  • Jaro/Jaro-Winkler : privilégie préfixes communs.
  • N-gram / Jaccard : sous-chaînes de k caractères.
  • Needleman-Wunsch : généralisation pondérée (bioinformatique).
  • Smith-Waterman : alignement local.

Applications

  • Correcteurs : Aspell, Hunspell.
  • Recherche floue : Elasticsearch, Solr.
  • Diff/merge : Unix, Git (Myers 1986).
  • ADN : BLAST, FASTA.
  • Déduplication d'enregistrements.
  • Post-traitement OCR.

Optimisations

  • Mémoire O(min(m,n)) : deux tableaux 1D suffisent (ligne courante et précédente).
  • Seuil d'Ukkonen : pour distance ≤ k, on se restreint à une bande diagonale de largeur 2k+1, complexité O(k·max(m,n)).
  • Bit-parallèle Myers 1999 : avec SIMD et opérations bitwise, ~60× plus rapide pour chaînes courtes (jusqu'à 64 caractères).
  • Pré-filtrage q-gram avant calcul exact : élimine les candidats lointains via hachage.

Exemple pas à pas

Calculons la distance entre « kitten » et « sitting ». La matrice PD 7×8 donne d[6][7] = 3. Séquence optimale : k→s (substitution), e→i (substitution), ajouter « g » (insertion). Vérification : 3 opérations minimales. Similarité = 1 − 3/7 = 0,571 = 57,1 %.

Ou la distance d'edition alimente le logiciel quotidien

La distance de Levenshtein est l'une de ces idees discretes qui operent sans se voir dans les outils que nous utilisons chaque jour. Le correcteur orthographique l'emploie pour proposer le mot correct le plus proche de celui que vous avez mal ecrit, et l'autocorrection du telephone s'en sert pour deviner votre intention a partir de frappes erronees. La recherche floue, qui trouve des resultats meme si le terme comporte des fautes, s'appuie sur un seuil de similarite derive de cette distance, et les systemes de reconnaissance optique de caracteres l'utilisent pour corriger des lectures douteuses en les comparant a un dictionnaire.

Sa portee va bien au-dela du texte ordinaire. En bio-informatique, des variantes de la meme idee alignent des sequences d'ADN et de proteines pour mesurer leur parente evolutive, un probleme au coeur de la genomique moderne. Les detecteurs de plagiat comparent des documents, les systemes de liaison d'enregistrements fusionnent des bases de donnees en identifiant des entrees quasi identiques ecrites differemment, et les outils de gestion de versions calculent les differences entre fichiers. Dans tous ces cas, compter le nombre minimal d'editions offre une mesure robuste et universelle de la ressemblance de deux chaines.

L'idee de la programmation dynamique derriere l'algorithme

Le calcul efficace de la distance de Levenshtein est un exemple classique de programmation dynamique. Au lieu d'essayer toutes les sequences possibles d'editions, qui seraient astronomiquement nombreuses, on construit un tableau ou chaque case garde la distance entre deux prefixes des chaines. La valeur de chaque case s'obtient de ses trois voisins deja calcules, en choisissant le minimum entre inserer, supprimer ou substituer un caractere. Cette propriete de sous-structure optimale permet de resoudre le probleme en temps proportionnel au produit des longueurs.

Une fois le tableau rempli, le coin inferieur droit contient la distance recherchee, et en parcourant la matrice a rebours on retrouve la sequence concrete d'operations qui la realise. Cette meme structure se relie au probleme de la plus longue sous-sequence commune et a l'alignement de sequences de Needleman-Wunsch, dont la distance d'edition est une variante. La calculatrice affiche la matrice complete pour les chaines courtes, de sorte qu'on peut suivre visuellement comment chaque valeur se propage du coin superieur gauche jusqu'a la solution finale.

Mis à jour en juillet 2026

Questions fréquentes

Qu'est-ce que la distance de Levenshtein ?

C'est le nombre minimal d'operations elementaires (inserer, supprimer ou substituer un caractere) necessaires pour transformer une chaine en une autre. Introduite par le mathematicien russe Vladimir Levenshtein en 1965, c'est la mesure la plus utilisee pour quantifier la difference entre deux mots ou textes. Pour "kitten" et "sitting" elle vaut 3.

Quels modes offre la calculatrice ?

Quatre : la distance classique avec la matrice de programmation dynamique, la similarite normalisee de 0 a 100%, la variante Damerau-Levenshtein qui ajoute la transposition de caracteres adjacents, et la recherche du mot le plus proche dans une liste. Chaque mode montre la sequence d'operations optimale.

Comment calcule-t-on la distance ?

Avec la programmation dynamique : on construit une matrice ou d[i][j] est la distance entre les i premiers caracteres de la premiere chaine et les j premiers de la seconde. Chaque case est le minimum de d[i-1][j]+1, d[i][j-1]+1 et d[i-1][j-1]+cout, ou le cout est 0 si les caracteres coincident, 1 sinon.

Qu'est-ce que la similarite normalisee ?

C'est la distance exprimee en pourcentage de la longueur maximale des deux chaines : similarite = (1 - distance/max(|s1|, |s2|)) x 100%. Elle vaut 100% pour des chaines identiques et descend vers 0 pour des chaines tres differentes. En fuzzy matching on utilise souvent un seuil de 80% pour considerer deux chaines similaires.

Qu'est-ce que la distance de Damerau-Levenshtein ?

C'est une variante qui ajoute une quatrieme operation : la transposition de deux caracteres adjacents, de cout 1. Elle capture mieux les fautes de frappe comme l'echange de lettres voisines ("teh" au lieu de "the"). La calculatrice affiche a la fois la distance de Levenshtein et celle de Damerau pour comparer.

Quelle est la complexite de l'algorithme ?

Le calcul avec la matrice demande un temps et un espace proportionnels au produit des longueurs des deux chaines, soit O(m x n). Des optimisations existent : la version en bande diagonale pour de petites distances, l'algorithme bit-parallel de Myers et le filtrage q-gram, qui accelerent beaucoup les comparaisons sur de grands dictionnaires.

Ou utilise-t-on la distance de Levenshtein ?

Dans les correcteurs orthographiques et l'autocorrection, dans la recherche floue, dans la reconnaissance optique de caracteres, en bio-informatique pour aligner des sequences d'ADN et de proteines, dans la detection de plagiat, dans la deduplication de bases de donnees et dans les outils de comparaison de fichiers. Elle sert partout ou l'on doit mesurer la ressemblance entre textes.

Comment trouve-t-on le mot le plus similaire ?

On calcule la distance de Levenshtein entre la chaine donnee et chaque mot d'une liste candidate, en choisissant celui de distance minimale. C'est le mecanisme des suggestions des correcteurs et de l'autocompletion : parmi tous les mots du dictionnaire, on propose celui qui demande le moins de modifications pour correspondre au texte saisi.

Commentaires (0)

Pas encore de commentaire. Soyez le premier !