| 主权项 |
一种比特序列检索方法，该方法采用了配对节点树，该配对节点树是用于比特序列检索的树，由根节点、以及配置在相邻存储区域中的分支节点和叶节点、或者分支节点之间或叶节点之间的节点对构成，上述根节点是表示树的起点的节点，当该树的节点为一个时上述根节点是上述叶节点，当树的节点为两个以上时上述根节点是上述分支节点，上述分支节点包含用于进行比特序列检索的检索关键字的鉴别比特位置、和表示作为链接目的地节点对中的一个节点的代表节点的位置的位置信息，上述叶节点包含由检索对象比特序列构成的索引关键字，该比特序列检索方法的特征在于，上述索引关键字由对前方有效比特序列进行编码后的编码比特序列构成，所述前方有效比特序列是以下比特序列中的任意一种：仅由有效比特构成的比特序列、仅由与比特值无关的无关比特构成的比特序列、或者在1比特以上的有效比特上连接了1比特以上的无关比特的比特序列，上述检索关键字由对前方有效比特序列进行编码后的编码比特序列构成，上述编码比特序列是由识别比特和数据比特的比特对构成的比特序列，该比特对是与构成上述前方有效比特序列的各比特对应的比特对，该识别比特表示该比特是无关比特还是有效比特，该数据比特在该比特是无关比特时为预定值，在该比特是有效比特时表示该比特的值，上述比特序列检索方法具有以下步骤：初始检索步骤，将上述配对节点树的任意部分树的根节点作为检索开始节点，一边依次反复下述动作：在上述分支节点中根据该分支节点所包含的鉴别比特位置的上述检索关键字的比特值，来链接到链接目的地节点对的代表节点或与该代表节点成对的非代表节点，一边通过至少 存储上述鉴别比特位置相当于在上述编码比特序列中识别比特所在的位置的分支节点的地址信息，来存储链接搜索的路径，直至到达上述叶节点为止；索引关键字取得步骤，从利用上述初始检索步骤到达的上述叶节点中取得索引关键字；差分比特位置取得步骤，在上述取得的上述索引关键字与上述检索关键字之间，在从比特序列开头到下述两种位置中任意一个更接近上述编码比特序列开头的比特位置的范围内，进行比特序列比较，取得成为不同比特值的开头比特位置作为差分比特位置，该两种位置是：上述取得的上述索引关键字中对末尾有效比特进行编码后的比特对的位置、和上述检索关键字中对开头无关比特进行编码后的比特对的位置；第1最长一致关键字取得步骤，如果上述取得的上述索引关键字与上述检索关键字在上述范围内一致，则取得上述取得的上述索引关键字作为最长一致关键字；分支节点选择步骤，作为上述比较结果，如果上述取得的上述索引关键字与上述检索关键字不一致，则针对上述路径上满足下述条件的分支节点中，选择上述鉴别比特位置为最接近上述编码比特序列末尾的比特位置的分支节点，上述条件是：鉴别比特位置相当于在上述编码比特序列中识别比特所在的位置、并且该鉴别比特位置是比上述差分比特位置更接近上述编码比特序列开头的比特位置；以及第2最长一致关键字取得步骤，针对从上述选择的上述分支节点链接到的节点对中，取得终端侧节点中包含的索引关键字作为最长一致关键字，其中所述终端侧节点是对应于表示上述无关比特的上述识别比特值而链接的叶节点。 |
