Similarité de texte : sept mesures côte à côte

Qu'est-ce que la similarité de texte ?

La similarité de texte est un nombre disant à quel point deux chaînes se ressemblent, généralement mis à l'échelle pour que 1 signifie identique et 0 rien en commun. C'est ce qui se trouve sous la recherche approximative, le dédoublonnage d'une liste de clients, la détection d'une coquille dans une référence produit, et la mise en correspondance d'un nom saisi par une personne avec un nom stocké en base.

L'ennui, c'est qu'il n'existe pas de définition unique. Levenshtein compte combien de modifications d'un caractère séparent les deux. Jaro compte les caractères concordants et à quel point ils sont dans le désordre. Dice et Jaccard ignorent complètement la position et comparent des ensembles de paires de lettres voisines. La plus longue sous-séquence commune demande quelle part d'une chaîne survit dans l'autre, dans l'ordre. Ce sont des questions différentes, et elles donnent des réponses différentes.

Cette page en calcule sept d'un coup au lieu d'en choisir une à votre place, car choisir est la vraie décision et elle se prend presque toujours par accident.

Comment l'utiliser

1. Mettez deux chaînes dans les champs du haut : toutes les mesures notent la paire aussitôt, avec le nombre brut d'éditions affiché à côté des deux qui reposent sur une distance.
2. Puis essayez le panneau de classement : donnez-lui quelque chose à chercher et une liste de candidates, une par ligne. Chaque mesure classe la liste de son côté et annonce sa gagnante.
3. Regardez les gagnantes diverger : la ligne sous ce tableau compte combien de réponses distinctes sont sorties d'une seule liste. Quand elle indique plus d'une, la mesure que vous auriez choisie faisait un vrai travail.

L'ampleur du désaccord, mesurée

Ce n'est pas une inquiétude théorique. En prenant le code source de ce site comme corpus et en tirant au hasard des triplets d'identifiants en camelCase, Levenshtein et Jaro-Winkler placent les deux mêmes candidates dans un ordre différent 27,7 % du temps sur 3 479 paires. Face à la mesure Ratcliff/Obershelp qu'emploie le difflib de Python, Levenshtein diverge sur 25,5 %.

L'effet est pire dans le cas que l'on construit réellement : choisir la correspondance la plus proche dans une liste. En choisissant parmi 400 candidates, Levenshtein et Jaro-Winkler ont désigné une gagnante différente pour 62 % des requêtes. Ce chiffre dépend de la taille du vivier : retenez donc les 27,7 % comme le titre honnête, et celui-ci comme une démonstration du sens dans lequel cela bouge.

L'exemple chargé par défaut est le cas classique. Cherchez la faute recieve parmi receive, relieve, reprieve, retrieve et recipe. Levenshtein seul préfère relieve, à une substitution de distance, alors que receive est à deux éditions : les lettres ont été interverties et Levenshtein n'a aucune notion d'interversion. Damerau-Levenshtein, qui compte l'échange de deux caractères voisins comme une seule édition, note receive et relieve à égalité à 0,857 et retient la première des deux. Jaro-Winkler place receive strictement en tête à 0,967. Trois comportements pour une même liste, et un seul vous rend le mot que vous vouliez.

Laquelle utiliser ?

Pour les fautes de frappe humaines, Damerau-Levenshtein est en général un meilleur choix par défaut que Levenshtein seul, car intervertir deux lettres est l'une des erreurs les plus fréquentes et Levenshtein la facture double. Pour les noms, Jaro-Winkler a été conçu précisément pour cet usage au bureau du recensement américain, et son bonus de préfixe traduit le fait qu'on écrit bien plus souvent correctement le début d'un nom que sa fin.

Pour des textes plus longs où des mots entiers se déplacent, les mesures ensemblistes s'en tirent mieux. Dice et Jaccard comparent des sacs de paires de lettres voisines : l'ordre leur importe donc beaucoup moins, et elles classent de façon identique — Jaccard donne simplement toujours une note plus basse pour la même paire, ce qui surprend qui compare des seuils recopiés de sources différentes.

La seule généralisation honnête est qu'un seuil n'est pas transférable. Une coupure à 0,8 ne veut pas dire la même chose avec Jaccard qu'avec Jaro-Winkler, et pour la paire MARTHA et MARHTA chargée plus haut les notes vont de 0,250 à 0,961 selon la mesure interrogée. Tout seuil hérité d'un billet de blog est attaché à une mesure, et la mesure n'est presque jamais précisée.

Ce que cette page ne peut pas vous dire

Aucune de ces mesures ne comprend le sens. Chat et félin obtiennent presque zéro ; colour et color obtiennent une note élevée. S'il faut savoir que deux phrases disent la même chose avec d'autres mots, la similarité entre chaînes est le mauvais outil et aucun seuil ne la sauvera.

Elles reposent aussi sur les caractères, et caractère signifie ici point de code, pas ce que vous appelleriez une lettre. Cela corrige le bug courant où un emoji compte pour deux caractères et où deux emojis différents ressortent à deux éditions, mais cela s'arrête avant les groupes de graphèmes : un drapeau ou un emoji avec teinte de peau reste plusieurs points de code, et les définitions classiques de ces mesures n'abordent pas la question.

Enfin, le panneau de classement départage les ex aequo par ordre de saisie. Quand deux candidates obtiennent la même note, celle qui est la plus haut dans votre liste l'emporte, ce qui est une propriété de cet outil et non de la mesure. Les notes sont affichées pour que vous puissiez voir quand cela s'est produit.

Pourquoi est-ce gratuit ?

Les sept mesures tiennent en quelques dizaines de lignes d'arithmétique qui s'exécutent dans votre navigateur. Rien de ce que vous tapez n'est envoyé, rien n'est journalisé, et il n'y a aucun compte à créer.

Sans inscription, sans limite, et sans filigrane sur ce que vous copiez.