Collecter à partir de plusieurs sources, ou d’une même source plusieurs fois, et les doublons suivent. Le même produit apparaît sur trois places de marché sous trois noms légèrement différents. La même entreprise est « Acme Widgets Ltd » dans un registre et « ACME WIDGETS LIMITED » dans un autre. La même annonce revient deux fois parce que la pagination a bougé pendant que vous crawliez, ou parce qu’un lien portait un paramètre de suivi et l’autre non.
Laissés tels quels, les doublons gonflent les comptages, fragmentent l’historique entre plusieurs enregistrements et corrompent silencieusement toute métrique construite dessus. Ce guide explique comment les résoudre : normaliser les identifiants, faire correspondre d’abord sur des clés fortes, effectuer un matching flou de manière sûre à grande échelle, regrouper en clusters, et choisir quelle version d’un enregistrement survit.
Points clés
- La plupart des doublons sont détectés en normalisant les identifiants avant tout matching flou : URLs canoniques, codes produits validés et noms d’entreprise nettoyés.
- Faire correspondre d’abord sur des identifiants forts. Un code-barres valide ou un numéro de registre l’emporte sur n’importe quel degré de similarité de noms.
- Ne jamais comparer chaque enregistrement avec tous les autres. Un million d’enregistrements donnent environ 500 milliards de paires ; le blocking ramène cela à quelque chose de gérable.
- Décider quelle erreur coûte le plus cher. Pour certains usages, une fusion erronée est pire qu’un doublon manqué ; pour d’autres, c’est l’inverse.
- Conserver la provenance. L’enregistrement fusionné doit toujours connaître chaque source dont il provient.
Trois types de doublons
| Type | Exemple | Comment il est détecté |
|---|---|---|
| Collecte répétée | La même URL récupérée deux fois, ou des pages de résultats qui se chevauchent | URL canonique ou identifiant de source |
| Même entité, source différente | Un produit listé sur trois places de marché | Identifiants partagés, puis matching flou |
| Contenu quasi identique | Le même article syndiqué avec de petites modifications | Similarité de contenu, comme traité dans la détection de changement à grande échelle |
Ce guide se concentre sur les deux premiers, où l’objectif est d’obtenir un enregistrement par produit, entreprise ou annonce réels.
Étape 1 : normaliser les identifiants
La normalisation est peu coûteuse et détecte plus de doublons que n’importe quel matching astucieux.
URLs. La même page arrive sous de nombreuses URLs. Mettre l’hôte en minuscules, supprimer www., retirer les paramètres de suivi tels que utm_*, gclid et fbclid, trier les paramètres de requête restants, et supprimer les barres obliques finales. http://www.Shop.com/p/123/?utm_source=x&b=2&a=1 et https://shop.com/p/123?a=1&b=2 deviennent la même clé.
Codes produits. Les Global Trade Item Numbers (les numéros derrière les codes-barres UPC et EAN) portent une clé de contrôle, ce qui permet de rejeter des codes mal saisis ou mal scrapés avant de leur faire confiance. La méthode de GS1 pondère les chiffres par 3, 1, 3, 1 et ainsi de suite, en commençant par le chiffre voisin de la clé de contrôle, en fait la somme, et prend la quantité nécessaire pour arrondir au multiple de dix supérieur. Dans l’exemple travaillé de GS1 lui-même, le corps à 11 chiffres 61414121022 obtient une clé de contrôle de 0. Compléter les codes valides jusqu’à 14 chiffres afin qu’une version à 13 chiffres et une version à 14 chiffres du même code se comparent comme égales.
Noms d’entreprise. Uniformiser la casse et les accents, retirer la ponctuation, et supprimer les suffixes juridiques tels que Ltd, Limited, Inc, GmbH et SA avant toute comparaison. « Acme Widgets Ltd. » et « ACME WIDGETS LIMITED » deviennent tous deux acme widgets. Lorsqu’une entreprise dispose d’un numéro de registre ou d’un Legal Entity Identifier, utiliser celui-ci plutôt que le nom ; la résolution des entreprises vers des identifiants est traitée dans surveiller l’empreinte publique de vos fournisseurs.
Étape 2 : faire correspondre d’abord sur des clés fortes
Une fois les identifiants normalisés, les correspondances exactes sur ceux-ci sont à la fois rapides et fiables. Deux enregistrements avec le même code-barres valide sont le même produit. Deux enregistrements avec la même URL canonique sont la même page. Deux entreprises avec le même numéro de registre sont la même entreprise, quel que soit leur nom.
Les données structurées aident aussi ici. De nombreuses pages produit publient des codes-barres et des SKU en JSON-LD, ce qui est bien plus fiable que de les extraire de la page visible ; voir arrêtez de parser du HTML.
Étape 3 : matching flou, mais uniquement au sein de blocs
Les enregistrements sans identifiants partagés nécessitent un matching flou sur les noms, adresses ou descriptions. Le piège est l’échelle. Comparer chaque enregistrement avec tous les autres croît avec le carré de la taille du jeu de données : un million d’enregistrements produisent environ 500 milliards de paires.
Le blocking résout ce problème. Regrouper les enregistrements par une clé peu coûteuse que les vraies correspondances partagent presque toujours, comme le pays plus le premier mot du nom normalisé, ou la marque plus la catégorie de produit, et ne comparer qu’au sein de chaque groupe. Une bonne clé de blocking réduit les comparaisons de plusieurs ordres de grandeur tout en perdant peu de vraies correspondances. Vérifier ce qu’elle perd en échantillonnant des paires à travers les blocs de temps en temps.
Au sein d’un bloc, un score de similarité de chaînes et un seuil déterminent les correspondances. Commencer strict, autour de 0,9, et assouplir seulement après avoir examiné ce que le réglage plus permissif fusionnerait.
Étape 4 : regrouper en clusters, avec prudence
Les correspondances sont par paires ; les entités sont des groupes. Une structure union-find transforme efficacement les paires en clusters. Elle comporte aussi un risque : la transitivité. Si A correspond à B et B correspond à C, A et C se retrouvent ensemble même s’ils n’ont rien en commun. De longues chaînes de correspondances faibles sont la manière dont deux entreprises différentes finissent fusionnées. Surveiller les clusters de taille inhabituellement grande et les examiner avant de les accepter.
L’ensemble du pipeline tient dans un petit module :
import re
import unicodedata
from collections import defaultdict
from difflib import SequenceMatcher
from urllib.parse import urlsplit, urlunsplit, parse_qsl, urlencode
LEGAL_SUFFIXES = {"ltd", "limited", "inc", "incorporated", "llc", "gmbh", "ag", "sa", "sas",
"srl", "bv", "nv", "plc", "co", "corp", "corporation", "company", "oy", "ab"}
TRACKING = re.compile(r"^(utm_|gclid$|fbclid$|mc_|ref$|ref_)")
def gtin_valid(code):
"""GS1 check digit: weights 3,1,3,... from the digit next to the check digit."""
digits = re.sub(r"\D", "", str(code or ""))
if len(digits) not in (8, 12, 13, 14):
return False
body, check = digits[:-1], int(digits[-1])
total = sum(int(d) * (3 if i % 2 == 0 else 1) for i, d in enumerate(reversed(body)))
return (10 - total % 10) % 10 == check
def norm_name(name):
text = unicodedata.normalize("NFKD", name or "").encode("ascii", "ignore").decode().lower()
tokens = [t for t in re.findall(r"[a-z0-9]+", text) if t not in LEGAL_SUFFIXES]
return " ".join(tokens)
def norm_url(url):
parts = urlsplit((url or "").strip())
query = urlencode(sorted((k, v) for k, v in parse_qsl(parts.query) if not TRACKING.match(k.lower())))
host = parts.netloc.lower().removeprefix("www.")
return urlunsplit(("https", host, parts.path.rstrip("/") or "/", query, ""))
def similar(a, b):
return SequenceMatcher(None, a, b).ratio()
def cluster(records, threshold=0.9):
"""Group records that refer to the same entity. Returns lists of record indexes."""
parent = list(range(len(records)))
def find(i):
while parent[i] != i:
parent[i] = parent[parent[i]]
i = parent[i]
return i
def union(i, j):
parent[find(i)] = find(j)
# 1. Exact matches on strong identifiers.
by_key = defaultdict(list)
for i, r in enumerate(records):
if gtin_valid(r.get("gtin")):
by_key["gtin:" + re.sub(r"\D", "", r["gtin"]).zfill(14)].append(i)
if r.get("url"):
by_key["url:" + norm_url(r["url"])].append(i)
for ids in by_key.values():
for j in ids[1:]:
union(ids[0], j)
# 2. Fuzzy name match, only within a cheap blocking key.
blocks = defaultdict(list)
for i, r in enumerate(records):
name = norm_name(r.get("name"))
if name:
blocks[(r.get("country") or "", name.split()[0])].append((i, name))
for members in blocks.values():
for a in range(len(members)):
for b in range(a + 1, len(members)):
if similar(members[a][1], members[b][1]) >= threshold:
union(members[a][0], members[b][0])
groups = defaultdict(list)
for i in range(len(records)):
groups[find(i)].append(i)
return list(groups.values())Sur un petit jeu de test, il fusionne « Acme Widgets Ltd », « ACME WIDGETS LIMITED » et un troisième enregistrement partageant l’URL canonique de l’entreprise, fusionne deux annonces de chaussures dont les codes-barres ne diffèrent que par un zéro initial, et laisse délibérément « Acme Widget Co » aux États-Unis comme une entité séparée, parce que la clé de blocking inclut le pays. La question de savoir si cette dernière décision est correcte dépend de vos données, ce qui est précisément l’objet de l’étape suivante.
Étape 5 : décider quel enregistrement survit
Un cluster contient plusieurs versions d’une même entité, et il en faut une seule. Règles de survivance courantes :
- Le plus complet l’emporte, champ par champ : prendre la valeur non vide provenant de la meilleure source pour chaque champ plutôt qu’un enregistrement entier.
- Le plus récent l’emporte pour les valeurs qui changent, comme le prix et la disponibilité.
- La source la plus fiable l’emporte pour des valeurs comme les noms officiels et les adresses, par exemple un registre plutôt qu’un annuaire.
Quel que soit votre choix, conserver chaque identifiant de source et chaque URL sur l’enregistrement fusionné, avec le moment où chacun a été observé. Quand une fusion se révèle erronée, la provenance est ce qui permet de la scinder à nouveau.
Mesurer précision et rappel
La résolution d’entités comporte deux types d’erreur, et celle qui compte dépend de l’usage.
| Erreur | Ce qui se passe | Le plus dommageable pour |
|---|---|---|
| Fusion erronée | Deux entités réelles n’en deviennent qu’une | Les données d’entreprises et proches des personnes, la conformité, tout ce qui est juridique |
| Doublon manqué | Une entité reste répartie sur plusieurs enregistrements | Les comptages, l’estimation de marché, la comparaison de prix |
Étiqueter à la main quelques centaines de paires candidates, mesurer les deux taux, et ajuster seuils et clés de blocking en fonction de l’erreur qui compte pour vous. Une base de leads B2B, comme celle décrite dans construire une base de leads B2B, tolère généralement bien mieux un doublon manqué que deux entreprises fusionnées à tort. Un flux de comparaison de prix, comme un flux de prix compétitifs en temps réel, fonctionne à l’inverse : un doublon manqué signifie qu’un produit apparaît deux fois avec deux prix.
Dédupliquer tôt, et à la source
Les doublons coûtent de l’argent avant de coûter en exactitude. Chaque récupération répétée de la même URL canonique est de la bande passante ou des crédits dépensés pour rien, ce qui explique pourquoi la canonicalisation des URLs a sa place dans la frontière du crawler, pas seulement dans l’entrepôt de données. L’effet sur le coût unitaire est traité dans coût par enregistrement propre.
En résumé
La déduplication est principalement affaire de normalisation. Les URLs canoniques, les codes produits validés et les noms d’entreprise nettoyés captent la majorité des doublons avant tout matching flou. Ensuite, faire correspondre sur des clés fortes, effectuer le matching flou uniquement au sein de blocs, regrouper en clusters en surveillant les longues chaînes, conserver la provenance sur chaque enregistrement fusionné, et mesurer les erreurs qui comptent pour votre usage.
Bien fait, une chose réelle du monde devient un enregistrement, avec tout son historique attaché. Mal fait, le jeu de données paraît à la fois plus grand et moins fiable.
Sources et références
- GS1 US, How to calculate a check digit manually.
- GLEIF, Open LEI data.