Distance de Levenshtein

Sommaire de l'article

Algorithmes et Mises à Jour de la Distance de Levenshtein : Concept, Calcul et Applications

Introduction

La distance de Levenshtein est une mesure de similarité utilisée pourévaluer la différence entre deux chaînes de caractères en comptant le nombre minimal d’opérations d’édition nécessaires pour transformer l’une en l’autre. Ces opérations sont généralement l’insertion, la suppression et la substitution d’un caractère. Définie en 1965 par le mathématicien soviétique Vladimir Levenshtein, cette distance est aujourd’hui un outil fondamental en traitement automatique du langage naturel (NLP), en bioinformatique, en reconnaissance vocale, en correction orthographique, en recherche approximative et dans de nombreux systèmes de recommandation et de dédoublonnage de données.

La distance de Levenshtein est une véritable distance mathématique : elle respecte la symétrie, la positivité et l’inégalité triangulaire. Elle permet de comparer des mots, des phrases, des identifiants, des adresses e‑mail, des noms de domaines, des séquences ADN ou protéiques, et plus largement toute donnée structurée sous forme de chaîne de symboles.

Cet article propose une présentation complète et à jour du concept de distance de Levenshtein, de ses algorithmes de calcul, de ses variantes, de ses optimisations et de ses principales applications pratiques. Vous y trouverezégalement des bonnes pratiques pour améliorer les performances et la qualité de vos traitements textuels, ainsi que des exemples de bibliothèques et d’outils prêts à l’emploi.

Concepts clés

Définition de la distance de Levenshtein

La distance de Levenshtein est définie comme le nombre minimal d’opérations d’éditionélémentaires nécessaires pour transformer une chaîne de caractères A en une chaîne de caractères B. Les opérations autorisées sont :

Insertion d’un caractère
Suppression (déletion) d’un caractère
Substitution d’un caractère par un autre

On note généralement cette distance d(A, B). Plus d(A, B) est faible, plus les chaînes sont similaires. Une distanceégale à 0 signifie que les deux chaînes sont identiques.

Sur le plan mathématique, la distance de Levenshtein vérifie notamment les propriétés suivantes :

Non-négativité : d(A, B) ≥ 0
Identité des indiscernables : d(A, B) = 0 si et seulement si A = B
Symétrie : d(A, B) = d(B, A)
Inégalité triangulaire : d(A, C) ≤ d(A, B) + d(B, C)

Si l’on note |A| la longueur de la chaîne A et |B| la longueur de la chaîne B, la distance de Levenshtein est toujours comprise entre les deux bornes suivantes :

Borne minimale : | |A| - |B| |
Borne maximale : max(|A|, |B|)

On parle souvent de distance d’édition (edit distance) pour désigner ce type de métrique. Toutefois, le terme edit distance recouvre en réalité une famille plus large de distances, dont la distance de Levenshtein n’est qu’un cas particulier (coûts unitaires, pas de transposition).

Exemples classiques de distance de Levenshtein

Voici quelques exemples standards de calcul de la distance de Levenshtein :

De "kitten" à "sitting" : la distance de Levenshtein est 3 (substitution de k en s, substitution de e en i, insertion de g en fin).
De "flaw" à "lawn" : la distance de Levenshtein est 2 (suppression de f, insertion de n en fin, ou bien substitution de f en l puis substitution de w en n selon la séquence choisie).
De "amazon.com" à "amazom.com" : la distance de Levenshtein est 1 (substitution de n en m).

Pour reprendre précisément l’exemple donné dans l’article original :

Pour transformer "kitten" en "sitting", il faut en réalité trois opérations d’édition et non deux. Un scénario possible est :

Substituer k → s
Substituer e → i
Insérer g à la fin

La distance de Levenshtein correcte entre "kitten" et "sitting" est donc 3.

Différence entre distance de Levenshtein et distance de Hamming

Il est important de distinguer la distance de Levenshtein de la distance de Hamming :

La distance de Hamming ne considère que les substitutions et suppose que les deux chaînes sont de même longueur. Elle compte le nombre de positions où les deux chaînes diffèrent.
La distance de Levenshtein autorise les insertions, suppression et substitutions, et fonctionne même lorsque les chaînes ont des longueurs différentes.

La distance de Levenshtein est donc plus générale et plus adaptée aux scénarios réels de saisie, de bruit ou d’erreurs d’orthographe.

Algorithmes de calcul de la distance de Levenshtein

Programmation dynamique : algorithme standard

L’algorithme classique de calcul de la distance de Levenshtein repose sur la programmation dynamique. Il s’agit de construire une matrice de dimensions (m + 1) × (n + 1), où m est la longueur de la première chaîne et n la longueur de la seconde. Chaque cellule D[i][j] représente le coût minimal pour transformer les i premiers caractères de la première chaîne en les j premiers caractères de la seconde.

Lesétapes générales sont les suivantes :

Initialisation de la première ligne : D[j] = j (j insertions nécessaires pour passer de la chaîne vide aux j premiers caractères de la seconde chaîne).
Initialisation de la première colonne : D[i] = i (i suppressions nécessaires pour passer des i premiers caractères de la première chaîne à la chaîne vide).
Remplissage récursif de la matrice selon une relation de récurrence basée sur insertion, suppression, substitution.

Pour deux chaînes A et B, de longueurs respectives m et n, la relation de récurrence typique est :

D[i] = i
D[j] = j Pour i de 1à m : Pour j de 1à n : coûtSubstitution = 0 si A[i] == B[j], sinon 1 D[i][j] = min( D[i-1][j] + 1, // suppression D[i][j-1] + 1, // insertion D[i-1][j-1] + coûtSubstitution // substitution )

À la fin du calcul, la distance de Levenshtein est donnée par la valeur dans la cellule D[m][n], située dans le coin inférieur droit de la matrice.

Complexité :

Temps : la complexité temporelle de l’algorithme dynamique standard est en O(m × n).
Mémoire : l’implémentation naïve nécessiteégalement O(m × n) en mémoire pour stocker la matrice complète.

Exemple de matrice pour "kitten" et "sitting"

Considérons un exemple de construction de matrice pour comparer "kitten" (6 caractères) et "sitting" (7 caractères). La matrice conceptuelle (sans toutes les valeurs détaillées) est de taille 7 × 8 :

		s	i	t	t	i	n	g
	0	1	2	3	4	5	6	7
k	1
i	2
t	3
t	4
e	5
n	6

En remplissant correctement cette matrice selon la relation de récurrence décrite plus haut, on obtient une valeur de 3 dans la cellule finale D[6][7], qui correspond bien à la distance de Levenshtein entre "kitten" et "sitting".

Optimisation mémoire : version espace réduit

Si l’on souhaite optimiser la consommation mémoire, il est possible de ne conserver que deux lignes de la matrice à la fois (la ligne courante et la ligne précédente). Dans ce cas, la complexité mémoire passe de O(m × n) à O(min(m, n)). Cette optimisation est très utile pour des chaînes longues, par exemple en bioinformatique ou dans l’analyse de grands corpus textuels.

Cette approche ne permet pas directement de reconstruire la séquence d’édition complète (les opérations exactes à appliquer) sans stockage supplémentaire, mais elle suffit largement lorsque seul le score de distance est nécessaire.

Autres optimisations et algorithmes avancés

Au-del à de l’algorithme classique, plusieurs optimisations sont possibles :

Bornes et coupures anticipées : si l’on connaît un seuil maximal de distance acceptable (par exemple pour de la recherche floue), on peut interrompre le calcul dès que la distance partielle dépasse ce seuil.
Algorithmes sous-quadratiques approximatifs : pour de très longues chaînes, des algorithmes d’approximation permettent de réduire le temps de calcul au prix d’une légère perte de précision.
Automates de Levenshtein : on peut construire un automate fini qui accepte toutes les chaînes situées à une distance ≤ k d’un motif donné, ce qui permet des recherches plus efficaces dans certains index.
Méthode de Hirschberg et algorithmes apparentés : utilisés surtout pour l’alignement de séquences, ils permettent de retrouver un alignement optimal avec une consommation mémoire réduite.

Variantes et extensions de la distance de Levenshtein

Distance de Damerau–Levenshtein

La distance de Damerau–Levenshtein est une extension de la distance de Levenshtein qui ajoute une quatrième opérationélémentaire :

Transposition de deux caractères adjacents (par exemple transformer "ab" en "ba" en une seule opération).

Cette variante est plus fidèle à certains types d’erreurs de frappe courantes, notamment dans les textes saisis au clavier, où l’inversion de deux lettres adjacentes est fréquente (par exemple "alogrithme" au lieu de "algorithme").

Distances d’édition pondérées

Dans la pratique, toutes les opérations d’édition ne coûtent pas nécessairement la même chose. On peut donc définir une distance d’édition pondérée en attribuant un coût spécifique à chaque type d’opération, voire à chaque paire de caractères (par exemple, substituer "m" par "n" est plus probable qu’une substitution "m" → "z").

Ce type de modèle est utile lorsque l’on dispose de statistiques sur les erreurs les plus fréquentes dans un corpus, en OCR, ou dans des systèmes de transcription automatique. On parle alors parfois de modèles de coûts d’édition.

Liens avec l’alignement de séquences

La distance de Levenshtein estétroitement liée aux algorithmes d’alignement de séquences, largement utilisés en bioinformatique. Des algorithmes comme Needleman–Wunsch (alignement global) ou Smith–Waterman (alignement local) généralisent l’idée de distance d’édition en utilisant des scores de substitution dépendant des caractères et des pénalités de gap (ouvertures et extensions d’espaces).

Dans ce cadre, la distance de Levenshtein peutêtre vue comme un cas particulier où toutes les substitutions coûtent 1, toutes les insertions et suppressions coûtent 1, et où l’on ne considère pas de différenciation entre ouverture de gap et extension de gap.

Applications pratiques de la distance de Levenshtein

Correction orthographique et recherche approximative

Une des utilisations les plus connues de la distance de Levenshtein concerne la correction orthographique et la recherche tolérante aux fautes de frappe :

Dans un moteur de recherche, la distance de Levenshtein permet de suggérer des requêtes proches lorsqu’un internaute fait une faute de frappe (par exemple, proposer "restaurant" lorsqu’il tape "restaurent").
Dans un éditeur de texte ou un environnement de développement (IDE), elle aide à suggérer des corrections ou complétions de mots mal saisis.
Dans des systèmes de recherche en base de données, elle est utilisée pour la recherche approximative de noms, prénoms, adresses, références produits, etc.

Dédoublonnage et qualité des données

La distance de Levenshtein est très utile pour améliorer la qualité des données :

Dédoublonnage de fiches clients ou de contacts lorsque des noms ou prénoms sont légèrement différents (erreurs de frappe, accents oubliés, espaces superflus).
Nettoyage d’adresses postales ou d’adresses e‑mail similaires mais pas strictement identiques.
Normalisation de codes produits, codes de référence ou identifiants mal saisis.

En combinant la distance de Levenshtein avec des règles métier (seuils de similarité, normalisation préalable, filtrage sur d’autres champs), on obtient des outils très efficaces pour détecter les doublons et les anomalies dans les bases de données.

Traitement automatique du langage naturel (NLP)

En NLP, la distance de Levenshtein intervient dans plusieurs tâches :

Mesure de similarité lexicale entre mots.
Évaluation de la qualité de transcription (par exemple, comparer une transcription automatique à une référence humaine).
Détection de plagiat ou de contenu proche en combinant des distances de Levenshtein sur des segments de texte.
Comparaison de tokens, d’entités nommées ou de noms propres issus de différentes sources.

Bioinformatique et séquences biologiques

En bioinformatique, des distances inspirées de la distance de Levenshtein sont utilisées pour :

Comparer des séquences ADN ou protéiques.
Détecter des mutations, insertions ou délétions dans des séquences.
Analyser la similarité entre différents génomes ou gènes.

Les modèles employés dans ce domaine sont souvent plus sophistiqués (matrices de substitution, pénalités de gap), mais l’intuition de base reste celle d’une distance d’édition entre deux chaînes de symboles.

Sécurité, noms de domaine et détection de typosquatting

La distance de Levenshtein estégalement utilisée dans la cybersécurité et la gestion de noms de domaine :

Détection de typosquatting : repérer des noms de domaine très proches d’une marque existante (par exemple, "amaz0n.com" ou "amazom.com") afin d’identifier de potentiels sites frauduleux.
Surveillance de marques et noms de produits, pour repérer des usages détournés ou trompeurs.

Reconnaissance optique de caractères (OCR) et reconnaissance vocale

En OCR comme en reconnaissance vocale, les systèmes produisent parfois des sorties bruitées ou imparfaites. La distance de Levenshtein sert alors à :

Comparer la sortie de l’OCR à un lexique de mots connus et sélectionner les candidates les plus proches.
Évaluer les performances d’un modèle de reconnaissance en comparant sa sortie à une transcription de référence.

Bonnes pratiques pour l’utilisation de la distance de Levenshtein

Prétraitement et optimisation du contenu à comparer

Avant de calculer une distance de Levenshtein, il est souvent recommandé de prétraiter les chaînes pour améliorer la pertinence des résultats et réduire le temps de calcul :

Normalisation : mettre les chaînes en minuscules ou majuscules, supprimer les accents, homogénéiser les espaces (espaces multiples, espaces en début/fin…).
Nettoyage : retirer les caractères non pertinents (ponctuation, symboles bruyants) lorsque cela est cohérent avec l’usage métier.
Suppression de doublons ou de préfixes/suffixes connus (titres, formules répétitives, codes invariants) si cela n’apporte pas de valeur à la comparaison.

Ce prétraitement permet parfois de diminuer considérablement la longueur des chaînes et donc le coût de calcul, tout en améliorant la pertinence sémantique de la distance mesurée.

Choix du seuil de distance et interprétation des scores

Pour exploiter la distance de Levenshtein dans des systèmes applicatifs, il faut souvent fixer un seuil à partir duquel on considère que deux chaînes sont « similaires » :

On peut travailler sur la distance brute (par exemple considérer qu’une distance ≤ 2 est acceptable pour des prénoms).
On peutégalement utiliser une distance normalisée, par exemple en divisant la distance par la longueur maximale des deux chaînes pour obtenir un score entre 0 et 1, puis utiliser ce score comme indicateur de similarité.

Le choix du seuil dépend fortement du contexte métier, de la longueur moyenne des chaînes et du coût acceptable en faux positifs / faux négatifs.

Algorithmes optimisés pour grandes volumes de données

Lorsque l’on doit comparer un grand nombre de chaînes entre elles (par exemple, comparer chaque nouvelle entrée avec des millions de lignes en base), un calcul de distance de Levenshtein naïf pour toutes les paires devient prohibitif.

Quelques stratégies d’optimisation :

Filtrage par longueur : ne comparer que des chaînes dont la différence de longueur ne dépasse pas un certain seuil.
Indexation phonétique ou lexicale (Soundex, Metaphone, n-grammes) pour réduire le nombre de candidats avant de calculer la distance exacte.
Utilisation de structures d’index spécialisées (arbres BK, automates de Levenshtein) pour accélérer les recherches de voisins proches.
Parallélisation des calculs sur plusieurs processeurs ou nœuds lorsque le volume de données est très important.

Algorithmes en espace réduit et contraintes mémoire

Sur des appareils contraints (applications mobiles, systèmes embarqués) ou pour des traitements à grandeéchelle, la mémoire est parfois un facteur limitant. L’utilisation d’implémentations en espace réduit (ne stocker que quelques lignes de la matrice à la fois) est alors fortement recommandée.

Qualité des données et réduction des faux positifs

Pour limiter les faux positifs (deux chaînes considérées comme similaires alors qu’elles ne devraient pas l’être), il est souvent utile de :

Combiner la distance de Levenshtein avec d’autres critères (code postal, date de naissance, identifiant secondaire…).
Appliquer des règles métier spécifiques (par exemple, ne comparer que les personnes ayant la même année de naissance).
Utiliser des scores composites où la distance de Levenshtein n’est qu’un des nombreux signaux agrégés.

Outils, bibliothèques et ressources

Bibliothèques Python pour la distance de Levenshtein

Pour implémenter la distance de Levenshtein en Python, plusieurs options existent :

Bibliothèque standard : difflib Même si difflib ne fournit pas directement la distance de Levenshtein, elle propose des mesures de similarité comme le SequenceMatcher qui peuvent servir dans des cas proches (comparaison de séquences, ratio de similarité).
Bibliothèque python-Levenshtein Une bibliothèque très utilisée qui implémente efficacement la distance de Levenshtein en C, avec des fonctions pour la distance brute, la similarité, et parfois des distances apparentées.

Pour des projets de traitement de texte, de data engineering ou d’IA, ces bibliothèques permettent d’intégrer rapidement la distance de Levenshtein dans vos pipelines.

Outils en ligne et démonstrateurs

De nombreux outils en ligne permettent de calculer la distance de Levenshtein entre deux chaînes :

Des calculateurs de distance où l’on saisit deux chaînes et où l’outil renvoie la distance et parfois la matrice d’édition.
Des démonstrateurs pédagogiques qui visualisent pas à pas le remplissage de la matrice de programmation dynamique.

Ces outils sont particulièrement utiles pour comprendre intuitivement le fonctionnement de l’algorithme et expliquer le concept à deséquipes non techniques.

Ressources pédagogiques et tutoriels

Pour aller plus loin, de nombreux tutoriels, articles de blog et ressourceséducatives détaillent :

La théorie mathématique des distances d’édition.
Des implémentations efficaces dans différents langages (Python, Java, C++, JavaScript, PHP, etc.).
Des exemples d’applications concrètes : moteurs de recherche, systèmes de recommandation, analyse de logs, etc.

Les plateformes spécialisées en algorithmique et en développement proposent souvent des exercices pratiques pour implémenter la distance de Levenshtein et ses variantes, ce qui constitue un excellent entraînement.

FAQ

Quelle est la différence entre la distance de Levenshtein et la distance de Hamming ?
La distance de Hamming ne tient compte que des substitutions et suppose que les deux chaînes sont de même longueur. Elle compte le nombre de positions où les caractères diffèrent. La distance de Levenshtein, au contraire, autorise les insertions, les suppression et les substitutions, et fonctionne même lorsque les chaînes ont des longueurs différentes.
Puis-je utiliser la distance de Levenshtein pour comparer des phrases entières ?
Oui, il est tout à fait possible d’utiliser la distance de Levenshtein pour comparer des phrases entières. Cependant, cette distance est souvent plus pertinente pour des unités plus petites comme les mots, les noms propres, les identifiants ou les segments courts de texte. Pour des phrases complètes ou des documents entiers, on combine généralement la distance de Levenshtein avec d’autres techniques (n‑grammes, vectorisation, modèles sémantiques) afin de mieux capturer le sens global.
Comment gérer l’efficacité du calcul sur des chaînes très longues ?
Pour des chaînes très longues, la complexité O(m × n) peut devenir coûteuse. Pour améliorer l’efficacité, on peut :
- Limiter le calcul à un seuil maximal de distance (coupure anticipée).
- Utiliser des versions en espace réduit pour diminuer la consommation mémoire.
- Recourir à des algorithmes approximatifs lorsqu’un score exact n’est pas indispensable.
- Appliquer des filtres préalables (par longueur, par index phonétique, par préfixes ou n‑grammes) pour réduire le nombre de comparaisons nécessaires.
La distance de Levenshtein est-elle adaptée aux langues avec accents et caractères spéciaux ?
Oui, la distance de Levenshtein fonctionne avec n’importe quel alphabet de symboles, y compris les caractères accentués et les alphabets non latins. Toutefois, il peutêtre pertinent de normaliser les textes (par exemple, suppression des accents ou translittération) si les accents ne sont pas significatifs pour l’usage visé.
Est-il possible d’attribuer des coûts différents aux opérations ?
Oui. Dans de nombreuses applications, on utilise une distance d’édition pondérée où chaque opération (insertion, suppression, substitution) a un coût spécifique. On peut même définir un coût variable selon les caractères concernés (par exemple, une substitution entre deux voyelles peut coûter moins cher qu’entre une voyelle et une consonne).

Conclusion

La distance de Levenshtein est une métrique simple à comprendre mais extrêmement puissante pour mesurer la similarité entre chaînes de caractères. Définie dans les années 1960, elle reste aujourd’hui au cœur de nombreuses applications modernes : moteurs de recherche, systèmes de recommandation, correction orthographique, qualité des données, NLP, bioinformatique, sécurité ou encore analyse de texte.

En maîtrisant :

sa définition (nombre minimal d’insertions, suppressions, substitutions),
ses algorithmes de calcul (programmation dynamique, complexité O(m × n), optimisations mémoire),
ses variantes (Damerau–Levenshtein, distances pondérées, alignement de séquences),
et ses bonnes pratiques d’utilisation (prétraitement, seuils, filtrage, indexation),

vous disposez d’un outil robuste pour améliorer la précision et l’efficacité de vos traitements de données textuelles et de vos algorithmes de recherche approximative.

Que vous travailliez sur des bases de données clients, des applications de recherche, des systèmes de recommandation ou des projets de , l’intégration judicieuse de la distance de Levenshtein peut apporter un gain significatif en qualité de résultats et en expérience utilisateur. N’hésitez pas à expérimenter différentes variantes, seuils et stratégies d’optimisation pour adapter cette distance à vos cas d’usage spécifiques.