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.

この種のパターンに一致するように、非常に基本的なステート マシンを実装しました。これは非常にうまく機能し、許容できるスループットを備えています。ただし、追加の時間制約を追加する場合、たとえば、2 番目のパターンは最初の 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 をサポートするルール エンジンを使用して、この種の条件に一致させました。これはかなりうまく機能しますが、必要な大量のデータ (1 秒あたり数十万イベント) を処理することはできません。

この問題を解決する効率的な方法はありますか? 私はJavaを使用しています。

ありがとう

4

1 に答える 1

0

ステート マシンを (値、時間) で遷移させる代わりに、次のようなイベントで遷移させることができます。

 value changed to x
 1 second passed

これにより、状態と遷移の数は増えますが、前 vs 後 vs x 秒後など、幅広い関係を表現できます。実行するすべてのチェックが 10 秒の境界で整列していることがわかっている場合は、「1 秒経過」の代わりに「10 秒経過」を使用してステート マシンのサイズを減らすことができます。

于 2012-02-27T18:43:56.627 に答える