Предварительный выбор вероятности для приближенного совпадения строк
Недавно мне было поручено разработать алгоритм проверки дубликатов записей клиентов в базе данных.
Структура БД довольно проста: десятки тысяч строк с полями, такими как FullName, Street, City, ZIP, Phone и т. Д.
Сначала немного истории:
Я провел несколько обширных исследований алгоритмов и решил, что каждое поле должно быть взвешено в определенном количестве.
с разными алгоритмами, так как не все работают одинаково хорошо при любых обстоятельствах.
Например, LastName имеет весовой коэффициент 0,50. Когда я оцениваю, я выбираю, какие алгоритмы использовать и как они влияют на окончательное решение:
Коэффициент 0,25: Яро Винклер
Фактор 0,60: сходство косинуса 2-грамм
Фактор 0,15: Дамерау, Левенштейн
Все работает хорошо, и с небольшой настройкой я обнаруживаю позитивы с небольшой ошибкой.
Все идет нормально. Однако, как вы можете себе представить, наличие времени выполнения O (n ^ 2) — или фактически E-формы от i = 0 до i = n — не очень эффективно при работе с десятками тысяч записей.
Излишне говорить, что агрессивная оптимизация, использование оптимизаций компилятора для скорости, многопоточности и т. Д. — это просто бандиты, поскольку реальная проблема заключается в сложности.
По сути, я ищу способ предварительной фильтрации потенциальных совпадений и провел три дня исследований по этому вопросу сейчас.
Я нашел некоторую ценную информацию о R-деревьях, R * -деревьях, KD-деревьях, евклидовых векторах, minhashing, et al.
Тем не менее, большая часть информации обо всем этом, в общем, довольно академична. Самый ценный ресурс, который я нашел, был в «Mining Massive Data Sets», глава 3.
Теперь к моему настоящему вопросу:
Я прочитал всю эту информацию, но я не уверен, как собрать все это вместе.
Я думал о какой-то индексации в древовидной или графической структуре данных, где я могу вставить строку и сказать: «Найдите мне все, у которых есть вероятность совпадения> 0,20».
Этот алгоритм должен быть очень быстрым. Затем, когда я получу список потенциальных (> 0,20) совпадений, я мог бы пойти и сравнить несколько элементов с моим «дорогим», но выборочным алгоритмом.
Это должно сократить время выполнения до очень разумного значения, я считаю.
Я пытался найти какой-то справочный код, чтобы делать то, что я хочу сделать выше, но, похоже, я не придумываю ничего, кроме научных статей.
Я нашел «simstring», которая фактически компилировалась, но, похоже, не очень хорошо соответствовала 7 тестовым записям.
Кто-нибудь может указать мне правильное направление? Наверняка кто-то уже сталкивался с этим раньше и нашел решение …
Заранее большое спасибо!
Постскриптум Я делаю это в C ++, но все образцы в C # / C / Java / PHP будут в порядке.
Решение
В качестве первого среза я выбрал бы те строки, которые достаточно близки к той же длине, с которой они могли бы соответствовать в пределах данной вероятности. Это не будет очень избирательным, но (если вы не укажете довольно свободные допуски), вероятно, удалит довольно большой процент невозможных совпадений очень быстро. (например, с метрикой редактирования, такой как Левенштейн, которая считает вставку как 1 операцию, если вы начинаете со строки длиной 5 и нуждаетесь в совпадении в течение 5 операций, то вы можете удалить все строки длиннее 10 без дальнейшего изучения).
Вопрос о том, будет ли это достаточно избирательным, чтобы перейти непосредственно к вашему дорогостоящему сравнению, остается под вопросом — очевидно, это будет зависеть от изменчивости длин строк, с которыми вы сравниваете.
Другие решения
Наконец-то мне удалось осуществить предварительный отбор, выполнив следующие действия:
1. Используйте определенные поля записи клиента, чтобы построить 2 грамма
2. Minhash 2Grams с семейством функций 6 minhash с 192-битной подписью
3. Используйте реализацию rtree библиотек boost :: geometry для создания 6-мерного пространственного индекса по сигнатурам.
4. Выберите ближайшие k (в моем случае 30) записей для записи, которую я сравниваю, и на этих кандидатах запустите оригинальное «дорогое» сравнение
5. Это уменьшает сложность с E (i, i = n, i = 1) до примерно 30n + m, где m — время, необходимое для построения индекса (на удивление, почти незначительное).
Теперь я могу выполнить 15 000 сравнений с высокой точностью за 60 секунд, и это в однопоточном тесте. Многопоточность до 4 или 8 ядер, это будет работать еще быстрее.