need an idea, recognize sequence, fsm or genetic ?

Martin DeMello martindemello at yahoo.com
Thu Sep 2 11:42:26 CEST 2004


Joh <joh12005 at yahoo.fr> wrote:
> 
> also i think this is related to some kind of finite state automata,
> but i do not know how to build automatically massive parallel FSM (i
> can have many many sequences and huge amount of sentences)

here's a naive but clean way to do it

Write a finite state machine class that scans the sentence for a single
sequence. Then instantiate one of them per sequence, and run the
following loop (pseudocode)

for word, index in enumerate sentence
  for fsm in sequences
    fsm.advance(word)
    if fsm.state == END
      results[fsm] += (index - fsm.sequence_length, index)
      fsm.state == START

A possible optimisation is to combine all your sequences into a single
trie; however, this will also require backtracking so I'm not sure how
much faster it'd be in practice.

martin



More information about the Python-list mailing list