Мы разработали веб-приложение для сопоставления имен. Он работает, разбивая имена на части, а значение Soundex каждой части сохраняется в базе данных. Показатель расстояния Левенштейн используются для применения процентного соответствия звука, а также написания против данного имени.
Во время выполнения мы загружаем все записи в память и применяем расстояние Левенштейна ко всем значениям Soundex и правописанию всех частей всех имен.
Сначала это работало нормально, потому что было максимум 20 тысяч имен, но теперь у одного из наших клиентов есть 30 миллионов имен. Загрузка этого огромного списка в память для каждого запроса и применение этого типа сопоставления - жалкий подход, использующий много памяти и времени выполнения.
Мы ищем предложения для поиска в базе данных 30 миллионов записей или более в ближайшем будущем с процентным соответствием звука и правописания.
Основная функциональность
Конечный пользователь вводит имя для сопоставления и минимальный процент. Мы должны показать все те имена в базе данных, для которых любая часть имени совпадает с любой частью имени до заданного процента. Полное имя не должно совпадать, любая часть, если она соответствует проценту, является успешной. Например.
Given Name: Helen Hunt
Name in DB: Holly Hunter
Обе части обоих имен не совпадают точно, но в некоторой степени, допустим, 80%, поэтому, если пользователь вводит 80%, то имя в БД должно отображаться как совпадающее имя.
Ответы:
Не зная полной информации о том, что вам нужно, вы, вероятно, захотите сделать одно из следующих действий:
Я не полностью знаю, что связано с установкой и настройкой sphinx; но у меня сложилось впечатление, что вы можете указать его в базе данных, указать, какие поля индексировать, как взвесить результаты, и он вернет вам упорядоченный список соответствующих записей.
Для пользовательского или критически важного материала используйте существующий инструмент поиска.
Если вы просто чувствуете академичность ... Играйте с ngrams:
Таблица поиска ngrams может служить вашим начальным набором потенциальных совпадений, и вы можете использовать расстояния Левенштейна для сокращения и сортировки результатов.
Предполагая, что вы хотите искать
people
, вы можете сделать что-то вроде:Вы можете либо периодически перестраивать свои ngram, либо создавать их на лету. В любом случае, простой, наивный алгоритм поиска может выглядеть так:
Используя что-то очень похожее на это (но с немного большей настройкой «популярности» ngram, черных списков, белых списков и т. Д.), Я видел такой алгоритм нечеткого слияния записей между наборами данных в массе, а также облегчения нестандартного нечеткого поиска утилиты и текущие усилия по устранению дублирования записей.
Теперь, в моем случае, я не сопоставлял миллионы записей, я искал, чтобы выбрать наилучшие возможные объединения двух наборов данных, порядка сотен тысяч записей каждый. И мы хотели, чтобы это работало довольно быстро - в течение нескольких минут. (Быстро, что такое 100 000 * 100 000?) И мы добились успеха.
Таким образом, при правильной настройке подобные вещи могут быть быстрыми и эффективными. В конечном итоге мы смогли создать объединенный набор на скромном устаревшем двухъядерном компьютере за несколько минут, а «сомнительные» объединения автоматически помечаются для просмотра вручную. Но потребовалось много времени, чтобы найти точку отсчета популярности / релевантности ngram, а также правильные пороговые значения расстояния между строками, черные списки и белые списки ... и т. Д.
Сказав это , вы действительно можете засосать в дыру, работая над этим материалом. Для любой реального мира вещи производства на уровень, вы должны вообще использовать устоявшийся инструмент , который уже сделал и оптимизированный для такого рода поиска.
Как Сфинкс или Люсен .
источник