Apparatus and method of multi-string matching based on sparse state transition list
First Claim
1. A collating apparatus, using a finite state machine for determining whether a key referring to a given symbol string exists in a file, said apparatus comprising:
- state transition storage means for storing in a compressed array format a sparse state transition table containing definitions of collating operations for at least one key, wherein an amount of data indicating a predetermined operation is reduced in the sparse state transition table; and
collating means for performing an operation corresponding to each symbol contained in the file while referring to the sparse state transition table, performing the predetermined operation when no operation is defined in the sparse state transition table, and collating a symbol string in the file with at least one key.
1 Assignment
0 Petitions
Accused Products
Abstract
A collating apparatus generates a sparse state transition table by reducing the amount of data indicating a specific transition operation and a shift operation in a state transition table in which a collating operation corresponding to each symbol contained in one or more retrieval keys is defined. Then, the collating apparatus stores the table after compressing it into an array format, and retrieves the keys in the file to be retrieved while referring to the compressed state transition table. This collating apparatus is applied to a word processor, database system, full-text search system, etc.
-
Citations
22 Claims
-
1. A collating apparatus, using a finite state machine for determining whether a key referring to a given symbol string exists in a file, said apparatus comprising:
-
state transition storage means for storing in a compressed array format a sparse state transition table containing definitions of collating operations for at least one key, wherein an amount of data indicating a predetermined operation is reduced in the sparse state transition table; and collating means for performing an operation corresponding to each symbol contained in the file while referring to the sparse state transition table, performing the predetermined operation when no operation is defined in the sparse state transition table, and collating a symbol string in the file with at least one key. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. A collating apparatus generating a finite state machine for determining whether a key referring to a given symbol string exists in a file, said apparatus comprising:
-
sparse finite state machine generating means for generating binary tree data representing at least one key, and generating a finite state machine having an intermediate structure corresponding to a sparse state transition table based on the binary tree data, whereby an amount of data indicating a predetermined operation is reduced in the sparse state transition table so as to compress the finite state machine; and state transition machine compressing means for converting the finite state machine into a compressed array format. - View Dependent Claims (14, 15)
-
-
16. A collating apparatus, using a finite state machine, for determining whether a key referring to a given symbol string exists in a file, said apparatus comprising:
-
sparse finite state machine generating means for generating binary tree data representing at least one key, and generating the finite state machine having an intermediate structure corresponding to a sparse state transition table based on the binary tree data, whereby the amount of data indicating a predetermined operation is reduced in the state transition table so as to compress the finite state machine; state transition machine compressing means for converting the finite state machine of the intermediate structure into a compressed array format; state transition storage means for storing the sparse state transition table converted into the array format; and collating means for referring to the sparse state transition table, performing an operation corresponding to each symbol contained in the file, performing the predetermined operation when there is no operation defined in the sparse state transition table, and collating a symbol string in the file with the at least one key.
-
-
17. A collating apparatus, using a finite state machine, for determining whether a key referring to a given symbol string exists in a file, said apparatus comprising:
-
state transition storage means for storing a state transition table containing defined collating operations on at least one key, at least one of data indicating a transition operation from a current state to an initial state and data indicating a transition operation for the current state to a next state to the initial state being removed from the state transition table; and collating means for collating a symbol string in the file with the at least one key be performing the transition operation to the initial state when the state transition table does not contain a defined transition corresponding to a symbol input from the file.
-
-
18. A collating apparatus for determining using a finite state machine whether or not a key referring to a given symbol string exists in a file, said apparatus comprising:
-
state transition storage means for storing a state transition table containing defined collating operations on at least one key, data indicating a shift operation being reduced in the state transition table and the shift operation setting a collation position in the file back in an inverse direction of a collation direction; and collating means for performing the shift operation when there is no operation, corresponding to an input symbol input from the collation position in the file, defined in the state transition table, and for collating the symbol string in the file with the at least one key.
-
-
19. A computer-readable medium used to direct a computer, using a finite state machine, to determine whether a key referring to a given symbol string exists in a file by performing the following action:
-
performing an operation corresponding to each symbol contained in the file by referring g to a sparse state transition table containing definition by collating operations for at least one key, data indicating a predetermined operation being reduced in the sparse state transition table; performing the predetermined operation when there is no operation define din the sparse state transition table; and collating the symbol string in the file with the at least one key.
-
-
20. A computer-readable medium used to direct a computer to generate a finite state machine for determining whether a key referring to a given symbol string exists in a file by performing the following actions:
-
generating binary tree data representing at least one key; generating the finite state machine of an intermediate structure corresponding to a sparse state transition table based on the binary tree data, data indicating a predetermined operation being reduced in the sparse state transition table to compress the finite state machine; and converting the finite state machine of the intermediate structure into a compressed array format.
-
-
21. A collating method, using a finite state machine, to determine whether a key referring a given symbol string exists in a file, comprising the steps of:
-
performing an operation corresponding to each symbol contained in the file by referring to a sparse state transition table containing definitions of collating operations for at least one key, data indicating a predetermined operation being reduced in the sparse state transition table; performing the predetermined operation when there is no operation defined in the sparse state transition table; and collating the symbol string in the file with the at least one key.
-
-
22. A collating method for generating a finite state machine to determine whether a key referring to a given symbol string exists in a file, comprising the steps of:
-
generating binary tree data representing at least one key; generating the finite state machine of an intermediate structure corresponding to a sparse state transition table based on the binary tree data, data indicating a predetermined operation being reduced in the sparse state transition table to compress the finite state machine; and converting the finite state machine of the intermediate structure into a compressed array format.
-
Specification