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)?

5
  • 9
    I think you are looking for a “state machine”.
    – amon
    Feb 3, 2017 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 5, 2017 at 21:05
  • You don't really need any special design pattern. Usually, state machines are implemented as a nested switch/case, but there are many variations possible.
    – amon
    Feb 5, 2017 at 21:14
  • 1
    btw did my task with spring-statemachine. worked quite nice! thanks for tip.
    – scorpp
    Apr 5, 2017 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, 2018 at 6:42

1 Answer 1

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.