Method of storing data in a memory circuit for AHO-corasick type character recognition automaton and corresponding storage circuit

• US 7,860,712 B2
• Filed: 11/02/2006
• Issued: 12/28/2010
• Est. Priority Date: 11/03/2005
• Status: Active Grant

• Current Assignee: STMicroelectronics SA (STMicroelectronics NV)
• Original Assignee: STMicroelectronics SA (STMicroelectronics NV)
• Inventors: Albarel, Nicolas, Furodet, David
• Primary Examiner(s): Lerner; Martin
• Application Number:
  US11/555,888
• Publication Number:
  US 20070104375A1
• Time in Patent Office: 1,517 Days
• Field of Search: 704/222, 704/231, 707/715, 707/797, 726/24, 382/182
• US Class Current: 704/231
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/268 Lexical context

Abstract

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.

Claims

1. A method of storing data in a memory circuit of an Aho-Corasick type character recognition automaton, the method comprising:

storing a tree of nodes in a memory in which each node in the tree corresponds to a state of automaton; and

operating a character recognition automation coupled to the memory circuit to perform the following

recognizing character strings by implementing successive transitions in the tree of nodes in which each node in the tree corresponds to a state of the automaton;

recognizing a sequence of each character string, with each node in the tree being associated with a transition vector used to determine at least one destination node of a transition in the tree of nodes;

determining if transition vectors point to common destination addresses;

combining the transition vectors to form a combination vector if the transition vectors do not point to a common destination address; and

storing the nodes in the tree at memory addresses pointed to by the combination vector.

2. A method according to claim 1, wherein the combination vector is formed by carrying out a logic OR between the transition vectors to be combined.

3. A method according to claim 1, further comprising performing a test to determine if the transition vectors point to common states by carrying out an AND logic function between the transition vectors to be combined.

4. A method according to claim 1, wherein successive transformations of a first vector to be combined are carried out until a configuration of the first vector is obtained in which the states to which this vector points are different from the states to which a second vector to be combined points.

5. A method according to claim 4, wherein if the configuration is not attained, then the first vector is combined with another vector.

6. A method according to claim 4, wherein the transformation is an offset and a rotation of the bits of the vector.

7. A method according to claim 1, wherein each node in the tree is associated in the memory circuit with transition parameters used to form the transition vectors based on a transition function.

8. A method according to claim 7, wherein a value of the transition parameters is modified as a function of the successive transformations of the vectors.

9. A method according to claim 7, wherein the states are stored in the memory circuit as a set of segments of descriptors, each segment corresponding to an input symbol and being addressable by a first transition parameter and each vector being addressable by a second transition parameter representing the position of the vector in a segment.

10. A method according to claim 1, wherein each node in the tree is associated with a confirmation key having a set of coding bits corresponding to a parameter for verifying a transition.

11. A method according to claim 1, wherein a set of combination vectors is initialized by setting each bit of the vectors to 0, and each transition vector and each combination vector are combined successively.

12. A method of operating an Aho-Corasick type character recognition automaton circuit comprising:

storing a tree of nodes in a memory in which each node in the tree corresponds to a state of the automaton; and

operating a character recognition automation coupled to the memory to perform the following

recognizing character strings by implementing successive transitions in the tree of nodes stored in the memory,

recognizing a sequence of each character string, with each node in the tree being associated with a transition vector used to determine at least one destination node of a transition in the tree of nodes,

determining if transition vectors point to common destination addresses,

combining the transition vectors to form a combination vector if the transition vectors do not point to a common destination address, and

storing the tree of nodes at memory addresses in the memory pointed to by the combination vector.

13. A method according to claim 12, wherein the combination vector is formed by carrying out a logic OR between the transition vectors to be combined.

14. A method according to claim 12, further comprising performing a test to determine if the transition vectors point to common states by carrying out an AND logic function between the transition vectors to be combined.

15. A method according to claim 12, wherein successive transformations of a first vector to be combined are carried out until a configuration of the first vector is obtained in which the states to which this vector points are different from the states to which a second vector to be combined points.

16. A method according to claim 15, wherein if the configuration is not attained, then the first vector is combined with another vector.

17. A method according to claim 15, wherein the transformation is an offset and a rotation of the bits of the vector.

18. A method according to claim 12, wherein each node in the tree is associated in the memory with transition parameters used to form the transition vectors based on a transition function.

19. A method according to claim 18, wherein a value of the transition parameters is modified as a function of the successive transformations of the vectors.

20. A method according to claim 18, wherein the states are stored in the memory as a set of segments of descriptors, each segment corresponding to an input symbol and being addressable by a first transition parameter and each vector being addressable by a second transition parameter representing the position of the vector in a segment.

21. A method according to claim 12, wherein each node in the tree is associated with a confirmation key having a set of coding bits corresponding to a parameter for verifying a transition.

22. A method according to claim 12, wherein a set of combination vectors is initialized by setting each bit of the vectors to 0, and each transition vector and each combination vector are combined successively.

23. An Aho-Corasick type character recognition automaton circuit comprising:

a memory for storing a tree of nodes in which each node in the tree corresponds to a state of the automaton; and

a character recognition automation coupled to said memory and configured for

recognizing character strings by implementing successive transitions in the tree of nodes stored in said memory,

recognizing a sequence of each character string, with each node in the tree being associated with a transition vector used to determine at least one destination node of a transition in the tree of nodes,

determining if transition vectors point to common destination addresses, and

combining the transition vectors to form a combination vector if the transition vectors do not point to a common destination address, and storing the nodes in the tree at memory addresses in said memory pointed to by the combination vector.

24. A circuit according to claim 23, wherein said character recognition automation forms the combination vector by carrying out a logic OR between the transition vectors to be combined.

25. A circuit according to claim 23, wherein said character recognition automation is configured for performing a test to determine if the transition vectors point to common states by carrying out an AND logic function between the transition vectors to be combined.

26. A circuit according to claim 23, wherein successive transformations of a first vector to be combined by said character recognition automation are carried out until a configuration of the first vector is obtained in which the states to which this vector points are different from the states to which a second vector to be combined points.

27. A circuit according to claim 26, wherein if the configuration is not attained, then the first vector is combined with another vector.

28. A circuit according to claim 26, wherein the transformation is an offset and a rotation of the bits of the vector.

29. A circuit according to claim 23, wherein said character recognition automation associates each node in the tree in said memory with transition parameters used to form the transition vectors based on a transition function.

30. A circuit according to claim 29, wherein a value of the transition parameters is modified as a function of the successive transformations of the vectors.

31. A circuit according to claim 29, wherein said character recognition automation stores the states in said memory as a set of segments of descriptors, each segment corresponding to an input symbol and being addressable by a first transition parameter and each vector being addressable by a second transition parameter representing the position of the vector in a segment.

32. A circuit according to claim 23, wherein said character recognition automation associates each node with a confirmation key having a set of coding bits corresponding to a parameter for verifying a transition.

33. A circuit according to claim 23, wherein said character recognition automation initializes a set of combination vectors by setting each bit of the vectors to 0, and each transition vector and each combination vector are combined successively.