Aller au contenu
English

La similarité de chaînes

  • Leçon 12
  • 40 min
  • Module 4 : Comparer les enregistrements : les mesures de similarité

Où nous en sommes

Le blocage nous a donné un petit ensemble de paires candidates. Nous devons maintenant mesurer à quel point deux valeurs se ressemblent. Dans cette leçon, nous comparons Levenshtein, Jaro–Winkler et le ratio d'ensembles de mots sur les mêmes noms, adresses et titres de produits.

Lue depuis YouTube. Rien ne se charge depuis YouTube avant que vous appuyiez sur lecture. Confidentialité

Ce que vous saurez faire

Mesurez à quel point deux valeurs se ressemblent, avec un nombre de 0 à 1. Calculez trois mesures courantes à la main sur de petits exemples, puis avec la bibliothèque rapidfuzz. Voyez quelle mesure convient aux noms, adresses et titres de produits, et où les trois échouent.

Carnet JupyterComparer les trois mesures dans un carnet JupyterColab · Kaggle · GitHub · en anglais

Le carnet (notebook) Jupyter calcule la distance de Levenshtein à la main et attribue des scores aux mêmes paires avec trois mesures. Ensuite, il utilise les paires étiquetées de TermeLarkfieldUne boutique en ligne canadienne inventée, qui vend des articles pour la maison et le jardin. Ce n’est pas une vraie entreprise. Tous les cours Nextia utilisent son service d’assistance et ses données comme exemple.En savoir plus Découvrez Larkfield pour choisir une mesure et un seuil. Ses cellules de préparation téléchargent les données. Aucune préparation locale n’est donc nécessaire.

Le carnet est en anglais. Colab et Kaggle ouvrent votre propre copie. Il faut un compte Google ou Kaggle gratuit. Vous êtes bloqué ? Consultez le carnet de solution.

Avant de commencerCe qu’il faut savoir et avoir sous la mainEnviron 40 minutes

Ce que vous devez savoir

Ce qu’il vous faut sur votre ordinateur

  • Le projet larkfield-match avec les commandes du module 3. Ou utilisez seulement le carnet Jupyter.

Testé sur macOS avec Python 3.12.13. Les commandes Windows (PowerShell) ne sont pas testées.

Une bibliothécaire trouve deux fiches dans le catalogue. L’une indique « Katherine Smyth ». L’autre indique « Kathy Smith ». S’agit-il de la même lectrice?

Elle ne demande pas « ces deux noms sont-ils exactement égaux? ». La réponse est non, et cela ne l’aide pas. Elle demande « à quel point se ressemblent-ils? ». « Smyth » et « Smith » diffèrent d’une lettre. « Kathy » est une forme courte de « Katherine ». Les deux fiches se ressemblent donc, et elle regarde ensuite l’adresse.

Un apparieur doit poser la même question. Il lui faut un nombre qui indique à quel point deux valeurs se ressemblent.

Les règles de Appariement exact et par règles comparent les valeurs nettoyées pour vérifier leur égalité. Après normalisation, « Thériault » et « THERIAULT » sont égaux. Mais une faute de frappe brise encore l’égalité :

Valeur A Valeur B Égales?
tremblay trembaly non
tremblay gagnon non

La règle donne la même réponse aux deux paires. Pourtant, la première diffère par deux lettres inversées, et la seconde contient deux noms différents. L’égalité efface la différence entre « presque identiques » et « aucune ressemblance ».

C’est courant dans nos enregistrements synthétiques. Le modèle d’erreurs insère une faute de frappe dans 4,5 % des noms de famille et 3,5 % des prénoms. Il insère un surnom dans 10 % des prénoms. (Ces taux sont nos hypothèses, inscrites dans la fiche du jeu de données.) Chacun de ces cas fait manquer une vraie paire à une règle exacte.

Une similarité de chaînes est un nombre qui indique à quel point deux textes se ressemblent. Une chaîne est un texte quelconque : un nom, une adresse ou un titre de produit. Dans ce cours, chaque similarité se situe entre 0 et 1 :

  • 1 signifie que les deux valeurs sont identiques.
  • 0 signifie qu’elles n’ont rien en commun.
  • Une valeur entre les deux signifie « en partie semblables ».

Il existe plusieurs façons de la calculer. Cette leçon utilise trois mesures courantes : Levenshtein, Jaro–Winkler et le ratio d’ensembles de mots (token set ratio). Chaque mesure examine le texte à sa façon. Chacune convient donc à des erreurs différentes.

La distance de Levenshtein est le plus petit nombre de changements d’une lettre pour transformer une valeur en l’autre. Un changement correspond à l’une de ces trois actions :

  • insérer une lettre,
  • supprimer une lettre, ou
  • remplacer une lettre par une autre.

« smith » → « smyth » demande un changement : remplacer « i » par « y ». La distance est donc de 1.

Prenons deux noms de famille français : « gagne » et « gagnon ». Les quatre premières lettres sont identiques. Ensuite, nous remplaçons « e » par « o », puis insérons « n ». Cela fait 2 changements.

L’ordinateur trouve le plus petit nombre à l’aide d’un tableau. Chaque cellule contient le minimum de changements pour les premières lettres de chaque valeur. Chaque cellule prend la plus petite valeur de trois cellules voisines, plus le coût d’un changement.

Le tableau de Levenshtein pour gagne (lignes) et gagnon (colonnes). La première ligne compte de 0 à 6, et la première colonne, de 0 à 5. La cellule en bas à droite vaut 2. Les cellules épaisses montrent le chemin le moins coûteux : quatre lettres identiques coûtent 0, puis viennent un remplacement et une insertion. La distance est de 2. La similarité est 1 moins 2 divisé par 6, soit 0,667.
Le tableau de Levenshtein pour « gagne » et « gagnon ». La cellule en bas à droite donne la distance : 2 changements. Les cellules épaisses forment le chemin le moins coûteux.
Description textuelle du diagramme

Un tableau avec les lettres de « gagne » sur le côté et celles de « gagnon » en haut. La première ligne compte de 0 à 6, et la première colonne, de 0 à 5. C’est le coût pour construire une valeur à partir de rien. Chaque autre cellule contient la plus petite de trois valeurs. Ce sont la cellule du dessus plus 1, celle de gauche plus 1, et celle en haut à gauche plus 0 ou 1. La cellule en bas à droite vaut 2. Le chemin le moins coûteux suit la diagonale pour « g a g n » sans coût. Il remplace « e » par « o » (1), puis insère « n » (1).

Une distance n’est pas encore une similarité. Deux valeurs longues avec 2 changements se ressemblent davantage que deux valeurs courtes avec 2 changements. Nous divisons donc par la longueur de la valeur la plus longue :

Similarité de Levenshtein = 1 − distance / longueur de la valeur la plus longue

Pour « gagne » et « gagnon » : 1 − 2 / 6 = 0,667.

Levenshtein est facile à expliquer et traite chaque lettre de la même façon. C’est aussi sa faiblesse. Des lettres inversées coûtent 2 changements. « tremblay » et « trembaly » obtiennent donc seulement 0,750.

Un changement dans l’ordre des mots coûte presque tout. « robert smith » et « smith robert » obtiennent 0,000.

Jaro–Winkler : des lettres presque au même endroit

Section intitulée « Jaro–Winkler : des lettres presque au même endroit »

Jaro–Winkler a été conçu pour les noms courts, comme ceux d’un formulaire de recensement. Il pose une autre question : combien de lettres les deux valeurs partagent-elles, presque au même endroit?

Il comporte deux parties :

  1. Jaro compte les lettres communes aux deux valeurs, près de la même position. Il compte aussi les transpositions : des lettres communes qui apparaissent dans un ordre différent. Deux lettres qui échangent leur place comptent comme une transposition.
  2. Winkler ajoute un bonus pour un début identique. Les gens font moins d’erreurs au début d’un nom. Le bonus augmente avec le nombre de premières lettres identiques, jusqu’à 4.

Le ratio d’ensembles de mots découpe d’abord chaque valeur en mots. Un mot (token) est une unité de ce découpage. La mesure compare ensuite les deux ensembles de mots. L’ordre des mots n’a donc pas d’importance. Elle donne aussi un score élevé quand une valeur contient tous les mots de l’autre, plus quelques mots supplémentaires.

Le diagramme montre les deux mesures sur de petits exemples, avec tous les nombres.

À gauche : Jaro-Winkler pour tremblay et trembaly. Les 8 lettres sur 8 sont communes, presque au même endroit. 2 lettres communes sont dans un ordre différent, l-a et a-l, ce qui fait 1 transposition. Jaro = (8/8 + 8/8 + (8 - 1)/8) / 3 = 0,958. Le début identique, trem, donne un bonus pour 4 lettres (au plus 4) : 4 × 0,1 × (1 - 0,958). Jaro-Winkler = 0,975. À droite : ratio d'ensembles de mots. robert smith et smith robert partagent les mots robert et smith, sans autres mots : 1,000. marie claude tremblay et marie tremblay partagent marie et tremblay, et claude est seulement dans la première valeur : 1,000.
Jaro–Winkler tolère les lettres inversées presque au même endroit. Le ratio d'ensembles de mots ignore l'ordre des mots et les mots supplémentaires.
Description textuelle du diagramme

Jaro–Winkler pour « tremblay » et « trembaly » : les 8 lettres sont communes, presque au même endroit. « l » et « a » apparaissent dans un ordre différent, ce qui fait 1 transposition. Jaro vaut (8/8 + 8/8 + 7/8) / 3 = 0,958. Les deux valeurs commencent par les mêmes 4 lettres. Winkler ajoute donc 4 × 0,1 × (1 − 0,958). Le résultat est de 0,975. Le ratio d’ensembles de mots pour « robert smith » et « smith robert » vaut 1,000, car ils contiennent les deux mêmes mots. Pour « marie claude tremblay » et « marie tremblay », chaque mot de la seconde valeur est dans la première. Le score vaut donc aussi 1,000.

Regardez le dernier exemple. « Marie-Claude Tremblay » et « Marie Tremblay » obtiennent 1,000. Il peut s’agir d’une personne qui omet parfois son deuxième prénom. Il peut aussi s’agir d’une fille et de sa mère à la même adresse. Le ratio d’ensembles de mots ne peut pas les distinguer. Un score de 1 ne signifie pas « la même personne ».

Nous attribuons maintenant des scores aux mêmes paires avec les trois mesures. Le script de mesure du projet a traité ces paires : six noms, quatre adresses et trois titres de produits. Les titres de produits sont de vraies lignes des deux flux fournisseurs de Larkfield. Les noms et adresses sont d’abord normalisés : minuscules, sans accents et sans ponctuation. La dernière colonne indique ce que dirait une personne qui connaît les clients et les produits.

Un tableau de 13 paires, chacune évaluée par Levenshtein, Jaro-Winkler et le ratio d'ensembles de mots. Noms : Katherine / Kathy 0,444, 0,849, 0,571 (même personne, surnom). Thériault / Theriault 1, 1, 1. Jean-François / Jean Francois 1, 1, 1. Smith / Smyth 0,800, 0,893, 0,800 (peut-être). Robert Smith / Smith Robert 0,000, 0,472, 1,000 (même personne). Marie-Claude Tremblay / Marie Tremblay 0,667, 0,890, 1,000 (peut-être, ou sa mère). Adresses : 12 rue des Érables / 12 r. des Erables 0,889, 0,915, 0,941. 2202 Kestrel Boulevard / 2202 Kestrel Blvd 0,773, 0,955, 0,872. 3 Elder Way Apt 4 / 4-3 Elder Way 0,529, 0,710, 1,000 (même lieu). 44 Juniper Dr / 21 Alder Cres 0,154, 0,510, 0,261 (différents). Titres de produits : le boyau en pieds et en mètres 0,154, 0,642, 0,800 (même produit). Le boyau et son paquet de 2 : 0,765, 0,953, 1,000 (différents). Le pot de fleurs de 12 po et de 16 po : 0,974, 0,990, 0,974 (différents).
Treize paires du script de mesure, évaluées par chaque mesure. Bleu foncé : 0,9 ou plus. Aucune mesure n'a raison pour toutes les paires.
Description textuelle du diagramme

Treize paires en trois groupes, avec un score de chaque mesure et ce qu’une personne dirait. Pour les noms, Jaro–Winkler donne les scores les plus élevés aux petites différences d’orthographe. Le ratio d’ensembles de mots est le seul à ignorer l’ordre des mots. Pour les adresses, le ratio d’ensembles de mots gère le numéro d’appartement écrit à un autre endroit. Pour les titres de produits, toutes les mesures se trompent. Les pots de fleurs de 12 pouces et de 16 pouces obtiennent de 0,97 à 0,99. Le paquet de 2 obtient 1,000 avec le ratio d’ensembles de mots. Mais ce sont des produits différents. Le même boyau décrit en pieds et en mètres obtient des scores faibles.

Que nous apprend le tableau?

  • Aucune mesure ne connaît le sens. « Katherine » et « Kathy » obtiennent de 0,444 à 0,849. Seule une liste de surnoms saurait que « Kathy » est une forme courte de « Katherine ».
  • L’ordre des mots fait échouer Levenshtein. « Robert Smith » et « Smith Robert » obtiennent 0,000. Le ratio d’ensembles de mots donne 1,000.
  • Jaro–Winkler tolère les petites fautes d’orthographe dans les valeurs courtes : « smith » / « smyth » obtient 0,893, le plus élevé des trois scores.
  • Les titres trompent toutes les mesures. Les pots de fleurs diffèrent d’un caractère : « 12 » contre « 16 ». Ils obtiennent 0,97 ou plus avec chaque mesure, mais ce sont des produits différents. Un paquet de 2 contient chaque mot de l’article vendu seul. Le ratio d’ensembles de mots lui donne donc 1,000. Pendant ce temps, le même boyau décrit en pieds et en mètres obtient 0,154 avec Levenshtein.

Les nombres et les unités ont donc besoin de leurs propres champs. Vous ne pouvez pas les confier à une mesure de similarité de chaînes. Nous y revenons dans Comparer champ par champ, puis combiner, et les flux de produits de Hana y reviennent au module 6.

Les petits exemples peuvent induire en erreur. Nous avons donc évalué les noms complets de chaque paire candidate du jeu de test. Ce sont les paires produites par les cinq clés de blocage. Pour chaque mesure, le graphique montre la proportion des paires qui obtiennent 0,9 ou plus. Les points bleus sont de vraies paires (un client); les points orange représentent deux personnes différentes.

  • Même personne (vraies paires)
  • Deux personnes (autres paires candidates)
Noms complets des 5 531 vraies paires et des 386 135 autres paires candidates du jeu de test (cinq clés de blocage), dans nos enregistrements synthétiques. Une bonne mesure place le point bleu loin à droite et le point orange loin à gauche.
Description textuelle du graphique

Un graphique à points avec six lignes, deux par mesure. Levenshtein : 0,829 des vraies paires et 0,470 des paires de deux personnes obtiennent 0,9 ou plus. Jaro–Winkler : 0,879 et 0,613. Ratio d’ensembles de mots : 0,890 et 0,541.

Le résultat donne à réfléchir. Chaque mesure donne 0,9 ou plus à la plupart des vraies paires. Mais elle donne aussi 0,9 ou plus à environ la moitié des paires de deux personnes différentes. Cela représente 47 % avec Levenshtein, 54 % avec le ratio d’ensembles de mots et 61 % avec Jaro–Winkler.

Pourquoi autant? Le blocage a choisi ces paires parce que leurs noms ou leurs adresses se ressemblent. La clé de nom de famille rassemble les personnes dont le nom commence par les mêmes lettres. Les membres d’un ménage partagent aussi un nom de famille. Un score de nom élevé est donc courant parmi les paires candidates, même pour deux personnes. Jaro–Winkler, la mesure la plus tolérante, en laisse passer le plus.

Ajoutez le code de similarité de ce module à votre projet.

  1. Dans votre dossier de projet, avec l’TermeEnvironnement virtuelUn dossier avec son propre Python et ses propres paquets, pour un seul projet. Les paquets installés là ne changent pas les autres projets.En savoir plus Isoler les dépendancesPython pour l'ingénierie de l'IA en pratique actif, copiez les fichiers de similarité de l’instantané end-of-m04. Copiez aussi son requirements.txt :

    Fenêtre de terminal
    S=../nextia-learning-labs/C39/snapshots/end-of-m04
    cp $S/larkfield_match/similarity.py larkfield_match/
    cp $S/larkfield_match/commands/similar.py larkfield_match/commands/
    cp $S/requirements.txt .

    Le nouveau requirements.txt ajoute deux paquets : rapidfuzz pour les mesures de similarité de chaînes, et jellyfish pour les codes phonétiques de la prochaine leçon.

  2. Installez les nouveaux paquets :

    Fenêtre de terminal
    python -m pip install -r requirements.txt

    La dernière ligne les nomme :

    Successfully installed jellyfish-1.3.0 rapidfuzz-3.14.6
  3. Exécutez les tests. Il y en a toujours 21 : les tests de ce module arrivent à la leçon 3.

    Fenêtre de terminal
    python -m pytest -q
    ..................... [100%]
    21 passed in 54.91s

    Notre portable était occupé pendant cette exécution. Votre durée sera différente.

La nouvelle commande match similar évalue deux valeurs avec les trois mesures. Elle les normalise d’abord, comme le fait l’apparieur :

Fenêtre de terminal
match similar "Katherine" "Kathy"
'katherine' / 'kathy'
levenshtein distance 5
levenshtein 0.444
jaro_winkler 0.849
token_set_ratio 0.571
soundex K365 / K300 different
metaphone K0RN / K0 different

Les deux dernières lignes sont des codes phonétiques : la prochaine leçon les explique. Essayez maintenant une inversion de mots et une valeur avec des accents :

Fenêtre de terminal
match similar "Robert Smith" "Smith Robert"
match similar "Thériault" "Theriault"
match similar --raw "Thériault" "Theriault"
'robert smith' / 'smith robert'
levenshtein distance 12
levenshtein 0.000
jaro_winkler 0.472
token_set_ratio 1.000
...
'theriault' / 'theriault'
levenshtein distance 0
levenshtein 1.000
...
'Thériault' / 'Theriault'
levenshtein distance 1
levenshtein 0.889
jaro_winkler 0.941
token_set_ratio 0.889
...

Avec --raw, la commande ne normalise pas. « é » et « e » sont alors deux lettres différentes. Normalisez d’abord, puis mesurez : une mesure ne peut pas corriger ce que la normalisation devrait corriger.

Ouvrez larkfield_match/similarity.py. Le calcul de la distance de Levenshtein est écrit au complet pour que vous puissiez le suivre. Il conserve une seule ligne du tableau à la fois :

def levenshtein_distance(a, b):
prev = list(range(len(b) + 1))
for i, ca in enumerate(a, 1):
cur = [i]
for j, cb in enumerate(b, 1):
cur.append(min(prev[j] + 1, cur[j - 1] + 1, prev[j - 1] + (ca != cb)))
prev = cur
return prev[-1]

Les trois mesures utilisées par l’apparieur viennent de rapidfuzz, une bibliothèque rapide écrite en C++ :

def levenshtein(a, b):
return Levenshtein.normalized_similarity(a, b)
def jaro_winkler(a, b):
return JaroWinkler.similarity(a, b)
def token_set_ratio(a, b):
return fuzz.token_set_ratio(a, b) / 100

rapidfuzz donne le ratio d’ensembles de mots de 0 à 100. Le projet le divise donc par 100. La vitesse compte ici : dans Pourquoi comparer toutes les paires est impossible, match allpairs comparait les noms en Python pur à environ 2 microsecondes par paire. Le Jaro–Winkler de rapidfuzz prend environ 0,34 microseconde par paire.

Champ Bonne mesure Pourquoi Attention
Prénom, nom de famille Jaro–Winkler valeurs courtes; fautes de frappe et lettres inversées près du même endroit surnoms (« Kathy »); un nom court qui commence comme un nom plus long
Nom complet ratio d’ensembles de mots (token set ratio) l’ordre des mots change entre les sources (« SURNAME, FIRST ») un nom supplémentaire donne 1,000 : un parent et son enfant peuvent sembler identiques
Adresse municipale ratio d’ensembles de mots les numéros d’appartement et les autres nombres changent de place (« Apt 4 », « 4-3 ») un autre numéro de maison dans la même rue obtient quand même un score élevé
Courriel, téléphone, code postal égalité après normalisation un seul chiffre erroné donne un autre numéro de téléphone utilisez une similarité seulement pour la partie du courriel avant le @
Titre du produit ratio d’ensembles de mots comme un signal parmi d’autres beaucoup de mots dans n’importe quel ordre les tailles, les unités et les formats doivent avoir leurs propres champs

Ce sont des points de départ, pas des lois. Dans Comparer champ par champ, puis combiner, nous mesurons chaque champ sur les paires candidates.

Combien cela coûte-t-il? Très peu. Une mesure de similarité de chaînes dans rapidfuzz prend bien moins d’une microseconde par paire. Le blocage a déjà réduit les paires à environ un million. Le vrai coût vient des choix : quelle mesure, sur quel champ, avec quel seuil.

Erreur courante

L'appariement approximatif des noms suffit

Symptôme : TermeTomásL’ingénieur en IA de Larkfield. Il propose souvent un raccourci rapide, et la leçon montre pourquoi il échoue. dit : « Les noms, c’est ce que les gens tapent mal. Une bonne mesure approximative sur le nom complet, c’est tout ce qu’il nous faut. » Il déclare deux enregistrements « identiques » quand le ratio d’ensembles de mots des noms complets est élevé. Les résultats sur les paires étiquetées semblent bons. Dans le carnet (notebook) Jupyter de cette leçon, la meilleure règle de ce type exige un ratio d’au moins 0,86. Elle concorde avec 0,939 des 3 000 paires étiquetées de Larkfield.

Cause : les paires étiquetées ne sont pas les paires candidates. Sur les vraies paires candidates du jeu de test, la même règle déclare 239 633 paires « identiques ». Seulement 5 064 de ces décisions sont correctes. La précision est de 0,021, et le rappel est de 0,910. Les membres d’une famille partagent un nom de famille et une adresse. Le blocage en réunit donc beaucoup. Et une personne peut apparaître avec deux prénoms, un surnom ou un nom de mariage.

Solution : ne décidez jamais à partir d’un seul champ. La similarité d’un nom est un élément de preuve parmi d’autres. Comparez aussi le courriel, le téléphone, l’adresse et la date de naissance. Combinez-les, comme dans Comparer champ par champ, puis combiner. Ensuite, mesurez les résultats sur les paires candidates, pas seulement sur un échantillon étiqueté.

Conséquence pour le travail en IA : un échantillon peut cacher les cas difficiles. Mesurez une règle sur les données qu’elle rencontrera. Vous retrouvez la même leçon dans Données d’entraînement, de validation et de test du cours d’apprentissage automatique.

Vérifiez votre compréhension

« tremblay » et « trembaly » obtiennent 0,750 avec Levenshtein et 0,975 avec Jaro–Winkler. Expliquez la différence à partir du fonctionnement de chaque mesure.

Afficher la réponse

Les deux valeurs ont les mêmes lettres, avec « l » et « a » inversés. Levenshtein compte les changements. Une inversion exige 2 remplacements, et 1 − 2 / 8 = 0,750. Jaro–Winkler compte les lettres communes près du même endroit. Les 8 lettres sont communes, et l’inversion compte comme une transposition. Jaro vaut 0,958. Les deux valeurs commencent aussi par les mêmes 4 lettres. Le bonus de Winkler porte donc le score à 0,975.

Vérifiez votre compréhension

Le ratio d'ensembles de mots donne 1,000 à « marie claude tremblay » / « marie tremblay », et à un boyau seul / son paquet de 2. Quel est le point commun entre ces cas, et pourquoi est-ce un risque pour un apparieur?

Afficher la réponse

Dans les deux cas, chaque mot d’une valeur figure aussi dans l’autre; l’autre valeur a seulement des mots supplémentaires. Le ratio d’ensembles de mots compare les mots communs à chaque valeur et garde le meilleur score. Il donne donc 1,000. Mais le mot supplémentaire peut changer le sens. « claude » peut désigner une autre personne (une fille et sa mère), et « pack of 2 » désigne un autre produit. Un apparieur qui se fie uniquement à ce score les fusionne.

Vérifiez votre compréhension

Un collègue veut comparer les numéros de téléphone avec Jaro–Winkler, car « un chiffre erroné devrait quand même donner une correspondance ». Est-ce une bonne idée? Que feriez-vous plutôt?

Afficher la réponse

Habituellement, non. Deux numéros de téléphone différents d’une même région partagent la plupart des chiffres et le même début. Ce début comprend l’indicatif régional et le préfixe : tous nos numéros synthétiques utilisent 555. Jaro–Winkler leur donne un score élevé, donc beaucoup de paires de personnes différentes semblent se ressembler. Vérifiez l’égalité des numéros de téléphone nettoyés et laissez les autres champs apporter les éléments de preuve. Si les fautes de frappe sont fréquentes dans les numéros, ajoutez un signal distinct. Par exemple, « identique sauf un chiffre », puis mesurez-le sur les paires candidates.

Récapitulatif

  • Une similarité de chaînes indique à quel point deux valeurs se ressemblent, de 0 (aucune ressemblance) à 1 (identiques).
  • Levenshtein compte les changements d’une lettre. Similarité = 1 − distance / longueur de la chaîne la plus longue. Les inversions et l’ordre des mots coûtent cher.
  • Jaro–Winkler compte les lettres communes près du même endroit, avec un bonus pour un début identique. Il convient aux noms courts.
  • Le ratio d’ensembles de mots compare des ensembles de mots. Il ignore l’ordre et les mots supplémentaires, donc un score de 1 ne signifie pas « identiques ».
  • Dans les titres de produits, les tailles et les formats trompent toutes les mesures : 12 in / 16 in obtient au moins 0,97.
  • Parmi les paires candidates de Larkfield, 47 % à 61 % des paires de personnes différentes obtiennent au moins 0,9 sur le nom complet. Un nom seul ne permet pas de décider.

Les lettres sont une façon de comparer les noms. Les gens disent aussi les noms à voix haute et écrivent ce qu’ils entendent. Dans la suite, les codes phonétiques comparent les noms selon leur sonorité.

Leçon suivante : Ça se prononce pareil