Perl: the Markov chain saw | |
PerlMonks |
comment on |
( [id://3333]=superdoc: print w/replies, xml ) | Need Help?? |
Make a Finite State Automaton (what a mouthful) as a chain of nodes where, in this particular case, each node can only move to the next node in the chain. The length of the chain is equal to the length of the pattern you try to detect. Also, i^th node knows about the i^th data point (DP) in your pattern in order to compare whatever data it is holding and make a response if same. Generally this is how it works: First DP in the stream enters the 1st node. That node checks if entered DP is the same as the DP from your pattern it knows. Depending on yes/no, it turns a bit on/off in a global message buffer (buffer is of length equal to your pattern's). Then pass the DP to the next node of the chain and load next DP from the stream. As a new DP is extracted from the stream, it enters the 1st node, that node does the check and propagates the DP to the second node. Second node does the same until the DP comes out from the last node. In the meantime, someone keeps an eye on the message buffer and if/when all bits are on, you got a pattern detected. Sometimes you will get 90% of the bits on, this is when a partial pattern match occured. Set a minimum match percentage to trigger a response. I think you are right to mention regex, I have just described how a regex works. If you go that way then of course there are plenty of modules in cpan, see Finite State Automata / Transducers Forgot to say, this is also common in electronics where data moves on a clock-pulse. Do not do any asynchronous message buffer checking, but instead follow a clock. Data moves, bits flipped, message buffer checked each new clock pulse. hope that helps, bliako In reply to Re: Algorithm inspiration required.
by bliako
|
|