Сравнение больших массивов

Question

У меня есть ~ 25.000 различных имен в базе данных SQL, и я хотел бы выполнить сравнение расстояний между ними для нормализации, например. John Doe & Jhon Doe.

Когда db было всего около 1000 имен, я использовал для хранения всех различных имен в массиве. Затем я использовал бы два цикла for-loops на этом массиве, тем самым сравнивая каждый элемент в массиве с каждым из остальных. Когда расстояние редактирования дало совпадение, скажем,> 0,9, я бы выполнил SQL-запрос, заменяя одно значение для другого во всех записях.

С моей гораздо большей базой данных это невозможно. Что бы вы сделали, ребята?

ps: Мне также интересны любые многопоточные решения для этого, потому что процесс уходит сейчас.

имп: Я кодирование в Java

Answer 1

Как насчет вычисления soundex каждого из ваших имен и, возможно, его сохранения в базе данных? Вы даже можете сделать это на стороне БД, например, есть a MySQL SOUNDEX function.

После вычисления soundex каждого имени все, что вам нужно сделать, это группировать строки по одинаковому soundex.

EDIT:

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

Answer 2

Там нет никакого способа вокруг согласования парного: так же эффективно, как он получает.

Если вам нужно сделать вашу запись связи быстрее, попробуйте использовать строку, расстояние метрику, что требует меньше вычислений, чем редактирование расстояние (Bonacci distance, Jaro–Winkler distance и т.д.)

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