Patent ID: 8200646

Claim:
An apparatus for retrieving a variable-length string of characters from a plurality of registration patterns, comprising: a pattern storage section for storing the plurality of registration patterns and index elements for respective ones of the plurality of registration patterns; and a pattern registration section for generating an index element for a given registration pattern of the plurality of registration patterns and registering the given registration pattern and the index element for the given registration pattern into the pattern storage section, wherein the index element for the given registration pattern is a prefix of the given registration pattern, wherein when a predetermined separating character is found a predetermined number N (natural number) times in the given retrieving pattern from the beginning, the region of the given registration pattern from the beginning to the position at which the N-th predetermined separating character is found is used as the index element, and wherein when the given retrieving pattern from the beginning does not include N predetermined separating characters, the region of the given registration pattern from the beginning to the position at which the last predetermined separating character is found from the beginning in the given registration pattern is used as the index element; and a pattern retrieval section comprises: a prefix extractor for extracting a plurality of retrieval key prefixes from the given retrieval key, wherein the pattern retrieval section scans the given retrieval key for the predetermined separating character same as the one used in the pattern registration section until the predetermined separating character has been found N times in the given retrieval key or the scan reaches the end of the given retrieval key, wherein, whenever the predetermined separating character is found, the region of the given retrieval key from the beginning to the position where the predetermined separating character is found is added to a list of retrieval key prefix, and wherein the plurality of retrieval key prefixes are the content of the list of retrieval key prefix; and a prefix retriever for retrieving an index element for the given retrieval key using the plurality of retrieval key prefixes that are extracted from the given retrieval key to narrow the scope of retrieval.