比特序列检索装置及检索方法

摘要

为了提供使用配对节点树根据检索对象比特序列的集合来进行各种应用检索的方法这样的简便、高速的方法，而具有如下的配对节点树，该配对节点树由根节点与配置在相邻的存储区域中的分支节点和叶节点、或分支节点之间、或叶节点之间的节点对构成，分支节点包含表示检索关键字的鉴别比特位置和链接目的地节点对中的一个节点的位置的信息，叶节点包含由检索对象比特序列构成的索引关键字，配对节点树存储在数组中，位置信息是存储有与位置信息对应的节点的数组元素的数组编号，将配对节点树的任意节点作为检索开始节点，仅链接节点对中的数组编号小的一方而到达叶节点，由此求出以检索开始节点为根节点的任意部分树的索引关键字的最小值。

主权项

一种比特序列检索装置，该比特序列检索装置通过由比特序列构成的检索关键字，根据存储有由作为检索对象的比特序列构成的索引关键字的树的数据结构，来检索所述索引关键字，其特征在于，该比特序列检索装置具有：配对节点树，其具备作为所述树的起点的根节点、以及具有配置在相邻的存储区域中的代表节点和非代表节点这两个节点的作为树的构成要素的节点对，所述节点具有存储表示该节点是分支节点还是叶节点的节点类别的区域，所述分支节点除了所述节点类别以外，还包含存储所述检索关键字的鉴别比特位置的区域和存储表示链接目的地节点对的代表节点的位置的位置信息的区域，但是不包含存储由所述检索对象的比特序列构成的索引关键字的区域，所述叶节点除了所述节点类别以外，还包含存储由所述检索对象的比特序列构成的索引关键字的区域，但是不包含存储所述检索关键字的鉴别比特位置的区域和存储表示链接目的地节点对的代表节点的位置的位置信息的区域；检索开始节点读出单元，其取得表示作为所述节点对中的某一个节点的检索开始节点的位置的位置信息，通过该取得的表示检索开始节点的位置的位置信息，来读出检索开始节点；节点类别判定单元，其从所述节点的存储节点类别的区域中读出该节点类别，判定该节点类别是表示所述叶节点还是表示分支节点；索引关键字读出单元，其从所述叶节点的存储索引关键字的区域中读出该索引关键字；以及链接单元，其分别从所述分支节点的存储鉴别比特位置的区域和存储表示链接目的地节点对的代表节点的位置的位置信息的区域中，读出该鉴别比特位置和表示链接目的地节点对的代表节点的位置的位置信息，并通过该读出的鉴别比特位置的所述检索关键字的比特值和所述读出的表示链接目的地节点对的代表节点的位置的位置信息之间的运算，来求出表示链接目的地节点对的某个节点的位置的位置信息，从该求出的表示节点位置的位置信息所示的存储区域中，读出配置在该存储区域中的节点作为链接目的地节点，利用所述节点类别判定单元来判定通过所述检索开始节点读出单元读出的检索开始节点的节点类别，如果该节点类别表示叶节点，则通过所述索引关键字读出单元从该叶节点中读出索引关键字，如果该节点类别表示分支节点，则通过所述链接单元读出链接目的地节点，并反复利用所述节点类别判定单元来判定该读出的链接目的地节点的节点类别，直到该节点类别表示叶节点为止，通过所述索引关键字读出单元从该叶节点中读出索引关键字，将通过所述索引关键字读出单元读出的索引关键字作为所述配对节点树的以所述检索开始节点为根节点的部分树的基于所述检索关键字的检索结果、即检索结果关键字。