Структура данных для быстрого полнотекстового поиска
Кажется, что trie будет работать для небольших строк, но не для больших документов, поэтому не уверен (1-100 страниц текста). Возможно, можно объединить инвертированный индекс с суффиксным деревом, чтобы получить лучшее из обоих миров. Или, возможно, используя b-дерево со словами, хранящимися в виде узлов, и деревом для каждого узла. Точно сказать не могу. Интересно, какой была бы хорошая структура данных (b-дерево, связанный список и т. д.).
Я подумываю о поиске документов, таких как обычные книги, веб-страницы и исходный код, поэтому идея хранить только слова в инвертированном индексе кажется не совсем правильной. Было бы полезно узнать, нужны ли вам альтернативные решения для каждого из них, есть ли общее, подходящее для всех, или их комбинация.
Ответы 1
Вам действительно нужен инвертированный индекс в конце дня для чередования результатов сопоставления для каждого из условий вашего запроса, но инвертированный индекс можно построить либо из Trie, либо из хеш-карты. Trie допускает нечеткий поиск, в то время как инвертированный индекс на основе хэш-карты допускает только точный поиск токена.
Чтобы оптимизировать использование памяти, вы можете использовать оптимизированные для памяти версии Trie, такие как Радиксное дерево или Адаптивное радиксное дерево (ART). Я добился большого успеха, используя ART для проекта нечеткой поисковой системы с открытым исходным кодом, над которым я работал: https://github.com/typesense/typesense
С помощью Typesense я смог проиндексировать около 1 миллиона заголовков Hacker News примерно в 165 МБ ОЗУ (несжатый размер на диске был 85 МБ). Вероятно, вы можете втиснуть его еще больше, если ваш вариант использования более конкретен и не требует некоторых полей метаданных, которые я добавил в структуру данных.
Взгляните на здесь, он обсуждает некоторые основы, но также перечисляет ряд решений с открытым исходным кодом (lucene, solr, ...)