JavaScript实现：统计位置倒排索引中符合proximity阈值的组合次数

问题分析 #

我们需要统计每个页码下，所有多词位置组合（每个词取一个位置）中，满足「位置累计差值之和不超过指定proximity值」的数量。结合邻近搜索的场景，最合理的“累计差值之和”定义为：将组合中的位置排序后，相邻位置的差值之和（等价于最大位置与最小位置的差，即极差）。如果你的需求是其他定义，可以直接调整判断逻辑。

实现方案 #

1. 暴力枚举法（适用于小规模数据）

直接生成所有词位置的笛卡尔积，逐个判断是否符合条件。逻辑简单易懂，但当词位置数组较大时性能会急剧下降。

// 生成多个数组的笛卡尔积
function cartesianProduct(arrays) {
  return arrays.reduce((acc, curr) => {
    return acc.flatMap(prev => curr.map(currVal => [...prev, currVal]));
  }, [[]]);
}

// 统计符合条件的组合数
function countProximityMatches(data, proximity) {
  const result = {};
  
  for (const pageno in data) {
    const wordPositions = data[pageno];
    const combinations = cartesianProduct(wordPositions);
    let validCount = 0;
    
    for (const combo of combinations) {
      // 计算组合的极差（等价于排序后相邻差值之和）
      const minPos = Math.min(...combo);
      const maxPos = Math.max(...combo);
      if (maxPos - minPos <= proximity) {
        validCount++;
      }
    }
    
    result[pageno] = validCount;
  }
  
  return result;
}

// 测试示例数据
const sampleData = {
  1: [
    [1, 5, 6],
    [2, 41],
    [4, 7, 11]
  ],
  2: [
    [1, 5, 6],
    [2, 41],
    [3, 7, 11]
  ]
};

console.log(countProximityMatches(sampleData, 2));

2. 优化多指针法（适用于大规模数据）

暴力法时间复杂度为O(M₁M₂...*Mn)（Mn为第n个词的位置数量），大规模数据下效率极低。我们可以用多指针结合滑动窗口的思路，减少不必要的枚举：

1. 确保每个词的位置数组按升序排序（输入已排序可跳过此步骤）。
2. 维护每个词的指针，初始都指向数组开头。
3. 计算当前指针指向位置的极差，若≤proximity则统计所有以当前最小位置为基准的有效组合数；若极差>proximity则移动指向最小位置的指针。

function countProximityMatchesOptimized(data, proximity) {
  const result = {};
  
  for (const pageno in data) {
    let wordPositions = data[pageno].map(arr => [...arr].sort((a, b) => a - b)); // 确保数组升序
    const pointers = new Array(wordPositions.length).fill(0);
    let validCount = 0;
    const n = wordPositions.length;
    
    while (true) {
      // 获取当前指针指向的所有位置
      const currentPositions = pointers.map((idx, i) => wordPositions[i][idx]);
      const minVal = Math.min(...currentPositions);
      const maxVal = Math.max(...currentPositions);
      const minIndex = currentPositions.indexOf(minVal);
      
      if (maxVal - minVal <= proximity) {
        // 统计所有以当前min位置为基准的有效组合
        let count = 1;
        for (let i = 0; i < n; i++) {
          if (i === minIndex) continue;
          // 找到当前词中≤maxVal的位置数量
          let cnt = 0;
          while (pointers[i] + cnt < wordPositions[i].length && wordPositions[i][pointers[i] + cnt] <= maxVal) {
            cnt++;
          }
          count *= cnt;
        }
        validCount += count;
        
        // 移动最小位置的指针
        pointers[minIndex]++;
        if (pointers[minIndex] >= wordPositions[minIndex].length) break;
      } else {
        // 极差超过阈值，移动最小位置的指针
        pointers[minIndex]++;
        if (pointers[minIndex] >= wordPositions[minIndex].length) break;
      }
    }
    
    result[pageno] = validCount;
  }
  
  return result;
}

// 测试优化方法
console.log(countProximityMatchesOptimized(sampleData, 2));

关于示例结果的说明 #

按照“极差≤proximity”的逻辑，示例数据运行暴力法得到的结果是{1:0, 2:1}，和你给出的预期输出{1:3,2:3}不符。这说明我们对“累计差值之和”的定义可能存在偏差。如果你的需求是其他定义，可以修改判断逻辑：

• 若为两两位置差的绝对值之和：将判断条件改为

  const sum = combo.reduce((total, val, i) => {
    for (let j = i+1; j < combo.length; j++) {
      total += Math.abs(val - combo[j]);
    }
    return total;
  }, 0);
  if (sum <= proximity) validCount++;
  

• 若为特定词序下的差值之和（比如词1位置<词2位置<...<词n位置，计算相邻差之和）：需要在生成组合时过滤词序，再计算差值之和。

请根据实际需求调整判断逻辑。

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