Я ищу эффективный алгоритм для сопоставления шаблонов / последовательностей в [большом] списке данных.Учитывая некоторый тип:
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 «правил» этого типа.
** EDIT **
Чтобы уточнить, пытался ли я сопоставить последовательность, такую как следующая:
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.Но единственный способ сделать это - сохранить все остальные переходы состояний?
** END EDIT **
Ранее я использовал Rule Engine с поддержкой CEP длясоответствуют условиям такого рода, которые работают достаточно хорошо, но не способны обрабатывать большие объемы требуемых данных (несколько сотен тысяч событий в секунду).
Есть ли эффективный способ решения этой проблемы?Я использую Java.
Спасибо