快速全文搜索的数据结构

Question

一棵 trie 树看起来适用于小型字符串，但对于大文档则不太适合（如 1-100 页的文本）。也许可以将倒排索引与后缀树结合起来，以获得两者的优点。或者使用 B 树，将单词存储为节点，并在每个节点上使用一棵 trie 树。不确定哪种数据结构更好（是 B 树、链表等）。

我想要搜索文档，例如普通书籍、网页和源代码，因此仅将单词存储在倒排索引中的想法似乎不太合适。希望了解是否需要针对每个文档类型提供替代解决方案，或者是否有一种通用解决方案适用于所有文档类型，或者它们都需要组合使用。

- Lance

---

请看这里，它讨论了一些基础知识，还列出了一些开源解决方案（lucene、solr等）。 - TilmannZ

如果您想支持近似搜索（拼写错误等），标准方法可能是n-grams。这里是Google n-gram查看器。 - TilmannZ

Answer 1

最终，您确实需要一个倒排索引来交错匹配每个查询词的结果，但倒排索引可以从Trie或哈希映射构建。 Trie允许模糊查找，而基于哈希映射的倒排索引仅允许对令牌进行精确查找。

为了优化内存使用，您可以使用内存优化版本的Trie，例如 Radix Tree或 Adaptive Radix Tree（ART）。我在一个开源模糊搜索引擎项目中使用了 ART 并取得了巨大成功： https://github.com/typesense/typesense 通过Typesense，我能够在大约165 MB的RAM中索引约1百万条Hacker News标题（磁盘上未压缩的大小为85 MB）。如果您的用例更具体，并且不需要我添加到数据结构的某些元数据字段，则可能可以进一步压缩它。

- jeffreyveon