2012-02-27 66 views
1

我正在尋找一種用於匹配[大]數據列表中的模式/序列的高效算法。鑑於某些類型:匹配序列的高效算法

class Data implements Event { 
    int valueA; 
    int valueB; 
    int valueC; 
    long timestamp; 

    ... 
} 

我想匹配以下情況。

valueA == 1 for 10 seconds 
then valueB == 2 for 10 seconds 
then valueC == 3 for 10 seconds. 

我已經實現了一個非常基本的狀態機,以匹配這種模式,它工作得很好,並有一個非常可接受的吞吐量。但是,如果我想增加額外的時間限制,例如第二圖案後一定會出現X秒第一

a : valueA == 1 for 10 seconds 
b : valueB == 2 for 10 seconds [ 10 seconds after a ] 
c : valueC == 3 for 10 seconds [ 10 seconds after b ] 

狀態機的概念似乎不再適用,因爲它有必要評估(並重新評估已經匹配條件)和狀態存儲在內存中,然後嘗試將它們關聯。系統中將有大約1000個這種類型的「規則」。

**編輯**

爲了澄清,如果我試圖序列匹配如下列:

x changed to 1 
1 second passed 
y changed to 1 
3 seconds passed 
z changed to 1 

而給出的輸入數據:

[ x=0, y=0, z=0, t=0 sec ] 
[ x=1, y=0, z=0, t=1 sec ] 
[ x=0, y=1, z=0, t=2 sec ] 
[ x=1, y=0, z=0, t=3 sec ] 
[ x=0, y=1, z=0, t=4 sec ] 
[ x=1, y=0, z=0, t=5 sec ] 
[ x=0, y=1, z=0, t=6 sec ] 
[ x=0, y=0, z=1, t=7 sec ] 

我預計這會在t = 7時達到最終狀態。但是,我能看到這樣做的唯一方法是存儲所有其他狀態轉換?

**編輯完**

我以前使用的規則引擎與CEP支持來匹配這些樣的條件,它的性能非常好,但不能處理大量需要的數據(每秒幾十萬個事件)。

有沒有一種有效的方法來解決這個問題?我正在使用Java。

感謝

回答

0

而不必對(值,時間),你的狀態機轉換的,你可以把它的活動變化,而不是如

value changed to x 
1 second passed 

這將提高狀態和轉換的數量,但是可以讓你表達廣泛的關係,比如在vs之後和之後的x秒之間。如果您知道所有要執行的檢查都是在10秒的邊界上排列的,則可以使用「10秒通過」而不是「1秒通過」來減少狀態機大小。

+0

謝謝你的建議,邁克。我仍然不確定如何按時間關聯這些事件。我用一個例子更新了我的問題。 – dropbear 2012-02-27 20:07:10