Calcul de la matrice des distances Python Levenshtein
Comparez plusieurs chaînes, calculez automatiquement leur matrice de distances d’édition, affichez un score normalisé et visualisez les écarts dans un graphique interactif.
Calculateur interactif
Visualisation
Le graphique montre la distance entre la chaîne de référence et toutes les autres chaînes. Plus la barre est haute, plus les chaînes sont éloignées.
Guide expert du calcul de la matrice des distances Python Levenshtein
Le calcul de la matrice des distances Python Levenshtein est un sujet central dès que l’on travaille sur la comparaison de textes, la correction orthographique, la déduplication de données, le rapprochement d’identités, la bio-informatique légère ou encore le nettoyage d’adresses et de catalogues produits. En pratique, la distance de Levenshtein mesure le nombre minimal d’opérations nécessaires pour transformer une chaîne en une autre. Les trois opérations classiques sont l’insertion, la suppression et la substitution d’un caractère.
Quand on parle de matrice des distances, on ne se limite plus à comparer deux mots isolés. On compare un ensemble complet de chaînes entre elles. Le résultat est un tableau carré où chaque cellule contient la distance entre l’élément de la ligne et l’élément de la colonne. Cette structure est très utile pour repérer des groupes similaires, choisir un seuil de rapprochement, alimenter un clustering, ou produire un contrôle qualité automatisé dans un pipeline Python.
Pourquoi la distance de Levenshtein est si utilisée
Son succès vient de son équilibre entre simplicité, interprétabilité et efficacité. Une distance de 0 signifie une égalité parfaite. Une distance de 1 signifie qu’une seule opération suffit pour passer d’une chaîne à l’autre. Plus la valeur augmente, plus les chaînes divergent. Contrairement à un simple test d’égalité, cette approche capture les fautes de frappe, les abréviations partielles ou les variantes orthographiques.
- Détection de doublons dans un CRM ou une base e-commerce.
- Correction de saisie utilisateur dans un moteur de recherche interne.
- Rapprochement de noms de communes, rues, personnes ou références produit.
- Prétraitement NLP pour comparer des tokens ou des labels courts.
- Audit de qualité de données dans un ETL Python.
Principe mathématique et programmation dynamique
La distance de Levenshtein se calcule généralement par programmation dynamique. Pour deux chaînes de longueur m et n, on construit une matrice interne de taille (m + 1) x (n + 1). La première ligne et la première colonne représentent le coût des insertions ou suppressions cumulées. Ensuite, chaque cellule est calculée à partir de ses voisins immédiats selon la règle suivante :
- Coût d’insertion = cellule de gauche + 1
- Coût de suppression = cellule du dessus + 1
- Coût de substitution = diagonale + 0 si les caractères sont égaux, sinon + 1
- La cellule prend le minimum de ces trois coûts
Cette logique fournit une solution exacte. En Python, elle peut être implémentée à la main avec des listes imbriquées, ou déléguée à des bibliothèques spécialisées comme python-Levenshtein, rapidfuzz ou certaines fonctions de textdistance. Si vous devez calculer une matrice pour des milliers de chaînes, la performance de l’implémentation devient un facteur décisif.
Exemple simple de matrice des distances
Supposons que vous compariez les chaînes chat, chats, char et rat. La matrice sera symétrique, car la distance entre A et B est la même qu’entre B et A. La diagonale sera toujours à 0, puisque la distance d’une chaîne à elle-même est nulle. C’est exactement le type de sortie produit par le calculateur ci-dessus.
| Méthode | Principe | Complexité temporelle typique | Cas d’usage idéal |
|---|---|---|---|
| Levenshtein | Insertions, suppressions, substitutions | O(m × n) | Fautes de frappe et variantes orthographiques |
| Hamming | Comparaison position par position | O(n) | Chaînes de même longueur uniquement |
| Jaro-Winkler | Proximité orientée noms courts | Souvent proche de O(m + n) | Noms de personnes, déduplication légère |
| Cosine sur n-grammes | Vecteurs de sous-chaînes | Variable selon l’indexation | Recherche approximative à grande échelle |
Comment construire une matrice des distances en Python
En Python, le flux de travail standard se découpe en plusieurs étapes claires. D’abord, vous constituez votre liste de chaînes. Ensuite, vous appliquez un prétraitement cohérent. Puis, vous calculez la distance pour chaque paire. Enfin, vous stockez le tout dans une structure tabulaire, typiquement une liste de listes, un tableau NumPy ou un DataFrame pandas.
Étape 1 : préparer les chaînes
Le prétraitement a un impact direct sur la qualité des résultats. Vous devez décider si vous :
- convertissez tout en minuscules ;
- supprimez les espaces en début et fin ;
- retirez ponctuation ou accents ;
- conservez ou non les doublons exacts.
Si vous comparez des noms propres, ignorer la casse est souvent pertinent. Si vous analysez des identifiants techniques, la casse peut au contraire être significative. Dans une base d’adresses, la normalisation des abréviations comme av, avenue, bd, boulevard peut aussi améliorer le rapprochement.
Étape 2 : calculer toutes les paires
Pour une liste de n chaînes, une matrice complète contient n × n cellules. Comme la matrice est symétrique, le nombre de comparaisons réellement distinctes est n × (n – 1) / 2. Voici quelques chiffres utiles :
| Nombre de chaînes | Cellules dans la matrice | Comparaisons distinctes | Lecture pratique |
|---|---|---|---|
| 10 | 100 | 45 | Très léger, exécutable instantanément |
| 100 | 10 000 | 4 950 | Supportable sur poste standard |
| 1 000 | 1 000 000 | 499 500 | Nécessite optimisation et filtrage |
| 10 000 | 100 000 000 | 49 995 000 | Trop lourd sans indexation avancée |
Ces statistiques montrent pourquoi le calcul naïf d’une matrice complète peut vite devenir coûteux. La croissance est quadratique sur le nombre de chaînes, et chaque comparaison Levenshtein est elle-même quadratique sur la longueur des chaînes. Autrement dit, il faut optimiser tôt dès qu’on passe à l’échelle.
Étape 3 : stocker les résultats
Pour l’exploration, un DataFrame pandas est souvent la meilleure option. Il permet d’afficher les lignes et colonnes avec les étiquettes de chaînes originales, d’exporter vers CSV, de filtrer par seuil, ou d’alimenter un clustering hiérarchique. Pour un moteur applicatif, une simple liste de listes peut suffire.
Distance brute ou distance normalisée
Une distance brute dépend de la longueur des chaînes. Une distance de 2 n’a pas le même sens entre des mots de 4 caractères et des chaînes de 40 caractères. C’est pourquoi on utilise souvent un score normalisé :
- distance normalisée = distance / longueur maximale
- résultat compris entre 0 et 1
- 0 = identité parfaite, 1 = divergence maximale dans ce cadre de normalisation
Par exemple, la distance entre chat et chats vaut 1. La longueur maximale vaut 5. La distance normalisée vaut donc 0,20. Ce score est bien plus simple à comparer d’une paire à l’autre. Dans le calculateur, vous pouvez basculer entre la version brute et la version normalisée selon votre besoin d’analyse.
Exemple de logique Python pour Levenshtein
Une implémentation Python pure suit presque toujours le même schéma : initialisation de la première ligne, boucle sur les caractères de la première chaîne, boucle imbriquée sur la seconde, puis calcul du minimum entre insertion, suppression et substitution. Cette méthode est fiable et pédagogique. Pour la production, l’usage d’une bibliothèque C-optimisée ou Rust-optimisée permet souvent un gain de vitesse important.
Conseil pratique : si votre objectif est le rapprochement à grande échelle, commencez par un filtrage simple avant Levenshtein : première lettre identique, longueurs proches, même code postal, même catégorie, même préfixe, ou blocage phonétique. Vous réduirez drastiquement le nombre de comparaisons inutiles.
Bonnes pratiques de performance
- Éviter de comparer des chaînes dont les longueurs diffèrent trop si votre seuil cible est faible.
- Exploiter la symétrie de la matrice pour ne calculer qu’un triangle.
- Mettre en cache les résultats si les mêmes paires reviennent souvent.
- Utiliser des bibliothèques natives pour les gros volumes.
- Normaliser les données avant calcul pour réduire le bruit.
Quand utiliser Python-Levenshtein, RapidFuzz ou une implémentation maison
python-Levenshtein est historiquement très populaire et rapide. RapidFuzz est extrêmement apprécié pour sa performance, sa compatibilité moderne et ses fonctions de scoring avancées. Une implémentation maison reste intéressante pour apprendre, pour déboguer ou pour intégrer des coûts personnalisés.
Choisir la bonne approche
- Apprentissage ou audit : implémentation Python pure.
- Projet analytique moyen : pandas + bibliothèque optimisée.
- Production volumineuse : préfiltrage, indexation, RapidFuzz et parallélisation.
Interpréter correctement la matrice
Une matrice des distances n’est pas seulement un tableau de nombres. Elle permet d’identifier rapidement des clusters de chaînes proches. Si plusieurs valeurs faibles se concentrent dans un sous-ensemble, il y a probablement une famille de doublons ou de variantes. À l’inverse, des valeurs uniformément élevées montrent que l’ensemble est très hétérogène. En visualisation, une heatmap ou un clustering hiérarchique peut rendre ces structures immédiatement visibles.
Dans un usage métier, vous pouvez définir des seuils tels que :
- 0 à 0,10 normalisé : quasi-identité ;
- 0,10 à 0,25 : forte similarité ;
- 0,25 à 0,40 : similarité possible selon le contexte ;
- au-delà de 0,40 : rapprochement faible, souvent à rejeter.
Ces seuils ne sont pas universels. Ils varient selon la longueur moyenne des chaînes, le domaine métier et le niveau de tolérance aux faux positifs. Un nom de famille, un titre de produit et une adresse postale n’ont pas la même dynamique de variation.
Limites de la distance de Levenshtein
Levenshtein reste une métrique de surface. Elle ne comprend ni le sens, ni la phonétique, ni les synonymes, ni la structure métier. Deux chaînes peuvent être sémantiquement proches mais textuellement éloignées. Inversement, deux chaînes peuvent être textuellement proches tout en désignant des entités différentes. Par exemple, une faute sur un numéro d’appartement peut avoir peu d’effet sur la distance mais un fort impact métier.
Cas où il faut aller plus loin
- Comparer des phrases longues ou du texte libre.
- Gérer des inversions fréquentes de mots.
- Prendre en compte la phonétique ou les translittérations.
- Réconcilier des données avec un fort bruit structurel.
Dans ces cas, il peut être utile de combiner Levenshtein avec des n-grammes, des métadonnées métier, des règles de normalisation, ou des représentations vectorielles plus modernes.
Sources académiques et institutionnelles utiles
Pour approfondir la théorie et les applications du rapprochement approximatif de chaînes, vous pouvez consulter ces ressources de référence :
- Stanford University – Edit distance in information retrieval
- NIST (.gov) – ressources institutionnelles sur la qualité des données et la normalisation
- Carnegie Mellon University – ressources académiques en algorithmique et NLP
Conclusion
Le calcul de la matrice des distances Python Levenshtein est un outil de base, mais extraordinairement puissant, pour analyser la similarité textuelle. Sa force réside dans sa lisibilité, son efficacité raisonnable et sa facilité d’intégration dans un pipeline Python. Pour des petits jeux de données, une implémentation simple suffit largement. Pour des volumes plus ambitieux, l’enjeu devient moins le calcul pur que la stratégie globale : normalisation, blocage, réduction du nombre de paires, puis visualisation et validation métier. Si vous maîtrisez ces briques, vous pourrez construire des systèmes de matching robustes, auditables et réellement utiles en production.