Beefy Boxes and Bandwidth Generously Provided by pair Networks
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
in thread Algorithm inspiration required. by BrowserUk

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or How to display code and escape characters are good places to start.
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others surveying the Monastery: (10)
As of 2024-03-29 15:24 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found