BIT SEQUENCE SEARCH DEVICE, SEARCH METHOD, AND PROGRAM

摘要

Provided is a bit sequence search method using such a data structure of a bit sequence to be searched that the required storage capacity is small, the search speed is high, and the data maintenance is easy. The data structure includes a branch node and a leaf node, or a pair of branch nodes or a pair of leaf nodes arranged in adjacent storage regions. The branch node contains information indicating a position of a search key discriminating bit and a position of one of the nodes of the pair of the link destination. The leaf node includes a coupled node tree containing an index key formed by a bit sequence to be searched. The bit sequence search method executes index key search from a root node to a branch node by using a search key by successively repeating linking to any one of the node pair of the link destination in accordance with the search key bit value of the discriminating bit position contained in the branch node until the leaf node is reached.