快速全文搜索的数据结构
Data structure for fast full text search
一个 trie 似乎适用于小字符串，但不适用于大型文档，所以不确定（1-100 页的文本）。也许可以将倒排索引与后缀树结合起来，两全其美。或者可能使用将单词存储为节点的 b 树，并为每个节点使用一个 trie。不确定。想知道什么是好的数据结构（b 树、链表等）。
我正在考虑搜索常规书籍、网页和源代码等文档，因此在倒排索引中仅存储单词的想法似乎不太正确。了解您是否需要针对每个解决方案的替代解决方案，或者是否有适用于所有解决方案的通用解决方案，或者它们的组合，这将很有帮助。
您确实需要在一天结束时使用倒排索引来交织每个查询词的匹配结果，但是可以从 Trie 或哈希映射构建倒排索引。特里树允许模糊 look-ups，而基于散列图 inverted-index 只允许精确查找标记。
要优化内存使用，您可以使用 Trie 的内存优化版本，例如 Radix Tree or Adaptive Radix Tree (ART). I've had great success using ART for an open source fuzzy search engine project I've been working on: https://github.com/typesense/typesense
使用 Typesense，我能够在大约 165 MB 的 RAM 中索引大约 100 万个 Hacker News 标题（磁盘上未压缩的大小为 85 MB）。如果您的用例更具体并且不需要我添加到数据结构中的一些元数据字段，您可以进一步压缩它。
一个 trie 似乎适用于小字符串，但不适用于大型文档，所以不确定（1-100 页的文本）。也许可以将倒排索引与后缀树结合起来，两全其美。或者可能使用将单词存储为节点的 b 树，并为每个节点使用一个 trie。不确定。想知道什么是好的数据结构（b 树、链表等）。
我正在考虑搜索常规书籍、网页和源代码等文档，因此在倒排索引中仅存储单词的想法似乎不太正确。了解您是否需要针对每个解决方案的替代解决方案，或者是否有适用于所有解决方案的通用解决方案，或者它们的组合，这将很有帮助。
您确实需要在一天结束时使用倒排索引来交织每个查询词的匹配结果，但是可以从 Trie 或哈希映射构建倒排索引。特里树允许模糊 look-ups，而基于散列图 inverted-index 只允许精确查找标记。
要优化内存使用，您可以使用 Trie 的内存优化版本，例如 Radix Tree or Adaptive Radix Tree (ART). I've had great success using ART for an open source fuzzy search engine project I've been working on: https://github.com/typesense/typesense
使用 Typesense，我能够在大约 165 MB 的 RAM 中索引大约 100 万个 Hacker News 标题（磁盘上未压缩的大小为 85 MB）。如果您的用例更具体并且不需要我添加到数据结构中的一些元数据字段，您可以进一步压缩它。