模式識別 - 「這是一種模式？」

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）時間內計算出來，如果只關心精確匹配，甚至可能更快。