Calcul distance de Levenshtein
Comparez deux mots, phrases ou chaînes de caractères pour mesurer leur proximité textuelle. Cet outil calcule la distance de Levenshtein, le pourcentage de similarité normalisé et un résumé visuel immédiat.
Distance
0Similarité
100 %Longueur texte A
0Longueur texte B
0- Saisissez deux textes puis cliquez sur Calculer la distance.
- Le graphique affichera les longueurs comparées et la distance calculée.
Guide expert : comprendre le calcul de distance de Levenshtein
Le calcul de distance de Levenshtein est une méthode fondamentale d’analyse textuelle. Utilisée en linguistique informatique, en recherche d’information, en contrôle qualité de bases de données, en détection d’erreurs de saisie et en rapprochement d’identités, elle mesure la différence entre deux chaînes de caractères. Si vous cherchez à comparer deux mots, deux noms de produits, deux requêtes utilisateur ou deux libellés administratifs, cet indicateur fait partie des outils les plus fiables pour une première estimation de similarité.
Définition simple
La distance de Levenshtein représente le nombre minimal d’opérations nécessaires pour transformer un texte A en texte B. Trois opérations sont autorisées : insérer un caractère, supprimer un caractère, ou remplacer un caractère par un autre. Plus la distance est faible, plus les chaînes sont proches. Une distance égale à 0 signifie que les textes sont identiques après application des règles choisies, comme l’ignorance de la casse ou le traitement des espaces.
Exemple classique : passer de kitten à sitting demande 3 opérations. Cette démonstration est devenue une référence pédagogique parce qu’elle illustre bien le mécanisme de substitution et d’insertion. Dans un contexte réel, ce même principe permet de comparer adress et address, Jonh et John, ou encore des variantes de noms de sociétés, de villes et de catégories produits.
Pourquoi cette mesure est si utile
Dans la pratique, les données textuelles sont rarement parfaites. Les fautes de frappe, les erreurs de transcription, les variations d’abréviations, les accents, les espaces superflus et les différences de casse créent des écarts parfois faibles visuellement mais importants pour un système informatique. Un moteur qui compare seulement l’égalité stricte considérera souvent deux informations équivalentes comme différentes. Levenshtein rétablit une logique de proximité.
- Recherche interne et autocomplete : proposer des résultats malgré une faute de clavier.
- Nettoyage de CRM et d’ERP : repérer les doublons de clients, fournisseurs ou produits.
- Traitement documentaire : rapprocher des titres ou des références proches.
- E-commerce : comparer des requêtes utilisateur à un catalogue de produits.
- Data quality : mesurer l’impact de corrections orthographiques ou normalisations.
Comment se fait le calcul
Le calcul standard repose sur une matrice dynamique de taille (n + 1) × (m + 1), où n est la longueur du premier texte et m celle du second. La première ligne et la première colonne sont initialisées avec des coûts progressifs. Ensuite, chaque cellule reçoit le coût minimal parmi trois possibilités : suppression, insertion ou substitution. Si les caractères comparés sont identiques, le coût de substitution est nul. Sinon, il vaut 1.
- Initialiser la matrice avec les coûts de base.
- Comparer les caractères de chaque position.
- Choisir le coût minimal entre insertion, suppression et substitution.
- Lire le résultat final dans la dernière cellule de la matrice.
Cette approche garantit un calcul exact. Elle est robuste, mais son coût théorique grandit avec le produit des longueurs comparées. Cela explique pourquoi il faut parfois prévoir des optimisations quand on traite des millions de lignes ou des chaînes très longues.
Distance brute ou similarité normalisée
Une distance seule n’est pas toujours suffisante. Une distance de 2 peut être très importante pour un mot de 4 lettres, mais presque négligeable pour une phrase de 80 caractères. Il est donc pertinent de convertir la distance en score de similarité. Une méthode simple consiste à utiliser la formule :
Similarité = ((longueur maximale – distance) / longueur maximale) × 100
Ce pourcentage est plus lisible dans les tableaux de bord, les workflows de qualité de données et les outils d’aide à la décision. Il facilite aussi la définition de seuils opérationnels, par exemple 90 % pour les très fortes correspondances, 75 % à 89 % pour les suggestions probables et moins de 75 % pour les vérifications manuelles.
Exemples chiffrés de comparaison
| Paire comparée | Longueur max | Distance de Levenshtein | Similarité normalisée | Observation |
|---|---|---|---|---|
| kitten / sitting | 7 | 3 | 57,1 % | Exemple académique classique avec substitution et insertion. |
| flaw / lawn | 4 | 2 | 50,0 % | Deux transformations suffisent malgré une forte proximité visuelle. |
| intention / execution | 9 | 5 | 44,4 % | Distance notable sur deux mots de même ordre de grandeur. |
| Saturday / Sunday | 8 | 3 | 62,5 % | Bonne illustration d’une différence moyenne sur des mots usuels. |
Ces statistiques sont de vraies mesures obtenues en appliquant l’algorithme standard. Elles montrent qu’une lecture purement visuelle est parfois trompeuse. Deux mots peuvent sembler très proches, mais générer une distance qui reste significative en proportion de leur longueur.
Impact des longueurs sur la charge de calcul
La complexité temporelle standard est souvent présentée en O(n × m). Cela signifie que le nombre de cellules à évaluer augmente rapidement quand les textes s’allongent. Pour un usage courant sur des mots, noms ou titres courts, la performance reste excellente. En revanche, pour comparer de grandes descriptions, des articles ou des champs concaténés, il faut surveiller les volumes.
| Longueur texte A | Longueur texte B | Cellules de matrice évaluées | Niveau de charge | Cas d’usage typique |
|---|---|---|---|---|
| 10 | 10 | 100 | Très faible | Mots, codes, petites requêtes |
| 50 | 50 | 2 500 | Faible | Noms complets, titres, adresses courtes |
| 100 | 100 | 10 000 | Modérée | Descriptions courtes et champs enrichis |
| 500 | 500 | 250 000 | Élevée | Paragraphes ou gros volumes documentaires |
Dans les pipelines de qualité de données, on évite souvent les comparaisons exhaustives entre tous les enregistrements. On utilise d’abord des filtres de blocage, des clés phonétiques, des index ou des pré sélections lexicales, puis on applique la distance de Levenshtein sur un sous ensemble de candidats plausibles.
Quand Levenshtein est le bon choix
Levenshtein est particulièrement pertinent lorsque l’on suspecte des erreurs de frappe simples ou des variations orthographiques légères. Il fonctionne bien pour :
- des noms propres avec inversions limitées ou lettres manquantes ;
- des références produits proches ;
- des champs de recherche saisis rapidement ;
- des labels standardisés, catégories et taxonomies ;
- des formulaires dans lesquels les utilisateurs peuvent se tromper d’une ou deux frappes.
En revanche, si vous comparez des textes très longs, des phrases avec mots déplacés, ou des formulations sémantiquement proches mais lexicalement différentes, d’autres approches peuvent être plus adaptées : Jaro-Winkler, cosine similarity, trigrammes, embeddings sémantiques ou modèles de langage. Levenshtein reste cependant une excellente base, rapide à comprendre, à implémenter et à expliquer aux métiers.
Bonnes pratiques avant de lancer le calcul
- Normaliser la casse si les majuscules n’ont pas de valeur métier.
- Gérer les espaces pour éviter les faux écarts dus à des doubles espaces ou à des fins de chaîne.
- Uniformiser les accents si votre référentiel ne les considère pas discriminants.
- Supprimer les ponctuations parasites selon votre domaine.
- Définir un seuil métier de correspondance exploitable, et non seulement technique.
L’outil ci dessus intègre déjà certaines options utiles, notamment la gestion de la casse et des espaces. Dans un projet réel, vous pouvez enrichir cette logique avec une translittération, une suppression de mots vides ou une pondération spécifique pour certains caractères.
Interprétation des résultats
Un bon résultat ne se résume pas à une distance faible. Il faut toujours relier la mesure à la longueur totale et au contexte d’usage. Par exemple, une distance de 2 sur deux codes alphanumériques de 6 caractères est importante, alors qu’elle peut être acceptable sur deux libellés de 40 caractères. Dans les processus de dédoublonnage, on combine souvent plusieurs signaux : distance textuelle, code postal, pays, identifiant de compte, domaine email ou date de naissance.
Une grille simple d’interprétation peut être la suivante :
- 95 % à 100 % : quasi identique, généralement fusionnable avec contrôle minimal.
- 85 % à 94 % : forte probabilité de correspondance, validation souvent utile.
- 70 % à 84 % : similarité moyenne, dépend fortement du contexte.
- moins de 70 % : proximité faible, vérification nécessaire avant toute décision.
Applications en SEO, search et data matching
En SEO et en recherche interne, la distance de Levenshtein peut servir à corriger les requêtes des internautes et à rapprocher des orthographes proches. Un visiteur qui tape une variante fautive d’un mot clé peut tout de même trouver la bonne page ou le bon produit. En gouvernance de données, elle aide à identifier les doublons, à réduire la fragmentation d’information et à améliorer la fiabilité des analyses aval. Dans les systèmes de support ou de ticketing, elle peut aussi aider à rapprocher des libellés de catégories similaires saisis différemment par plusieurs équipes.
Le bénéfice majeur est double : meilleure expérience utilisateur d’un côté, meilleure qualité de données de l’autre. C’est précisément ce qui explique la longévité de cet algorithme dans des environnements très variés.
Ressources académiques et institutionnelles
Pour approfondir le sujet, voici quelques sources fiables et reconnues :
FAQ rapide
La distance de Levenshtein gère-t-elle les mots inversés ?
Pas parfaitement. Si l’ordre change fortement, la distance peut monter rapidement. Dans ce cas, d’autres mesures peuvent compléter l’analyse.
Peut-on l’utiliser pour des noms de personnes ?
Oui, très souvent, surtout si vous normalisez au préalable la casse, les accents et les espaces.
Existe-t-il des variantes ?
Oui. La distance de Damerau-Levenshtein prend aussi en compte certaines transpositions de caractères adjacents, ce qui peut être plus réaliste pour les fautes de frappe.
Conclusion
Le calcul de distance de Levenshtein est un outil de référence pour évaluer la proximité entre deux chaînes. Il est simple à expliquer, fiable, largement documenté et immédiatement utile dans de nombreux projets concrets. Pour bien l’exploiter, il faut toutefois l’accompagner d’une normalisation adaptée, d’un score relatif de similarité et d’un seuil métier cohérent. Utilisé intelligemment, il améliore à la fois la recherche, la détection de doublons, la correction de saisie et la qualité générale des données.
Servez-vous du calculateur ci dessus pour tester vos propres cas d’usage. Comparez des mots, des expressions, des identifiants ou des libellés, puis observez la distance, le taux de similarité et le graphique. Cette lecture combinée vous donnera une vision claire de l’écart réel entre vos chaînes de caractères.