Как найти лучшее нечеткое соответствие для строки в большой базе данных строк
У меня есть база данных строк (произвольной длины), которая содержит более одного миллиона элементов (потенциально больше).
Мне нужно сравнить предоставленную пользователем строку со всей базой данных и извлечь идентичную строку, если она существует, или иным образом вернуть самое близкое нечеткое совпадение (я) (сходство 60% или лучше). Время поиска в идеале должно быть меньше одной секунды.
Моя идея состоит в том, чтобы использовать расстояние редактирования для сравнения каждой строки БД со строкой поиска после сужения кандидатов из БД на основе их длины.
Однако, поскольку мне нужно будет выполнять эту операцию очень часто, я думаю о создании индекса строк db для хранения в памяти и запроса индекса, а не непосредственно db.
Любые идеи о том, как подойти к этой проблеме по-другому или как построить индекс в памяти?
7 ответов
Эта статья, кажется, описывает именно то, что вы хотите.
Lucene ( http://lucene.apache.org/) также реализует расстояние редактирования Левенштейна.
Вы не упомянули свою систему баз данных, но для PostrgreSQL вы могли бы использовать следующий модуль contrib: trgm - сопоставление триграмм для PostgreSQL
Модуль pg_trgm contrib предоставляет функции и классы индексов для определения сходства текста на основе сопоставления триграмм.
Если ваша база данных поддерживает это, вы должны использовать полнотекстовый поиск. В противном случае вы можете использовать такой индексатор, как lucene и его различные реализации.
Вычислить хеш SOUNDEX (который встроен во многие механизмы баз данных SQL) и индексировать его.
SOUNDEX - это хэш, основанный на звучании слов, поэтому ошибки в написании одного и того же слова могут иметь одинаковый хэш SOUNDEX.
Затем найдите хэш SOUNDEX строки поиска и сопоставьте ее.
Поскольку объем данных велик, при вставке записи я бы вычислял и сохранял значение фонетического алгоритма в индексированном столбце, а затем ограничивал (предложение WHERE) мои запросы на выборку в диапазоне этого столбца.
https://en.wikipedia.org/wiki/Levenshtein_distance
Алгоритм Левенштейна был реализован в некоторых СУБД
(Например, PostgreSql: http://www.postgresql.org/docs/9.1/static/fuzzystrmatch.html).
Очень подробное объяснение соответствующих алгоритмов содержится в книге Дэна Гусфилда " Алгоритмы на строках, деревьях и последовательностях: компьютерные науки и вычислительная биология".