配对节点树保存/复原方法、最长一致/最短一致检索方法、比特序列检索方法以及存储介质

摘要

配对节点树由根节点、以及在相邻的存储区域中配置的分支节点和叶节点、或者分支节点之间或叶节点之间的节点对构成。分支节点包含进行比特序列检索的检索关键字的鉴别比特位置、和表示作为链接目的地节点对中的一个节点的代表节点的位置的位置信息。叶节点包含由检索对象比特序列构成的索引关键字。按照深度优先搜索顺序保存配对节点树的节点。重复下述处理来复原配对节点树：按照保存顺序读出节点，在堆栈中存储待复原节点的位置的位置信息，在分支节点持续的期间依次复原子节点，如果读出了叶节点则复原叶节点，追溯堆栈而确定下一个待复原的节点。

主权项

1.一种配对节点树保存方法，该配对节点树是用于比特序列检索的树，由根节点、以及在相邻的存储区域中配置的分支节点和叶节点、或者分支节点之间或叶节点之间的节点对构成，所述根节点是表示树的起点的节点，当该树的节点为一个时所述根节点是所述叶节点，当树的节点为两个以上时所述根节点是所述分支节点，所述分支节点包含进行比特序列检索的检索关键字的鉴别比特位置、和表示作为链接目的地节点对中的一个节点的代表节点的位置的位置信息，所述叶节点包含由检索对象比特序列构成的索引关键字，将如下构成的配对节点树的任意部分树保存在与配置该配对节点树的区域不同的其它存储区域中，该配对节点树构成为以所述树的任意节点作为检索开始节点，依次反复下述动作：在所述分支节点中根据该分支节点中包含的鉴别比特位置的检索关键字的比特值，来链接到链接目的地节点对的代表节点或与该代表节点成对的非代表节点，直至到达所述叶节点为止，由此将存储在所述叶节点中的索引关键字作为检索结果关键字，该检索结果关键字是所述树的以所述检索开始节点为根节点的任意部分树的、基于所述检索关键字的检索结果，该配对节点树保存方法的特征在于，将待保存的所述部分树的根节点指定为与保存节点的顺序对应的路径的开始点即巡回开始节点，从所述巡回开始节点仅链接所述节点对中的代表节点或非代表节点而巡回至叶节点，同时针对从所述巡回开始节点到所述叶节点的所述路径上的各节点，将表示该节点的位置的所述位置信息依次存储在堆栈中，并且将该节点的内容依次保存在所述其它存储区域中，反复进行所述堆栈的出栈动作直到得到代表节点或非代表节点的位置信息，从该堆栈中读出该位置信息，将与已读出该位置信息的所述代表节点或所述非代表节点形成节点对的非代表节点或代表节点指定为新的所述巡回开始节点，反复所述节点的巡回和保存。