特里似乎适用于小字符串,但不适用于大文档,所以不确定(1-100 页的文本)。也许可以将倒排索引与后缀树结合起来,以达到两全其美的效果。或者可能使用将单词存储为节点的 b 树,并为每个节点使用一个特里树。没有把握。想知道什么是好的数据结构(b 树、链表等)。
我正在考虑搜索诸如普通书籍、网页和源代码之类的文档,因此仅将单词存储在倒排索引中的想法似乎不太正确。了解您是否需要针对每个解决方案的替代解决方案,或者是否有适用于所有解决方案的通用解决方案或它们的组合会有所帮助。
最佳答案
您确实需要在一天结束时使用倒排索引来交错每个查询词的匹配结果,但可以从 Trie 或哈希映射构建倒排索引。 trie 将允许模糊查找,而基于哈希映射的倒排索引仅允许对 token 进行精确查找。
要优化内存使用,您可以使用内存优化版本的 Trie,例如 Radix Tree或 Adaptive Radix Tree (艺术)。我使用 ART
取得了巨大的成功对于我一直在从事的开源模糊搜索引擎项目:https://github.com/typesense/typesense
使用 Typesense,我能够在大约 165 MB 的 RAM(磁盘上未压缩的大小为 85 MB)中索引大约 100 万个 Hacker News 标题。如果您的用例更具体并且不需要我添加到数据结构中的一些元数据字段,您可能可以进一步压缩它。
关于string - 用于快速全文搜索的数据结构,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50127290/