Longest match / shortest match retrieval apparatus of coupled node tree, search methods and programs

摘要

PPROBLEM TO BE SOLVED: To provide a method for the longest comformity/shortest comformity retrieval with a coupled node tree as the object of retrieval. PSOLUTION: A coupled node tree is comprised of: a root node; a branch node disposed between neighboring memory areas; and a pair of leaf nodes or branch nodes or a pair of a leaf node and a branch node. The branch node includes information indicating the discriminating bit position of a retrieval key and the position of one node of the pair of nodes to be linked. The leaf node includes an index key comprised of a retrieval subject bit sequence. The coupled node tree is retrieved by using the longest comformity/shortest comformity retrieval key, and the longest comformity/shortest comformity node is determined based on the comparison of the difference bit position of the index key of the retrieval result and the longest comformity/shortest comformity retrieval key and the discriminating bit position of the branch node on a retrieval path from the route node stored upon retrieval. PCOPYRIGHT: (C)2009,JPO&INPIT