面向共现查询与文档检索的高效数据结构选型咨询

背景 #

现有1000万份文档，每份是约100个唯一tokens的词袋模型，全局词汇表V规模约5万。需要支持两个核心查询需求，且要求无需遍历所有文档。

需求2：查找包含指定tokens的所有文档 #

这个需求是基础场景，最直接且高效的方案是倒排索引：

• 为每个token t ∈ V 维护一个有序的文档ID列表，记录所有包含t的文档。
• 查询时，对指定tokens对应的文档列表求交集即可得到结果：
  • 若文档列表是有序的，用归并法逐一遍历列表找共同ID，时间复杂度与列表长度之和成正比；
  • 若追求极致性能，可将文档列表用**位图（Bitmask）**存储：每个token对应一个长度为1000万的二进制位串，某位置为1表示对应文档包含该token。交集操作直接是按位与运算，速度极快。不过5万token的位图总内存约62.5GB，需结合磁盘存储+热门token内存缓存的方式优化；
  • 也可以用跳表、B树等结构优化文档列表的有序性，进一步加速交集计算。

需求1：查找与指定tokens共现的所有tokens #

需求本质是：找到所有u ∈ V，存在至少一份文档同时包含指定tokens集合T和u。推荐两种精准方案：

方案1：基于倒排索引的联动查询 #

1. 先用需求2的方法，找到所有包含T的文档集合D；
2. 收集D中所有文档的tokens，去重后剔除T本身的tokens，得到结果。
   • 优化点：提前为每个文档建立token集合的快速访问结构（比如将每个文档的tokens存入哈希集合或有序数组），若D的规模不大（比如数千到数万级），这个方法速度极快；
   • 若D规模很大（比如百万级），可以将文档按块划分，每个块维护该块内所有文档的tokens的全局集合，先过滤出包含T的块，再在块内收集tokens，减少遍历范围。

方案2：预计算高频组合的共现表 #

如果某些token组合T是高频查询项，可以提前预计算这些T对应的共现tokens集合，存入哈希表。查询时直接查表返回，无需实时计算。但该方案仅适合高频固定组合，无法覆盖任意T的查询。

注：如果允许近似结果，可以用Word2Vec、GloVe等词向量模型，将tokens映射到向量空间，通过向量相似度筛选近似共现的tokens，但结果不保证精确匹配。

内容的提问来源于stack exchange，提问作者namespace-Pt