Алгоритм дедупликации данных для большого числа контактов

Question

Я разрабатываю приложение, которое должно быть в состоянии найти & объединить дубликаты в Сотнях тысяч контактных данных, хранящихся в DB сервера SQL. Мне нужно сравнить все столбцы в таблице, каждый столбец имеет значение веса. Сравнение должно работать на основе значения веса. Исходя из результата сравнения & степени эквивалентности, я должен решить автоматически объединить контакты или запросить у пользователя внимание. Я знаю, что существует множество алгоритмов нечеткой логики для дедупликации.

Читайте о алгоритмах на основе N-грамм или Q-грамм в http://www.melissadata.com/. Является ли этот алгоритм выполнимым для большого набора данных? Если нет, кто-нибудь может мне помочь с каким-то алгоритмом или с телом, с чего начать?

Пример того, что я хочу достичь,

Gonzales = Gonzalez (two different spelling of different name) 
Smith = Smyth (Phonetic sound the same) 
123 Main st = 123 Main street (abbrevation) 
Bob Smith = Robert Smith (synonym) 

Answer 1

Нашли частичное решение с использованием алгоритма simhash. Нашел хороший пример здесь http://simhash.codeplex.com/

Answer 2

Я считаю, что лучший вариант для deduping имен с помощью phonetic encoder. фонетического кодер сможет DeDup альтернативные варианты написания одного и того же имени, вот пример с некоторыми общими названиями:

 
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} 
============================================================== 

В примере вы можете увидеть, что для Caverphone и DoubleMetaphone все имена были закодированы в то же строка. вы должны понимать, что имеет смысл для ваших данных, используемый кодировщик зависит от языка и этимологии имен (например, английских имен, немецких имен ...)

Answer 3

Вся эта область исследований, как правило, известна как запись связи (по иронии судьбы, она имеет около дюжины дубликатов имен). Существует немало инструментов, которые позволят вам настроить сопоставление для ваших конкретных данных, обмануть данные и вывести дубликаты для вас. Некоторые инструменты даже создадут для вас соответствие, если вы ответите на некоторые вопросы о правильности возможных совпадений.

Сравнение Q/N-грамм (и индексация) - один из возможных путей решения этого вопроса, но есть целый плот других. Вы быстро обнаружите, что различные типы компараторов хорошо работают для разных типов данных. Я не пробовал индексировать Q-грамму самостоятельно, но исследователи в этой области описали это для меня как относительно медленные.

Что касается сравнения с фонетическими ключевыми функциями (например, Soundex или Metaphone или что-то еще), это подходит только тогда, когда у вас небольшие текстовые поля, такие как отдельные поля для заданного имени, фамилии, имени и т. Д. Даже тогда эти функции имеют тенденцию быть довольно грубым. И остерегайтесь Soundex. Он не только чрезвычайно грубый, превращая очень разные имена в один и тот же ключ, но также пропускает ряд похожих имен, к которым следует относиться одинаково. Метафон намного лучше.

На странице Wikipedia для записи ссылок используется список инструментов, но редакторы удалили его. Я написал инструмент с открытым исходным кодом под названием Duke для решения такого рода вещей. Он имеет генетический алгоритм, который может помочь вам создать конфигурацию, или вы можете написать ее вручную. Существуют и другие инструменты.

Я бы посоветовал использовать один из инструментов, которые уже существуют, а не пытаться решить это с нуля.