用于快速全文搜索的数据结构

Question

特里似乎适用于小字符串，但不适用于大文档，所以不确定（1-100 页的文本）。也许可以将倒排索引与后缀树结合起来，以达到两全其美的效果。或者可能使用将单词存储为节点的 b 树，并为每个节点使用一个特里树。没有把握。想知道什么是好的数据结构（b 树、链表等）。

我正在考虑搜索诸如普通书籍、网页和源代码之类的文档，因此在倒排索引中仅存储单词的想法似乎不太正确。了解您是否需要针对每个解决方案的替代解决方案，或者是否有适用于所有解决方案的通用解决方案或它们的组合会有所帮助。

Answer 1

您确实需要一个倒排索引来交错每个查询词的匹配结果，但倒排索引可以从 Trie 或哈希映射构建。trie 允许模糊查找，而基于倒排索引的哈希图则只允许精确查找标记。

要优化内存使用，您可以使用 Trie 的内存优化版本，例如基数树或自适应基数树(ART)。ART我在我一直致力于的开源模糊搜索引擎项目中取得了巨大成功：https: //github.com/typesense/typesense

借助 Typesense，我能够在大约 165 MB 的 RAM 中索引大约 100 万个黑客新闻标题（磁盘上未压缩的大小为 85 MB）。如果您的用例更具体并且不需要我添加到数据结构中的一些元数据字段，您可能可以进一步压缩它。