3

There some times appears a task when you have a sequence of object and you need perform some action when a particular pattern (subsequence?) occurs.

As more concrete example we can imagine a log monitoring solution which should alert when a predefined sequence of messages is detected (A followed by B, followed by C, but no D in the middle).

This sounds a bit like CEP, but a) no need for real-time processing; b) no large volumes.

What patterns\algorithms exists to solving problems of this kind? Is there a well-known name for the problem (so that i can search for solutions myself)?

scorpp
  • 141
  • 2
  • 9
    I think you are looking for a “state machine”. – amon Feb 03 '17 at 14:01
  • thanks! i was also thinking about a state machine. do you know of any good design patters to implement one in OO language? – scorpp Feb 05 '17 at 21:05
  • You don't really need any special design pattern. Usually, state machines are implemented as a [nested switch/case](https://en.wikipedia.org/wiki/Event-driven_finite-state_machine), but there are many variations possible. – amon Feb 05 '17 at 21:14
  • 1
    btw did my task with [spring-statemachine](http://projects.spring.io/spring-statemachine/). worked quite nice! thanks for tip. – scorpp Apr 05 '17 at 11:14
  • Will there be intervening messages between A and B, or between B and C, etc? What if message A appears multiple times, and B also appears multiple times? Would that still count as a detection? – rwong Jan 30 '18 at 06:42

1 Answers1

1

Parser generators, such as ANTLR, specifically address this task. They generate a parser that can perform some task when a production is complete. You can either trigger an alert directly in the production definition, or merely use the parser to generate an abstract syntax tree that is more abstract (has less complexity) than the original input. You can then process the tree using complex logic that is entirely outside the parser.

Frank Hileman
  • 3,922
  • 16
  • 18