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

摘要

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.