Stmicroelectronics S.a.

Nicolas Albarel

David Furodet

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.

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

A method of storing data in a memory circuit of an Aho-Corasick type character recognition automaton recognizes character strings by implementing successive transitions in a tree of nodes stored in a memory. Each node corresponds to a state of the automaton and to a recognition of a sequence of the character string. Each node is associated with a transition vector serves to determine the destination node or nodes of a transition. For storage of the data, a test is performed to find out whether transition vectors point to common destination addresses. The transition vectors are combined if the addresses to which the vectors point are separate by formulating a combination vector and the nodes are stored at the memory addresses pointed at by the combination vector.

Growing community of inventors

Grenoble, France

Nicolas Albarel