Дедупликация нечеткого сопоставления менее чем за экспоненциальное время?

Question

У меня есть большая база данных (потенциально в миллионах записей) с относительно короткими строками текста (порядка адресов, имен и т. Д.).

Я ищу стратегию для устранения неточныхдубликаты, и нечеткое соответствие, кажется, метод выбора.Моя проблема: многие статьи и вопросы SO касаются сопоставления одной строки со всеми записями в базе данных.Я хочу дедуплицировать всю базу данных одновременно.

Первой была бы линейная проблема времени (сравнение значения с миллионом других значений, каждый раз вычисляя некоторую меру подобия).Последняя представляет собой экспоненциальную проблему времени (сравните значения каждой записи со значением каждой другой записи; для миллиона записей это примерно 5 x 10 ^ 11 вычислений против 1 000 000 вычислений для первого варианта).

I'mинтересно, есть ли другой подход, кроме метода "грубой силы", который я упомянул.Я думал о том, чтобы, возможно, сгенерировать строку для сравнения значения каждой записи и затем сгруппировать строки, которые имели примерно одинаковые меры сходства, а затем запустить метод грубой силы через эти группы.Я бы не достиг линейного времени, но это могло бы помочь.Кроме того, если я обдумываю это правильно, это может пропустить потенциальное нечеткое совпадение между строками A и B, потому что их сходство со строкой C (сгенерированная контрольная строка) очень отличается, несмотря на то, что они очень похожи друг на друга.

Есть какие-нибудь идеи?

PS Я понимаю, что, возможно, я использовал неправильные термины для сложности времени - это концепция, которой я обладаю базовыми знаниями, но недостаточно хорошо, чтобы я мог отброситьалгоритм в нужную категорию на месте.Если я использовал неправильные термины, я приветствую исправления, но, надеюсь, я получил хотя бы свою точку зрения.

Редактировать

Некоторые комментаторы спросили, учитывая нечеткостьсовпадения между записями, какая моя стратегия заключалась в том, чтобы выбрать, какие из них удалить (т.е. с учетом "foo", "boo" и "coo", которые будут отмечены как дубликаты и удалены).Я должен отметить, что я не ищу автоматического удаления здесь.Идея состоит в том, чтобы отметить потенциальные дубликаты в базе данных с более чем 60 миллионами записей для целей анализа и оценки человеком.Это нормально, если есть некоторые ложные срабатывания, при условии, что это примерно предсказуемое / последовательное количество.Мне просто нужно понять, насколько распространены дубликаты.Но если запуск нечеткого сопоставления занимает месяц, то это даже не вариант.

Answer 1

Взгляните на http://en.wikipedia.org/wiki/Locality-sensitive_hashing. Один очень простой подход - разделить каждый адрес (или любой другой) на набор перекрывающихся n-грамм. Этот STACKOVERFLOW становится набором {STACKO, TACKO, ACKOV, CKOVE ..., RFLOW}. Затем используйте большую хеш-таблицу или сортировку-слияние, чтобы найти сталкивающиеся n-граммы и проверить столкновения с помощью нечеткого сопоставителя. Таким образом, STACKOVERFLOW и SXACKOVRVLOX будут сталкиваться, потому что оба связаны с сталкивающимся n-граммовым ACKOV.

Следующий уровень сложности - выбрать случайную хэш-функцию - например, HMAC с произвольным ключом и n-граммами, которые вы найдете, сохраняют только тот, который имеет наименьшее хешированное значение. Тогда вам нужно отслеживать меньшее количество n-грамм, но совпадение будет видно только в том случае, если наименьшее значение хеширования в обоих случаях - ACKOV. Здесь, очевидно, существует компромисс между длиной n-граммы и вероятностью ложных попаданий. На самом деле, кажется, что люди делают n довольно маленьким и получают более высокую точность, объединяя результаты более чем одной хеш-функции в одной записи, поэтому вам нужно получить совпадение в нескольких разных хеш-функциях одновременно - Я предполагаю, что вероятности работают лучше таким образом. Попробуйте поискать в Google "minhash для обнаружения дубликатов"

Answer 2

Думаю, вы неправильно рассчитали сложность для всех комбинаций.Если сравнение одной строки со всеми другими строками является линейным, это означает, что из-за небольшой длины каждое сравнение равно O (1).Процесс сравнения каждой строки с любой другой строкой не экспоненциальный, а квадратичный, что не так уж и плохо.Проще говоря, вы сравниваете nC2 или n (n-1) / 2 пары строк, так что это просто O (n ^ 2)

Я не мог придумать, как вы можете отсортировать их по порядку, как вы не можетенаписать объективный компаратор, но даже если вы это сделаете, сортировка потребует O (nlogn) для сортировки слиянием, и, поскольку у вас так много записей, и, вероятно, вы бы предпочли не использовать дополнительную память, вы бы использовали быструю сортировку, которая принимает O (n ^2) в наихудшем случае, нет улучшения по сравнению с худшим временем грубой силы.

Answer 3

Вы можете использовать преобразователь Левенштейна , который «принимает [s] запросный термин и возвращает [s] все термины в словаре, которые находятся в пределах n орфографических ошибок от него». Вот демоверсия .

Answer 4

Парные сравнения всех записей O (N ^ 2) не экспоненциальные.В принципе, есть два способа сократить эту сложность.

Первый - это блокировка, когда вы сравниваете только записи, которые уже имеют что-то общее, что легко вычислить, например, первые три буквы или обычный n-грамм.Это в основном та же идея, что и локально-чувствительного хеширования.В библиотеке дедупликации Python реализован ряд методов блокировки, а документация дает хороший обзор общего подхода .

В худшем случае парное сравнение с блокировкойвсе еще O (N ^ 2).В лучшем случае это O (N).Ни лучший, ни худший случай на практике не встречаются.Как правило, блокирование уменьшает количество пар для сравнения более чем на 99,9%.

Существуют некоторые интересные альтернативные парадигмы для связи записей, которые не основаны на парных сравнениях.У них есть худшие гарантии сложности дела.Смотрите работы Бека Стортс и Майкла Вика.

Answer 5

Полагаю, это однократная уборка.Я думаю, что проблема не в том, чтобы делать так много сравнений, а в том, чтобы решить, какие сравнения стоит сделать.Вы упоминаете имена и адреса, поэтому смотрите эту ссылку , чтобы узнать о некоторых проблемах сравнения, которые у вас будут.

Это правда, что для сравнения миллиона нужно выполнить почти 500 миллиардов грубых сравнений.записи против самих себя, но это при условии, что вы никогда не пропустите какие-либо записи, ранее объявленные как совпадающие (то есть, никогда не делали «разрыв» из j-цикла в псевдокоде ниже).

Мои pokey E-машиныT6532 с частотой 2,2 ГГц способен выполнять 1,4 млн операций поиска и чтения в секунду 100-байтовых записей текстовых файлов, поэтому для 500 млрд. Сравнений потребуется около 4 дней.Вместо того, чтобы тратить 4 дня на исследование и написание какого-нибудь причудливого решения (только для того, чтобы обнаружить, что мне все еще нужны еще x дней, чтобы на самом деле выполнить прогон), и предположить, что моя процедура сравнения не может вычислить и сохранить ключи, которые я буду сравнивать, я 'я просто позволю ему перебрать все эти сравнения, пока я найду что-то еще:

for i = 1 to LASTREC-1
  seektorec(i)
  getrec(i) into a
  for j = i+1 to LASTREC
    getrec(j) into b
    if similarrecs(a, b) then [gotahit(); break]

Даже если данный прогон обнаруживает только простые для определения совпадения, мы надеемся, что он уменьшает оставшиеся несопоставленные записи доболее разумный меньший набор, для которого дальнейшие прогоны грубой силы не так трудоемки.

Но кажется маловероятным, что Similarrecs () не может независимо вычислить и сохранить части сравниваемого a + b, в которомВ этом случае гораздо более эффективный подход:

for i = 1 to LASTREC
  getrec(i) in a
  write fuzzykey(a) into scratchfile
sort scratchfile
for i = 1 to LASTREC-1
  if scratchfile(i) = scratchfile(i+1) then gothit()

Большинство баз данных могут выполнять вышеуказанное в одной командной строке, если вам разрешено вызывать собственный код для вычисления fuzzykey () каждой записи.

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

Answer 6

Отношения эквивалентности - особенно хорошие виды соответствия; они удовлетворяют трем свойствам:

• рефлексивность: для любого значения A, A ~ A
• симметрия: если A ~ B, то обязательно B ~ A
• транзитивность: если A ~ B и B ~ C, то обязательно A ~ C

Что делает их приятными, так это то, что они позволяют вам разбивать ваши данные на непересекающиеся наборы, так что каждая пара элементов в любом данном наборе связана ~. Итак, что вы можете сделать, это применить алгоритм union-find, чтобы сначала разбить все ваши данные, а затем выбрать один репрезентативный элемент из каждого набора в разделе; это полностью де-дублирует данные (где «дубликат» означает «связанный с ~»). Более того, это решение является каноническим в том смысле, что независимо от того, каких представителей вы случайно выбрали из каждого раздела, вы получаете одинаковое количество конечных значений, и каждое из конечных значений попарно не дублируется.

К сожалению, нечеткое сопоставление не является отношением эквивалентности, поскольку оно предположительно не транзитивно (хотя, вероятно, оно рефлексивно и симметрично). Результатом этого является то, что не существует канонического способа разделения данных; Вы можете обнаружить, что при любом способе разбиения данных некоторые значения в одном наборе эквивалентны значениям из другого набора или что некоторые значения из одного набора не эквивалентны.

Итак, какое поведение вы хотите именно в этих ситуациях?