BIT STRING RETRIEVAL DEVICE, RETRIEVAL METHOD AND PROGRAM

摘要

In order to make a duplicate key operable in a retrieval technique to which a coupled node tree is applied, a plurality of keys as a key string in which the key at the tail end is made a unique key are combined into an index key, and a plurality of keys as a key string in which the key at the tail end is made a unique key are combined into a retrieval key. Branch nodes are provided with a first discrimination position indicative of position information of a key to carry out a bit string comparison and a second discrimination position of the key in the retrieval key string to carry out a bit string retrieval and includes position information indicative of a position of a representative node, i.e., one of a pair of nodes of a link. A key at the first discrimination position of a branch node is taken out from the retrieval key string and the taken-out key is linked to one of a pair of nodes of a link in accordance with a bit value at the second discrimination position of the key. This is carried up to the arrival at a leaf node associated with an index key, so that the index key is retrieved.