Correspondência parcial de nome em milhões de registros

Desenvolvemos um aplicativo baseado na Web para correspondência de nomes. Ele opera dividindo nomes em partes e o valor Soundex de cada parte é armazenado em um banco de dados. A métrica de distância de Levenshtein é usada para aplicar a porcentagem de correspondência de som, bem como a ortografia em um determinado nome.

Em tempo de execução, carregamos todos os registros na memória e aplicamos a distância de Levenshtein a todos os valores do Soundex e a ortografia de todas as partes de todos os nomes.

No começo, tudo funcionou bem porque havia no máximo 20 mil nomes, mas agora um de nossos clientes tem 30 milhões de nomes. Carregar essa lista enorme na memória para cada solicitação e aplicar esse tipo de correspondência é uma abordagem patética, usando muita memória e tempo de execução.

Estamos procurando sugestões para pesquisar no banco de dados de 30 milhões de registros ou mais em um futuro próximo com a porcentagem correspondente de Som e ortografia.

Funcionalidade principal

O usuário final digita o nome a ser correspondido e a porcentagem mínima. Devemos mostrar todos os nomes no banco de dados para os quais qualquer parte do nome corresponde a qualquer parte do nome fornecido até a porcentagem especificada. Não é necessário corresponder o nome completo; qualquer parte se corresponder à porcentagem é um sucesso. Por exemplo.

Given Name: Helen Hunt
Name in DB: Holly Hunter 

Ambas as partes de ambos os nomes não estão correspondendo exatamente, mas até certo ponto, vamos assumir 80%; portanto, se o usuário digitar 80%, o nome no DB deverá ser mostrado como nome correspondente.

Sem conhecer os detalhes completos do que você precisa, você provavelmente deseja fazer um dos seguintes:

• Use uma ferramenta de pesquisa existente, como Sphinx ou Lucene
• Executar correspondência aproximada em n-grama

Não sei completamente o que está envolvido na instalação e configuração da esfinge; mas, tenho a impressão de que você pode apontá-lo para um banco de dados, informar quais campos indexar, como ponderar os resultados e fornecerá uma lista ordenada de registros correspondentes.

Para itens voltados para o usuário ou de missão crítica, use uma ferramenta de pesquisa existente.

Se você está apenas se sentindo acadêmico ... Jogue com ngrams:

Uma tabela de pesquisa ngrams pode servir como seu conjunto inicial de possíveis correspondências, e você pode usar as distâncias de Levenshtein para remover e classificar os resultados.

Supondo que você deseja pesquisar people, você pode fazer algo como:

_ people _________
personId: int
name: varchar
soundex_name: varchar

_ people_ngrams __
personId: int
ngramId: int

_ ngrams _________
ngramId: int
ngram: char(3)
count: int

Você pode reconstruir periodicamente seus ngrams ou construí-los on-the-fly. De qualquer maneira, um algoritmo de pesquisa simples e ingênuo pode ser assim:

search_ngrams = ngrammify(soundex(search_string));

notable_ngrams = select top 10 *
  from ngrams
  where ngram in (search_ngrams)
  order by count asc;

possible_matches = select top 1000 distinct people.*
  from people_ngrams, people
  where ngramId in (notable_ngrams);

best_matches = top 100 possible_matches
  ordered by Levenshtein_distance(match, soundex(search_string));

Usando algo bem parecido com isso (mas com um pouco mais de ajuste de "popularidade" do ngram, listas negras, listas brancas, etc.), eu já vi esse tipo de algoritmo mesclar os registros entre conjuntos de dados em massa, além de facilitar a pesquisa difusa personalizada esforços de desduplicação de registros em andamento.

Agora, no meu caso, eu não estava correspondendo a milhões de registros, estava procurando selecionar as melhores mesclas possíveis entre dois conjuntos de dados na ordem de centenas de milhares de registros cada. E queríamos que funcionasse rapidamente - em alguns minutos. (Rápido, o que é 100.000 * 100.000?) E fomos bem-sucedidos.

Portanto, com a afinação correta, esse tipo de coisa pode ser ágil e eficaz. Em última análise, conseguimos produzir um conjunto mesclado em uma máquina humilde, datada e de núcleo duplo em alguns minutos, com mesclagens "questionáveis" sinalizadas automaticamente para revisão manual. Mas demorou muito tempo para encontrar o ponto ideal de popularidade / relevância do ngram, os limites de distância da corda certos, as listas negras e as listas brancas ... etc.

Dito isto , você pode realmente ser sugado para um buraco trabalhando nessas coisas. Para qualquer coisa no nível de produção do mundo real, você geralmente deve usar uma ferramenta bem estabelecida que já foi criada e otimizada para esse tipo de pesquisa.

Como Esfinge ou Lucene .