Code string search apparatus, search method, and program

A tree data configuration for a code string search method for searching search target code strings that are bit strings encoding search keys consisting of code strings, comprising:

• a coupled-node tree having a root node that is the starting point for the tree and node pairs which are two nodes, a primary node and a non-primary node, located in adjacent storage areas, as configurational elements of the tree, wherein
• the nodes have an area holding a node type which expresses whether the node is a branch node or a leaf node, and
• the branch node, in addition to the node type, includes an area holding a discrimination bit position for the encoded search key and an area holding information expressing the position of a primary node of a node pair that is a link target, and
• the leaf node, in addition to the node type, includes an area holding a search target code string or a reference pointer that points to a storage area for the search target code string,
• the tree data configuration being prescribed by the bit values for index keys that are bit strings encoding search target code strings and
• the encoding of a search key consisting of code strings and the search target code strings being one wherein
• at the head of the bit string expressing each code configuring each of those code strings is appended
• a continue bit, which is a differentiating bit expressing the fact that a code is following, and
• an end bit, which is a differentiating bit expressing the end of the code string;
• and
• wherein
• a search method by means of the search key is enabled such that
• an initial search step that
• searches, by means of the encoded search key, the search target code strings based on the tree data configuration of the coupled-node tree and
• obtains a search result code string in an initial search while memorizing the path in the coupled-node tree traversed in the initial search and
• a longest prefix match search step that
• obtains, as the longest prefix matching key, the longest search target code string that prefix-matches the search key from
• the search result code string obtained in the initial search and
• the search target code strings
• included in the leaf nodes existing on the memorized path over the coupled-node tree or
• stored in an areas pointed to by the reference pointers included in the leaf nodes existing on the memorized path over the coupled-node tree.