【手続補正書】
【提出日】平成22年1月26日(2010.1.26)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ビット列検索に用いるツリーの任意の部分木を退避するツリーの退避装置において、
ツリーの始点であるルートノードと、隣接した記憶領域に配置される代表ノードと非代表ノードである２つのノードを有する、ツリーの構成要素としてのノード対を有し、前記ノードは該ノードがブランチノードであるかリーフノードであるかを示すノード種別を格納する領域を有し、前記ブランチノードは、前記ノード種別に加えて、前記検索キーの弁別ビット位置を格納する領域とリンク先のノード対の代表ノードの位置を示す位置情報を格納する領域を含むが、前記検索対象のビット列からなるインデックスキーを格納する領域を含まないものであり、前記リーフノードは、前記ノード種別に加えて、前記検索対象のビット列からなるインデックスキーを格納する領域を含むが、前記検索キーの弁別ビット位置を格納する領域とリンク先のノード対の代表ノードの位置を示す位置情報を格納する領域を含まないものであり、前記ツリーの任意のノードを検索開始ノードとして、前記ブランチノードにおいて該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいは該代表ノードと対になる非代表ノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより、前記リーフノードに格納されたインデックスキーを、前記検索開始ノードをルートノードとする前記ツリーの任意の部分木の前記検索キーによる検索の結果である検索結果キーとするように構成されたカップルドノードツリーと、
退避しようとする前記部分木のルートノードを、ノードを退避する順序に対応する経路の開始点である巡回開始ノードとして指定する巡回開始ノード指定手段と、
前記巡回開始ノード指定手段あるいは後記次巡回開始ノード指定手段で指定された巡回開始ノードから、前記ノード対のうち代表ノードのみあるいは非代表ノードのみをリンクしてリーフノードに至るまで巡回しながら、前記巡回開始ノードから前記リーフノードに至る前記経路上の各ノードについて、当該ノードの位置を示す前記位置情報を順次スタックに格納するとともに当該ノードの内容を順次カップルドノードツリーが配置されている記憶領域とは別の記憶領域に退避するノード退避手段と、
代表ノードあるいは非代表ノードの位置情報が得られるまで前記スタックから順次位置情報を読み出し、該位置情報が読み出された前記代表ノードあるいは前記非代表ノードとノード対をなす非代表ノードあるいは代表ノードを、次の前記巡回開始ノードとして指定する次巡回開始ノード指定手段と、
を備え、
前記ノード退避手段によるノードの退避と前記次巡回開始ノード指定手段による次の巡回開始ノードの指定を、前記退避しようとする前記部分木の全てのノードを退避するまで繰り返す、
ことを特徴とするカップルドノードツリーの退避装置。
【請求項２】
コンピュータがビット列検索に用いるツリーの任意の部分木を退避するツリーの退避方法において、
前記ツリーは、
該ツリーの始点であるルートノードと、隣接した記憶領域に配置される代表ノードと非代表ノードである２つのノードを有する、ツリーの構成要素としてのノード対を有し、前記ノードは該ノードがブランチノードであるかリーフノードであるかを示すノード種別を格納する領域を有し、前記ブランチノードは、前記ノード種別に加えて、前記検索キーの弁別ビット位置を格納する領域とリンク先のノード対の代表ノードの位置を示す位置情報を格納する領域を含むが、前記検索対象のビット列からなるインデックスキーを格納する領域を含まないものであり、前記リーフノードは、前記ノード種別に加えて、前記検索対象のビット列からなるインデックスキーを格納する領域を含むが、前記検索キーの弁別ビット位置を格納する領域とリンク先のノード対の代表ノードの位置を示す位置情報を格納する領域を含まないものであり、前記ツリーの任意のノードを検索開始ノードとして、前記ブランチノードにおいて該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいは該代表ノードと対になる非代表ノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより、前記リーフノードに格納されたインデックスキーを、前記検索開始ノードをルートノードとする前記ツリーの任意の部分木の前記検索キーによる検索の結果である検索結果キーとするように構成されたカップルドノードツリーであって、
退避しようとする前記部分木のルートノードを、ノードを退避する順序に対応する経路の開始点である巡回開始ノードとして指定する巡回開始ノード指定ステップと、
前記巡回開始ノード指定ステップあるいは後記次巡回開始ノード指定ステップで指定された巡回開始ノードから、前記ノード対のうち代表ノードのみあるいは非代表ノードのみをリンクしてリーフノードに至るまで巡回しながら、前記巡回開始ノードから前記リーフノードに至る前記経路上の各ノードについて、当該ノードの位置を示す前記位置情報を順次スタックに格納するとともに当該ノードの内容を順次カップルドノードツリーが配置されている記憶領域とは別の記憶領域に退避するノード退避ステップと、
代表ノードあるいは非代表ノードの位置情報が得られるまで前記スタックから順次位置情報を読み出し、該位置情報が読み出された前記代表ノードあるいは前記非代表ノードとノード対をなす非代表ノードあるいは代表ノードを、次の前記巡回開始ノードとして指定する次巡回開始ノード指定ステップと、
を備え、
前記ノード退避ステップによるノードの退避と前記次巡回開始ノード指定ステップによる次の巡回開始ノードの指定を、前記退避しようとする前記部分木の全てのノードを退避するまで繰り返す、
ことを特徴とするカップルドノードツリーの退避方法。
【請求項３】
前記カップルドノードツリーは配列に記憶され、前記位置情報は、該位置情報に対応する前記ノードが格納された前記配列の配列要素の配列番号である、ことを特徴とする請求項２記載のカップルドノードツリーの退避方法。
【請求項４】
前記別の記憶領域に退避される前記内容には、前記ブランチノードを退避する場合は前記弁別ビット位置が含まれ、前記リーフノードを退避する場合は前記インデックスキーが含まれ、前記ブランチノードと前記リーフノードを区別する種別情報が前記ブランチノードと前記リーフノードの双方に含まれ、前記種別情報も退避され、前記ブランチノードに含まれる前記位置情報は退避されないことを特徴とする請求項２載のカップルドノードツリーの退避方法。
【請求項５】
前記別の記憶領域は配列であることを特徴とする請求項２記載のカップルドノードツリーの退避方法。
【請求項６】
前記ノード退避ステップは、前記ノードの内容を順次カップルドノードツリーが配置されている記憶領域とは別の記憶領域に退避することに替えて、当該ノードの内容を順次伝送媒体を介して外部装置に送信すること、
を特徴とする請求項２記載のカップルドノードツリーの退避方法。
【請求項７】
請求項２記載のカップルドノードツリーの退避方法により退避されたノードの内容からなる退避情報により、退避された順番で順次ノードを復元することによって前記カップルドノードツリーを復元するカップルドノードツリーの復元装置において、
復元しようとするカップルドノードツリーのルートノードを格納するノード格納用記憶領域を取得するルートノード格納用記憶領域取得手段と、
前記退避情報を順次読出し、前記ルートノード格納用記憶領域取得手段あるいは後記ブランチノード復元手段により取得された、もしくは後記ノード格納用記憶領域探索手段により探索されたノード格納用記憶領域に書き込むことでノードを復元するノード復元手段と、
前記ノード復元手段で復元されたノードの種別を判定するノード種別判定手段と、
前記ノード種別判定手段で判定されたノードの種別がブランチノードであれば、該ブランチノードの次に退避したノードである子ノードと該子ノードと対をなすノードをそれぞれ格納するノード格納用記憶領域を取得するとともに、該子ノードを含むノード対の代表ノードを格納する前記ノード格納用記憶領域の位置情報を前記ブランチノードの代表ノード番号に書き込むブランチノード復元手段と、
前記ノード種別判定手段で判定されたノードの種別がリーフノードであれば、復元中の前記カップルドノードツリーのツリー構造をルートノードに向かって遡って、取得済みだがノードの内容がいまだ格納されていないノード格納用記憶領域を探索するノード格納用記憶領域探索手段と、
を備え、
前記ノード復元手段、前記ノード種別判定手段、前記ブランチノード復元手段、及び前記ノード格納用記憶領域探索手段による処理を、前記復元しようとするカップルドノードツリーの全ての前記退避されたノードを復元するまで繰り返す、
ことを特徴とするカップルドノードツリーの復元装置。
【請求項８】
コンピュータが、請求項２記載のカップルドノードツリーの退避方法により退避されたノードの内容からなる退避情報により、退避された順番で順次ノードを復元することによって前記カップルドノードツリーを復元するカップルドノードツリーの復元方法において、
復元しようとするカップルドノードツリーのルートノードを格納するノード格納用記憶領域を取得するルートノード格納用記憶領域取得ステップと、
前記退避情報を順次読出し、前記ルートノード格納用記憶領域取得ステップあるいは後記ブランチノード復元ステップにより取得された、もしくは後記ノード格納用記憶領域探索ステップにより探索されたノード格納用記憶領域に書き込むことでノードを復元するノード復元ステップと、
前記ノード復元ステップで復元されたノードの種別を判定するノード種別判定ステップと、
前記ノード種別判定ステップで判定されたノードの種別がブランチノードであれば、該ブランチノードの次に退避したノードである子ノードと該子ノードと対をなすノードをそれぞれ格納するノード格納用記憶領域を取得するとともに、該子ノードを含むノード対の代表ノードを格納する前記ノード格納用記憶領域の位置情報を前記ブランチノードの代表ノード番号に書き込むブランチノード復元ステップと、
前記ノード種別判定ステップで判定されたノードの種別がリーフノードであれば、復元中の前記カップルドノードツリーのツリー構造をルートノードに向かって遡って、取得済みだがノードの内容がいまだ格納されていないノード格納用記憶領域を探索するノード格納用記憶領域探索ステップと、
を備え、
前記ノード復元ステップ、前記ノード種別判定ステップ、前記ブランチノード復元ステップ、及び前記ノード格納用記憶領域探索ステップの処理を、前記復元しようとするカップルドノードツリーの全ての前記退避されたノードを復元するまで繰り返す、
ことを特徴とするカップルドノードツリーの復元方法。
【請求項９】
前記カップルドノードツリーは配列に復元され、復元された前記ブランチノードに書き込まれる前記位置情報は、該位置情報に対応する前記代表ノードを格納する配列要素の配列番号である、ことを特徴とする請求項８記載のカップルドノードツリーの復元方法。
【請求項１０】
前記復元しようとするカップルドノードツリーは、前記退避情報に退避された元の前記カップルドノードツリーの部分木に相当するものであり、
前記ノード復元ステップは、該部分木のルートノードよりも前の順番で退避された前記退避情報の読出をスキップし、該部分木の該ルートノードの前記内容から順次、前記退避情報を読み出すものであり、
前記ノード格納用記憶領域探索ステップにおいて、復元中の前記部分木のルートノードまで遡ると復元を終了する、
ことを特徴とする請求項８記載のカップルドノードツリーの復元方法。
【請求項１１】
前記退避情報は配列に格納されていることを特徴とする請求項８記載のカップルドノードツリーの復元方法。
【請求項１２】
コンピュータが、請求項６記載のカップルドノードツリーの退避方法により前記外部装置に送信された退避情報を受信し、送信された順番で順次ノードを前記外部装置の記憶領域に復元することによって前記カップルドノードツリーを復元するカップルドノードツリーの復元方法であって、
復元しようとするカップルドノードツリーのルートノードを格納するノード格納用記憶領域を取得するルートノード格納用記憶領域取得ステップと、
前記退避情報を順次受信し、前記ルートノード格納用記憶領域取得ステップあるいは後記ブランチノード復元ステップにより取得された、もしくは後記ノード格納用記憶領域探索ステップにより探索されたノード格納用記憶領域に書き込むことでノードを復元するノード復元ステップと、
前記ノード復元ステップで復元されたノードの種別を判定するノード種別判定ステップと、
前記ノード種別判定ステップで判定されたノードの種別がブランチノードであれば、該ブランチノードの次に退避したノードである子ノードと該子ノードと対をなすノードをそれぞれ格納するノード格納用記憶領域を取得するとともに、該子ノードを含むノード対の代表ノードを格納する前記ノード格納用記憶領域の位置情報を前記ブランチノードの代表ノード番号に書き込むブランチノード復元ステップと、
前記ノード種別判定ステップで判定されたノードの種別がリーフノードであれば、復元中の前記カップルドノードツリーのツリー構造をルートノードに向かって遡って、取得済みだがノードの内容がいまだ格納されていないノード格納用記憶領域を探索するノード格納用記憶領域探索ステップと、
を備え、
前記ノード復元ステップ、前記ノード種別判定ステップ、前記ブランチノード復元ステップ、及び前記ノード格納用記憶領域探索ステップの処理を、前記復元しようとするカップルドノードツリーの全ての前記退避されたノードを復元するまで繰り返す、
ことを特徴とするカップルドノードツリーの復元方法。
【請求項１３】
請求項２〜６のいずれか１項に記載のカップルドノードツリーの退避方法または請求項８〜１２のいずれか１項に記載のカップルドノードツリーの復元方法をコンピュータに実行させるためのプログラム。
【請求項１４】
請求項２〜６のいずれか１項に記載のカップルドノードツリーの退避方法または請求項８〜１２のいずれか１項に記載のカップルドノードツリーの復元方法をコンピュータに実行させるためのプログラムを記憶したことを特徴とするコンピュータ読み取り可能な記憶媒体。
【請求項１５】
請求項２記載のカップルドノードツリーの退避方法により前記別の記憶領域に退避されたカップルドノードツリーのノード列のデータ構造。
【請求項１６】
請求項８または１２記載のカップルドノードツリーの復元方法により前記カップルドノードツリーを復元可能なように構成されたデータ構造。
【請求項１７】
請求項２記載のカップルドノードツリーの退避方法により前記別の記憶領域に退避されたカップルドノードツリーのノード列のデータ構造、請求項８記載のカップルドノードツリーの復元方法により前記カップルドノードツリーを復元可能なように構成されたデータ構造、または請求項１２記載のカップルドノードツリーの復元方法により前記カップルドノードツリーを復元可能なように構成されたデータ構造のいずれか１つのデータ構造を記憶したことを特徴とするコンピュータ読み取り可能な記憶媒体。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】発明の名称
【補正方法】変更
【補正の内容】
【発明の名称】カップルドノードツリーの退避／復元装置、退避／復元方法及びプログラム
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００７２
【補正方法】変更
【補正の内容】
【００７２】
図３は、本発明を実施するためのハードウェア構成例を説明する図である。
本発明の検索装置による検索処理及び退避／復元処理を含むデータメンテナンスは中央処理装置３０２及びキャッシュメモリ３０３を少なくとも備えたデータ処理装置３０１によりデータ格納装置３０８を用いて実施される。カップルドノードツリーが配置される配列３０９と検索中にたどるノードが格納された配列要素の配列番号を記憶する探索経路スタック３１０を有するデータ格納装置３０８は、主記憶装置３０５または外部記憶装置３０６で実現することができ、あるいは通信装置３０７を介して接続された遠方に配置された装置を用いることも可能である。図１の配列１００は、配列３０９の一例である。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０１０４
【補正方法】変更
【補正の内容】
【０１０４】
ステップＳ９１５に進み、ステップＳ９１２で得た代表ノードの配列番号にステップＳ９１３で得たブール値の論理否定値を加算した配列番号を得る。
ステップＳ９１４で得た配列番号は、挿入キーをインデックスキーとして持つリーフノードが格納される配列要素の配列番号であり、ステップＳ９１５で得た配列番号は、そのリーフノードと対を成すノードが格納される配列要素のものである。