Структура данных для быстрого полнотекстового поиска

Question

Похоже, что три подходит для небольших строк, но не для больших документов, поэтому не уверен (1-100 страниц текста). Возможно, можно объединить инвертированный индекс с деревом суффиксов, чтобы получить лучшее из обоих миров. Или, возможно, используя b-дерево со словами, хранящимися как узлы, и три для каждого узла. Точно сказать не могу. Хотите знать, какой будет хорошая структура данных (b-дерево, связанный список и т. Д.).

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

Answer 1

Вам нужен инвертированный индекс в конце дня для чередования результатов сопоставления для каждого из ваших условий запроса, но инвертированный индекс можно построить либо из Trie, либо из Hash Map. Три позволили бы нечеткие поиски, в то время как инвертированный индекс на основе хэш-карты позволял бы только точный поиск токена.

Для оптимизации использования памяти вы можете использовать оптимизированные для памяти версии Trie, такие как Radix Tree или Adaptive Radix Tree (ART). Я имел большой успех, используя ART для проекта нечеткой поисковой системы с открытым исходным кодом, над которым я работал: https://github.com/typesense/typesense

С Typesense я смог проиндексировать около 1 миллиона заголовков Hacker News в 165 МБ ОЗУ (размер несжатого диска составил 85 МБ). Вероятно, вы можете сжать его еще дальше, если ваш вариант использования более конкретен и вам не нужны поля метаданных, которые я добавил в структуру данных.