匹配序列的高效算法

Question

我正在寻找一种用于匹配[大]数据列表中的模式/序列的高效算法。鉴于某些类型：

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。

感谢

Answer 1

而不必对（值，时间），你的状态机转换的，你可以把它的活动变化，而不是如

value changed to x 
1 second passed 

这将提高状态和转换的数量，但是可以让你表达广泛的关系，比如在vs之后和之后的x秒之间。如果您知道所有要执行的检查都是在10秒的边界上排列的，则可以使用“10秒通过”而不是“1秒通过”来减少状态机大小。