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。

谢谢

4

1 回答 1

0

您可以让它在事件上转换，而不是让您的状态机转换为（值，时间），例如

 value changed to x
 1 second passed

这将增加状态和转换的数量，但允许您表达范围广泛的关系，例如之前、之后和 x 秒后。如果您知道要在 10 秒边界上进行的所有检查，则可以通过使用“10 秒通过”而不是“1 秒通过”来减小状态机大小。

于 2012-02-27T18:43:56.627 回答