Colete de mais de um lugar, ou do mesmo lugar mais de uma vez, e as duplicatas surgem. O mesmo produto aparece em três marketplaces com três nomes ligeiramente diferentes. A mesma empresa é “Acme Widgets Ltd” em um registro e “ACME WIDGETS LIMITED” em outro. O mesmo anúncio aparece duas vezes porque a paginação mudou enquanto você fazia o crawling, ou porque um link trazia um parâmetro de rastreamento e o outro não.
Se deixadas de lado, as duplicatas inflam contagens, dividem o histórico entre registros e corrompem silenciosamente toda métrica construída em cima delas. Este guia cobre como resolvê-las: normalizando identificadores, casando primeiro por chaves fortes, fazendo fuzzy matching com segurança em escala, agrupando (clustering) e escolhendo qual versão do registro sobrevive.
Principais conclusões
- A maioria das duplicatas é detectada ao normalizar identificadores antes de qualquer fuzzy matching: URLs canônicas, códigos de produto validados e nomes de empresas limpos.
- Faça o casamento primeiro pelos identificadores fortes. Um código de barras válido ou um número de registro vence qualquer grau de similaridade de nome.
- Nunca compare cada registro com todos os outros. Um milhão de registros geram cerca de 500 bilhões de pares; o blocking reduz isso a algo tratável.
- Decida qual erro custa mais caro. Para alguns trabalhos, uma fusão falsa é pior do que uma duplicata não detectada; para outros, é o contrário.
- Preserve a proveniência. O registro mesclado ainda deve saber de qual fonte veio cada dado.
Três tipos de duplicata
| Tipo | Exemplo | Como é detectada |
|---|---|---|
| Coleta repetida | A mesma URL buscada duas vezes, ou páginas de resultados sobrepostas | URL canônica ou identificador de fonte |
| Mesma entidade, fonte diferente | Um produto listado em três marketplaces | Identificadores compartilhados, depois fuzzy matching |
| Conteúdo quase duplicado | O mesmo artigo republicado com pequenas edições | Similaridade de conteúdo, como abordado em detecção de mudanças em escala |
Este guia foca nos dois primeiros casos, em que o objetivo é ter um registro por produto, empresa ou anúncio do mundo real.
Etapa 1: normalizar identificadores
A normalização é barata e detecta mais duplicatas do que qualquer casamento sofisticado.
URLs. A mesma página chega sob diversas URLs. Coloque o host em minúsculas, remova o www., elimine parâmetros de rastreamento como utm_*, gclid e fbclid, ordene os parâmetros de consulta restantes e remova barras finais. http://www.Shop.com/p/123/?utm_source=x&b=2&a=1 e https://shop.com/p/123?a=1&b=2 se tornam a mesma chave.
Códigos de produto. Os Global Trade Item Numbers (os números por trás dos códigos de barras UPC e EAN) carregam um dígito verificador, o que permite rejeitar códigos digitados errado ou coletados incorretamente antes de confiar neles. O método da GS1 pondera os dígitos com 3, 1, 3, 1 e assim por diante, começando a partir do dígito ao lado do dígito verificador, soma-os e obtém o valor necessário para arredondar até o próximo múltiplo de dez. No exemplo resolvido pela própria GS1, o corpo de 11 dígitos 61414121022 tem um dígito verificador igual a 0. Complete os códigos válidos até 14 dígitos para que uma versão de 13 e uma de 14 dígitos do mesmo código sejam comparadas como iguais.
Nomes de empresas. Normalize maiúsculas/minúsculas e acentos, remova pontuação e retire sufixos legais como Ltd, Limited, Inc, GmbH e SA antes de comparar. “Acme Widgets Ltd.” e “ACME WIDGETS LIMITED” ambos se tornam acme widgets. Quando uma empresa tem um número de registro ou um Legal Entity Identifier, use-o em vez do nome; resolver empresas para identificadores é abordado em monitorando a presença pública dos seus fornecedores.
Etapa 2: casar primeiro pelas chaves fortes
Uma vez que os identificadores estejam normalizados, os casamentos exatos sobre eles são rápidos e confiáveis. Dois registros com o mesmo código de barras válido são o mesmo produto. Dois registros com a mesma URL canônica são a mesma página. Duas empresas com o mesmo número de registro são a mesma empresa, seja qual for o nome usado.
Dados estruturados também ajudam aqui. Muitas páginas de produto publicam códigos de barras e SKUs em JSON-LD, o que é muito mais confiável do que extraí-los da página visível; veja pare de analisar HTML.
Etapa 3: fuzzy matching, mas apenas dentro de blocos
Registros sem identificadores compartilhados precisam de fuzzy matching em nomes, endereços ou descrições. A armadilha é a escala. Comparar cada registro com todos os outros cresce com o quadrado do tamanho do conjunto de dados: um milhão de registros produz aproximadamente 500 bilhões de pares.
O blocking resolve isso. Agrupe os registros por uma chave barata que correspondências verdadeiras quase sempre compartilham, como país mais a primeira palavra do nome normalizado, ou marca mais categoria de produto, e compare apenas dentro de cada grupo. Uma boa chave de blocking reduz as comparações em ordens de grandeza, perdendo poucas correspondências verdadeiras. Verifique o que ela perde amostrando pares entre blocos de tempos em tempos.
Dentro de um bloco, uma pontuação de similaridade de string e um limiar decidem as correspondências. Comece de forma rígida, em torno de 0,9, e afrouxe apenas depois de revisar o que a configuração mais permissiva mesclaria.
Etapa 4: agrupar (cluster) com cuidado
As correspondências são par a par; as entidades são grupos. Uma estrutura union-find transforma pares em clusters de forma eficiente. Mas isso também traz um risco: a transitividade. Se A corresponde a B e B corresponde a C, A e C acabam juntos mesmo que não compartilhem nada. Longas cadeias de correspondências fracas são como duas empresas diferentes acabam mescladas. Fique atento a clusters incomumente grandes e revise-os antes de aceitar.
Todo o pipeline cabe em um pequeno módulo:
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())Em um pequeno conjunto de teste, o código mescla “Acme Widgets Ltd”, “ACME WIDGETS LIMITED” e um terceiro registro que compartilha a URL canônica da empresa, mescla dois anúncios de calçados cujos códigos de barras diferem apenas por um zero à esquerda e deliberadamente deixa “Acme Widget Co” nos Estados Unidos como uma entidade separada, porque a chave de blocking inclui o país. Se essa última decisão está certa depende dos seus dados, que é justamente o ponto da próxima etapa.
Etapa 5: decidir qual registro sobrevive
Um cluster é composto por várias versões de uma entidade, e você precisa de apenas uma. Regras comuns de sobrevivência:
- O mais completo vence, campo a campo: pegue o valor não vazio da melhor fonte para cada campo, em vez de um registro inteiro.
- O mais recente vence para valores que mudam, como preço e disponibilidade.
- A fonte mais confiável vence para valores como nomes oficiais e endereços, por exemplo um registro público em vez de um diretório.
Seja qual for a escolha, mantenha todos os identificadores de fonte e URLs no registro mesclado, com o momento em que cada um foi observado. Quando uma fusão se mostra errada, a proveniência é o que permite desfazê-la.
Meça precisão e recall
A resolução de entidades tem dois tipos de erro, e qual deles importa depende do trabalho.
| Erro | O que acontece | Pior para |
|---|---|---|
| Fusão falsa | Duas entidades reais se tornam uma | Dados de empresas e pessoas, compliance, qualquer coisa jurídica |
| Duplicata não detectada | Uma entidade permanece como vários registros | Contagens, dimensionamento de mercado, comparação de preços |
Rotule algumas centenas de pares candidatos manualmente, meça ambas as taxas e ajuste limiares e chaves de blocking em função do erro que mais importa para você. Um banco de dados de leads B2B, como o descrito em construindo um banco de dados de leads B2B, geralmente tolera muito melhor uma duplicata não detectada do que duas empresas fundidas incorretamente. Um feed de comparação de preços, como um feed de preços competitivos em tempo real, é o oposto: uma duplicata não detectada significa que um produto aparece duas vezes com dois preços.
Faça a deduplicação cedo, e na fonte
As duplicatas custam dinheiro antes de custarem precisão. Cada nova busca repetida da mesma URL canônica é banda ou créditos gastos à toa, e é por isso que canonizar URLs pertence à fronteira do crawler, não apenas ao data warehouse. O efeito no custo unitário é abordado em custo por registro limpo.
Conclusão
A deduplicação é principalmente normalização. URLs canônicas, códigos de produto validados e nomes de empresas limpos detectam a maior parte das duplicatas antes que qualquer fuzzy matching seja executado. Depois disso, faça o casamento pelas chaves fortes, aplique fuzzy matching apenas dentro dos blocos, agrupe com atenção às cadeias longas, mantenha a proveniência em todo registro mesclado e meça os erros que importam para o seu caso de uso.
Bem feita, uma coisa do mundo real se torna um registro, com todo o seu histórico anexado. Malfeita, o conjunto de dados parece maior e menos confiável ao mesmo tempo.
Fontes e referências
- GS1 US, Como calcular um dígito verificador manualmente.
- GLEIF, Dados abertos de LEI.