Pattern matching using deterministic finite automata and organization of such automata

摘要

A deterministic finite state machine is operated to detect any one of a plurality of digital signatures each corresponding to a succession of characters and each defined by a sequence of states in the state machine. The machine is organized such that for each state after the first in any sequence there are not more than two allowed exit transitions of which one is to a default state. Input characters are examined to determine a transition from a current state of the machine to a next state. When the machine responds to an input character to perform a transition to the default state, the input character is reexamined to determine the next state of the state machine. The reduction in transitions saves considerable space in memory.