Patent ID: 8145665
Filing Date: 2012-03-27
Classification: G06F

Abstract:
1. A bit string search apparatus comprising: a coupled node tree which is used in a bit string search and comprises a root node and a node pair, the node pair being a branch node and leaf node, or a pair of branch nodes, or a pair of leaf nodes located in adjacent storage areas, the root node being a node that expresses a starting point of the tree and, which is a leaf node when there is one node in the tree and a branch node when there are two or more nodes in the tree, the branch node including a discrimination bit position of a search key for the bit string search, and position information indicating a position of a primary node, which is one node of a node pair of a link target, and the leaf node including an index key that is a bit string that is a target of a search, wherein the index key comprises an encoded bit string that is obtained by encoding a significant bit prefixed bit string, which is either a bit string of only significant bits or a bit string of only don't-care bits or a bit string comprising one or more significant bits to which one or more don't-care bits are suffixed, and the search key comprises an encoded bit string that is obtained by encoding a significant bit prefixed bit string, and the encoded bit string is a bit string which is a sequence of bit pairs corresponding to each bit configuring the significant bit prefixed bit string and is a bit string comprising bit pairs with a distinguishing bit which expresses whether the bit is a don't-care bit or a significant bit and, if the bit is a don't-care bit, with a bit with a previously decided value, and, if the bit is a significant bit, with a data bit expressing the value of that bit; an initial search means performing, with the root node of an arbitrary subtree of the coupled node tree as a search start node, repeated and successive linkage to a primary node of a node pair of the link target or a non-primary node that is a pair to that primary node, in accordance with a bit value of a search key at the discrimination bit position included in the branch node until the leaf node is reached, while memorizing a path being traversed by at least memorizing address information of the branch nodes with the discrimination bit position corresponding to the position wherein exists a distinguishing bit in the encoded bit string; an index key acquiring means acquiring an index key from the leaf node reached by the initial search means; a difference bit position acquiring means which compares bits strings between the index key and the search key in the range from the head of the bit string until the bit position which is closer to the head of the bit string, which bit position is determined by comparing the position of the bit pair that is encoded at the tail end of the significant bits of the index key acquired above and the position of the bit pair that is encoded at the first of the don't-care bits in the search key, and which acquires the bit position of the highest-order differing bit value as a difference bit position; a first longest matching key acquiring means which acquires the index key acquired above as a longest matching key if the index key acquired above and the search key coincide in the above range; a branch node selecting means which, if the result of the above comparison indicates that the index key acquired above and the search key do not coincide, selects the branch node with a discrimination bit position that is a bit position closest to the tail end of the encoded bit string, from among the branch nodes on the path where the discrimination bit position of that node points to one of the positions of the distinguishing bits in the encoded bit string and its discrimination bit position is a bit position closer to the head of the encoded bit string than the difference bit position; and a second longest matching key acquiring means which acquires, as the longest matching key, the index key of a terminal-side node of the node pairs linked to from the branch node selected above, the terminal-side node which is the leaf node that is linked to in accordance with a distinguishing bit value which expresses a don't-care bit.