模式识别 - “这是一种模式？”

Question

我有一个很大的数字向量，比如500个数字。我想一个程序来检测图案在这种载体（在这种情况下复发）的基础上如下规则：

数字序列是一个模式，如果：

• 序列的大小是3至20位数字。

• 序列中数字的相对位置至少在另一个时间在 处重复。假设我有一个序列 （1,4,3）然后（3,6,5）在向量中的其他地方，那么（1,4,3）是 模式。 （以及（2,5,4），（3,6,5）等）

• 序列不能相交。所以，一个向量（1,2,3,4,5）不包含模式（1,2,3）和（3,4,5）（我们不能在 两个序列中使用相同的数字） 。然而，（1,2,3,3,4,5）确实包含模式 （1,2,3）（或（3,4,5））

• 模式B的子集A是一个模式只有在A出现在其他地方的某处 因此，一个向量（1,2,3,4,7,8,9,2,3,4,5）将包含 模式（1,2,3，因为（1,2,3,4）被重复（以（2,3,4,5）的 形式）并且（1,2,3）被重复（1,2,3,4）以（7,8,9）的形式）。但是，如果矢量为（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

只是一对夫妇的观察：

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

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日志 n）时间内计算出来，如果只关心精确匹配，甚至可能更快。