Подобный алгоритм данных

Question

У меня есть пара БД с информацией о пользователях, каждая из которых содержит от 10 до 20 тысяч записей, каждая из нескольких разных источников, и каждая постоянно растет. Я пытаюсь создать инструмент, который может в пределах определенного допуска замечать похожие электронные письма или похожие имена (первый + '' + последний). Я использую базу данных MySQL и могу работать с C ++ или PHP для сравнения. Может ли кто-нибудь предложить какие-либо существующие решения / учебные пособия, которые позволили бы мне просто выполнить проверку базы данных или массива данных и вернуть возможные дубликаты? Я бы хотел, чтобы он обнаружил несколько распространенных ошибок, подобных этим:

josh@test.com <> josh@test.test.com <> jash@test.com
Josh O <> josh t O <> Joshua O

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

Answer 1

У меня есть отличные новости для вас и несколько ужасных новостей для вас.

Хорошая новость заключается в том, что в PHP есть реализации нескольких алгоритмов для сравнения строк, встроенных в:

• similar_text
• levenshtein

У него также есть два относительно популярных способа разбить английские слова на более простые представления, подходящие для сравнения:

• soundex
• metaphone

Хотя это хорошая новость, ужасная новость заключается в том, что с записями по 10–20 тыс. Вам потребуется выполнить где-то около полутора метрических сравнений, если вы используете первые два варианта, и они не великие исполнители. Я не слишком уверен в том, что это было бы в нотации big-O, но я думаю, что это где-то в диапазоне O(run away).

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

Answer 2

Учитывая максимальное расстояние до символа, это звучит как работа для алгоритма bitap (Ву и Мэнбер, «Быстрый поиск с ошибками текста») .Это основной алгоритм программы agrep, и он может быть довольно быстрым, когда число допустимых ошибок символов ограничено.Реализацию Google в форме библиотеки для нескольких языков можно найти здесь . (код для выполнения приблизительного сопоставления относительно короткий и хорошо задокументированный.)

Вы все еще смотрите на O (n ² ) - общее количество сравнений электронной почты с электронной почтой (~ 400M для электронной почты 20k).Но хорошо настроенная реализация хорошей функции сравнения, такой как bitap, должна помочь уменьшить константу.Вы также можете отбросить кучу сравнений, разделив электронные письма на группы по длине и сопоставив только электронные письма между группами, размер которых ограничен (например, если вы допускаете разницу в 3 символа, этобессмысленно сравнивать любые 10-символьные электронные письма с любыми 20-символьными.)Вы также должны иметь возможность распараллеливать сравнения, если у вас есть многоядерный компьютер.Опять же, это сокращение константы, а не порядка, но я предполагаю, что хорошая реализация C ++ на быстрой машине может справиться с этим за пару минут.

Answer 3

Это будет зависеть от вашего понятия «сходство».Если вы ищете количество символов, которое нужно вставить, удалить или заменить, чтобы преобразовать одну строку в другую, алгоритм называется Расстояние Левенштейна .Имейте в виду, однако, что это довольно медленно для длинных строк (поскольку каждое сравнение использует ряд операций, которые пропорциональны mn , где m и n являются длинами сравниваемых строк), но если ваши данные являются адресами электронной почты и другими короткими строками, у вас все будет в порядке (и вашей самой большой проблемой будет количество сравнений, так как вам нужно будет сравнить каждую пару строк с каждымпрочее).