基于位置倒排索引的NodeJS多词邻近搜索实现问询

一、当前索引结构与需求 #

我正在基于文本构建位置倒排索引，当前索引结构如下（欢迎提出优化建议）：

{
    "term": {
        "documentID": { "pageno": [positions], "pageno": [positions] },
        "documentID": { "pageno": [positions] }
    }
}

我需要在Node.js中实现支持2个及以上词汇的邻近搜索，邻近搜索定义：

形如X AND Y /3或X Y /2的查询为邻近查询，意为检索同时包含X和Y且二者间隔不超过3个词或2个词的文档。

我原本的思路是：为每个查询词从索引生成如下结构的搜索结果对象，再对比所有词汇在交集页面中的位置计算邻近度。

{
    "word": { "document1": { "page1": [positions], "page2": [positions] } }
}

比如查询nodejs hello world，在字符串hello extra words world more extra words nodejs中，邻近度为5（统计所有间隔词汇数量，不考虑查询词顺序）。

现有疑问 #

1. 当前索引结构是否高效？若高效，如何对比所有词汇在交集页面中的位置？
2. 若查询为"jakarta apache lucene"~3（3为最大允许邻近度），文本为jakarta jakarta apache lucene时，是否会匹配两次？

编辑补充 #

我已处理得到每个文档的如下结构（仅包含所有查询词都存在的页面）：

{
    "pageno": [
        [positions of word 1],
        [positions of word 2],
        [positions of word n]
    ]
}

示例：

{
    "1": [
        [1, 5, 6],
        [2, 41],
        [3, 7, 11]
    ],
    "2": [
        [1, 5, 6],
        [2, 41],
        [3, 7, 11]
    ]
}

现在需要基于上述位置数组，统计特定页面中满足位置差小于邻近度的查询文本出现次数。

二、问题解答 #

1. 索引结构效率与位置对比方案 #

索引结构效率分析

当前结构属于标准位置倒排索引的变体，在中小规模数据（百万级文档以内）下完全够用，但有两个优化点：

• 将pageno的字符串键改为数字类型，能节省内存并提升访问速度；
• 给每个term下的documentID按字典序排序，后续求多词文档交集时，可通过双指针法快速筛选，避免全量遍历。

如果是超大规模数据，还可以考虑将索引分片存储，或者引入前缀压缩进一步降低内存占用。

多词位置对比实现思路

基于你补充的页面位置数组，核心判断逻辑是：所有查询词的位置中，最大值与最小值的差值 ≤ 邻近度 + 查询词数量 - 1（因为间隔词数=最大位置-最小位置-查询词数量+1，要让间隔词数≤设定值，等价于该差值条件）。具体实现步骤如下：

1. 确保每个词的位置数组已排序（索引构建时就做排序，可省略此步）；
2. 用多路归并+滑动窗口遍历所有位置组合：
   • 初始化指针数组，每个指针对应一个词的位置数组起始位置；
   • 记录当前指针指向的所有位置的最大值和最小值；
   • 若满足差值条件，计数+1，然后移动最小位置对应的指针（尝试寻找更多符合条件的组合）；
   • 若不满足条件，直接移动最小位置对应的指针，缩小窗口范围；
   • 直到任意一个指针超出对应数组长度，停止遍历。

2. 重复词的匹配次数问题 #

会匹配两次：

• 第一个jakarta（位置1）、apache（位置3）、lucene（位置4）：最大值-最小值=3，满足≤3+3-1=5的条件；
• 第二个jakarta（位置2）、apache（位置3）、lucene（位置4）：最大值-最小值=2，同样满足条件。

如果需要去重（同一连续词组只算一次），可以在统计时记录已匹配的位置区间，避免重复计数；如果需要精确统计所有可能的组合，保留当前逻辑即可。

内容的提问来源于stack exchange，提问作者Exter