在特定累积距离下，查找数组中出现的总次数。

Question

我正在构建一种在位置倒置索引- Implementing proximity search in positional inverted index nodejs中进行近距离搜索的方法。这是个子问题。

我有一个数组数组，包含页面上不同单词的位置。

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

就像-

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

对于每个pageNo，我希望找到出现的次数，以便单词位置之间的差异之和不超过指定的值(proximity)。

如果proximity的值为1，则所有单词之间不应超过一个单词。因此，“”应该与“nodejs中的Hello”匹配，因为在- ' in‘之间只有一个单词。但是，它与nodejs中的“hello from world in”不匹配，因为在“from”和“in”之间总共有两个单词。

请注意，混乱的词语是允许的。

如何在JavaScript中做到这一点？-我试图做一些类似于Finding matches between multiple JavaScript Arrays的事情，但无法进行必要的更改以使其在这里工作。

上述情况的预期产出为(接近: 2)：

{
    1 : 3,
    2 : 3
}

第1页：(1,2,4)-Proximity (2 -1 )+(4-2 -1)=1，(5,2,4)-邻近(5-4 -1)+(4-2 -1)=1和(6,2,4)

第2页：(1,2,3)，(5,2,3)，(6,2,3)

Answer 1

我使用another answer中的“笛卡尔积”函数。然后对计算项目间最大差的每个结果进行排序。检查这与接近，并增加计数，如果合法。

更新:根据评论修正距离公式。此外，sort在这里需要显式转换为数字。(为什么？(请在下面的评论中告诉我)

​

var input = {
  1: [
    [1, 5, 6],
    [2, 41],
    [4, 7, 11]
  ],
  2: [
    [1, 5, 6],
    [2, 41],
    [3, 7, 11]
  ]
}

function cartesianProduct(arr) {
  return arr.reduce(function(a, b) {
    return a.map(function(x) {
      return b.map(function(y) {
        return x.concat([y]);
      })
    }).reduce(function(a, b) {
      return a.concat(b)
    }, [])
  }, [
    []
  ])
}

function distance(arr) {
  arr.sort(function(a,b) {
    return +a - +b;
  });
  var total = 0;
  for (var i = 1; i < arr.length; i++) {
    total += (arr[i] - arr[i - 1] - 1)
  }
  return total;
}

function count_index(arrs, proximity) {
  var product = cartesianProduct(arrs);
  var count = 0;
  product.forEach(function(series) {
    if (distance(series) <= proximity) {
      console.log("found: " + series)
      count++
    }
  })
  return count
}

var result = {}
var proximity = 2;
Object.entries(input).forEach(function([key, value]) {
  result[key] = count_index(value, proximity)
})
console.log(result)

​