Memory circuit for Aho-corasick type character recognition automaton and method of storing data in such a circuit

摘要

A memory circuit for an Aho-Corasick type character recognition automaton uses a node tree for recognizing predetermined strings of characters in an incoming data stream. The recognization is based upon successive transitions in the node tree stored in memory in which each node corresponds to a recognized sequence of a character string. At least part of the nodes are related to a consecutive node by a valid transition, from an initial state to terminal states, with each one corresponding to a recognized character string This memory circuit includes first sets of consecutive memory addresses defining respectively strings of consecutive nodes accessible sequentially during successive transitions to a terminal state, and second sets of memory addresses defining multiple nodes each pointing to several states.

主权项

1. A memory circuit for an Aho-Corasick type character recognition automaton in which character strings are recognized in an incoming data stream by implementation of successive transitions in a node tree in which each node corresponds to a recognized sequence of a character string and in which at least part of the nodes are related to a consecutive node by a valid transition, from an initial state to terminal states each corresponding to a recognized character string, the memory circuit comprising:
a plurality of first sets of consecutive memory addresses defining respective strings of consecutive nodes accessible sequentially during successive transitions to a terminal state for the Aho-Corasick type character recognition automaton; a plurality of second sets of memory addresses defining multiple nodes each pointing to a plurality of states for the Aho-Corasick type character recognition automaton, and with at least one of the multiple nodes pointing to at least three states; and with the nodes of each string of consecutive nodes and the multiple nodes being addressable based upon the address of a base node and a relative shift with respect to the address of the base node, each node in the string of consecutive nodes being coded as a frame of bytes of variable length, with each frame comprising fields that determine transition relating to the node, and a plurality of flags describing content of the bytes used for destination of the transition, to describe a state associated with the node, and a type of transition; with each node of each multiple node being coded as a frame of coding bits having characteristics relating to a transition associated therewith, with each coding frame comprising bits for coding parameters for calculating a valid transition function, and bits for coding a parameter for verification of the transition.