Papo nerd: Otimização de caso O(N × M) sem IA nem libs pesadas
Apenas um ensaio do meu blog e uma discussão nerd sobre uma otimização de um caso super especifico que dificilmente ocorreria mas pelo bem e pelo mal eu passei um bom tempo tentando consertar de maneira eficiente esse problema e espero que alguém que gosta desses tipos de problemas pelo menos se divirta um pouco com o processo.
Estou desenvolvendo o bibliolatam, um pacote em R voltado para integração, harmonização e cienciometria sobre bases acadêmicas da América Latina (SciELO, BDTD, Oasisbr, Redalyc, LA Referencia, SPELL).
Um dos pontos mais sensíveis da ferramenta é a função de merge e deduplicação (merge_bibliolatam). Quando os artigos possuem um identificador unico (DOI), o problema é trivial: faz-se uma indexação direta de hash em e resolve o pareamento.
O gargalo começa quando caímos no mundo real da produção científica que simplesmente não possuem DOI (identificador unico). Nesses casos, o fallback obrigatório é fazer fuzzy matching pelo título do artigo normalizado e cruzar com os metadados complementares (ano e autoria).
Onde a CPU chora e a mãe não vê
Caso você entenda BigO você já entendeu, se tem um dataset com 20.000 artigos e vai cruzar com outro de 30.000 sem DOI, comparar todo mundo contra todo mundo por matriz de distância de edição (Levenshtein) geraria 600 milhões de chamadas de comparação de strings.
Por contexto a matriz de distancia de Levenshtein é uma tabela usada em programação dinâmica para calcular o número mínimo de operações (inserção, remoção ou substituição de um caractere) necessárias para transformar uma string em outra.
É verdade que na prática isso não é o fim do mundo para 90% dos casos cotidianos. Eu já apliquei alguns bloqueios prévios:
- Agrupamos por janela de ano ( ano de tolerância).
- Exigimos compatibilidade de sobrenomes de autores com tolerância fonética.
Mas ainda assim surgem cenários patológicos em censos bibliométricos massivos (> 50.000 registros):
- Artigos em anais de congressos que não trazem autor cadastrado (metadado
ANONYMOUSouNA), onde o guardrail de autor não consegue atuar para podar candidatos. - Sobrenomes super frequentes na nossa região (como Silva, Santos, Oliveira). Em um único ano, você pode facilmente ter centenas ou milhares de teses e artigos sob o mesmo sobrenome.
Rodar o algoritmo de Wagner-Fischer / Levenshtein (mesmo compilado em C dentro do adist do R) contra centenas de candidatos para cada linha sem DOI vira um desperdício massivo de ciclos de clock.
Sempre dá para melhorar, e foi aqui que entrou uma sugestão do meu professor (obrigado prof. Carlos) usar um Length Bound Filter.
A soluçmatemática: Length Bound Filter
A distância de Levenshtein entre duas strings e , denotada por , obedece à desigualdade triangular métrica. Disso decorre uma propriedade fundamental: a distância mínima de edição entre duas palavras é limitada inferiormente pela diferença absoluta dos seus comprimentos em caracteres:
No bibliolatam, calculamos a similaridade normalizada dividindo a distância pelo comprimento da maior string:
Se estabelecemos um limiar de corte rígido (por exemplo, para 90% de similaridade mínima), então é matematicamente obrigatório que:
Substituindo a desigualdade triangular , temos dois casos:
-
Se o candidato for menor ou igual ():
, logo:
Como o número de caracteres é um número inteiro:
-
Se o candidato for estritamente maior ():
, logo:
Como o número de caracteres é um número inteiro:
O que isso significa na prática?
Se o título do artigo que estamos tentando casar tem 60 caracteres normalizados e exigimos :
Qualquer candidato com menos de 54 ou mais de 66 caracteres tem 0% de chance matemática de atingir 90% de similaridade.
Não importa o que está escrito dentro da string, ela simplesmente não pode atingir a nota de corte.
O ganho aqui é brutal porque medir nchar() (ou ler um vetor de inteiros pré-computado uma única vez) é uma operação que roda em nanossegundos direto na CPU. Uma checagem booleana de range (lens >= min_len & lens <= max_len) joga fora entre 80% e 90% de todos os candidatos do pool antes de qualquer cálculo de Levenshtein ser invocado.
Fechando o pacote: Fast-Path Exato e Canopy
Junto com o filtro de extensão, adicionamos duas outras proteções:
- Exact Match Fast-Path ( vetorizado): Na prática cienciométrica, cerca de 70% das duplicações entre bases compartilham o mesmo título exato (com pequenas variações de maiúsculas/acentos já removidas na normalização). Fazendo um
cand_titles == t1antes do Levenshtein, se houver correspondência exata e autoria compatível, o par é resolvido na hora. Nos benchmarks, isso deu um speedup de ~230x para esses pares. - Significant Content Word Canopy: Se mesmo após o filtro de ano, autor e comprimento restarem mais de 15 candidatos (cenário comum em relatórios anônimos de governo), exigimos que o candidato compartilhe pelo menos uma palavra de conteúdo com caracteres antes de gastar tempo na matriz de edição.
Resultado nos Benchmarks
Rodando em um container de testes contra um pool com 100 armadilhas adversariais e perturbações sintéticas:
- All-pairs Levenshtein tradicional: ~0.57s para 300 comparações repetidas.
- Com Length Bound Filter: ~0.10s (speedup de 5.2x nos pares que divergem em texto).
- Com Exact Fast-Path: ~0.002s (speedup de ~230x para pares idênticos).
- Taxa de Falsos Positivos (FPR): 0.0% mantida em toda a suíte de testes (1.840 testes passando).
Às vezes a gente fica tentado a colocar índices complexos, bancos vetoriais ou bibliotecas pesadas de terceiros para resolver problemas de escala, quando um teorema básico de desigualdade métrica e operações inteiras em resolvem o gargalo com zero dependências externas.