Как найти лучшее нечеткое соответствие для строки в большой базе данных строк

Question

У меня есть база данных строк (произвольной длины), которая содержит более одного миллиона элементов (потенциально больше).

Мне нужно сравнить предоставленную пользователем строку со всей базой данных и извлечь идентичную строку, если она существует, или иным образом вернуть наиболее близкое нечеткое совпадение (я) (сходство 60% или лучше). Время поиска в идеале должно быть меньше одной секунды.

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

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

Есть идеи, как по-другому подойти к этой проблеме или как построить индекс в памяти?

Answer 1

Эта статья, кажется, описывает именно то, что вы хотите.

Lucene (http://lucene.apache.org/) также реализует расстояние редактирования Левенштейна.

Answer 2

Вы не упомянули свою систему баз данных, но для PostrgreSQL вы могли бы использовать следующий модуль contrib: trgm - соответствие триграмм для PostgreSQL

Модуль pg_trgm contrib предоставляет функции и классы индексов для определения сходства текста на основе сопоставления триграмм.

Answer 3

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

Answer 4

https://en.wikipedia.org/wiki/Levenshtein_distance

В некоторых СУБД реализован алгоритм Левенштейна

(например, PostgreSql: http://www.postgresql.org/docs/9.1/static/fuzzystrmatch.html)

Answer 5

Очень подробное объяснение соответствующих алгоритмов содержится в книге Алгоритмы на строках, деревьях и последовательностях: информатика и вычислительная биология Дэн Гусфилд .

Answer 6

Вычислить хеш SOUNDEX (который встроен во многие механизмы баз данных SQL) и индексировать его.

SOUNDEX - это хэш, основанный на звучании слов, поэтому ошибки в написании одного и того же слова могут иметь одинаковый хэш SOUNDEX.

Затем найдите хэш SOUNDEX строки поиска и сопоставьте ее.

Answer 7

Поскольку объем данных велик, при вставке записи я вычисляю и сохраняю значение фонетического алгоритма в индексированном столбце, а затем ограничиваю (предложение WHERE) мои запросы на выборку в диапазоне этого столбца.