Apparatus and method of multi-string matching based on sparse state transition list

• US 5,995,963 A
• Filed: 03/04/1997
• Issued: 11/30/1999
• Est. Priority Date: 06/27/1996
• Status: Expired due to Term

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Igata, Nobuyuki, Nanba, Isao
• Primary Examiner(s): Lintz, Paul R.
• Assistant Examiner(s): FLEURANTIN, JEAN B
• Application Number:
  US08/811,534
• Time in Patent Office: 1,001 Days
• Field of Search: 707/3, 707/6, 707/7
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06V 10/768 using context analysis, e.g. recognition aided by known co-occurring patterns
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting

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.

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.

2. The collating apparatus according to claim 1, wherein

said state transition storage means stores the sparse state transition table excluding data indicating a transition operation from a current state to an initial state;

and

said collating means performs the transition operation to the initial state when there is no transition, corresponding to an input symbol from the file, defined in the sparse state transition table.

3. The collating apparatus according to claim 2, wherein

said state transition storage means stores the sparse state transition table excluding the data indicating the transition operation from the current state to a next state to the initial state;

and

said collating means performs a transition operation to the next state to the initial state through the initial state when there is no transition, corresponding to the input symbol, defined in the sparse state transition table.

4. The collating apparatus according to claim 1, wherein

said state transition storage means stores the sparse state transition table containing a reduced amount of data indicating a shift operation for setting a collation position in the file back in an inverse direction of a collation direction;

and

said collating means performs the shift operation when there is no operation, corresponding to an input symbol input from the collation position in the file, defined in the sparse state transition table.

5. The collating apparatus according to claim 4, wherein

said collating means performs a defined operation when one of a transition operation to a next state corresponding to the input symbol and a specific shift operation corresponding to the input symbol is defined in the sparse state transition table.

6. The collating apparatus according to claim 1, wherein

said state transition storage means stores a next transition state array storing a next state from a current state according to an input symbol input from the file, and a confirmation label array storing a label indicating whether or not an operation corresponding to the input symbol is stored at a corresponding position in the next transition state array;

and

said collating means confirms the label in the confirmation label array, and performs a transition operation to a next transition state when the next transition state corresponding to the input symbol is stored at the corresponding position.

7. The collating apparatus according to claim 6, wherein

said collating means shifts a collation position in the file through a specific shift operation when data indicating the specific shift operation corresponding to the input symbol is stored at the corresponding position.

8. The collating device according to claim 6, further comprising

storage means for storing an output symbol array storing data which specifies a key corresponding to an input symbol contained in the at least one key;

and

output means for outputting a key corresponding to the input symbol based on the data in the output symbol array.

9. The collating device according to claim 6, further comprising

storage means storing a replacement symbol array containing data which specifies the replacement symbol string output instead of a key corresponding to an input symbol contained in the at least one key;

and

output means for outputting the replacement symbol string corresponding to the input symbol based on the data in the replacement symbol array.

10. The collating apparatus according to claim 1, wherein

at least one of a symbol string retrieving function and a symbol string replacing function is performed using said collating apparatus.

11. The collating apparatus according to claim 1, wherein

at least one of a symbol string replacing function is performed using said collating apparatus.

12. The collating apparatus according to claim 1, wherein

at least one of a symbol string retrieving function and a symbol string replacing function is performed using said collating apparatus.

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.

14. The collating apparatus according to claim 13, wherein

said sparse finite state machine generating means includes binary tree data generating means for generating the binary tree data, and transition adding means for adding, to the binary tree data, information about a possible state in case of transition failure excluding an initial state and a state preceded by the initial state;

and

said state transition machine compressing means generates a compressed state transition array in such a way that a plurality of elements do not overlap each other based on the binary tree data received from said transition adding means.

15. The collating apparatus according to claim 13, wherein

said sparse finite state machine generating means includes binary tree data generating means for generating the binary tree data, and shift amount computing means for computing one of a possible state in case of transition failure, a default shift, and a specific shift corresponding to a specific symbol and for adding a computation result to the binary tree data;

and

said state transition machine compressing means generates a compressed state transition array in such a way that a plurality of elements do not overlap each other based on the binary tree data received from said shift amount computing means.

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.