Efficient retrieval of variable-length character string data

Abstract

Prefixes are registered on a first list as index elements for respective registration patterns. Each prefix is selected as the longest of different-length prefixes that are extractable from a registration pattern in accordance with an extraction rule. Suffixes, which are the remaining parts of the registration patterns excluding the respective prefixes, are registered on a second list. Using different-length prefixes that are extracted from a retrieval key in accordance with the extraction rule, a prefix retriever searches the first list to retrieve a registration pattern whose prefix matches any of the prefixes of the retrieval key. A suffix checker carries out a check on the suffix of the registration pattern retrieved by the prefix retriever, among the suffixes on the second list, as to whether the suffix of the registration pattern matches the suffix of the retrieval key.

Description

BACKGROUND OF THE INVENTION [0001] 1. Field of the Invention [0002] The present invention relates to an information retrieval technology of retrieving variable-length character string data. More particularly, the present invention relates to a technology to enhance efficiency in retrieving the longest prefix match or longest suffix match of a variable-length character string. [0003] 2. Description of the Related Art [0004] First of all, a description will be given of a general outline of the retrieval of the longest prefix match; which is the primary application target of the present invention. In the retrieval of the longest prefix match, a retrieval result is, in a pattern list, the longest of patterns that match leading characters of a retrieval key (character string to retrieve). For example, when there are three patterns “ABCD”, “ABCDEFGH” and “ABCDE” that match leading characters of a retrieval key (e.g., “ABCDEFGHIJ”), the longest matching pattern “ABCDEFGH” is outputted as a...

AI Technical Summary

Benefits of technology

[0009] Accordingly, an object of the present invention is to provide an information retrieval technique, which achieves high retrieval efficiency even when the overlapping parts of registration patterns have a variety of lengths.

[0010] According to a first aspect of the present invention, an index element for a registration pattern is generated, wherein the index element is a partial string of characters which is selected from a plurality of possible partial strings of characters according to a predetermined selection rule, wherein the plurality of possible partial strings of characters are extracted from the registration pattern according to a predetermined extraction rule. An index element for a given retrieval key is retrieved using a plurality of partial strings of characters with different lengths that are extracted from the given retrieval key according to the predetermined extraction rule, to narrow scope of retrieval.

[0011] As described above, according to the present invention, high retrieval efficiency can be achieved even when the overlapping parts of registration patterns vary in length.

Problems solved by technology

On the other hand, a pattern that does not match leading characters of the retrieval key, such as a pattern “BCDE”, does not meet a condition of prefix matching, even if the pattern is a partial character string of the retrieval key.

Such a prior art has a disadvantage, which will be described with reference to FIG. 1.

Therefore, if a character string starting with “PQRSPQRSP” is inputted as a retrieval key, the narrowing of the patterns1305 to 1310 based on the indexes is insufficient, leading to increased costs of suffix-part comparison to be performed thereafter, lowering the retrieval efficiency.

As described above, the prior art has a problem that, when the overlapping parts of registration patterns vary in length, the registration patterns are not narrowed sufficiently based on indexes, resulting in the costs of comparing the remaining parts of the character strings becoming large.

Images