部分数值数组 - 模式匹配

数据挖掘 时间序列 数值 模糊分类
2022-03-15 14:20:38

我有一个线性数值数组source，我想查找/匹配test数组作为模式：

source = [39,36,23,21,28,36,30,22,34,37]
test = [36,23,21,28]

我们可以使用brute force或类似的方法来查找完全匹配，通过检查test数组从索引0到len(source)-len(test)

但在我们的问题中，我们也可以接受这种模式（顺序很重要）

test = [36,24,21,28] // changed 23 to 24

因为我们有很多不同的方法来解决这个问题（也许是模糊的！），我想知道一些解决方案的标题。

1个回答

根据您的定义（连续，顺序很重要，最大 +/-2 差异），这不是模糊匹配情况。这只是搜索子序列的一个小变种：

for i=0 to len(source)-len(test) {
  j=0
  while (j<len(test)) && (abs(source[i+j]-test[j]) <= 2) {
    j++
  if (j == len(test)) { 
     // match found
  }
}

这是简单的版本，如果效率是一个问题，有一个使用动态编程的更高效的版本。

其它你可能感兴趣的问题
上一篇NCF Recommender - 在模型输入中编码的目标，为什么它不容易过拟合？ 下一篇我应该如何为自定义数据集构建知识图？