Частичное совпадение имен в миллионах записей

10

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

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

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

Мы ищем предложения для поиска в базе данных 30 миллионов записей или более в ближайшем будущем с процентным соответствием звука и правописания.

Основная функциональность

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

Given Name: Helen Hunt
Name in DB: Holly Hunter 

Обе части обоих имен не совпадают точно, но в некоторой степени, допустим, 80%, поэтому, если пользователь вводит 80%, то имя в БД должно отображаться как совпадающее имя.

bjan
источник
1
Вы используете SQL Server? Я вижу, вы отметили это asp.net. Думая о возможности сборки CLR, которая предотвратит сетевой трафик и позволит SQL-серверу управлять памятью.
RubberChickenLeader
@WindRaven мы используем как SQL Server, так и Oracle
bjan
1
Разве это не та же самая проблема с веб-сканированием, которую решает Google?
candied_orange
@bjan где хранятся имена? они хранятся в SQL Server?
RubberChickenLeader
Что вы ищете? Лучшие 100 имен, которые лучше всего соответствуют заданному запросу?
Док Браун

Ответы:

6

Не зная полной информации о том, что вам нужно, вы, вероятно, захотите сделать одно из следующих действий:

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

Для пользовательского или критически важного материала используйте существующий инструмент поиска.

Если вы просто чувствуете академичность ... Играйте с ngrams:

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

Предполагая, что вы хотите искать people, вы можете сделать что-то вроде:

_ people _________
personId: int
name: varchar
soundex_name: varchar

_ people_ngrams __
personId: int
ngramId: int

_ ngrams _________
ngramId: int
ngram: char(3)
count: int

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

search_ngrams = ngrammify(soundex(search_string));

notable_ngrams = select top 10 *
  from ngrams
  where ngram in (search_ngrams)
  order by count asc;

possible_matches = select top 1000 distinct people.*
  from people_ngrams, people
  where ngramId in (notable_ngrams);

best_matches = top 100 possible_matches
  ordered by Levenshtein_distance(match, soundex(search_string));

Используя что-то очень похожее на это (но с немного большей настройкой «популярности» ngram, черных списков, белых списков и т. Д.), Я видел такой алгоритм нечеткого слияния записей между наборами данных в массе, а также облегчения нестандартного нечеткого поиска утилиты и текущие усилия по устранению дублирования записей.

Теперь, в моем случае, я не сопоставлял миллионы записей, я искал, чтобы выбрать наилучшие возможные объединения двух наборов данных, порядка сотен тысяч записей каждый. И мы хотели, чтобы это работало довольно быстро - в течение нескольких минут. (Быстро, что такое 100 000 * 100 000?) И мы добились успеха.

Таким образом, при правильной настройке подобные вещи могут быть быстрыми и эффективными. В конечном итоге мы смогли создать объединенный набор на скромном устаревшем двухъядерном компьютере за несколько минут, а «сомнительные» объединения автоматически помечаются для просмотра вручную. Но потребовалось много времени, чтобы найти точку отсчета популярности / релевантности ngram, а также правильные пороговые значения расстояния между строками, черные списки и белые списки ... и т. Д.

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

Как Сфинкс или Люсен .

svidgen
источник
Я только что искал нечеткое в справочном руководстве по выпуску Sphinx 2.2.11 и похоже, что оно соответствует точному слову, тогда как мне нужно частично сопоставить слова. Поправь меня, если я ошибаюсь по этому поводу.
Бьян
@bjan Да. Глядя на документы дальше, я не уверен, что нечеткий поиск Сфинкса - это именно то, что вы ищете. Он может использовать морфологию Soundex . Но, основываясь на вашем недавнем редактировании, вы, возможно, захотите выполнить собственный поиск ngram + string-distance. И, как я сказал выше, может потребоваться некоторое время, чтобы настроить алгоритм и пороги, чтобы получить правильные значения; но это не невозможно. И если вам нужен этот уровень гибкости ...
svidgen
@bjan О, я также полностью забыл о Lucene . Я не уверен, что он делает то, что вам нужно; но он чертовски популярен, и на него стоит обратить внимание, прежде чем начать свой собственный. В документах Люсена упоминается нечеткий поиск и ранжирование с использованием расстояния строк Левенштейна.
svidgen