Algoritmo de deduplicação de dados para um grande número de contactos

Toda esta área de investigação é geralmente conhecida como ligação de registos (ironicamente, tem cerca de uma dúzia de nomes duplicados). Existem algumas ferramentas lá fora que lhe permitirão configurar a correspondência para os seus dados específicos, fazer churn através dos dados, e enviar os duplicados para você. Algumas ferramentas irão até mesmo criar uma correspondência para você, se você responder a algumas perguntas sobre a correção de potenciais correspondências.

A comparação Q/n-gram (e indexação) é uma forma possível de resolver isto, mas há é um monte de outros. Você vai rapidamente descobrir que diferentes tipos de comparadores funcionam bem para diferentes tipos de dados. Eu não tentei indexar Q-gram, mas pesquisadores no campo descreveram-no para mim como relativamente lento.

Quanto à comparação com funções de chave fonética (como Soundex ou Metafone ou o que quer que seja) isto só é adequado quando você tem pequenos campos de texto, como campos separados para nome próprio, nome de família, nome do meio, etc. Mesmo assim, estas funções tendem a ser bastante grosso. E cuidado com o Soundex. Não só é extremamente grosseiro, transformando nomes muito diferentes na mesma chave, mas também falha um número de nomes semelhantes que devem ser tratados o mesmo. Metafona é muito melhor.

A página do Wikipedia for record linkage costumava ter uma lista de ferramentas, mas os editores removeram-na. Escrevi uma ferramenta de código aberto chamada Duke para resolver este tipo de coisas. Ele tem um algoritmo genético que pode ajudá-lo a criar uma configuração, ou você pode escrever um manualmente. Também existem outras ferramentas.

Aconselho-o a usar uma das ferramentas que já existem, em vez de tentar resolver isto do zero.

Eu acredito que a melhor opção para a remoção de nomes é por meio de um codificador fonético . Um codificador fonético será capaz de decifrar ortografias alternativas do mesmo nome, aqui está um exemplo com alguns nomes comuns:

Group: Kathryn names: [Kathryn, Katharine, Katherin, Katherynn, Kathrynn, Katherynne, Kathrynne, Catherine, Cathryn, Catharine, Catherin, Catherynn, Cathrynn, Catherynne, Cathrynne]
Group: Assaf names: [Assaf, Asaf]
Group: Megan names: [Megan, Meagan, Meghan, Meaghan]
Group: Allison names: [Allison, Alyson, Allyson, Alison, Allisyn]
==============================================================
Phonetic Encoder: Caverphone2
---- Names Group: Kathryn ----
Encoded names: {KTRN111111=16}
---- Names Group: Assaf ----
Encoded names: {ASF1111111=3}
---- Names Group: Megan ----
Encoded names: {MKN1111111=5}
---- Names Group: Allison ----
Encoded names: {ALSN111111=6}
==============================================================
Phonetic Encoder: DoubleMetaphone
---- Names Group: Kathryn ----
Encoded names: {K0RN=16}
---- Names Group: Assaf ----
Encoded names: {ASF=3}
---- Names Group: Megan ----
Encoded names: {MKN=5}
---- Names Group: Allison ----
Encoded names: {ALSN=6}
==============================================================
Phonetic Encoder: Nysiis
---- Names Group: Kathryn ----
Encoded names: {CATRYN=7, CATARA=6, CATARY=5}
---- Names Group: Assaf ----
Encoded names: {ASAF=3}
---- Names Group: Megan ----
Encoded names: {MAGAN=5}
---- Names Group: Allison ----
Encoded names: {ALASAN=3, ALYSAN=3, ALASYN=2}
==============================================================
Phonetic Encoder: Soundex
---- Names Group: Kathryn ----
Encoded names: {K365=8, C365=9}
---- Names Group: Assaf ----
Encoded names: {A210=3}
---- Names Group: Megan ----
Encoded names: {M250=5}
---- Names Group: Allison ----
Encoded names: {A425=6}
==============================================================
Phonetic Encoder: RefinedSoundex
---- Names Group: Kathryn ----
Encoded names: {C30609080=5, K3060908=5, K30609080=4, C3060908=5}
---- Names Group: Assaf ----
Encoded names: {A0302=3}
---- Names Group: Megan ----
Encoded names: {M80408=5}
---- Names Group: Allison ----
Encoded names: {A070308=6}
==============================================================

No exemplo você pode ver que para Caverphone e DoubleMetaphone todos os nomes foram codificados para a mesma cadeia. você deve ver o que faz sentido para seus dados, o codificador a usar depende da linguagem e etimologia dos nomes (i.e. nomes ingleses, alemães...)