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.

1 . An apparatus for retrieving a variable-length string of characters, comprising: 
 an index generating section for generating an index element for a registration pattern, 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; and    a retrieval section for retrieving an index element for a given retrieval key 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.    
   
   
       2 . An apparatus for retrieving a variable-length string of characters from a plurality of registration patterns, comprising: 
 a pattern storage section for registering the plurality of registration patterns and index elements for respective ones of the plurality of registration patterns, wherein each of the index elements for a corresponding registration pattern 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 corresponding registration pattern according to a predetermined extraction rule; and    a retrieval execution section for retrieving an index element for a given retrieval key 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.    
   
   
       3 . An apparatus for retrieving a variable-length string of characters from a plurality of registration patterns, comprising: 
 a pattern storage section for registering the plurality of registration patterns and index elements for respective ones of the plurality of registration patterns, wherein each of the index elements for a corresponding registration pattern is a longest one of a plurality of possible registration pattern prefixes which are extracted from the corresponding registration pattern according to a predetermined extraction rule; and    a retrieval execution section for retrieving an index element for a given retrieval key using a plurality of retrieval key prefixes with different lengths that are extracted from the given retrieval key according to the predetermined extraction rule, to narrow scope of retrieval.    
   
   
       4 . The apparatus according to  claim 3 , wherein the pattern storage section comprises: 
 a prefix pattern list containing registration pattern prefixes of respective ones of the registration patterns, wherein each of the registration pattern prefixes is an index element for a corresponding registration pattern; and    a suffix pattern list containing suffixes of respective ones of the registration patterns, wherein each of the suffixes is a portion of a corresponding registration pattern excepting its prefix, and the retrieval execution section comprises:    a prefix extractor for extracting the plurality of retrieval key prefixes with different lengths from the given retrieval key according to the predetermined extraction rule;    a prefix retriever for retrieving a registration pattern having an index element that matches any one of the plurality of retrieval key prefixes extracted by the prefix extractor by searching the prefix pattern list using the plurality of retrieval key prefixes with different lengths; and    a suffix checker for checking whether a suffix of the retrieval key matches a suffix of the registration pattern retrieved by the prefix retriever in the suffix pattern list.    
   
   
       5 . The apparatus according to  claim 4 , wherein 
 the prefix pattern list stores a registration pattern prefix to be an index element for each registration pattern at a location corresponding to a hash value obtained by applying a predetermined hash function to the registration pattern prefix, and    the prefix retriever uses the predetermined hash function to obtain hash values for respective ones of the plurality of retrieval key prefixes and searches the prefix pattern list using the hash values obtained.    
   
   
       6 . The apparatus according to  claim 4 , wherein the predetermined extraction rule is to determine the plurality of possible registration pattern prefixes to be extracted according to different numbers of characters from a first character of each registration pattern.  
   
   
       7 . The apparatus according to  claim 4 , wherein the predetermined extraction rule is to determine the plurality of possible registration pattern prefixes to be extracted by a predetermined separating character.  
   
   
       8 . An apparatus for retrieving a variable-length string of characters from a plurality of registration patterns, comprising: 
 a pattern storage section for registering the plurality of registration patterns and index elements for respective ones of the plurality of registration patterns, wherein each of the index elements for a corresponding registration pattern is a longest one of a plurality of possible registration pattern suffixes with different lengths from a tail end of the corresponding registration pattern, wherein the plurality of possible registration pattern suffixes are extracted from the corresponding registration pattern according to a predetermined extraction rule; and    a retrieval execution section for retrieving an index element for a given retrieval key using a plurality of retrieval key suffixes with different lengths that are extracted from the given retrieval key according to the predetermined extraction rule, to narrow scope of retrieval.    
   
   
       9 . The apparatus according to  claim 8 , wherein the pattern storage section comprises: 
 a suffix pattern list containing registration pattern suffixes of respective ones of the registration patterns, wherein each of the registration pattern suffixes is an index element for a corresponding registration pattern; and    a prefix pattern list containing prefixes of respective ones of the registration patterns, wherein each of the prefixes is a portion of a corresponding registration pattern excepting its suffix, and the retrieval execution section comprises:    a suffix extractor for extracting the plurality of retrieval key suffixes with different lengths from the given retrieval key according to the predetermined extraction rule;    a suffix retriever for retrieving a registration pattern having an index element that matches any one of the plurality of retrieval key suffixes extracted by the suffix extractor by searching the suffix pattern list using the plurality of retrieval key suffixes with different lengths; and    a prefix checker for checking whether a prefix of the retrieval key matches a prefix of the registration pattern retrieved by the suffix retriever in the prefix pattern list.    
   
   
       10 . The apparatus according to  claim 9 , wherein 
 the suffix pattern list stores a registration pattern suffix to be an index element for each registration pattern at a location corresponding to a hash value obtained by applying a predetermined hash function to the registration pattern suffix, and    the suffix retriever uses the predetermined hash function to obtain hash values for respective ones of the plurality of retrieval key suffixes and searches the suffix pattern list using the hash values obtained.    
   
   
       11 . The apparatus according to  claim 9 , wherein the predetermined extraction rule is to determine the plurality of possible registration pattern suffixes to be extracted according to different numbers of characters from a first character of each registration pattern.  
   
   
       12 . The apparatus according to  claim 9 , wherein the predetermined extraction rule is to determine the plurality of possible registration pattern suffixes to be extracted by a predetermined separating character.  
   
   
       13 . A method for retrieving a variable-length string of characters, comprising: 
 generating an index element for a registration pattern, 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; and    retrieving an index element for a given retrieval key 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.    
   
   
       14 . A method for retrieving a variable-length string of characters from a plurality of registration patterns, comprising: at registration pattern registration, 
 extracting a plurality of possible partial strings of characters from each of the plurality of registration patterns according to a predetermined extraction rule;    selecting a partial string of characters as an index element for a corresponding registration pattern from the plurality of possible partial strings of characters according to a predetermined selection rule;    registering the plurality of registration patterns and index elements for respective ones of the plurality of registration patterns in a pattern storage section; at registration pattern retrieval,    extracting a plurality of partial strings of characters with different lengths from a given retrieval key according to the predetermined extraction rule; and    searching the pattern storage section using the plurality of partial strings of characters extracted from the given retrieval key to narrow a search.    
   
   
       15 . A method for retrieving a variable-length string of characters from a plurality of registration patterns, comprising: at registration pattern registration, 
 extracting a plurality of possible registration pattern prefixes with different lengths from a front end of a corresponding registration pattern from each of the plurality of registration patterns according to a predetermined extraction rule;    selecting a longest possible registration pattern prefix as an index element for a corresponding registration pattern from the plurality of possible registration pattern prefixes according to a predetermined selection rule;    registering the plurality of registration patterns and index elements for respective ones of the plurality of registration patterns in a pattern storage section; at registration pattern retrieval,    extracting a plurality of retrieval key prefixes with different lengths from a given retrieval key according to the predetermined extraction rule; and    searching the pattern storage section using the plurality of retrieval key prefixes with different lengths to narrow a search.    
   
   
       16 . A method for retrieving a variable-length string of characters from a plurality of registration patterns, comprising: at registration pattern registration, 
 extracting a plurality of possible registration pattern suffixes with different lengths from a tail end of a corresponding registration pattern from each of the plurality of registration patterns according to a predetermined extraction rule;    selecting a longest possible registration pattern suffix as an index element for a corresponding registration pattern from the plurality of possible registration pattern suffixes according to a predetermined selection rule;    registering the plurality of registration patterns and index elements for respective ones of the plurality of registration patterns in a pattern storage section; at registration pattern retrieval,    extracting a plurality of retrieval key suffixes with different lengths from a given retrieval key according to the predetermined extraction rule; and    searching the pattern storage section using the plurality of retrieval key suffixes with different lengths to narrow a search.    
   
   
       17 . A computer-readable program to instruct a computer to retrieve a variable-length string of characters, comprising: 
 generating an index element for a registration pattern, 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; and    retrieving an index element for a given retrieval key 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.    
   
   
       18 . A computer-readable program to instruct a computer to retrieve a variable-length string of characters from a plurality of registration patterns, wherein the computer comprises a pattern storage section for registering the plurality of registration patterns and index elements for respective ones of the plurality of registration patterns, wherein each of the index elements for a corresponding registration pattern 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 corresponding registration pattern according to a predetermined extraction rule, 
 the program instructing the computer to extract a plurality of partial strings of characters with different lengths from a given retrieval key according to the predetermined extraction rule, and search the pattern storage section using the plurality of partial strings of characters extracted from the given retrieval key to narrow a search.    
   
   
       19 . A computer-readable program to instruct a computer to retrieve a variable-length string of characters from a plurality of registration patterns, wherein the computer comprises a pattern storage section for registering the plurality of registration patterns and index elements for respective ones of the plurality of registration patterns, wherein each of the index elements for a corresponding registration pattern is a longest one of a plurality of possible registration pattern prefixes which are extracted from the corresponding registration pattern according to a predetermined extraction rule, 
 the program instructing the computer to extract a plurality of retrieval key prefixes with different lengths from a given retrieval key according to the predetermined extraction rule, and search the pattern storage section using the plurality of retrieval key prefixes with different lengths to narrow a search.    
   
   
       20 . A computer-readable program to instruct a computer to retrieve a variable-length string of characters from a plurality of registration patterns, 
 wherein the computer comprises a pattern storage section for registering the plurality of registration patterns and index elements for respective ones of the plurality of registration patterns, wherein each of the index elements for a corresponding registration pattern is a longest one of a plurality of possible registration pattern suffixes with different lengths from a tail end of the corresponding registration pattern, wherein the plurality of possible registration pattern suffixes are extracted from the corresponding registration pattern according to a predetermined extraction rule,    the program instructing the computer to extract a plurality of retrieval key suffixes with different lengths from a given retrieval key according to the predetermined extraction rule, and search the pattern storage section using the plurality of retrieval key suffixes with different lengths to narrow a search.