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

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

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

Моя идея - использовать расстояние редактирования для сравнения каждой строки db с поисковой строкой после сужения кандидатов из db на основе их длины.

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

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

Ответы

Ответ 2

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

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

Ответ 3

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

Ответ 4

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

Ответ 5

Вычислить хэш SOUNDEX (который встроен во многие СУБД SQL) и индексировать его.

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

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

Ответ 6

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