c - 模式识别 - "is this a pattern?"

Question

我有一个很大的数字 vector ，比如 500 个数字。我想要一个程序根据以下规则检测此类 vector 中的模式(在这种情况下重复出现):

如果满足以下条件，则数字序列是一种模式:

• 序列的大小在 3 到 20 个数字之间。

• 序列中数字的相对位置在 在 vector 中至少有一次。所以假设我有一个序列 (1,4,3) 然后 (3,6,5) 在 vector 中的其他地方然后 (1,4,3) 是 一种模式。 (以及 (2,5,4)、(3,6,5) 等)

• 序列不能相交。所以， vector (1,2,3,4,5) 不 包含模式 (1,2,3) 和 (3,4,5)(我们不能使用相同的数字 两个序列)。但是，(1,2,3,3,4,5) 确实包含一个模式 (1,2,3)(或(3,4,5))

• 只有当 A 出现在某处时，模式 B 的子集 A 才是模式 否则在 B 之外。因此， vector (1,2,3,4,7,8,9,2,3,4,5) 将包含 模式 (1,2,3,4) 和 (1,2,3)，因为 (1,2,3,4) 重复(在 (2,3,4,5)) 和 (1,2,3) 的形式重复(以 (7,8,9) 的形式)。 但是，如果 vector 是 (1,2,3,4,2,3,4,5)，则唯一的模式将 是 (1,2,3,4)，因为 (1,2,3) 仅出现在 (1,2,3,4) 的上下文中。

我想知道几件事:

首先，我希望规则不会相互冲突。它们是我自己制作的，所以可能会有我没有注意到的冲突，如果您注意到了，请告诉我。

其次，如何以最有效的方式实现这样的系统？也许有人可以指出有关该主题的某些特定文献？我可以逐个编号，从搜索 3 的所有子集的序列重复开始，然后是 4,5，直到 20。但这似乎不是很有效。 我对用 C 语言实现这样的系统很感兴趣，但非常欢迎任何一般性指导。

提前致谢!

Answer 1

只是一些观察:

如果您对相对值感兴趣，那么您的第一步应该是计算 vector 的相邻元素之间的差异，例如:

Original numbers:
1   4   3   2   5   1   1   3   6   5   6   2   5   4   4   4   1   4   3   2
*********                   *********       *********           *********
Difference values:
  3   -1  -1  3   -4  0   2   3   -1  1   4   3   -1  -3  0   -3  3   -1  -1
  ******                      ******          ******              ******

完成后，您可以使用 autocorrelation在数据中寻找重复模式的方法。这可以在 O(n log n) 时间内计算出来，如果您只关心精确匹配，可能会更快。