Home Original page

Sequence and/or pattern matching

Mike Meyer mwm at mired.org
Thu Oct 20 10:14:34 EDT 2005 
"Séb" <scapt at unil.ch> writes:

> Hi everybody,
>
> Thanks for the time taken to answer my question. Unfortunatly, it seems
> that there's a little confusion about what I want to do.
>
> In fact, I don't want to search for a particular path between
> computers. What I really want is to detect sequences of connection that
> are repeated along the log. Is it clearer, if not, I will put another
> exmample ;-)

You're right - I was confused. That's why I asked about the timing
issue. But I also indicated that I might be way off base with that.

Everyone may be confused as well - we thought you were looking for
*any* series of connections that started at one computer and ended at
a second computer. That problem is the well-understood problem of
finding a path through a graph, where "path" is used in a
graph-theoretic sense and not a network sense.

>From what you say above, it looks like you're looking for a specfic
sequence of connections in your connetions record. That's a much
easier problem. Roughly, you'd do:

def matches(desired, history):
"""Determines if history contains the desired path.
    desired = # List of connections we're looking for.
    history = # List of connections that were actually made."""

    for con in desired:
        try:
            while not con.matches(history[hp]):
                hp += 1
        except IndexError:
            return False
   return True


   <mike
-- 
Mike Meyer <mwm at mired.org>			http://www.mired.org/home/mwm/
Independent WWW/Perforce/FreeBSD/Unix consultant, email for more information.
More information about the Python-list mailing list