Code string search apparatus, search method, and program

Abstract

An index data configuration adapted to a code-string search method for a structured code string having data codes, first separator codes that separate a data code or a data code string and second separator codes that divide a code string into partial code strings. The configuration has a code ID range table holding the code ID ranges for each code and a next code ID table holding next code IDs. Using the configuration, a partial code string is searched for in the search target code string by a first search code string consisting of the data code or the data code string and a first separator code. Next, using a second search code string consisting of first separator codes, the data code or the data code string separated by each of the first separator codes is searched from the found partial code string.

1 . A code string search apparatus that
 searches a search target code string that is the object of a search and is configured from
 partial code strings, each of the partial code strings being a combination of a data code or a data code string expressing data and a first separator code that expresses separator positions between the data code or the data code string, and 
 a second separator code expressing the separator position for the partial code strings, 
 by means of a first search code string that is configured from the data code or the data code string and the first separator code 
 so as to obtain the partial code string that includes the first search code string, and 
   searches the obtained partial code string by means of a second search code string that is the first separator code or a code string configured from the first separator code so as to output the data code or data code string fitting the second search code string as an output code string,   
       the code string search apparatus comprising:
 a code ID range table holding a code ID range for codes of a same code type, which is a range of code IDs uniquely identifying each and every code located in the search target code string; 
 a next code ID table
 holding, corresponding to each of the code IDs except the second separator code, a next ID code, which is a code ID of a code located next to a code whose code ID is the corresponding code ID in the search target code string and 
 holding, as a next code ID, for each of the code IDs of second separator codes, the code ID of a head code in each of the partial code strings related to the second separator codes; 
 
 a first search execution part that, referencing the code ID range table and the next code ID table, executes a search using the first search code string; 
 a second search execution part that, referencing the code ID range table and the next code ID table, executes a search using the second search code string; 
 wherein the first search execution part includes
 a first search code string read-out means that reads out the first search code string, and 
 a first code ID range read-out means that successively reads out from the code ID range table a code ID range pointed to by a code type of each code from the head code configuring the search code string read out by the first search code string read-out means, and 
 a first next code ID read-out means that
 reads out from the next code ID table a next code ID held corresponding to the code ID included within the code ID range of the head code type in the search code string and read out by the first code ID range read-out means, and thereafter 
 successively reads out from the next code ID table the next code ID held corresponding to the read-out next code ID, and 
 
 a first code ID verify means that verifies whether the next code ID read out by the first next ID read-out means is included within the code ID range read out by the first code ID range read-out means, and 
 a partial code string extraction means that
 when the first code ID verify means determines that the next code ID read out by the first next ID read-out means is included within the code ID range for the first separator code in the first search code string read out by the first code ID range read-out means,
 successively reads out, from the next code ID table, a next code ID held corresponding to the next code ID and 
 determines whether the read-out next code ID is included within the code ID range for the second separator code, and 
 
 when the determination is that the read-out next code ID is included within the code ID range for the second separator code,
 sets the next code ID held in the next code ID table corresponding to the read-out next code ID as a search start code ID for a partial code string; and wherein 
 
 
 
 the second search execution part includes
 a second search code string read-out means that reads out the second search code string, and 
 a second code ID range read-out means that successively reads out from the code ID range table a code ID range pointed to by a code type of each code from the head code configuring the search code string read out by the second search code string read-out means, and 
 a search start code ID read-out means that
 reads out the search start code ID set by the partial code string extraction means or the search start code ID modified by the output code string output means described below, and 
 
 a second next code ID read-out means that
 reads out from the next code ID table a next code ID held corresponding to the search start code ID read out by the search start code ID read-out means and after that 
 successively reads out from the next code ID table the next code ID held corresponding to the read-out next code ID, and 
 
 a second code ID verify means that verifies whether the next code ID read out by the second next code ID read-out means is included within the code ID range read out by the second code ID range read-out means, and 
 a code ID conversion means that converts the search start code ID read out by the search start code ID read-out means and the next code ID read out by the second next code ID read-out means into codes, and 
 an output code string storage means that
 successively appends each of the codes converted by the code ID conversion means so as to generate a code string and 
 stores the code string as an output code string, and 
 
 an output code string output means that,
 when the second code ID verify means determines that the next code ID read out by the second next code ID read-out means is included within the code ID range for the first separator code in the second search code string read out by the second code ID range read-out means, 
 outputs the output code string stored in the output code string storage means as a search result code string fitting the second search code string and, 
 by reading out from the next code ID table a next code ID held corresponding to the next code ID, 
 modifies the search start code ID by means of the read-out next code ID. 
 
 
 
     
     
         2 . The code string search apparatus according to  claim 1 , wherein,
 when a head code ID is taken to be a first code ID, which head code ID is included within the code ID range pointed to by the code type of a first code which is the head code in the first search code string,   the first code ID verify means verifies whether the next code ID held corresponding to the first code ID is included within the code ID range pointed to by the code type of a second code which is the code positioned next after the first code in the search target code string, and thereafter,   when the positions of the first code and second code in the search code string are modified by the read-out operations of the first code ID range read-out means and the first next ID read-out means,   the first code ID verify means verifies whether the next code ID held corresponding to the code ID of the first code, whose position has been modified, is included within the code ID range pointed to by a code type of the second code, whose position has been modified.   
     
     
         3 . The code string search apparatus according to  claim 2 , wherein
 the output code string output means deletes the output code string stored in the output code string storage means
 if the code converted from the next code by the code ID conversion means is not a data code and the next code ID is determined by the second code ID verify means not to be included within the code ID range read out by the second code ID range read-out means. 
   
     
     
         4 . The code string search apparatus according to  claim 3 , wherein
 the first code ID verify means, using each of all the code IDs included within the code ID range pointed to by the code type of the head code in the first search code string as a head code ID,
 verifies whether the next code ID read out by the first next ID read-out means is included within the code ID range read out by the code ID range read-out means. 
   
     
     
         5 . A code string search method performed by the code string search apparatus according to  claim 1 , comprising:
 a first search code string read-out step that reads out the first search code string;   a first code ID range read-out step that successively reads out from the code ID range table a code ID range pointed to by a code type of each code from the head code configuring the search code string read out by the search code string read-out step;   a first next ID read-out step that
 reads out from the next code ID table a next code ID held corresponding to the code ID included within the code ID range of the head code type in the search code string and read out by the first code ID range read-out step, and thereafter 
 successively reads out from the next code ID table the next code ID held corresponding to the read-out next code ID; 
   a first code ID verify step that verifies whether the next code ID read out by the first next ID read-out step is included within the code ID range read out by the first code ID range read-out step;   a partial code string extraction step that
 when the first code ID verify step determines that the next code ID read out by the first next ID read-out step is included within the code ID range for the first separator code in the first search code string read out by the first code ID range read-out step,
 successively reads out, from the next code ID table, a next code ID held corresponding to the next code ID and 
 determines whether the read-out next code ID is included within the code ID range for the second separator code, and 
 
 when the determination is that the read-out next code ID is included within the code ID range for the second separator code,
 sets the next code ID held in the next code ID table corresponding to the read-out next code ID as a search start code ID for a partial code string; 
 
   a second search code string read-out step that reads out the second search code string;   a second code ID range read-out step that successively reads out from the code ID range table a code ID range pointed to by a code type of each code from the head code configuring the search code string read out by the second search code string read-out step;   a search start code ID read-out step that
 reads out the search start code ID set by the partial code string extraction step or the search start code ID modified by the output code string output step described below; 
   a second next code ID read-out step that
 reads out from the next code ID table a next code ID held corresponding to the search start code ID read out by the search start code ID read-out step and after that
 successively reads out from the next code ID table the next code ID held corresponding to the read-out next code ID; 
 
   a second code ID verify step that verifies whether the next code ID read out by the second next code ID read-out step is included within the code ID range read out by the second code ID range read-out step;   a code ID conversion step that converts the search start code ID read out by the search start code ID read-out step and the next code ID read out by the second next code ID read-out step into codes;   an output code string storage step that
 successively appends each of the codes converted by the code ID conversion step so as to generate a code string and 
 stores the code string as an output code string; and 
   an output code string output step that,
 when the second code ID verify step determines that the next code ID read out by the second next code ID read-out step is included within the code ID range for the first separator code in the second search code string read out by the second code ID range read-out step, 
 outputs the output code string stored in the output code string storage step as a search result code string fitting the second search code string and, by reading out from the next code ID table a next code ID held corresponding to the next code ID, 
 modifies the search start code ID by means of the read-out next code ID. 
   
     
     
         6 . The code string search method according to  claim 5 , wherein,
 when a head code ID is taken to be a first code ID, which head code ID is included within the code ID range pointed to by the code type of a first code which is the head code in the first search code string,   the first code ID verify step verifies whether the next code ID held corresponding to the first code ID is included within the code ID range pointed to by the code type of a second code which is the code positioned next after the first code in the search target code string, and thereafter,   when the positions of the first code and second code in the search code string are modified by the read-out operations of the first code ID range read-out step and the first next ID read-out step,   the first code ID verify step verifies whether the next code ID held corresponding to the code ID of the first code, whose position has been modified, is included within the code ID range pointed to by a code type of the second code, whose position has been modified.   
     
     
         7 . The code string search method according to  claim 6 , wherein
 the output code string output step deletes the output code string stored in the output code string storage means
 if the code converted from the next code by the code ID conversion step is not a data code and the next code ID is determined by the second code ID verify step not to be included within the code ID range read out by the second code ID range read-out step. 
   
     
     
         8 . The code string search method according to  claim 7 , wherein
 the first code ID verify step, using each of all the code IDs included within the code ID range pointed to by the code type of the head code in the first search code string as a head code ID,
 verifies whether the next code ID read out by the first next ID read-out step is included within the code ID range read out by the code ID range read-out step. 
   
     
     
         9 . A code string search program for causing a computer which realizes the code string search apparatus according to  claim 1  to execute a code string search method, comprising:
 a first search code string read-out step that reads out the first search code string; 
 a first code ID range read-out step that successively reads out from the code ID range table a code ID range pointed to by a code type of each code from the head code configuring the search code string read out by the search code string read-out step; 
 a first next ID read-out step that
 reads out from the next code ID table a next code ID held corresponding to the code ID included within the code ID range of the head code type in the search code string and read out by the first code ID range read-out step, and thereafter 
 successively reads out from the next code ID table the next code ID held corresponding to the read-out next code ID; 
 
 a first code ID verify step that verifies whether the next code ID read out by the first next ID read-out step is included within the code ID range read out by the first code ID range read-out step; 
 a partial code string extraction step that
 when the first code ID verify step determines that the next code ID read out by the first next ID read-out step is included within the code ID range for the first separator code in the first search code string read out by the first code ID range read-out step,
 successively reads out, from the next code ID table, a next code ID held corresponding to the next code ID and 
 determines whether the read-out next code ID is included within the code ID range for the second separator code, and 
 
 when the determination is that the read-out next code ID is included within the code ID range for the second separator code,
 sets the next code ID held in the next code ID table corresponding to the read-out next code ID as a search start code ID for a partial code string; 
 
 
 a second search code string read-out step that reads out the second search code string; 
 a second code ID range read-out step that successively reads out from the code ID range table a code ID range pointed to by a code type of each code from the head code configuring the search code string read out by the second search code string read-out step; 
 a search start code ID read-out step that
 reads out the search start code ID set by the partial code string extraction step or the search start code ID modified by the output code string output step described below; 
 
 a second next code ID read-out step that
 reads out from the next code ID table a next code ID held corresponding to the search start code ID read out by the search start code ID read-out step and after that
 successively reads out from the next code ID table the next code ID held corresponding to the read-out next code ID; 
 
 
 a second code ID verify step that verifies whether the next code ID read out by the second next code ID read-out step is included within the code ID range read out by the second code ID range read-out step; 
 a code ID conversion step that converts the search start code ID read out by the search start code ID read-out step and the next code ID read out by the second next code ID read-out step into codes; 
 an output code string storage step that
 successively appends each of the codes converted by the code ID conversion step so as to generate a code string and 
 stores the code string as an output code string; and 
 
 an output code string output step that,
 when the second code ID verify step determines that the next code ID read out by the second next code ID read-out step is included within the code ID range for the first separator code in the second search code string read out by the second code ID range read-out step, 
 outputs the output code string stored in the output code string storage step as a search result code string fitting the second search code string and, by reading out from the next code ID table a next code ID held corresponding to the next code ID, 
 modifies the search start code ID by means of the read-out next code ID. 
 
 
     
     
         10 . The code string search program according to  claim 9 , wherein,
 when a head code ID is taken to be a first code ID, which head code ID is included within the code ID range pointed to by the code type of a first code which is the head code in the first search code string,   the first code ID verify step verifies whether the next code ID held corresponding to the first code ID is included within the code ID range pointed to by the code type of a second code which is the code positioned next after the first code in the search target code string, and thereafter,   when the positions of the first code and second code in the search code string are modified by the read-out operations of the first code ID range read-out step and the first next ID read-out step,   the first code ID verify step verifies whether the next code ID held corresponding to the code ID of the first code, whose position has been modified, is included within the code ID range pointed to by a code type of the second code, whose position has been modified.   
     
     
         11 . The code string search program according to  claim 10 , wherein
 the output code string output step deletes the output code string stored in the output code string storage means
 if the code converted from the next code by the code ID conversion step is not a data code and the next code ID is determined by the second code ID verify step not to be included within the code ID range read out by the second code ID range read-out step. 
   
     
     
         12 . The code string search program according to  claim 11 , wherein
 the first code ID verify step, using each of all the code IDs included within the code ID range pointed to by the code type of the head code in the first search code string as a head code ID,
 verifies whether the next code ID read out by the first next ID read-out step is included within the code ID range read out by the code ID range read-out step. 
   
     
     
         13 . A computer readable storage medium storing the code string search program according to  claim 9 . 
     
     
         14 . A data configuration adapted to a code string search method for searching for a search target code string that is the object of a search and is configured from
 partial code strings, each of the partial code strings being a combination of a data code or a data code string expressing data and a first separator code that expresses separator positions between the data code or the data code string, and   a second separator code expressing the separator position for the partial code strings,   by means of a first search code string that is configured from the data code or the data code string and the first separator code   so as to obtain the partial code string that includes the first search code string, and   searches the obtained partial code string by means of a second search code string that is the first separator code or a code string configured from the first separator code so as to output the data code or data code string fitting the second search code string as an output code string,   
       the data configuration comprising:
 a code ID range table holding a code ID range for codes of a same code type, which is a range of code IDs uniquely identifying each and every code located in the search target code string; 
 a next code ID table
 holding, corresponding to each of the code IDs except the second separator code, a next ID code, which is a code ID of a code located next to a code whose code ID is the corresponding code ID in the search target code string and 
 holding, as a next code ID, for each of the code IDs of second separator codes, the code ID of a head code in each of the partial code strings related to the second separator codes; and wherein 
 
 
       the code string search method according to  claim 5  is enabled by using the code ID range table and the next code ID table. 
     
     
         15 . A computer readable storage medium storing data with the data configuration according to  claim 14 . 
     
     
         16 . An index data creation apparatus for creating the index data for a code string search that
 searches a search target code string that is the object of a search and is configured from
 partial code strings, each of the partial code strings being a combination of a data code or a data code string expressing data and a first separator code that expresses separator positions between the data code or the data code string, and 
 a second separator code expressing the separator position for the partial code strings, 
 by means of a first search code string that is configured from the data code or the data code string and the first separator code 
 so as to obtain the partial code string that includes the first search code string, and 
   searches the obtained partial code string by means of a second search code string that is the first separator code or a code string configured from the first separator code so as to output the data code or data code string fitting the second search code string as an output code string,   
       the index data creation apparatus comprising:
 a search target code string read-out means that reads out the search target code string and obtains the number of occurrences of each code type for the codes in the read-out search target code string; 
 a code ID range table creation means that
 creates a code ID range table holding a code ID range for each code of a same code type, which is a range of code IDs uniquely identifying each and every code positioned in the search target code string, based on the number of occurrences of each code type obtained by the search target code string read-out means; 
 
 a next code ID table creation means that
 creates a next code ID table holding, corresponding to each of the code IDs, a next code ID, which is a code ID of a code located next to a code whose code ID is the corresponding code ID in the search target code string,
 based on the search target code string read out by the search target code string read-out means and the code ID range table created by the code ID range table creation means; and wherein 
 
 
 the next code ID table creation means, in correspondence to code IDs for the second separator code, stores a head code in a partial code string separated by the second separator code in the next code ID table instead of the code ID of the code located next to the second separator code. 
 
     
     
         17 . An index data creation method performed by the code string search apparatus according to  claim 16 , comprising:
 a search target code string read-out step that reads out the search target code string and obtains the number of occurrences of each code type for the codes in the read-out search target code string;   a code ID range table creation step that
 creates a code ID range table holding a code ID range for each code of a same code type, which is a range of code IDs uniquely identifying each and every code positioned in the search target code string, based on the number of occurrences of each code type obtained by the search target code string read-out step; 
   a next code ID table creation means that
 creates a next code ID table holding, corresponding to each of the code IDs, a next code ID, which is a code ID of a code located next to a code whose code ID is the corresponding code ID in the search target code string,
 based on the search target code string read out by the search target code string read-out means and the code ID range table created by the code ID range table creation step; and wherein 
 
   the next code ID table creation step, in correspondence to code IDs for the second separator code, stores a head code in a partial code string separated by the second separator code in the next code ID table instead of the code ID of the code located next to the second separator code.   
     
     
         18 . An index data creation program for causing a computer which realizes the index data creation apparatus according to  claim 16  to execute an index data creation method, comprising:
 a search target code string read-out step that reads out the search target code string and obtains the number of occurrences of each code type for the codes in the read-out search target code string; 
 a code ID range table creation step that
 creates a code ID range table holding a code ID range for each code of a same code type, which is a range of code IDs uniquely identifying each and every code positioned in the search target code string, based on the number of occurrences of each code type obtained by the search target code string read-out step; 
 
 a next code ID table creation means that
 creates a next code ID table holding, corresponding to each of the code IDs, a next code ID, which is a code ID of a code located next to a code whose code ID is the corresponding code ID in the search target code string,
 based on the search target code string read out by the search target code string read-out means and the code ID range table created by the code ID range table creation step; and wherein 
 
 
 the next code ID table creation step, in correspondence to code IDs for the second separator code, stores a head code in a partial code string separated by the second separator code in the next code ID table instead of the code ID of the code located next to the second separator code. 
 
     
     
         19 . A computer readable storage medium storing the index data creation program according to  claim 18 .