Мне недавно поручили разработать алгоритм проверки дубликатов записей клиентов в базе данных. макета DB довольно прост: десятки тысяч строк с полями, как FullName, улица, город, почтовый индекс, телефон, и т.д. ...Предварительный выбор вероятности для приближенного соответствия строк
Сначала немного:
Я сделал некоторые обширные исследования по алгоритмов, и решили, что каждое поле должно взвешиваться в определенной сумме с различными алгоритмами, поскольку не все они одинаково хорошо подходят при любых обстоятельствах. Например, LastName имеет коэффициент веса 0.50. Когда я оцениваю я выбирать, какие алгоритмы использовать и сколько они весят на окончательном решении:
фактора 0,25: JaroWinkler
Factor 0,60: косинус 2-гры Сходство
Factor 0,15: DamerauLevenshtein
Все работает хорошо, и с небольшой настройкой я обнаруживаю положительные результаты с небольшой ошибкой. Пока все хорошо. Однако, как вы можете себе представить, наличие времени выполнения O (n^2) - или фактически E-формы i = 0 до i = n - не очень эффективно при работе с десятками тысяч записей. Излишне говорить, что оптимизация с помощью оптимизации компилятора для скорости, многопоточности и т. Д. - это просто бандаиды, так как реальной проблемой является сложность.
По существу, я ищу способ предварительной фильтрации потенциальных совпадений и провел три дня исследований по этому вопросу. Я нашел ценную информацию о R-деревьях, R * -Trees, KD-деревьях, евклидовых векторах, minhashing и др. Тем не менее, большая часть информации обо всех этих, ну, весьма высокообразовательная. Самый ценный ресурс, я нашел в «Mining Наборов Массивных данных», глава 3.
Теперь мой вопрос:
Я прочитал всю эту информацию, но я не знаю, как поставить его все вместе.
Я думал о некотором индексировании в структуре данных дерева или графа, где я могу положить строку и сказать «Найди мне все, что имеет вероятность совпадения> 0,20». Этот алгоритм должен быть очень быстрым. Затем, когда я получаю список потенциальных (> 0.20) совпадений, я мог бы пойти и сравнить несколько элементов с моим «дорогим», но выборочным алгоритмом. Это должно сократить время выполнения до очень разумного значения, которое я считаю.
Я пытаюсь найти какой-то ссылочный код, чтобы делать то, что хочу делать выше, но я, кажется, не придумываю ничего, кроме научных статей. Я нашел «simstring», который на самом деле скомпилирован, но, похоже, не очень хорошо соответствовал 7 тестовым записям. Может ли кто-нибудь указать мне в правильном направлении? Конечно, кто-то должен был столкнуться с этим раньше и нашел решение ...
Спасибо вам большое!
P.S. Я делаю это в C++, но любые образцы в C#/C/Java/PHP будут в порядке.
Спасибо, что это определенно полезно. Об этом они говорили в главе 3 книги по интеллектуальному анализу. Я думаю, что длина строки может быть жизнеспособной, но не Левенштейном (иногда в записях есть почитаемые поля, такие как «Джон Смит» и «Смит, Джон», где Левенштейн ошибочно устраняет их как совпадение). Я дам длину строки и сравните время выполнения. У вас есть какой-либо вклад в жизнеспособность других вариантов (R/KD Tree и т. Д.), Упомянутых тоже? По крайней мере, почему они не будут красивыми (кроме сложности)? – namezero