Какая структура данных лучше всего подходит для быстрого поиска текстовых данных?

Question

При просмотре таких продуктов, как DnD Insider и приложение Kindle, пользователи могут быстро найти подходящие текстовые строки в большой структуре текстовых данных. Если бы мне нужно было создать веб-приложение, которое позволяло бы пользователям быстро искать в «своде правил» (или аналогичном тексте) соответствующую запись и извлекать данные для чтения, как мне организовать данные?

Я не думаю, что это хорошая идея - поместить все данные в память. Но если бы я хранил его в какой-то базе данных, что было бы хорошим способом поиска в базе данных и получения соответствующей соответствующей записи?

Пока, я думаю, что я собираюсь использовать алгоритм Бойера-Мура, чтобы фактически выполнить поиск. Я могу поместить различные разделы текста-правила в разные записи базы данных. Пользовательский поиск будет иметь приоритет при поиске заголовков разделов над текстом основного раздела. Поскольку текст будет статичным и не будет редактироваться пользователем, возможно, будет работать массив для хранения каждого слова?

Answer 1

Обычно для этой цели используется какой-то инвертированный индекс : https://en.wikipedia.org/wiki/Inverted_index

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

Результаты поискаобычно ранжируется с некоторым вариантом tf-idf: https://en.wikipedia.org/wiki/Tf%E2%80%93idf