木構造処理装置及びプログラム
【課題】木構造を分割した各部分木内のノード数とそれら部分木間の関係を表す情報の規模とを共に抑制する。
【解決手段】木構造処理装置は、木構造を分割して得られる各部分木がそれぞれ当該木構造のうちのどのノードを含むかを表す部分木情報と、各部分木を参照する各参照ノードを特定する参照関係情報とを記憶するクラスタ保持部２０と、木構造へのノードの追加により第１の部分木のノードの数が上限数を超えた場合に第１の部分木から第２の部分木を分割し、分割に応じて部分木情報を更新する分割手段１６と、分割手段による分割に応じて第２の参照ノードを新たに生成して参照関係情報を更新すると共に、第２の参照ノードが第１の参照ノードが含まれる部分木に含まれることを表す情報を部分木情報に追加し、第１及び第２の参照ノードが第１及び第２の部分木と、親子関係を構成することを表す情報を木構造情報に追加するクラスタ構成部１８とを備える。
【解決手段】木構造処理装置は、木構造を分割して得られる各部分木がそれぞれ当該木構造のうちのどのノードを含むかを表す部分木情報と、各部分木を参照する各参照ノードを特定する参照関係情報とを記憶するクラスタ保持部２０と、木構造へのノードの追加により第１の部分木のノードの数が上限数を超えた場合に第１の部分木から第２の部分木を分割し、分割に応じて部分木情報を更新する分割手段１６と、分割手段による分割に応じて第２の参照ノードを新たに生成して参照関係情報を更新すると共に、第２の参照ノードが第１の参照ノードが含まれる部分木に含まれることを表す情報を部分木情報に追加し、第１及び第２の参照ノードが第１及び第２の部分木と、親子関係を構成することを表す情報を木構造情報に追加するクラスタ構成部１８とを備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、木構造処理装置及びプログラムに関する。
【背景技術】
【０００２】
特許文献１に開示された装置は、ＸＭＬ（eXtensible Markup Language）文書等、文書要素同士が木構造を構成している構造化文書をいくつかのクラスタと呼ばれる部分木構造に分割した上で、クラスタ毎にその内部の文書要素の木構造を表現するデータ構造を持つようにするものである。このように構造化文書を分割することで、個々のクラスタ毎にロックをかけて複数人が同時に編集できるようにし、さらに一つのデータ構造のサイズを小さくしている。また、要素の先祖・子孫関係の判定のために、さらに元の構造化文書の木構造におけるクラスタレベルでの先祖・子孫関係を表すデータ構造を持つようにしている。そして、クラスタレベルで先祖・子孫関係がなければ、要素間にも先祖・子孫関係がないことを利用して、要素間の先祖・子孫関係の有無の判定に要する時間を低減している。この従来技術では、文書要素の数が膨大なものとなった場合、分割するクラスタの数を増やせば個々のクラスタ内の文書要素の数を抑制できるが、クラスタレベルの関係を表すデータ構造が大きくなる。逆に、クラスタレベルの関係を表すデータ構造の規模を抑制しようとすると、個々のクラスタに含まれる文書要素の数が大きくなる。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特許第４０４５４００号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明は、木構造を分割した各部分木内のノード数とそれら部分木間の関係を表す情報の規模とを共に抑制できるようにすることを目的とする。
【課題を解決するための手段】
【０００５】
請求項１に係る発明は、実ノード及び参照ノードを含むノード群が構成する１以上の木構造を表す木構造情報と、前記１以上の木構造の各々を分割して得られる各部分木がそれぞれ当該木構造のうちのどのノードを含むかを表す部分木情報と、前記各部分木を参照する各参照ノードを特定する参照関係情報と、を記憶する記憶手段と、前記木構造情報に対するノードの追加により前記部分木情報が表す各部分木のうち第１の参照ノードが参照する第１の部分木のノードの数があらかじめ定めた上限数を超えた場合に、当該第１の部分木から第２の部分木を分割することにより、前記第１の部分木及び前記第２の部分木のノードの数が共に前記上限数以下となるようにし、当該分割に応じて前記記憶手段に記憶された前記部分木情報を更新する分割手段と、前記分割手段による分割に応じて前記第２の部分木を参照する第２の参照ノードを新たに生成し、前記第２の部分木を参照する参照ノードが前記第２の参照ノードであることを示す情報を前記参照関係情報に追加すると共に、前記第２の参照ノードが前記第１の参照ノードが含まれる部分木に含まれることを表す情報を前記部分木情報に追加し、前記第１の参照ノードと前記第２の参照ノードとが前記第１の部分木と前記第２の部分木との親子関係に対応する親子関係を構成することを表す情報を前記木構造情報に追加する、情報追加手段と、を備える木構造処理装置である。
【０００６】
請求項２に係る発明は、実ノード及び参照ノードを含むノード群が構成する１以上の木構造を表す木構造情報と、前記１以上の木構造の各々を分割して得られる各部分木がそれぞれ当該木構造のうちのどのノードを含むかを表す部分木情報と、前記各部分木を参照する各参照ノードを特定する参照関係情報と、を記憶する記憶手段と、前記木構造情報に対するノードの追加により前記部分木情報が表す各部分木のうち第１の参照ノードが参照する第１の部分木のノードの数があらかじめ定めた上限数を超えた場合に、当該第１の部分木から第２の部分木を分割することにより、前記第１の部分木及び前記第２の部分木のノードの数が共に前記上限数以下となるようにし、当該分割に応じて前記記憶手段に記憶された前記部分木情報を更新する分割手段と、前記分割手段による分割に応じて前記第２の部分木を参照する第２の参照ノードを新たに生成し、前記第２の部分木を参照する参照ノードが前記第２の参照ノードであることを示す情報を前記参照関係情報に追加すると共に、前記第２の参照ノードが前記第１の部分木に含まれることを表す情報を前記部分木情報に追加し、前記第２の参照ノードが前記第２の部分木の根ノードの親ノードに該当する前記第１の部分木のノードの子であることを示す情報を前記木構造情報に追加する、情報追加手段と、を備える木構造処理装置である。
【０００７】
請求項３に係る発明は、前記木構造情報が表す１以上の木構造のうちのいずれかの木構造の中から、先祖と子孫の関係にあるか否かの判定対象とする第１の実ノードと第２の実ノードとの指定を受け付ける指定受付手段と、同一の部分木内にある２つのノードについて、当該ノード同士の間に先祖と子孫の関係があるか否かを、前記記憶手段に記憶された部分木情報が表す各ノード間の親子関係をたどることで判定する第１の判定手段と、前記指定受付手段で受け付けた前記第１の実ノードと前記第２の実ノードとの間に先祖と子孫の関係があるかどうかを判定するための判定処理を行う第２の判定手段と、を更に備え、前記第２の判定手段が行う前記判定処理では、ある部分木を参照する参照ノードが含まれる部分木を前記ある部分木の１階層上位の部分木と呼ぶ場合に、前記第１の実ノードが属する部分木の上位に該当する各階層の部分木からなる第１の部分木系列と前記第２の実ノードが属する部分木の上位に該当する各階層の部分木からなる第２の部分木系列とを前記記憶手段に記憶された前記部分木情報及び前記参照関係情報に基づき求め、求めた前記第１の部分木系列と前記第２の部分木系列との間で共通する部分木を特定し、特定した部分木内にノードのうち前記第１の実ノード及び前記第２の実ノードにそれぞれ対応する２つのノードを特定し、特定した２つのノード同士の間に先祖と子孫の関係があるか否かの判定を前記第１の判定手段に実行させ、この判定の結果、前記特定した２つのノード同士の間に先祖と子孫の関係がないと判定された場合に、前記指定受付手段で受け付けた前記第１の実ノードと前記第２の実ノードとの間に先祖と子孫の関係がないと判定する、ことを特徴とする請求項１又は２に記載の木構造処理装置である。
【０００８】
請求項４に係る発明は、前記第２の判定手段が行う前記判定処理では、前記特定した２つのノード同士の間に先祖と子孫の関係があると前記第１の判定手段により判定された場合、前記指定受付手段で受け付けた前記第１の実ノードと前記第２の実ノードの中から、前記特定した２つのノードのうち先祖側のノードに対応するノードを新たな第１の実ノードとして特定し、前記特定した部分木内の前記特定した２つのノード同士を結ぶ経路上のノードのうちの前記先祖側のノードの子に該当する参照ノードが参照する下位の部分木の根ノードを求め、求めた根ノードが参照ノードである場合には更に当該根ノードが参照する下位の部分木の根ノードを求めるという処理を、下位の部分木の根ノードとして実ノードが求められるまで繰り返し、求められた実ノードの親の実ノードを新たな第２の実ノードとして特定する特定処理を実行し、前記特定処理により特定された前記新たな第１の実ノードと前記新たな第２の実ノードとが同一の部分木に属する場合には、前記第１の判定手段に前記新たな第１の実ノードと前記新たな第２の実ノードとが先祖と子孫の関係にあるか否かを判定させ、その判定の結果を、前記指定受付手段で受け付けた前記第１の実ノードと前記第２の実ノードとの間に先祖と子孫の関係があるか否かの判定結果とし、前記特定処理により特定された前記新たな第１の実ノードと前記新たな第２の実ノードとが同一の部分木に属さない場合には、前記新たな第１の実ノードと前記新たな第２の実ノードとを処理対象として前記判定処理を繰り返す、ことを特徴とする請求項３に記載の木構造処理装置である。
【０００９】
請求項５に係る発明は、コンピュータを、実ノード及び参照ノードを含むノード群が構成する１以上の木構造を表す木構造情報と、前記１以上の木構造の各々を分割して得られる各部分木がそれぞれ当該木構造のうちのどのノードを含むかを表す部分木情報と、前記各部分木を参照する各参照ノードを特定する参照関係情報と、を記憶する記憶手段、前記木構造情報に対するノードの追加により前記部分木情報が表す各部分木のうち第１の参照ノードが参照する第１の部分木のノードの数があらかじめ定めた上限数を超えた場合に、当該第１の部分木から第２の部分木を分割することにより、前記第１の部分木及び前記第２の部分木のノードの数が共に前記上限数以下となるようにし、当該分割に応じて前記記憶手段に記憶された前記部分木情報を更新する分割手段、前記分割手段による分割に応じて前記第２の部分木を参照する第２の参照ノードを新たに生成し、前記第２の部分木を参照する参照ノードが前記第２の参照ノードであることを示す情報を前記参照関係情報に追加すると共に、前記第２の参照ノードが前記第１の参照ノードが含まれる部分木に含まれることを表す情報を前記部分木情報に追加し、前記第１の参照ノードと前記第２の参照ノードとが前記第１の部分木と前記第２の部分木との親子関係に対応する親子関係を構成することを表す情報を前記木構造情報に追加する、情報追加手段、として機能させるためのプログラムである。
【００１０】
請求項６に係る発明は、コンピュータを、実ノード及び参照ノードを含むノード群が構成する１以上の木構造を表す木構造情報と、前記１以上の木構造の各々を分割して得られる各部分木がそれぞれ当該木構造のうちのどのノードを含むかを表す部分木情報と、前記各部分木を参照する各参照ノードを特定する参照関係情報と、を記憶する記憶手段、前記木構造情報に対するノードの追加により前記部分木情報が表す各部分木のうち第１の参照ノードが参照する第１の部分木のノードの数があらかじめ定めた上限数を超えた場合に、当該第１の部分木から第２の部分木を分割することにより、前記第１の部分木及び前記第２の部分木のノードの数が共に前記上限数以下となるようにし、当該分割に応じて前記記憶手段に記憶された前記部分木情報を更新する分割手段、前記分割手段による分割に応じて前記第２の部分木を参照する第２の参照ノードを新たに生成し、前記第２の部分木を参照する参照ノードが前記第２の参照ノードであることを示す情報を前記参照関係情報に追加すると共に、前記第２の参照ノードが前記第１の部分木に含まれることを表す情報を前記部分木情報に追加し、前記第２の参照ノードが前記第２の部分木の根ノードの親ノードに該当する前記第１の部分木のノードの子であることを示す情報を前記木構造情報に追加する、情報追加手段、として機能させるためのプログラムである。
【発明の効果】
【００１１】
請求項１，２，５又は６に係る発明によれば、木構造を分割した各部分木内のノード数とそれら部分木間の関係を表す情報の規模とを共に抑制できる。
【００１２】
請求項３に係る発明によれば、木構造を構成するノード同士が先祖と子孫の関係にない場合を判定できる。
【００１３】
請求項４に係る発明によれば、木構造を構成するノード同士が先祖と子孫の関係にあるか否かを判定できる。
【図面の簡単な説明】
【００１４】
【図１】実施形態のシステム構成の一例を示す図である。
【図２】クラスタ保持部が保持する各種データの意味とデータ構造を説明するための図である。
【図３Ａ】木構造の部分木であるクラスタの一例を示す図である。
【図３Ｂ】クラスタの分割位置の決め方の一例を説明するための図である。
【図４Ａ】図３ＡのクラスタＣ０が分割されたときの木構造を例示する図である。
【図４Ｂ】図４Ａに例示した分割の後、クラスタＣ０内のノード数が再び上限値に達した場合の木構造を例示する図である。
【図４Ｃ】図４Ｂに例示したクラスタＣ０が分割されたときの木構造を例示する図である。
【図５Ａ】クラスタ間の上位・下位関係を説明するための図である。
【図５Ｂ】クラスタ間の親子関係を説明するための図である。
【図６】実ノードからなる第１層の木構造のクラスタ群の構造と、それらクラスタ群を参照する参照ノードからなる上位の各層のクラスタ群の構造の例を示す図である。
【図７】先祖・子孫関係判定部の処理手順の一例を示す図である。
【図８】クラスタ検索部の処理手順の一例を示す図である。
【図９Ａ】第１の変形例において図３ＡのクラスタＣ０が分割されたときの木構造を例示する図である。
【図９Ｂ】第１の変形例において図９Ａに例示した分割の後、クラスタＣ０内のノード数が再び上限値に達した場合の木構造を例示する図である。
【図９Ｃ】第１の変形例において図９Ｂに例示したクラスタＣ０が割されたときの木構造を例示する図である。
【図１０Ａ】第２の変形例におけるクラスタ分割の仕方を説明するための図である。
【図１０Ｂ】第２の変形例におけるクラスタ分割の仕方を説明するための図である。
【図１０Ｃ】第２の変形例におけるクラスタ分割の仕方を説明するための図である。
【発明を実施するための形態】
【００１５】
［実施形態］
図１を参照して、この実施形態のシステムの機能構成を概説する。
【００１６】
このシステムは、複数のノードから構成される木構造を管理する。ノードを構成するデータの例としてはＸＭＬ要素がある。この例では、ＸＭＬ文書中のそれらＸＭＬ要素が構成する構造を、それらノードからなる木構造として表現される。
【００１７】
このシステム間は、ノード入力部１０，ノード登録部１２，分割必要性判断部１４，クラスタ分割部１６，クラスタ構成部１８，クラスタ保持部２０，検索対象ノード入力部２２，クラスタ検索部２４，先祖・子孫判定部２６を備える。
【００１８】
ノード入力部１０は、クラスタ保持部２０内に保持された既存の木（ツリー）に対して新たに追加するノードの入力を行う入力装置である。新たなノードの追加には、例えば、既存の木構造において、追加対象のノードの親のノードを指定すればよい。ノード入力部１０は、例えば、既存の木構造を表す図を表示し、その表示上でマウス等の操作により追加対象のノードの親のノードの指定を受け付ければよい。ノード入力部１０は、入力された新たなノードを表す情報（例えば既存のどのノードに子が追加されたかを示す情報）を、ノード登録部１２に送る。
【００１９】
また、別の例として、ＸＭＬエディタなどを用いて既存のＸＭＬ文書中のある要素の中にその要素の子要素が新たに追加される場合を考えると、ノード入力部１０は、ＸＭＬエディタから新たに追加された子要素の情報（例えば既存のどの要素の子として追加されたかを示す情報）を取得し、その情報をノード登録部１２に送る。
【００２０】
ノード登録部１２は、ノード入力部１０に入力された新たなノードを、クラスタ保持部２０に保持された管理対象の既存の木構造に登録するための処理を行う。詳しい処理の内容は後述する。
【００２１】
クラスタ保持部２０には、管理対象の木構造を表す情報が記憶される。ここで、この実施形態では、木構造を１以上の部分木に分けて管理する。部分木は、木の一部であり、それ自体が木の構造をなすものをいう。以下では、部分木のことをクラスタと呼ぶ。すなわち、クラスタは、元の木構造の一部分であり、木の構造をなす１以上のノードを含んでいる。クラスタ保持部２０には、木の各ノードがそれぞれどのクラスタに属するかを表す情報など、管理対象の木構造に含まれる各クラスタについての情報も登録されている。クラスタ保持部２０が保持するデータの種類や内容、構造などについては、後で説明する。
【００２２】
このように、この実施形態では、管理対象の木構造をクラスタに分割して別々に管理することにより、木構造に対する操作を、クラスタごとに並列して実行可能としている。例えば、ＸＭＬ文書を要素間の木構造を用いて管理する場合では、クラスタ分割の手法を用いることで、クラスタ毎にロックをかけることで、１つのクラスタは１人しか操作できないが、異なるクラスタについては並列して操作が可能となる。また、クラスタ分割の手法を用いる場合、例えば、一度にメモリ上に展開する範囲を１乃至少数のクラスタに絞ることで、転送速度の遅いハードディスクへのアクセスを少なくして処理の高速化を図ってもよい。
【００２３】
分割必要性判断部１４は、ノード登録部１２による新たなノードの登録（追加）により、クラスタを分割する必要があるかどうかを判定する。
【００２４】
すなわち、新たなノードを管理対象の木構造中の指定されたノードの子として追加する場合、新たなノードは指定されたノードのクラスタ内に追加することとなる。ここで、この実施形態では、コンピュータ上或いはネットワークを跨る情報処理システム上でのクラスタの取扱を容易にするために、クラスタのサイズ（ノード数、又はデータ量など）を制限する。以下の例では、クラスタ内に含まれるノードの数を、あらかじめ定めた上限値以下に制限する。この制限のために、分割必要性判定部１４は、新たなノードの追加により、追加先のクラスタを分割する必要があるかどうかを判断する。
【００２５】
分割必要性判断部１４によりクラスタの分割が必要と判断されれば、クラスタ分割部１６により、そのクラスタが複数のクラスタに分割される。クラスタ分割部１６によりクラスタを分割した場合、クラスタ構成部１８により、分割後の複数のクラスタの間の関係が構成される。クラスタの分割結果や、分割結果のクラスタ間の関係の情報は、クラスタ保持部２０に登録される。
【００２６】
また、このシステムは、上述のようにして構築され管理される管理対象の木構造、及びクラスタの情報を用いることで、２つのノード同士の間に先祖・子孫関係（それら２つのノードの一方が他方の先祖である（言い換えれば他方が一方の子孫である）という関係）があるかどうかを判定する機能を備える。この機能は、検索対象ノード入力部２２，クラスタ検索部２４，及び先祖・子孫判定部２６により提供される。
【００２７】
検索対象ノード入力部２２は、先祖・子孫関係の有無の判定対象となる２つのノードの指定を受け付ける。検索対象ノード入力部２２は、例えば、管理対象の木構造を表す図を表示し、その表示上でマウス等の操作に応じて２つのノードの指定を受け付ける。検索対象ノード入力部２２に入力された、判定対象の２つのノードを示す情報（すなわち、それら各ノードの識別情報）は、クラスタ検索部２４に渡される。
【００２８】
また、管理対象の木構造、又はその木構造の元になったデータ（例えばＸＭＬ文書等の構造化文書）に対して処理を行うプログラムから、その処理のためにその木構造内の２つのノードが先祖・子孫関係にあるかどうかの問合せを受けた場合に、検索対象ノード入力部２２は、そのプログラムからの問合せに含まれる２つのノードの識別情報を受け取り、クラスタ検索部２４に渡す。
【００２９】
クラスタ検索部２４は、それら２つのノードの関係を判定するために、クラスタ単位での先祖・子孫関係を調べる。先祖・子孫判定部２６は、１つのクラスタ内のノード間の先祖・子孫関係の有無を判定する。クラスタ検索部２４と先祖・子孫判定部２６とが協働して、判定対象の２つのノードが先祖・子孫関係にあるかどうかを判定する。
【００３０】
以上、システムの概略を説明した。次に、このシステムを構成する各構成要素の詳細を説明する。
【００３１】
＜ノードの登録＞
以下に説明する例では、管理対象の木構造を構成する各ノードに対して、それぞれ識別情報として、当該ノードがその木構造に登録（追加）された順番を示す通し番号が割り当てられているものとする。この通し番号を以下ではノード番号と呼ぶ。ノード番号は、木構造の中でノードを位置に特定する番号である。以下の例では、最初に登録されたノードのノード番号を０番とする。なお、通し番号は説明のための一例に過ぎず、ノードの識別情報は通し番号以外の仕方で付与しても構わない。
【００３２】
ノード入力部１０は、登録対象のノードの親ノードの指定を受け付け、当該親ノードのノード番号をノード登録部１２に通知する。
【００３３】
ノード登録部１２は、登録対象のノードをクラスタ保持部２０内の管理対象の木構造に登録するために、ノード入力部１０から通知された親ノード番号をキーとして、クラスタ保持部２０からその親ノードを保持するクラスタの情報を取得する。そして、登録対象のノードを、そのクラスタ内のその親ノードの子ノードとして登録するための処理を行う。ここで、ノード登録部１２は、登録対象のノードに対して一意なノード番号を付与する。
【００３４】
クラスタ保持部２０には、図２に例示する実ノード情報４２，クラスタ情報５２，及び参照ノード情報６２が記憶されている。
【００３５】
実ノード情報４２は、図２に例示する管理対象の木構造３０に含まれる各ノード４０の情報である。図２中で白抜きの丸印で表現したノード４０は、木構造３０を用いて管理する対象データを構成するデータ要素に対応する、木構造３０上での要素である。例えば、対象データがＸＭＬ文書である場合、ノード４０は、そのＸＭＬ文書中の文書要素に対応する。なお、後述するクラスタ５０を参照する参照ノード６０（図中では黒塗りの丸印で表現した）との区別のために、管理対象データの要素と対応づけられたノード４０のことを「実ノード」と呼ぶことにする。１つの実ノード４０を表す実ノード情報４２には、当該実ノード４０自身のノード番号と、親ノードのノード番号（図中の「親ノード番号」）と、当該実ノード４０が表すデータ要素のデータ内容（図中の「データ」）とが含まれる。各ノードが持つ自身のノード番号と親ノード番号との対応関係の集まりが、木構造３０を表現する。
【００３６】
この実施形態では、木構造３０を、複数のクラスタ５０に分割して管理する。図２では、破線で示した三角形の中に含まれるノード群が構成する木が１つのクラスタ５０である。
【００３７】
クラスタ情報５２は、木構造３０内の個々のクラスタ５０を表す情報である。クラスタ情報５２には、当該クラスタ自身のクラスタ番号と、当該クラスタに含まれるノード集合の情報（「保持するノード集合の情報」）と、当該クラスタを参照する参照ノード６０のノード番号である参照ノード番号とを含む。クラスタ番号は、木構造３０内の各クラスタ５０の識別情報である。以下では、説明のための一例として、クラスタ番号として、クラスタ５０が生成された順番に付与される通し番号を用いている。また、「保持するノード集合の情報」は、例えば当該クラスタに含まれるノードのノード番号のリストなどである。
【００３８】
参照ノード６０は、クラスタ５０を表すために導入したノードである。この実施形態では、１つのクラスタ５０を生成すると、これに応じて１つの参照ノード６０を生成する。このようにクラスタ５０と参照ノード６０は一対一に対応している。このような関係を「参照ノード６０がクラスタ５０を参照する」と呼ぶこととする。図２では、参照ノード６０とこれに参照されるクラスタ５０との間の、参照・被参照の関係を破線で表現している。前述の実ノードは、システム外から入力されたデータを構成する構成要素に対応しているのに対し、参照ノードは、この実施形態のシステムの内部処理でのみ使用する。なお、木構造３０におけるノード同士の親子の関係は実線で表示している。
【００３９】
参照ノード６０にも、識別情報としてノード番号が付与される。以下の例では、実ノード４０も参照ノード６０も分け隔て無く、当該ノードが登録された順序を表す通し番号をノード番号とする（但しこれは一例に過ぎない）。
【００４０】
参照ノード６０を表す参照ノード情報６２は、当該参照ノード自身のノード番号、当該参照ノードが参照するクラスタ５０のクラスタ番号、及び当該参照ノードの親ノードのノード番号を含む。参照ノード６０の親は、別の参照ノードである場合もあれば、実ノードである場合もある。
【００４１】
この実施形態では、参照ノード６０同士の木構造を実ノードの木構造３０とは別に構築するか、又は参照ノード６０を木構造３０内に組み込むようにしている。そして、参照ノード６０もいずれかのクラスタ５０内に含まれるようにする。すなわち、この実施形態では、参照ノード６０を木構造に組み込むことで、ノードだけでなくクラスタも木構造を構成させる役目を果たしている。
【００４２】
１つの参照ノード６０は１つのクラスタ５０を代表しているので、第１のクラスタを代表する参照ノード６０を別の第２のクラスタ５０に含めることは、第１のクラスタを第２のクラスタ内に入れ子にすることに相当する。また、この実施形態では、参照ノードを含んだクラスタを参照する別の参照ノードが別のクラスタに含まれる場合もあり、これはクラスタが多重に入れ子構造をなす場合に相当する。
【００４３】
図１の説明に戻ると、ノード登録部１２は、登録対象のノードに一意なノード番号を付与し、そのノードの実ノード情報４２を作成して、クラスタ保持部２０に登録する。その実ノード情報４２は、付与したノード番号と、親ノードとして指定されたノードのノード番号と、登録対象のノードのデータ内容とが含まれる。このように新たなノードの実ノード情報４２を登録することで、そのノードがクラスタ保持部２０内の木構造３０に追加されることになる。
【００４４】
また、ノード登録部１２は、指定された親ノードを含んだクラスタのクラスタ情報５２の「保持するノード集合の情報」に、新たに登録したノードのノード番号を追加する。
【００４５】
＜クラスタの分割＞
上述のようにしてクラスタ保持部２０内の木構造３０へノードの追加を行うと、ノードの追加先のクラスタ５０内のノード数が増える。この実施形態ではクラスタ５０内のノード数を上限値未満に抑えるようにしているので、ノードの追加によりクラスタ５０内のノード数が上限値に達すると、そのクラスタ５０を分割することとなる。
【００４６】
分割必要性判断部１４は、このようなクラスタ分割の必要性の判断を行う。すなわち、分割必要性判断部１４は、ノード登録部１２によりノードが追加されたクラスタのクラスタ情報５２の「保持するノード集合の情報」内のノードの数を調べ、その数が上限値以上になると、クラスタ分割の必要があると判断する。クラスタ内のノード数が上限値未満であれば、クラスタ分割は不要と判断する。
【００４７】
以下に説明する例では、クラスタ内のノード数の上限値は１０とする（もちろんこの上限値は一例に過ぎない）。例えば、図３Ａに例示したクラスタＣ０はノード数が１０に達しているので、分割必要性判断部１４により分割が必要と判断される。なお、図３Ａ以降の図において、実ノード４０を表す白抜き丸印、及び参照ノード６０を表す黒塗り丸印の中の数字は、当該ノードのノード番号を示す。
【００４８】
分割が必要と判断されたクラスタはクラスタ分割部１６にて分割される。以下では、クラスタを２分割する場合を例にとって説明する。
【００４９】
クラスタの分割は、例えば、元のクラスタの構造を保存したままで、部分木を抜き出す形で行われる。すなわち、この例では、元のクラスタの中の一部の部分木を抜き出し、抜き出した部分木を新たなクラスタとするのである。このために、クラスタ分割部１６は、クラスタＣ０中の各ノードについて、そのノードをルートノードとした場合のクラスタＣ０内での部分木に含まれるノード数を数える。図３ＡのクラスタＣ０についての計算結果は、図３Ｂに例示するようなものとなる。この計算結果をもとに、クラスタ分割部１６は、例えば、ノード数がなるべく半分に近いところでクラスタＣ０を分割できるノードを探す。
【００５０】
図３Ａ及び図３Ｂの例ではノード番号５のノードが、クラスタＣ０のノード数１０の半分となる５つのノードからなる部分木のルートノードとなり得るので、クラスタ分割部１６は、ノード番号４とノード番号５の間でクラスタを分割すると決定する。
【００５１】
クラスタ分割部１６によりクラスタ分割位置が決定されると、クラスタ構成部１８が、その位置で分割されたクラスタを構成する。すなわち、この例ではクラスタＣ０から新たなクラスタＣ１を分割し、分割後のクラスタＣ０及びＣ１を表すクラスタ情報５２をそれぞれ構成する。また、１つの例では、クラスタ構成部１８は、そのクラスタＣ０及びＣ１の再構成と同時に、新たにクラスタＣ２を生成して、クラスタＣ０を参照するノード１０と、クラスタＣ１を参照するノード１１を登録する（図４Ａ参照）。これら参照ノード１０及び１１はクラスタを参照するものであり、データ内容は持たない。分割により新たに生成されたクラスタＣ１はノード５をルートとする。ノード４とノード５との親子関係は保存される。
【００５２】
このとき、クラスタ構成部１８は、ノード０〜４を含むクラスタＣ０のクラスタ情報５２と、ノード５〜９を含むクラスタＣ１のクラスタ情報５２とを生成し、クラスタ保持部２０に格納する。クラスタ構成部１８は、新たに生成したクラスタにはクラスタ番号を付与し、このクラスタ番号をクラスタ情報５２に含める。また、クラスタに対応する参照ノードを生成した場合は、その参照ノードのノード番号を、クラスタ情報５２の「このクラスタを参照する参照ノード番号」として含める。
【００５３】
また、クラスタ構成部１８は、クラスタＣ０を参照する参照ノード１０とクラスタＣ１を参照する参照ノード１１との参照ノード情報６２をそれぞれ生成すると共に、それら参照ノード１０及び１１を含んだクラスタＣ２のクラスタ情報５２を生成する。参照ノード１０と１１の各参照ノード情報６２には、各々に付与した一意な参照ノード番号を「自身のノード番号」として組み込むとともに、「参照するクラスタ番号」の欄に参照先のクラスタ番号Ｃ０及びＣ１をそれぞれ書き込む。また、参照ノード１１の参照ノード情報６２の「親ノード番号」の欄には、親である参照ノード１０のノード番号「１０」を記録する。参照ノード１０は、親ノードを持たないので「親ノード番号」の欄は空値となる。
【００５４】
なお、クラスタＣ２を参照する参照ノードは、クラスタＣ２を生成したときに生成してもよいし、後でそのクラスタＣ２を分割する際に生成してもよい。
【００５５】
また、以上の例では、分割前のクラスタＣ０には参照ノードを対応づけず、クラスタＣ０を分割した際に、分割後のクラスタＣ０に対応する参照ノード１０を生成したが、この代わりに、クラスタＣ０を最初に生成したとき（クラスタＣ０を分割する前）に、これを参照する参照ノードを生成しておいてもよい。
【００５６】
また、クラスタは、ノードが１つしかない時点では作成せず、ノードが２以上の予め定めた数以上になったときに生成するようにしてもよい。例えば、クラスタＣ０を生成した時点でこれを参照する参照ノードを生成したとしても、その参照ノードを含むクラスタはこの時点では作成しなくてもよい。
【００５７】
次に、以下での説明で用いるクラスタ間の関係の種類を説明する。図５Ａの例では、クラスタＣ０内の参照ノード６０ａがクラスタＣ１を参照しているが、このときクラスタＣ０をクラスタＣ１の上位クラスタといい、クラスタＣ１をクラスタＣ０の下位クラスタという。すなわち、参照ノードを含んだクラスタＣ０は、その参照ノードが参照するクラスタＣ１の上位クラスタと呼ばれる。
【００５８】
一方、図５Ｂの例では、クラスタＣ０内のノードＮ０はクラスタＣ１内のルートノードＮ１の親となっているが、このときクラスタＣ０はクラスタＣ１の親クラスタといい、クラスタＣ１はクラスタＣ０の子クラスタという。すなわち、あるクラスタＣ１のルートノードの親ノードを含んだクラスタＣ０は、クラスタＣ１の親クラスタと呼ばれる。なお、この場合、ノードＮ０とＮ１は、実ノード、参照ノードのいずれであってもよい。
【００５９】
図４Ａの例では、例えば、クラスタＣ２内の参照ノード１０からクラスタＣ０が参照されているので、クラスタＣ２はクラスタＣ０の上位クラスタであり、クラスタＣ０はクラスタＣ２の下位クラスタである。クラスタＣ２、クラスタＣ１の間にも同じ関係が成り立つ。また、クラスタＣ０内のあるノードがクラスタＣ１のルートノードの親となっている状況から、クラスタＣ０はクラスタＣ１の親クラスタであり、クラスタＣ１はクラスタＣ０の子クラスタである。
【００６０】
この実施形態では、２つのクラスタが親子（すなわち親クラスタと子クラスタ）の関係を持つ場合、それらクラスタを参照する２つの参照ノード同士も親子関係となるようにする。すなわち、親クラスタを参照する参照ノードは、子クラスタを参照する参照ノードの親となる。図４Ａの例では、クラスタＣ１はＣ０の子なので、Ｃ１を参照する参照ノード１１は、Ｃ０を参照する参照ノード１０の子とする（すなわち、参照ノード１１の参照ノード情報６２の「親ノード番号」を「１０」とする）。
【００６１】
さて、図４Ａに示した状態から、クラスタＣ０に更に実ノードが追加され、クラスタＣ０のノード数が再び上限値１０に達した場合を考える（図４Ｂ参照）。この場合、クラスタ分割部１６は、クラスタＣ０をノード２と３の間で分割すると決定し、これに応じクラスタ構成部１８が、クラスタＣ０からノード３，４，１４〜１６を削除し、それら削除されたノード群を含んだクラスタＣ３を生成する（図４Ｃ参照）。また、クラスタ構成部１８は、生成したクラスタＣ３を参照する参照ノード１７を生成する。ここで、生成したクラスタＣ３はＣ０の子であり且つＣ１の親であるので、Ｃ３を参照する参照ノード１７は、Ｃ０を参照する参照ノード１０の子、且つＣ１を参照する参照ノード１１の親となる位置に挿入される。すなわち、クラスタ構成部１８は、生成したクラスタＣ３の参照ノード情報６２の親ノード番号をＣ０とし、既存のクラスタＣ１の親ノード番号をＣ０からＣ３に書き換える。
【００６２】
さて、実ノードが更に追加されていき、参照ノードで構成されるクラスタＣ２内のノード数が上限値１０に到達したとする。この実施形態では、参照ノードを含んだクラスタについても、クラスタ内のノード数が上限値に達したら分割を行う。図６に、クラスタＣ２からクラスタＣ１１が分割され、更にＣ２とＣ１１を参照する参照ノード６０及び６２を含んだクラスタＣ１２が生成された状態を示す。図６に示すように、実ノードのなす木構造及びクラスタＣ０，Ｃ１等を第１層とすると、その第１層のクラスタを参照する参照ノードがなす木構造及びクラスタＣ２，Ｃ１１は第１層に対して一段階上位の第２層となる。そして、第２層のクラスタを参照する参照ノードがなす木構造及びクラスタＣ１２は第２層より１段階上位の第３層となる。
【００６３】
図６の状況から更に実ノードが追加され、第３層のクラスタが分割されると、第３層のクラスタを参照する参照ノードからなる第４層の木構造及びクラスタが生成される。
【００６４】
以上のように、この実施形態では、ある層（第ｎ層：ｎは１以上の整数）ＬnのあるクラスタＣLn1のノード数が上限値に達するとそのクラスタＣLn1が分割される。この分割によって生成された子クラスタＣLn2を参照する参照ノードＲLn2が、クラスタＣLn1を参照する参照ノードＲLn1の子として、１段上位の層Ｌ（n+1）内のクラスタＣL（n+1）1に追加される。この追加によりクラスタＣL（n+1）1のノード数が上限に達し、クラスタＣL（n+1）1が分割されると、分割により生成された子クラスタＣL（n+1）2を参照する参照ノードＲL（n+1）2が、クラスタＣL（n+1）1を参照する参照ノードＲL（n+1）1の子として、更に上位の層Ｌ（n+2）内のクラスタＣL（n+2）1に追加される。この実施形態では、実ノードが追加されると、以上のような処理が第１層から順に上位層に向かって、クラスタの分割が生じなくなるまで繰り返される。
【００６５】
以上の例では、第１層，第２層，第３層，・・・の各階層におけるクラスタのノード上限数をすべて同じ値（具体例としては１０）としたが、これは必須ではなく、クラスタ内のノード上限数を階層ごとに変えてもよい。
【００６６】
また、以上の例では、クラスタを２分割した場合、分割後の２つのクラスタのうちの親の方が元のクラスタのクラスタ番号を引き継いだが、これは必須ではない。この代わりに、子の方が元のクラスタのクラスタ番号を引き継ぐようにし、親の方が新たなクラスタ番号を割り当てられるようにしてもよい。また、分割後の２つのクラスタについてそれぞれ新たなクラスタ番号を付与してもよいが、この場合それら２つのクラスタのうちの一方のクラスタ情報５２の内容は、上述の例における元のクラスタの分割後のクラスタ情報５２の内容と同じものになるので、結局は、元のクラスタのクラスタ番号が変わるだけにすぎない。したがって、この明細書では、分割後のクラスタのうちの１つが元のクラスタのクラスタ番号を引き継ぐ場合の例のみを説明する。
【００６７】
また、以上の例では、クラスタを分割する場合の分割数は２分割であったが、これは必須ではない。クラスタを３以上のクラスタに分割してもよい。クラスタ（分割前クラスタと呼ぶ）をｋ個（ｋは２以上の整数）のクラスタ（分割後クラスタと呼ぶ）に分割した場合、それらｋ個のうちの１つが元のクラスタのクラスタ番号を引き継ぐ。そして、残りの（ｋ−１）個の分割後クラスタが新たに生成され、新たなクラスタ番号の割り当てを受けるとともに、それら（ｋ−１）個の分割後クラスタのそれぞれについて、当該分割後クラスタを参照する参照ノードが生成される。クラスタ構成部１８は、それら新たに生成された（ｋ−１）個の分割後クラスタと、元のクラスタのクラスタ番号を引き継いだ分割後クラスタとにそれぞれ対応する合計ｋ個の参照ノードが、それら各参照ノードに対応する各分割後クラスタ同士の分割前クラスタ内での親子関係を反映した親子関係を持つようにする。すなわち、ある分割後クラスタＣａのルートノードが別の分割後クラスタＣｂ内のノードの子である場合に、クラスタＣａを参照する参照ノードＲａがクラスタＣｂを参照する参照ノードＲｂの子になるようにする（すなわちＲａの参照ノード情報６２の親ノード番号を、Ｒｂのノード番号とする）。ｋ個の分割後クラスタは１つの分割前クラスタの木構造を分割したものなので、それら分割後クラスタを参照するｋ個の参照ノードは木構造をなす。
【００６８】
また、分割前クラスタと別のクラスタとの親子関係は、分割後クラスタにも引き継がれる。例えば、分割前クラスタが別のクラスタＣｘの子であれば、クラスタ構成部１８は、ｋ個の分割後クラスタのうち、クラスタＣｘ内のノードの子を持つ分割後クラスタを参照する参照ノード（言い換えれば、ｋ個の参照ノードがなす木構造のルートの参照ノード）を、クラスタＣｘを参照する参照ノードの子とする。また分割前クラスタが別のクラスタＣｙの親であれば、ｋ個の分割後クラスタのうちクラスタＣｙのルートノードの親のノードを含んだ分割後クラスタを参照する参照ノードを、クラスタＣｙを参照する参照ノードの親とする。
【００６９】
また、クラスタ構成部１８は、分割前クラスタの分割により新たに生成した（ｋ−１）個の参照ノードを、分割前クラスタを参照する参照ノードが属するクラスタＣｚに所属させる。すなわち、クラスタ構成部１８は、クラスタＣｚのクラスタ情報５２に、新たに生成した（ｋ−１）個の参照ノードのノード番号を追加する。この追加により、クラスタＣｚのノード数が上限値に達するか、又は上限値を超えると、クラスタ分割部１６はクラスタＣｚを分割する。
【００７０】
＜先祖・子孫関係検索＞
次に、このシステムの、先祖・子孫関係検索の機能について説明する。
【００７１】
ここで、木構造の中から任意の２つのノードＡ、Ｂを選択した場合に、一方のノードＡからルートノードに向かって木構造を辿って行く際に通る経路上にもう一方のノードＢが存在する場合これらのノードは先祖・子孫関係にあるという。この場合ノードＡが子孫、ノードＢが先祖である。
【００７２】
図１の例では、検索対象ノード入力部２２がユーザから先祖・子孫関係の有無の判定対象とする２つのノードを受け付け、クラスタ検索部２４と先祖・子孫判定部２６とが協働して、それら２つのノードが先祖・子孫関係にあるかどうかを判定する。
【００７３】
この判定のためにクラスタ検索部２４及び先祖・子孫判定部２６が実行する処理手順の例を、図７及び図８に示す。図７が先祖・子孫判定部２６の処理手順の例を、図８がクラスタ検索部２４の処理手順の例を、それぞれ示す。
【００７４】
検索対象ノード入力部２２が検索対象の２つのノード（以下、ノードＡ，Ｂと呼ぶ）の指定を受けると、クラスタ検索部２４は、それらノードＡ，Ｂについて図８の処理を開始する（Ｓ０）。まずクラスタ検索部２４は、それら２つのノードＡ，Ｂを、それぞれ順に注目ノードａ，ｂに代入する（Ｓ１０）。この処理では、クラスタ検索部２４は、まずクラスタ保持部２０に記憶された各クラスタ情報５２の「保持するノード集合の情報」を調べることにより、それら２つの注目ノードａ，ｂが同一クラスタに属しているか否かを判定する（Ｓ１１）。前述のクラスタ分割処理の例から判るように、１つのノードが複数のクラスタに属することは起こらない。
【００７５】
ノードａ，ｂが同一クラスタに属していると判った場合、クラスタ検索部２４はステップＳ１３に進む。
【００７６】
一方、ノードａ，ｂが同一クラスタに属していないと判った場合、クラスタ検索部２４はステップＳ１２の処理を行う。ステップＳ１２では、クラスタ検索部２４は、ノードａが属するクラスタを求め、そのクラスタを参照する参照ノードが属するクラスタを求め、更にこのクラスタを参照する参照ノードの属するクラスタを求め、というように、ノードａの属するクラスタを起点として１つずつ上位クラスタへと遡上する。そして、これ以上上位へと遡れなくなるまでこの遡上を繰り返し、その過程で通過するノードａの上位の各階層の参照ノード及びクラスタを記録する。ノードｂについても、同様の遡上を行い、ノードｂの上位の各階層の参照ノード及びクラスタを特定する。そして、ノードａの上位の各階層のクラスタとノードｂの上位の各階層のクラスタの中で、下位側から見て最初の共通のクラスタを求め、その共通クラスタに含まれるノードａ及びノードｂそれぞれの上位階層の参照ノードａ’，ｂ’を特定する。このように特定した参照ノードａ’，ｂ’は、同一クラスタに属している。クラスタ検索部２４は、特定した参照ノードａ’，ｂ’を、それぞれ、新たな注目ノードａ，ｂとし、ステップＳ１３の処理を行う。したがって、ステップＳ１３で操作の対象となる注目ノードａ，ｂは同一クラスタに属するものとなっている。
【００７７】
ステップＳ１３では、クラスタ検索部２４は、先祖・子孫判定部２６を呼び出し、そのノードｂがノードａの子孫であるかどうかを判定させる。
【００７８】
呼び出された先祖・子孫判定部２６は、図７の手順を実行する。図７は、判定対象の２つのノードのうちのノードｂを起点として、ノードｂがノードａの子孫であるか否かを判定する処理を示している。このように、図７自体はノードｂを起点とする処理であるが、先祖・子孫判定部２６は、ノードａを起点とした場合についても同様の処理手順を行い、ノードａがノードｂの子孫であるかどうかも確認する。以下、図７の手順を詳細に説明する。
【００７９】
図７の手順では、先祖・子孫判定部２６は、まずノードｂを、図７の手順における着目ノードとする（Ｓ１）。次に、着目ノード（現段階ではノードｂ）が、ノードａであるか否かを判定する（Ｓ２）。この判定では、着目ノードとノードａのノード番号同士が同じかどうかを調べればよい。この判定結果が肯定（ＹｅＳ）の場合、先祖・子孫判定部２６は、ノードｂはノードａの子孫であると判定する（Ｓ５）。これは、ノードａとｂとが同一ノードである場合である。
【００８０】
ステップＳ２の判定結果が否定（Ｎｏ）の場合、先祖・子孫判定部２６は、着目ノードがルート（根）ノードであるかどうかを判定する（Ｓ３）。この判定では、着目ノードの実ノード情報４２に含まれる親ノード番号を調べればよい。着目ノードの親ノード番号が空値（ＮＵＬＬ。すなわち親がない）である場合、着目ノードはルートノードであると判定される（判定結果が肯定）。この場合、先祖・子孫判定部２６は、ノードｂがノードａの子孫ではないと判定する（Ｓ６）。
【００８１】
ステップＳ３の判定結果が否定の場合、先祖・子孫判定部２６は、着目ノードを親ノードに移動する（Ｓ４）。すなわち、現在の着目ノードの親ノードを新たな着目ノードとする。この処理において、着目ノードの親ノードは、着目ノードの実ノード情報４２の親ノード番号から特定される。そして、先祖・子孫判定部２６は、再びステップＳ２に戻り、着目ノードがノードａ又はルートノードのいずれかであることが判明するまで、ステップＳ２〜Ｓ４の処理を繰り返す。この繰り返しは、ノードｂを起点に、着目ノードを１つずつ先祖に遡らせていく処理である。この繰り返しにより、着目ノードがノードａに一致したことがステップＳ２で判明すると、ノードｂはノードａの子孫であると判定することができる（Ｓ５）。一方、繰り返しにより、着目ノードが、ノードａに一致しないまま、ルートノードまで達したことがステップＳ３で判明すると、ノードｂはノードａの子孫ではないと判定することができる（Ｓ６）。
【００８２】
ノードｂを起点とする図７の処理が完了（すなわちＳ５又はＳ６のいずれかに到達）すると、先祖・子孫判定部２６は、ａとｂを読み替え、ノードａを起点として図７の処理をもう一度実行する。このように、ノードｂ，ａをそれぞれ起点とした場合の図７の処理により、（ア）ノードｂがノードａの子孫である、（イ）ノードａがノードｂの子孫である、（ウ）ノードａとノードｂは互いに先祖でも子孫でもない、のいずれかの結果が得られる。（ア）と（イ）の場合はノードａとノードｂとの間に先祖・子孫関係があるが、（ウ）の場合はノードａとノードｂとの間に先祖・子孫関係がない。
【００８３】
このようにして、注目ノードａ，ｂについての先祖・子孫判定部２６の判定処理が終わると、その結果がクラスタ検索部２４に返される。クラスタ検索部２４は、その判定処理の結果を図８ステップＳ１３の判定結果として、処理を進める。
【００８４】
再び図８の説明に戻ると、ステップＳ１３での先祖・子孫係判定部２６の判定にて、ノードａとｂの間に先祖・子孫関係がないと判定される（Ｓ１３の判定結果が否定）と、クラスタ検索部２４は、最終的にノードａとノードｂとの間に先祖・子孫関係がないと判定する。この判定結果は、検索対象ノード入力部２２に対して検索対象のノードを入力したユーザに対して提示してもよい。この提示は、例えば、検索対象ノード入力部２２を備えたコンピュータの画面上にその判定結果を表示することにより行ってもよい。
【００８５】
一方、ステップＳ１３での先祖・子孫判定部２６の判定にて、ノードａ，ｂの間に先祖・子孫関係があると判定されると、クラスタ検索部２４は、ノードａ，ｂのうちの先祖側のノードが参照ノードであるかどうかを判定する（Ｓ１４）。この判定は、当該先祖側のノードのノード番号に対応するノード情報が実ノード情報４２と参照ノード情報６２のいずれであるかに基づき行えばよい。
【００８６】
ステップＳ１４で、ノードａ，ｂのうちの先祖側のノードが参照ノードでない（判定結果が否定（Ｎｏ））、すなわち実ノードであると判定された場合、クラスタ検索部２４は、検索対象ノード入力部２２から入力された検索対象のノードＡ，Ｂ間に先祖・子孫関係があると最終的に判定する。この判定結果は、検索対象ノード入力部２２に対して検索対象のノードを入力したユーザに対して提示してもよい。この提示は、例えば、検索対象ノード入力部２２を備えたコンピュータの画面上にその判定結果を表示することにより行ってもよい。
【００８７】
ステップＳ１４で、ノードａ，ｂのうちの先祖側のノードが参照ノードであると判定された場合、クラスタ検索部２４はステップＳ１５の処理を実行する。
【００８８】
ステップＳ１５では、まずノードＡ，Ｂのうちの先祖側のノードを特定し、特定した先祖側のノードを次の処理ループにおける新たなノードＡとする。前述のステップＳ１２では、ノードＡ，Ｂを起点としてクラスタを上位階層へと遡上したが、ノードＡ，Ｂのうち、その遡上の結果現在の注目ノードａ及びｂのうちの先祖側のノードに到達した方のノードを、新たなノードＡとするのである。
【００８９】
またステップＳ１５では、現在の注目ノードａとｂ（これらは先祖・子孫関係にある）とを結ぶ木の経路上のノードの中から、注目ノードａとｂのうちの先祖側のノードの直近の子孫ノード（すなわち子）に該当するノードを特定し、特定したノードが参照するクラスタのルートノードを求める。この処理では、例えば、先祖側のノードの直近の子孫ノード（これは参照ノードである）の参照ノード情報６２の「参照するクラスタ番号」を調べ、このクラスタ番号に対応するクラスタ情報５２の「保持するノード集合の情報」から、当該クラスタのルートノードを求めればよい。そして、求めたルートノードが参照ノードであれば、そのルートノードが参照するクラスタのルートノードを求める。求めたルートノードが実ノードであることが判明するまで、この処理を繰り返す。そして、最終的に求められた実ノードであるルートノードを、次の処理ループにおける新たなノードＢとする。求められた新たなノードＢは、元のノードＡ，Ｂのうちの子孫側のノードに対する先祖に該当する。なぜなら、上述の求め方から判るように、新たなノードＢが属するクラスタは、元のノードＢが属するクラスタの先祖であり、新たなノードＢはその先祖のクラスタのルートであるからである。
【００９０】
このように、ステップＳ１５では、ノードＡ，Ｂのうちの先祖側を新たなノードＡとして残し、子孫側のノードから遡った先祖のノードを新たなノードＢとするのである。新たなノードＡが新たなノードＢの先祖であれば、新たなノードＡは、元のノードＡ，Ｂのうちの子孫側のノードの先祖である。したがって、新たなノードＡと新たなノードＢとが先祖・子孫関係を持つかどうかを判定すれば、元のノードＡと元のノードＢが先祖・子孫関係を持つかどうかが判る。
【００９１】
そこで、クラスタ検索部２４は、ステップＳ０に戻り、ステップＳ１５で求めた新たなノードＡ，Ｂを対象として図８の処理を繰り返す。
【００９２】
クラスタ検索部２４は、以上のような処理を、ステップＳ１３の判定結果が否定、又はステップＳ１４の判定結果が否定になるまで繰り返す。これにより、検索対象ノード入力部２２から入力された検索対象のノード同士が先祖・子孫関係にあるか否かが判定される。
【００９３】
次に、上述したクラスタ検索部２４及び先祖・子孫判定部２６の処理手順を、図６に例示した木構造中のノード同士の先祖・子孫関係の判定に用いた場合の具体例を説明する。
【００９４】
まず第１の例として、図６の木構造（第１層）中の実ノード４６と実ノード４３とを検索対象ノードとした場合の処理の流れを説明する。
【００９５】
この場合、実ノード４６と実ノード４３は同じクラスタＣ８に属していることがステップＳ１１で判る。同じクラスタ内の２つのノードの先祖・子孫関係判定は図７に示すように、片方のノードＡからクラスタのルートノードに向かって辿っていき、もう片方のノードＢに突き当たれば、ノードＡはノードＢの子孫であり、逆にノードＢからルートノードに向かって辿っていき、ノードＡに突き当たれば、ノードＢはノードＡの子孫である。片方のノードを起点として先祖・子孫判定部２６が図７の手順を実行し、その結果先祖・子孫関係がみつからなかった場合はもう片方を起点として同じ手順を実行する。第１の例のノード４６とノード４３はこの先祖・子孫関係判定により先祖・子孫関係にないことが明らかとなる。
【００９６】
次に、第２の例として、図６において実ノード４６と実ノード３１が先祖・子孫関係にあるか検索する。ノード４６とノード３１は、それぞれクラスタＣ８、Ｃ６と、所属するクラスタが異なる。そこでクラスタＣ８とＣ６をそれぞれ参照する参照ノードを辿り、直近の共通する先祖クラスタ中のノードを取得する。
【００９７】
クラスタ保持部２０はクラスタＣ８が参照ノード４７に参照されているという情報（クラスタ情報５２）を持っている。クラスタ検索部２４は、これを用いて参照ノード４７を特定し、参照ノード４７を保持するクラスタをクラスタ保持部２０に問い合わせてそれがクラスタＣ１１であることを知る。更に、同様にクラスタＣ１１を参照する参照ノード６２と、それを保持するクラスタがＣ１２であるという情報も取得する。このようにして、クラスタのなす階層をクラスタＣ８から上位へと遡っていった場合に得られる最上位階層のクラスタまでのクラスタの系列（連なり）はＣ８（４６）→Ｃ１１（４７）→Ｃ１２（６２）となる。括弧内の番号は、括弧の前に示したクラスタ内の参照ノードであって、その系列における１段階下位のクラスタを参照する参照ノードを示す（ただし、最下位のクラスタについての括弧内の番号は、実ノードを示す）。クラスタ検索部２４は、求めたＣ８（４６）→Ｃ１１（４７）→Ｃ１２（６２）というクラスタ系列を記憶する。
【００９８】
同様に、クラスタ検索部２４は、クラスタＣ６から上位階層へと遡上した場合のルートクラスタまでのクラスタの系列、Ｃ６（３１）→Ｃ１１（３５）→Ｃ１２（６２）、を求めて記憶する。
【００９９】
そして、クラスタ検索部２４は、それら２つのクラスタ系列同士の間で、最も下位で共通するクラスタを特定する。例えば、クラスタ検索部２４は、２つの系列の一方、例えばクラスタＣ８から開始する系列を選択し、最下位のクラスタを選択する。そして、選択したクラスタと同じものをもう一方の系列から探す。見つからなければ、選択した系列から、選択したクラスタよりも１つ上位のクラスタを選択し、この選択したクラスタと同じものをもう一方の系列から探す。選択した系列から選択したクラスタと同じものがもう一方の系列から見つかるまで、以上の処理を繰り返す。クラスタは階層構造をなしているので（図６参照）、選択した系列から選択したクラスタと同じものがもう一方の系列から必ず見つかる。
【０１００】
具体的には、Ｃ８を選択すると、もう一方の系列はＣ６、Ｃ１１、Ｃ１２であるので共通する先祖クラスタは存在しない。次にＣ１１を選択するともう一方の系列の２番目にＣ１１が存在することを発見する。これが両系列に共通する最下位のクラスタである。これより上位のクラスタＣ１２も両系列で共通のクラスタであるが、共通する最下位のクラスタが判ればよいので、処理はＣ１１が見つかった段階で終了してよい。
【０１０１】
次の注目ノードは、Ｃ１１内の参照ノード４７、３５となる（図８のＳ１２）。同じクラスタ上の２つのノードに対しては先祖・子孫関係判定処理（図７）が適用可能であるので、この処理により判定を行う。検索の結果ノード３５と４７は先祖・子孫関係にあることが判る（図８のＳ１３）。ここでノード３５、４７は参照ノードであり、実ノードではない（図８のＳ１４）。そこでクラスタ検索部２４は、両者のうちの先祖側のノード３５の直近の子孫ノードがノード４１であることを求め、そのノード４１が参照するクラスタＣ７のルートノード３６の親ノード３２を取得する（図８のＳ１５）。このノード３２は実ノードである。また、検索対象の実ノード４６と３１のうち、現在の注目ノード３５、４７のうちの先祖側のノード３５に対応するノードはノード３１である。
【０１０２】
そこで、クラスタ検索部２４は、次にノード３１，３２を新たなノードＡ，Ｂとし（図８のＳ０）、これらノードＡ，Ｂについて図８の手順を行って先祖・子孫関係を調べる。ノード３１、３２は同じクラスタに属し、先祖・子孫関係にある（図８のＳ１１、Ｓ１３）。またこれらのノードは参照ノードでない（図８のＳ１４の判定結果が否定）。したがって、ノード３１はノード３２の先祖であることが分かり、ノード３２はノード４６の先祖であるので、最終的に検査対象のノード４６とノード３１は先祖・子孫関係にあると判定される。ここで検索処理を終える。
【０１０３】
更に第３の例として、実ノード１３と実ノード４６の先祖・子孫関係の判定処理の流れを説明する。
【０１０４】
クラスタ検索部２４は、ノード１３とノード４６がそれぞれクラスタＣ０とＣ８に属し、同一のクラスタに属しないことを求める（図８のＳ１１）。そこで、ノード１３、４６が属するクラスタを参照する参照ノードを辿り、直近の共通する先祖クラスタ中のノードを取得する。それぞれクラスタの系列はＣ０（１３）→Ｃ２（１０）→Ｃ１２（６０）、及びＣ８（４６）→Ｃ１１（４７）→Ｃ１２（６２）であるので、前述同様にして直近の共通する祖先クラスタはＣ１２と判明し、Ｃ１２内での注目ノードはノード６０，６２になる（図８のＳ１２）。そして、クラスタ検索部２４は、先祖・子孫判定部２６に、ノード６０と６２を対象として先祖・子孫関係判定（図７）を行わせ、この結果ノード６０、６２は先祖・子孫関係にあることが判明する（図８のＳ１３）。ここで、先祖側のノード６０は参照ノードであるので、クラスタ検索部２４は、当該先祖側ノード６０の直近の子孫ノード６２が参照するクラスタＣ１１のルートノード３５を取得し、更にノード３５は参照ノードであるので、ノード３５が参照するクラスタＣ６のルートノード３０を取得して、その親ノード１６を取得する（図８のＳ１５）。このノード１６は実ノードであるので、これを新たなノードＢとする。また、検索対象として指定されたノード１３及び４６のうち、先祖側の注目ノード６０に対応するノード１３を、新たなノードＡとする。
【０１０５】
そして、クラスタ検索部２４は、それら新たな対象ノードＡ，Ｂであるノード１３，ノード１６について、図８の手順を実行する。ノード１３,１６はそれぞれクラスタＣ０、Ｃ３に属しており同一クラスタには属さない（図８のＳ１１）。そこでクラスタ検索部２４は、ノード１３とノード１６が属するクラスタを参照する参照ノードを辿り、直近の共通する先祖クラスタ中のノードを取得する。それぞれクラスタ系列はＣ０（１３）→Ｃ２（１０）→Ｃ１２（６０）、及びＣ３（１６）→Ｃ２（１７）→Ｃ１２（６０）であるので前述同様の方法でＣ２が直近（最下位）の共通クラスタであり、その共通クラスタ内の注目ノードがノード１０、１７であることをつきとめる（図８のＳ１２）。次に、それらノード１０，１７を対象として、先祖・子孫判定部２６が先祖・子孫関係の検索処理（図７）を実施し、その結果両ノードが先祖・子孫関係にあると判定される（図８のＳ１３）。ここで、注目ノードのうちの先祖側のノード１０は参照ノードであるので、クラスタ検索部２４は、当該ノード１０の直近の子孫ノード１７が参照するクラスタＣ３のルートノード３を取得し、ルートノード３の親ノード２を取得する。ノード２は実ノードである。
【０１０６】
次に、クラスタ検索部２４は、このノード２と、検索対象のノードのうちの先祖側であるノード１３とを対象として、図８の処理を再び行う。ここで、ノード２，１３は同一クラスタＣ０に属しているので、クラスタ検索部２４は、先祖・子孫判定部２６に判定を行わせる。この判定の結果、結果ノード１３,２は先祖・子孫関係に無いことが判明し、ステップＳ１３により、検索対象のノード１３とノード４６とは先祖・子孫関係に無いことが最終的に判明する。
【０１０７】
＜処理に要する計算量＞
ノード１３とノード４６の先祖・子孫関係判定を行うとき、階層的なクラスタ構造を用いた本実施形態の検索処理を用いず、単にノード群がなす木構造のみ（すなわち図８の第１層における実ノード間の関係のみ）を用いて検索を行う場合を考える。この場合、ノード４６から木構造のルートノードまで１４回のノード移動を行わねばならない。このようにルートノードまで移動する経路にノード１３が現れないことで、初めてノード１３がノード４６の先祖でないことが判明する。
【０１０８】
これに対し、この実施形態の仕組みを使った場合、最上位クラスタ（第３層）で１回（ノード６２→６０）、次位のクラスタ（第２層）で１回（ノード１７→１０）、最下位（第１層）のクラスタで２回（ノード２→０）と、合計４回のノード移動を行えば、先祖・子孫関係が判別される。
【０１０９】
より一般的に説明すると、この実施形態で用いるクラスタの階層数Ｌは実ノード数Ｎとクラスタあたりのノード上限数Ｔを使ってＬ=floor（log（Ｎ/Ｔ）+２）と表せる。floor（）は小数点以下を切り捨てる床関数である。ノード数Ｎの増加に対してlogＮのオーダーで階層Ｌが増加する。図８のＳ１２は、２つのノードが同一クラスタに納まるまで上位クラスタ中の参照ノード取得を繰り返す。この処理は最大で階層Ｌの回数分繰り返す。また図８のＳ１３（すなわち図７の処理）の処理時間は１クラスタ中のノード数上限数Ｔに依存する。よって、この実施形態の方法での検索時間は、階層数Ｌと、１つのクラスタ内のノード上限数Ｔにより決まる。従って、この方法は、実ノード数Ｎの増加に対して検索時間が増加しにくい方法であると言える。また、この方法では、階層Ｌとクラスタ内ノード上限数Ｔにより最遅の検索時間が決まるので、木構造上の検索対象の２ノードが近い場所にあっても、離れた場所にあっても、変動の小さい一定範囲内の検索時間が見積もられる。
【０１１０】
［変形例］
上述の実施形態ではクラスタ分割を行った際、分割により新しく生成されたクラスタを参照する参照ノードを上位クラスタに追加した。これに対し、変形例ではクラスタを分割する際、元のクラスタから分割により取り出された新たなクラスタの部分木が元のクラスタの部分木にて占めていた位置に、その新たなクラスタを参照する参照ノードを追加する。ここで、分割により取り出された新たなクラスタの部分木が元のクラスタの部分木にて占めていた位置とは、元のクラスタ内のノード位置であり、かつ当該新たなクラスタの根ノードの親ノード（これは元のクラスタ内のノードである）の子となる位置である。したがって、この実施形態では、分割により生成された新たなクラスタを参照する参照ノードは、当該新たなクラスタの親クラスタ（すなわち元のクラスタから新たなクラスタを除いたもの）に追加されることになる。
【０１１１】
この変形例のための装置構成は、図１に示したものと同様でよい。また、クラスタ保持部２０が保持する実ノード情報４２，クラスタ情報５２及び参照ノード情報６２のデータ構造は、図２に示したものと同様でよい。変形例において実施形態と異なるのは、クラスタ構成部１８の処理の内容であり、他の構成要素については実施形態の場合と同様でよい。
【０１１２】
以下、変形例における各フェーズの処理について説明する。
【０１１３】
＜ノードの登録＞
実ノードの登録処理は、上述実施形態と同じでよい。
【０１１４】
＜クラスタの分割＞
クラスタ構成部１８は、クラスタを分割する場合、元のクラスタから分割した新たなクラスタを参照する参照ノードを、元のクラスタ内の、当該新たなクラスタが占めていた位置に入れる。すなわち、クラスタ構成部１８は、新たなクラスタのクラスタ情報５２を作成すると共に、その新たなクラスタを参照する参照ノードの参照ノード情報６２を作成し、元のクラスタのクラスタ情報５２の［保持するノード集合の情報」から新たなクラスタに含まれるノードを削除し、代わりにその参照ノードを追加する。
【０１１５】
図３Ａに例示するように、実ノードの追加により、あるクラスタ中のノード数が上限値（この例では１０）に達したらクラスタを分割する（図９Ａ参照）。実施形態の場合と同様、クラスタ分割部１６が、元のクラスタ内のノード数のなるべく半分に近いところで分割する。図９Ａの例ではノード５のところで分割すると、分割後の各部分木のノード数が元のちょうど半分になる。そこで、ノード５をルートノードとする部分木を元のクラスタＣ０から分割して新たなクラスタＣ１とする。
【０１１６】
この分割の際、クラスタ構成部１８は、元のクラスタＣ０の中のノード５が存在した場所に、新たなクラスタＣ１を参照する参照ノード１０を追加する。図９Ａでは、この参照ノード１０とクラスタＣ１との対応関係が破線で示されている。また、このように分割されても、ノード４と５の間の親子関係は維持される（図では実線で示している）。
【０１１７】
このようにしてできたクラスタＣ１はクラスタＣ０の参照ノード１０に参照されているので、クラスタＣ０はクラスタＣ１の上位クラスタ、クラスタＣ１はクラスタＣ０の下位クラスタの関係になる。また、クラスタＣ１のノード５の親ノードはクラスタＣ０のノード４であるので、クラスタＣ０はクラスタＣ１の親クラスタ、クラスタＣ１はクラスタＣ０の子クラスタという関係も併せ持つ。
【０１１８】
このように、変形例では、分割により生成された子クラスタを参照する参照ノードが親クラスタに入るので、クラスタ同士の親子関係がすなわちクラスタ同士の上位・下位の関係となる。
【０１１９】
この分割の後、クラスタＣ０に更にノードが追加され、クラスタＣ０内のノード数がノード上限数１０に再び到達した状態を図９Ｂに示す。この場合、クラスタ分割部１６は、ノード３をルートとする部分木をクラスタＣ０から分割すればよいと判定する。クラスタ構成部１８は、ノード３をルートとする部分木（すなわち新たなクラスタＣ２）をクラスタＣ０から削除し、クラスタＣ０においてノード３が存在した箇所に、分割により生じた新たなクラスタＣ２を参照する参照ノード１５を挿入する。クラスタＣ２には１回目のクラスタ分割で生成された参照ノード１０が含まれる。この分割の結果を図９Ｃに示す。
【０１２０】
＜先祖・子孫関係検索＞
この変形例では、クラスタの上位・下位関係がクラスタの親子関係へと縮退しただけであり、上位・下位の関係の情報は存在しているので、先祖・子孫関係の検索には、実施形態と同じく、図８及び図７に示した手順を実行すればよい。
【０１２１】
処理の具体例を、図９Ｃの木構造を例にとって説明する。
【０１２２】
第１の例として、その木構造中の実ノード９と実ノード１２とが検索対象ノードとして指定された場合を考える。以下では簡単の為、ノード９を子孫側候補とした場合の処理の流れを説明するが、実際はノード１２を子孫側候補とした場合の処理も同様に行う。
【０１２３】
この例では、ノード９はクラスタＣ１に、ノード１２はクラスタＣ０に属しており同一のクラスタに無い（図８のＳ１１）。そこで、クラスタ検索部２４は、ノード９、１２が属するクラスタを参照する参照ノードをそれぞれ辿り、直近の共通する先祖クラスタ中の参照ノードを取得する。ここで、ノード９に対するクラスタ系列はＣ１（９）→Ｃ２（１０）→Ｃ０（１５）である。一方、ノード１２が属するクラスタＣ０を参照する参照ノードが存在しない（Ｃ０はルートクラスタ）ので、ノード１２に対応するクラスタ系列はＣ０（１２）となる。
【０１２４】
実施形態と同様にして、両系列で共通する最下位のクラスタを求める。この例では、クラスタＣ０がその最下位の共通クラスタであることが分かり、その共通クラスタ内での注目ノードは１５、１２であると求められる（図８のＳ１２）。なお、図８のＳ１２では、判定対象の実ノードのうちの一方が共通クラスタに含まれる場合、その実ノード自身を注目クラスタとする。なお、判定対象の２つの実ノードの両方が同じクラスタに含まれる場合は、Ｓ１１からＳ１３に進むので、ステップＳ１２の処理は行われない。先祖・子孫判定部２６が、それら注目ノード１５、１２に対して先祖・子孫関係の有無を判定する。この結果、先祖・子孫関係に無いことが分かる（図８のＳ１３）ので、最終的に判定対象のノード９と１２とは先祖・子孫関係に無いと判定される。
【０１２５】
＜処理に要する計算量＞
変形例で生成されるクラスタの数Ｃは、実ノード数Ｎとクラスタあたりのノード上限数Ｔを使うとＣ=floor（Ｎ/Ｔ+１）で表せる。floor（）は小数点以下を切り捨てる床関数である。この式から分かるように、ノード数Ｎの増加に対してＮのオーダーでクラスタ数Ｃが増加する。変形例では図８のＳ１２により２つの注目ノードが同じクラスタに納まるまで親（上位）クラスタ中の参照ノードの遷移を繰り返し、同じクラスタ内では図８のＳ１３によりクラスタ内のノードを遷移する。従ってクラスタ数Ｃとクラスタ内ノード数により最遅の検索時間が決まる。よって変形例と比較して木構造のノード数増加による検索時間への増加影響が大きい。また、検索対象ノード間の距離が大きくなるほど、検索時間が長くなる傾向を持つ。
【０１２６】
しかし、変形例は、クラスタの上位・下位関係を用いるので、実ノードの親子関係のみから検査対象ノード間の先祖・子孫関係を判定するよりも、計算量は少なくて済む。
【０１２７】
また、参照ノードの数に着目すると、この実施形態は、実施形態の第２層のクラスタ群がもつ参照ノードと同じ数の参照ノードを持つ。しかし、実施形態の第３層以上の階層にある参照ノードに相当するノードは、変形例では生成しない。したがって、必要な記憶容量は上記実施形態よりも少ない。
【０１２８】
［第２の変形例］
上述の変形例を改良した第２の変形例を以下に説明する。第２の変形例のための装置構成は図１に示したものでよい。この改良例は、クラスタ構成部１８の処理内容が上述の変形例と異なるが、他の要素の処理内容は上位変形例及び実施形態と同様でよい。
【０１２９】
以下、この改良例における各フェーズの処理を説明する。
【０１３０】
＜ノードの登録＞
実ノードの登録処理は、上述実施形態と同じでよい。
【０１３１】
＜クラスタの分割＞
上記変形例では、図９Ｂ及び図９Ｃに示す通り、クラスタＣ０をノード２と３の間で分割してクラスタＣ２を新たに生成する際に、ノード３をルートとする部分木に含まれる参照ノード１０を新たなクラスタＣ２に含めた。
【０１３２】
これに対し、この改良例では、図１０Ａに示す通り、参照ノード１０を分割元のクラスタＣ０に残し、新たなクラスタＣ２からは除いた。
【０１３３】
なお、この改良例では、参照ノード１０をクラスタＣ０に残すので、クラスタＣ０の分割位置の決め方が以下の２つの点で上記変形例と異なる。
（１）参照ノードをまたいで部分木のノード数をカウントしない。
（２）クラスタ内ノード上限数の半分からの距離が同じ場合は、部分木に参照ノードを含まない方を分割対象として選択する。
【０１３４】
この決め方により、図１０Ａの例では、ノード１と２の間でクラスタを分割している。
【０１３５】
分割により生成された新たなクラスタＣ２を参照する参照ノード１５は、元のクラスタＣ０においてクラスタＣ２の部分木が占めていた位置（すなわち元のクラスタＣ０内の、ノード１の子となり且つノード１０の親となる位置）に挿入される。したがって、参照ノード１０は参照ノード１５の子となる。
【０１３６】
クラスタ構成部１８は、上述のような分割後のクラスタＣ０，Ｃ２が構成されるよう、クラスタＣ２のクラスタ情報５２と参照ノード１５の参照ノード情報６２を生成し、更にクラスタＣ０のクラスタ情報５２（特に「保持するノード集合の情報」）と参照ノード１０の参照ノード情報６２（特に親ノード番号）を修正する。
【０１３７】
クラスタ分割後の図１０Ａの木構造では、参照ノード１０がクラスタＣ１を参照していることから、クラスタＣ０はクラスタＣ１の上位クラスタ、クラスタＣ１はクラスタＣ０の下位クラスタという関係にある。同様にクラスタＣ０はクラスタＣ２の上位クラスタ、クラスタＣ２はクラスタＣ０の下位クラスタの関係にある。また、ノード５の親ノードはノード４であるので、クラスタＣ２はクラスタＣ１の親クラスタ、クラスタＣ１はクラスタＣ２の子クラスタの関係にある。同様にクラスタＣ０はクラスタＣ２の親クラスタ、クラスタＣ２はクラスタＣ０の子クラスタの関係にある。従ってクラスタＣ２、Ｃ１を参照する参照ノード１５、１０の親子関係はクラスタの親子関係に対応したものになる。
【０１３８】
図１０Ｂに、更に実ノードが増えてクラスタ分割が繰り返された結果、クラスタＣ０のノードが参照ノードにより飽和（ノード上限数に到達）した状態の例を示す。この場合は参照ノードも分割対象となる。この例では、最も分割に適したノードとして参照ノード３０が選択され、クラスタＣ０内の参照ノード３０をルートとする部分木が、新たなクラスタＣ１０としてＣ０から分割される（図１０Ｃ参照）。この場合、新たなクラスタＣ１０を参照する参照ノード４５を、クラスタＣ０内でそのクラスタＣ０の部分木が占めていた位置に挿入する。
【０１３９】
＜先祖・子孫関係検索＞
この第２の変形例でも、クラスタの上位・下位関係がクラスタの親子関係へと縮退しただけであり、上位・下位の関係の情報は存在しているので、先祖・子孫関係の検索には、実施形態と同じく、図８及び図７に示した手順を実行すればよい。
【０１４０】
例えば、図１０Ａにおいて、実ノード９と実ノード１２とが先祖・子孫関係にあるか調べる場合の処理の例を以下に示す。この例では、ノード９はクラスタＣ１に、ノード１２はクラスタＣ０に属しており同一のクラスタに無い（図８のＳ１１）。そこでノード９、１２が属するクラスタを参照する参照ノードを辿り、直近の共通する先祖クラスタ中のノードを取得する。上記変形例と同様、ノード９に対応するクラスタ系列はＣ１（９）→Ｃ０（１０）であり、ノード１２に対応するクラスタ系列はＣ０（１２）であることが分かる。両系列で共通する最下位のクラスタはＣ０となる（図８のＳ１２）。また、その共通クラスタＣ０内の注目ノードはノード１０と１２であることも求められる。先祖・子孫判定部２６がそれら注目ノード１０と１２に対して先祖・子孫関係の有無を判定し、この結果それら両者には先祖・子孫関係に無いことが明らかとなる（図８のＳ１３）。以上から判定対象である実ノード９と実ノード１２は先祖・子孫関係に無いことが判定される。
【０１４１】
もう１つの例として、図１０Ａの木構造において実ノード９と実ノード１４が先祖・子孫関係にあるか調べる場合を以下に示す。ノード９、１４はそれぞれクラスタＣ１、Ｃ２に属しており同一のクラスタに無い（図８のＳ１１）。そこでノード９、１４が属するクラスタを参照する参照ノードを辿り、直近の共通する先祖クラスタ中のノードを取得する。これにより、ノード９、１４に対応するクラスタ系列はそれぞれＣ１（９）→Ｃ０（１０）、Ｃ２（１４）→Ｃ０（１５）であることが求められる。これら両系列の比較から、直近の共通する先祖クラスタはＣ０であることが分かり、注目ノードは１０、１５であることが求められる。先祖・子孫判定部２６が、それら注目ノード１０、１５に対して先祖・子孫関係の有無を判定し（図８のＳ１３）、それら注目ノード１５、１０は先祖・子孫関係にあることが判明する。そこで、クラスタ検索部２４は、注目ノード１５，１０の内先祖側であるノード１５は参照ノードであるので（図８のＳ１４）、当該注目ノード１５の直近の子孫であるノード１０が参照するクラスタＣ１のルートノード５の親ノード４を取得する（図８のＳ１５）。取得したノード４は実ノードなので、クラスタ検索部２４は、ステップＳ０に戻り、新たに取得した実ノード４と、判定対象のうちの先祖側である実ノード１４と、を判定対象として、図７及び図８に例示した処理を繰り返す。この場合、実ノード１４の方が実ノード４の先祖側であることを前提として処理を行えばよい。この例では、ノード４、１４は同一のクラスタＣ２に属しているので（図８のＳ１１）、図８のＳ１３に進み、先祖・子孫判定部２６によりそれらノード４，１４間に先祖・子孫関係があるかどうかを判定する。この場合、図１０Ａの例では、ノード４はノード１４の親なので一見先祖・子孫関係があるように見えるが、上述のようにこの繰り返しではノード１４の方がノード４よりも先祖側であることが前提であり、ノード４がノード１４の親であるという関係はこの前提に矛盾する。したがって、ノード４とノード１４とは先祖・子孫関係にないと判定される。図７の手順に即して言えば、子孫側であるノード４を起点として図７の処理により部分木を遡っていっても、ノード１４には到達できないので、ノード４と１４とは先祖・子孫関係に無いと判定されることになる。以上から判定対象であるノード９、１４は先祖・子孫関係に無いと判定される。
【０１４２】
ノード９と１２の先祖・子孫検索において、上述の変形例ではクラスタＣ１からクラスタＣ２の参照ノード１０を取得することと、更にクラスタＣ０の参照ノード１５を取得することとで、合計２回の参照ノード取得を行った。これに対し、この変形例２ではクラスタ階層が少なくなるようにクラスタ分割を行っている成果として、クラスタＣ１からクラスタＣ０の参照ノード１０の１回のみの取得で済んでいる。
【０１４３】
このように、変形例２では、クラスタの親子関係の層をなるべく増加しないようにクラスタ構成を行っているので、上記変形例よりも早く同一クラスタに到達できることが期待できる。
【０１４４】
＜コンピュータへの実装＞
以上に例示したシステムは、例えば、汎用のコンピュータに上述の各機能モジュールの処理を表すプログラムを実行させることにより実現される。ここで、コンピュータは、例えば、ハードウエアとして、ＣＰＵ等のマイクロプロセッサ、ランダムアクセスメモリ（ＲＡＭ）およびリードオンリメモリ（ＲＯＭ）等のメモリ（一次記憶）、ＨＤＤ（ハードディスクドライブ）を制御するＨＤＤコントローラ、各種Ｉ／Ｏ（入出力）インタフェース、ローカル・エリア・ネットワークなどのネットワークとの接続のための制御を行うネットワークインタフェース等が、たとえばバスを介して接続された回路構成を有する。また、そのバスに対し、例えばＩ／Ｏインタフェース経由で、ＣＤやＤＶＤなどの可搬型ディスク記録媒体に対する読み取り及び／又は書き込みのためのディスクドライブ、フラッシュメモリなどの各種規格の可搬型の不揮発性記録媒体に対する読み取り及び／又は書き込みのためのメモリリーダライタ、などが接続されてもよい。上に例示した各機能モジュールの処理内容が記述されたプログラムがＣＤやＤＶＤ等の記録媒体を経由して、又はネットワーク等の通信手段経由で、ハードディスクドライブ等の固定記憶装置に保存され、コンピュータにインストールされる。固定記憶装置に記憶されたプログラムがＲＡＭに読み出されＣＰＵ等のマイクロプロセッサにより実行されることにより、上に例示した機能モジュール群が実現される。なお、それら機能モジュール群のうちの一部又は全部を、専用ＬＳＩ(Large Scale Integration)、ＡＳＩＣ（Application Specific Integrated Circuit、特定用途向け集積回路）又はＦＰＧＡ（Field Programmable Gate Array）等のハードウエア回路として構成してもよい。
【産業上の利用可能性】
【０１４５】
情報処理分野には、例示したＸＭＬ文書などの構造化文書をはじめとして、木構造をなす複数のデータ要素からなるデータが多種多様に存在する。このようなデータの処理においては、データ要素同士の間に先祖・子孫関係があるかどうかで、それらデータ要素に対するデータ処理の内容を切り換える場合がある。例えば、先祖のデータ要素の属性や状態に応じて子孫のデータ要素の処理内容が決まる場合などである。このような場合、データ要素同士の間の先祖・子孫関係の判定の計算量（計算時間）を低減することには、産業上大きな意義がある。
【符号の説明】
【０１４６】
１０ ノード入力部、１２ ノード登録部、１４ 分割必要性判断部、１６ クラスタ分割部、１８ クラスタ構成部、２０ クラスタ保持部、２２ 検索対象ノード入力部、２４ クラスタ検索部、２６ 先祖・子孫判定部。
【技術分野】
【０００１】
本発明は、木構造処理装置及びプログラムに関する。
【背景技術】
【０００２】
特許文献１に開示された装置は、ＸＭＬ（eXtensible Markup Language）文書等、文書要素同士が木構造を構成している構造化文書をいくつかのクラスタと呼ばれる部分木構造に分割した上で、クラスタ毎にその内部の文書要素の木構造を表現するデータ構造を持つようにするものである。このように構造化文書を分割することで、個々のクラスタ毎にロックをかけて複数人が同時に編集できるようにし、さらに一つのデータ構造のサイズを小さくしている。また、要素の先祖・子孫関係の判定のために、さらに元の構造化文書の木構造におけるクラスタレベルでの先祖・子孫関係を表すデータ構造を持つようにしている。そして、クラスタレベルで先祖・子孫関係がなければ、要素間にも先祖・子孫関係がないことを利用して、要素間の先祖・子孫関係の有無の判定に要する時間を低減している。この従来技術では、文書要素の数が膨大なものとなった場合、分割するクラスタの数を増やせば個々のクラスタ内の文書要素の数を抑制できるが、クラスタレベルの関係を表すデータ構造が大きくなる。逆に、クラスタレベルの関係を表すデータ構造の規模を抑制しようとすると、個々のクラスタに含まれる文書要素の数が大きくなる。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特許第４０４５４００号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明は、木構造を分割した各部分木内のノード数とそれら部分木間の関係を表す情報の規模とを共に抑制できるようにすることを目的とする。
【課題を解決するための手段】
【０００５】
請求項１に係る発明は、実ノード及び参照ノードを含むノード群が構成する１以上の木構造を表す木構造情報と、前記１以上の木構造の各々を分割して得られる各部分木がそれぞれ当該木構造のうちのどのノードを含むかを表す部分木情報と、前記各部分木を参照する各参照ノードを特定する参照関係情報と、を記憶する記憶手段と、前記木構造情報に対するノードの追加により前記部分木情報が表す各部分木のうち第１の参照ノードが参照する第１の部分木のノードの数があらかじめ定めた上限数を超えた場合に、当該第１の部分木から第２の部分木を分割することにより、前記第１の部分木及び前記第２の部分木のノードの数が共に前記上限数以下となるようにし、当該分割に応じて前記記憶手段に記憶された前記部分木情報を更新する分割手段と、前記分割手段による分割に応じて前記第２の部分木を参照する第２の参照ノードを新たに生成し、前記第２の部分木を参照する参照ノードが前記第２の参照ノードであることを示す情報を前記参照関係情報に追加すると共に、前記第２の参照ノードが前記第１の参照ノードが含まれる部分木に含まれることを表す情報を前記部分木情報に追加し、前記第１の参照ノードと前記第２の参照ノードとが前記第１の部分木と前記第２の部分木との親子関係に対応する親子関係を構成することを表す情報を前記木構造情報に追加する、情報追加手段と、を備える木構造処理装置である。
【０００６】
請求項２に係る発明は、実ノード及び参照ノードを含むノード群が構成する１以上の木構造を表す木構造情報と、前記１以上の木構造の各々を分割して得られる各部分木がそれぞれ当該木構造のうちのどのノードを含むかを表す部分木情報と、前記各部分木を参照する各参照ノードを特定する参照関係情報と、を記憶する記憶手段と、前記木構造情報に対するノードの追加により前記部分木情報が表す各部分木のうち第１の参照ノードが参照する第１の部分木のノードの数があらかじめ定めた上限数を超えた場合に、当該第１の部分木から第２の部分木を分割することにより、前記第１の部分木及び前記第２の部分木のノードの数が共に前記上限数以下となるようにし、当該分割に応じて前記記憶手段に記憶された前記部分木情報を更新する分割手段と、前記分割手段による分割に応じて前記第２の部分木を参照する第２の参照ノードを新たに生成し、前記第２の部分木を参照する参照ノードが前記第２の参照ノードであることを示す情報を前記参照関係情報に追加すると共に、前記第２の参照ノードが前記第１の部分木に含まれることを表す情報を前記部分木情報に追加し、前記第２の参照ノードが前記第２の部分木の根ノードの親ノードに該当する前記第１の部分木のノードの子であることを示す情報を前記木構造情報に追加する、情報追加手段と、を備える木構造処理装置である。
【０００７】
請求項３に係る発明は、前記木構造情報が表す１以上の木構造のうちのいずれかの木構造の中から、先祖と子孫の関係にあるか否かの判定対象とする第１の実ノードと第２の実ノードとの指定を受け付ける指定受付手段と、同一の部分木内にある２つのノードについて、当該ノード同士の間に先祖と子孫の関係があるか否かを、前記記憶手段に記憶された部分木情報が表す各ノード間の親子関係をたどることで判定する第１の判定手段と、前記指定受付手段で受け付けた前記第１の実ノードと前記第２の実ノードとの間に先祖と子孫の関係があるかどうかを判定するための判定処理を行う第２の判定手段と、を更に備え、前記第２の判定手段が行う前記判定処理では、ある部分木を参照する参照ノードが含まれる部分木を前記ある部分木の１階層上位の部分木と呼ぶ場合に、前記第１の実ノードが属する部分木の上位に該当する各階層の部分木からなる第１の部分木系列と前記第２の実ノードが属する部分木の上位に該当する各階層の部分木からなる第２の部分木系列とを前記記憶手段に記憶された前記部分木情報及び前記参照関係情報に基づき求め、求めた前記第１の部分木系列と前記第２の部分木系列との間で共通する部分木を特定し、特定した部分木内にノードのうち前記第１の実ノード及び前記第２の実ノードにそれぞれ対応する２つのノードを特定し、特定した２つのノード同士の間に先祖と子孫の関係があるか否かの判定を前記第１の判定手段に実行させ、この判定の結果、前記特定した２つのノード同士の間に先祖と子孫の関係がないと判定された場合に、前記指定受付手段で受け付けた前記第１の実ノードと前記第２の実ノードとの間に先祖と子孫の関係がないと判定する、ことを特徴とする請求項１又は２に記載の木構造処理装置である。
【０００８】
請求項４に係る発明は、前記第２の判定手段が行う前記判定処理では、前記特定した２つのノード同士の間に先祖と子孫の関係があると前記第１の判定手段により判定された場合、前記指定受付手段で受け付けた前記第１の実ノードと前記第２の実ノードの中から、前記特定した２つのノードのうち先祖側のノードに対応するノードを新たな第１の実ノードとして特定し、前記特定した部分木内の前記特定した２つのノード同士を結ぶ経路上のノードのうちの前記先祖側のノードの子に該当する参照ノードが参照する下位の部分木の根ノードを求め、求めた根ノードが参照ノードである場合には更に当該根ノードが参照する下位の部分木の根ノードを求めるという処理を、下位の部分木の根ノードとして実ノードが求められるまで繰り返し、求められた実ノードの親の実ノードを新たな第２の実ノードとして特定する特定処理を実行し、前記特定処理により特定された前記新たな第１の実ノードと前記新たな第２の実ノードとが同一の部分木に属する場合には、前記第１の判定手段に前記新たな第１の実ノードと前記新たな第２の実ノードとが先祖と子孫の関係にあるか否かを判定させ、その判定の結果を、前記指定受付手段で受け付けた前記第１の実ノードと前記第２の実ノードとの間に先祖と子孫の関係があるか否かの判定結果とし、前記特定処理により特定された前記新たな第１の実ノードと前記新たな第２の実ノードとが同一の部分木に属さない場合には、前記新たな第１の実ノードと前記新たな第２の実ノードとを処理対象として前記判定処理を繰り返す、ことを特徴とする請求項３に記載の木構造処理装置である。
【０００９】
請求項５に係る発明は、コンピュータを、実ノード及び参照ノードを含むノード群が構成する１以上の木構造を表す木構造情報と、前記１以上の木構造の各々を分割して得られる各部分木がそれぞれ当該木構造のうちのどのノードを含むかを表す部分木情報と、前記各部分木を参照する各参照ノードを特定する参照関係情報と、を記憶する記憶手段、前記木構造情報に対するノードの追加により前記部分木情報が表す各部分木のうち第１の参照ノードが参照する第１の部分木のノードの数があらかじめ定めた上限数を超えた場合に、当該第１の部分木から第２の部分木を分割することにより、前記第１の部分木及び前記第２の部分木のノードの数が共に前記上限数以下となるようにし、当該分割に応じて前記記憶手段に記憶された前記部分木情報を更新する分割手段、前記分割手段による分割に応じて前記第２の部分木を参照する第２の参照ノードを新たに生成し、前記第２の部分木を参照する参照ノードが前記第２の参照ノードであることを示す情報を前記参照関係情報に追加すると共に、前記第２の参照ノードが前記第１の参照ノードが含まれる部分木に含まれることを表す情報を前記部分木情報に追加し、前記第１の参照ノードと前記第２の参照ノードとが前記第１の部分木と前記第２の部分木との親子関係に対応する親子関係を構成することを表す情報を前記木構造情報に追加する、情報追加手段、として機能させるためのプログラムである。
【００１０】
請求項６に係る発明は、コンピュータを、実ノード及び参照ノードを含むノード群が構成する１以上の木構造を表す木構造情報と、前記１以上の木構造の各々を分割して得られる各部分木がそれぞれ当該木構造のうちのどのノードを含むかを表す部分木情報と、前記各部分木を参照する各参照ノードを特定する参照関係情報と、を記憶する記憶手段、前記木構造情報に対するノードの追加により前記部分木情報が表す各部分木のうち第１の参照ノードが参照する第１の部分木のノードの数があらかじめ定めた上限数を超えた場合に、当該第１の部分木から第２の部分木を分割することにより、前記第１の部分木及び前記第２の部分木のノードの数が共に前記上限数以下となるようにし、当該分割に応じて前記記憶手段に記憶された前記部分木情報を更新する分割手段、前記分割手段による分割に応じて前記第２の部分木を参照する第２の参照ノードを新たに生成し、前記第２の部分木を参照する参照ノードが前記第２の参照ノードであることを示す情報を前記参照関係情報に追加すると共に、前記第２の参照ノードが前記第１の部分木に含まれることを表す情報を前記部分木情報に追加し、前記第２の参照ノードが前記第２の部分木の根ノードの親ノードに該当する前記第１の部分木のノードの子であることを示す情報を前記木構造情報に追加する、情報追加手段、として機能させるためのプログラムである。
【発明の効果】
【００１１】
請求項１，２，５又は６に係る発明によれば、木構造を分割した各部分木内のノード数とそれら部分木間の関係を表す情報の規模とを共に抑制できる。
【００１２】
請求項３に係る発明によれば、木構造を構成するノード同士が先祖と子孫の関係にない場合を判定できる。
【００１３】
請求項４に係る発明によれば、木構造を構成するノード同士が先祖と子孫の関係にあるか否かを判定できる。
【図面の簡単な説明】
【００１４】
【図１】実施形態のシステム構成の一例を示す図である。
【図２】クラスタ保持部が保持する各種データの意味とデータ構造を説明するための図である。
【図３Ａ】木構造の部分木であるクラスタの一例を示す図である。
【図３Ｂ】クラスタの分割位置の決め方の一例を説明するための図である。
【図４Ａ】図３ＡのクラスタＣ０が分割されたときの木構造を例示する図である。
【図４Ｂ】図４Ａに例示した分割の後、クラスタＣ０内のノード数が再び上限値に達した場合の木構造を例示する図である。
【図４Ｃ】図４Ｂに例示したクラスタＣ０が分割されたときの木構造を例示する図である。
【図５Ａ】クラスタ間の上位・下位関係を説明するための図である。
【図５Ｂ】クラスタ間の親子関係を説明するための図である。
【図６】実ノードからなる第１層の木構造のクラスタ群の構造と、それらクラスタ群を参照する参照ノードからなる上位の各層のクラスタ群の構造の例を示す図である。
【図７】先祖・子孫関係判定部の処理手順の一例を示す図である。
【図８】クラスタ検索部の処理手順の一例を示す図である。
【図９Ａ】第１の変形例において図３ＡのクラスタＣ０が分割されたときの木構造を例示する図である。
【図９Ｂ】第１の変形例において図９Ａに例示した分割の後、クラスタＣ０内のノード数が再び上限値に達した場合の木構造を例示する図である。
【図９Ｃ】第１の変形例において図９Ｂに例示したクラスタＣ０が割されたときの木構造を例示する図である。
【図１０Ａ】第２の変形例におけるクラスタ分割の仕方を説明するための図である。
【図１０Ｂ】第２の変形例におけるクラスタ分割の仕方を説明するための図である。
【図１０Ｃ】第２の変形例におけるクラスタ分割の仕方を説明するための図である。
【発明を実施するための形態】
【００１５】
［実施形態］
図１を参照して、この実施形態のシステムの機能構成を概説する。
【００１６】
このシステムは、複数のノードから構成される木構造を管理する。ノードを構成するデータの例としてはＸＭＬ要素がある。この例では、ＸＭＬ文書中のそれらＸＭＬ要素が構成する構造を、それらノードからなる木構造として表現される。
【００１７】
このシステム間は、ノード入力部１０，ノード登録部１２，分割必要性判断部１４，クラスタ分割部１６，クラスタ構成部１８，クラスタ保持部２０，検索対象ノード入力部２２，クラスタ検索部２４，先祖・子孫判定部２６を備える。
【００１８】
ノード入力部１０は、クラスタ保持部２０内に保持された既存の木（ツリー）に対して新たに追加するノードの入力を行う入力装置である。新たなノードの追加には、例えば、既存の木構造において、追加対象のノードの親のノードを指定すればよい。ノード入力部１０は、例えば、既存の木構造を表す図を表示し、その表示上でマウス等の操作により追加対象のノードの親のノードの指定を受け付ければよい。ノード入力部１０は、入力された新たなノードを表す情報（例えば既存のどのノードに子が追加されたかを示す情報）を、ノード登録部１２に送る。
【００１９】
また、別の例として、ＸＭＬエディタなどを用いて既存のＸＭＬ文書中のある要素の中にその要素の子要素が新たに追加される場合を考えると、ノード入力部１０は、ＸＭＬエディタから新たに追加された子要素の情報（例えば既存のどの要素の子として追加されたかを示す情報）を取得し、その情報をノード登録部１２に送る。
【００２０】
ノード登録部１２は、ノード入力部１０に入力された新たなノードを、クラスタ保持部２０に保持された管理対象の既存の木構造に登録するための処理を行う。詳しい処理の内容は後述する。
【００２１】
クラスタ保持部２０には、管理対象の木構造を表す情報が記憶される。ここで、この実施形態では、木構造を１以上の部分木に分けて管理する。部分木は、木の一部であり、それ自体が木の構造をなすものをいう。以下では、部分木のことをクラスタと呼ぶ。すなわち、クラスタは、元の木構造の一部分であり、木の構造をなす１以上のノードを含んでいる。クラスタ保持部２０には、木の各ノードがそれぞれどのクラスタに属するかを表す情報など、管理対象の木構造に含まれる各クラスタについての情報も登録されている。クラスタ保持部２０が保持するデータの種類や内容、構造などについては、後で説明する。
【００２２】
このように、この実施形態では、管理対象の木構造をクラスタに分割して別々に管理することにより、木構造に対する操作を、クラスタごとに並列して実行可能としている。例えば、ＸＭＬ文書を要素間の木構造を用いて管理する場合では、クラスタ分割の手法を用いることで、クラスタ毎にロックをかけることで、１つのクラスタは１人しか操作できないが、異なるクラスタについては並列して操作が可能となる。また、クラスタ分割の手法を用いる場合、例えば、一度にメモリ上に展開する範囲を１乃至少数のクラスタに絞ることで、転送速度の遅いハードディスクへのアクセスを少なくして処理の高速化を図ってもよい。
【００２３】
分割必要性判断部１４は、ノード登録部１２による新たなノードの登録（追加）により、クラスタを分割する必要があるかどうかを判定する。
【００２４】
すなわち、新たなノードを管理対象の木構造中の指定されたノードの子として追加する場合、新たなノードは指定されたノードのクラスタ内に追加することとなる。ここで、この実施形態では、コンピュータ上或いはネットワークを跨る情報処理システム上でのクラスタの取扱を容易にするために、クラスタのサイズ（ノード数、又はデータ量など）を制限する。以下の例では、クラスタ内に含まれるノードの数を、あらかじめ定めた上限値以下に制限する。この制限のために、分割必要性判定部１４は、新たなノードの追加により、追加先のクラスタを分割する必要があるかどうかを判断する。
【００２５】
分割必要性判断部１４によりクラスタの分割が必要と判断されれば、クラスタ分割部１６により、そのクラスタが複数のクラスタに分割される。クラスタ分割部１６によりクラスタを分割した場合、クラスタ構成部１８により、分割後の複数のクラスタの間の関係が構成される。クラスタの分割結果や、分割結果のクラスタ間の関係の情報は、クラスタ保持部２０に登録される。
【００２６】
また、このシステムは、上述のようにして構築され管理される管理対象の木構造、及びクラスタの情報を用いることで、２つのノード同士の間に先祖・子孫関係（それら２つのノードの一方が他方の先祖である（言い換えれば他方が一方の子孫である）という関係）があるかどうかを判定する機能を備える。この機能は、検索対象ノード入力部２２，クラスタ検索部２４，及び先祖・子孫判定部２６により提供される。
【００２７】
検索対象ノード入力部２２は、先祖・子孫関係の有無の判定対象となる２つのノードの指定を受け付ける。検索対象ノード入力部２２は、例えば、管理対象の木構造を表す図を表示し、その表示上でマウス等の操作に応じて２つのノードの指定を受け付ける。検索対象ノード入力部２２に入力された、判定対象の２つのノードを示す情報（すなわち、それら各ノードの識別情報）は、クラスタ検索部２４に渡される。
【００２８】
また、管理対象の木構造、又はその木構造の元になったデータ（例えばＸＭＬ文書等の構造化文書）に対して処理を行うプログラムから、その処理のためにその木構造内の２つのノードが先祖・子孫関係にあるかどうかの問合せを受けた場合に、検索対象ノード入力部２２は、そのプログラムからの問合せに含まれる２つのノードの識別情報を受け取り、クラスタ検索部２４に渡す。
【００２９】
クラスタ検索部２４は、それら２つのノードの関係を判定するために、クラスタ単位での先祖・子孫関係を調べる。先祖・子孫判定部２６は、１つのクラスタ内のノード間の先祖・子孫関係の有無を判定する。クラスタ検索部２４と先祖・子孫判定部２６とが協働して、判定対象の２つのノードが先祖・子孫関係にあるかどうかを判定する。
【００３０】
以上、システムの概略を説明した。次に、このシステムを構成する各構成要素の詳細を説明する。
【００３１】
＜ノードの登録＞
以下に説明する例では、管理対象の木構造を構成する各ノードに対して、それぞれ識別情報として、当該ノードがその木構造に登録（追加）された順番を示す通し番号が割り当てられているものとする。この通し番号を以下ではノード番号と呼ぶ。ノード番号は、木構造の中でノードを位置に特定する番号である。以下の例では、最初に登録されたノードのノード番号を０番とする。なお、通し番号は説明のための一例に過ぎず、ノードの識別情報は通し番号以外の仕方で付与しても構わない。
【００３２】
ノード入力部１０は、登録対象のノードの親ノードの指定を受け付け、当該親ノードのノード番号をノード登録部１２に通知する。
【００３３】
ノード登録部１２は、登録対象のノードをクラスタ保持部２０内の管理対象の木構造に登録するために、ノード入力部１０から通知された親ノード番号をキーとして、クラスタ保持部２０からその親ノードを保持するクラスタの情報を取得する。そして、登録対象のノードを、そのクラスタ内のその親ノードの子ノードとして登録するための処理を行う。ここで、ノード登録部１２は、登録対象のノードに対して一意なノード番号を付与する。
【００３４】
クラスタ保持部２０には、図２に例示する実ノード情報４２，クラスタ情報５２，及び参照ノード情報６２が記憶されている。
【００３５】
実ノード情報４２は、図２に例示する管理対象の木構造３０に含まれる各ノード４０の情報である。図２中で白抜きの丸印で表現したノード４０は、木構造３０を用いて管理する対象データを構成するデータ要素に対応する、木構造３０上での要素である。例えば、対象データがＸＭＬ文書である場合、ノード４０は、そのＸＭＬ文書中の文書要素に対応する。なお、後述するクラスタ５０を参照する参照ノード６０（図中では黒塗りの丸印で表現した）との区別のために、管理対象データの要素と対応づけられたノード４０のことを「実ノード」と呼ぶことにする。１つの実ノード４０を表す実ノード情報４２には、当該実ノード４０自身のノード番号と、親ノードのノード番号（図中の「親ノード番号」）と、当該実ノード４０が表すデータ要素のデータ内容（図中の「データ」）とが含まれる。各ノードが持つ自身のノード番号と親ノード番号との対応関係の集まりが、木構造３０を表現する。
【００３６】
この実施形態では、木構造３０を、複数のクラスタ５０に分割して管理する。図２では、破線で示した三角形の中に含まれるノード群が構成する木が１つのクラスタ５０である。
【００３７】
クラスタ情報５２は、木構造３０内の個々のクラスタ５０を表す情報である。クラスタ情報５２には、当該クラスタ自身のクラスタ番号と、当該クラスタに含まれるノード集合の情報（「保持するノード集合の情報」）と、当該クラスタを参照する参照ノード６０のノード番号である参照ノード番号とを含む。クラスタ番号は、木構造３０内の各クラスタ５０の識別情報である。以下では、説明のための一例として、クラスタ番号として、クラスタ５０が生成された順番に付与される通し番号を用いている。また、「保持するノード集合の情報」は、例えば当該クラスタに含まれるノードのノード番号のリストなどである。
【００３８】
参照ノード６０は、クラスタ５０を表すために導入したノードである。この実施形態では、１つのクラスタ５０を生成すると、これに応じて１つの参照ノード６０を生成する。このようにクラスタ５０と参照ノード６０は一対一に対応している。このような関係を「参照ノード６０がクラスタ５０を参照する」と呼ぶこととする。図２では、参照ノード６０とこれに参照されるクラスタ５０との間の、参照・被参照の関係を破線で表現している。前述の実ノードは、システム外から入力されたデータを構成する構成要素に対応しているのに対し、参照ノードは、この実施形態のシステムの内部処理でのみ使用する。なお、木構造３０におけるノード同士の親子の関係は実線で表示している。
【００３９】
参照ノード６０にも、識別情報としてノード番号が付与される。以下の例では、実ノード４０も参照ノード６０も分け隔て無く、当該ノードが登録された順序を表す通し番号をノード番号とする（但しこれは一例に過ぎない）。
【００４０】
参照ノード６０を表す参照ノード情報６２は、当該参照ノード自身のノード番号、当該参照ノードが参照するクラスタ５０のクラスタ番号、及び当該参照ノードの親ノードのノード番号を含む。参照ノード６０の親は、別の参照ノードである場合もあれば、実ノードである場合もある。
【００４１】
この実施形態では、参照ノード６０同士の木構造を実ノードの木構造３０とは別に構築するか、又は参照ノード６０を木構造３０内に組み込むようにしている。そして、参照ノード６０もいずれかのクラスタ５０内に含まれるようにする。すなわち、この実施形態では、参照ノード６０を木構造に組み込むことで、ノードだけでなくクラスタも木構造を構成させる役目を果たしている。
【００４２】
１つの参照ノード６０は１つのクラスタ５０を代表しているので、第１のクラスタを代表する参照ノード６０を別の第２のクラスタ５０に含めることは、第１のクラスタを第２のクラスタ内に入れ子にすることに相当する。また、この実施形態では、参照ノードを含んだクラスタを参照する別の参照ノードが別のクラスタに含まれる場合もあり、これはクラスタが多重に入れ子構造をなす場合に相当する。
【００４３】
図１の説明に戻ると、ノード登録部１２は、登録対象のノードに一意なノード番号を付与し、そのノードの実ノード情報４２を作成して、クラスタ保持部２０に登録する。その実ノード情報４２は、付与したノード番号と、親ノードとして指定されたノードのノード番号と、登録対象のノードのデータ内容とが含まれる。このように新たなノードの実ノード情報４２を登録することで、そのノードがクラスタ保持部２０内の木構造３０に追加されることになる。
【００４４】
また、ノード登録部１２は、指定された親ノードを含んだクラスタのクラスタ情報５２の「保持するノード集合の情報」に、新たに登録したノードのノード番号を追加する。
【００４５】
＜クラスタの分割＞
上述のようにしてクラスタ保持部２０内の木構造３０へノードの追加を行うと、ノードの追加先のクラスタ５０内のノード数が増える。この実施形態ではクラスタ５０内のノード数を上限値未満に抑えるようにしているので、ノードの追加によりクラスタ５０内のノード数が上限値に達すると、そのクラスタ５０を分割することとなる。
【００４６】
分割必要性判断部１４は、このようなクラスタ分割の必要性の判断を行う。すなわち、分割必要性判断部１４は、ノード登録部１２によりノードが追加されたクラスタのクラスタ情報５２の「保持するノード集合の情報」内のノードの数を調べ、その数が上限値以上になると、クラスタ分割の必要があると判断する。クラスタ内のノード数が上限値未満であれば、クラスタ分割は不要と判断する。
【００４７】
以下に説明する例では、クラスタ内のノード数の上限値は１０とする（もちろんこの上限値は一例に過ぎない）。例えば、図３Ａに例示したクラスタＣ０はノード数が１０に達しているので、分割必要性判断部１４により分割が必要と判断される。なお、図３Ａ以降の図において、実ノード４０を表す白抜き丸印、及び参照ノード６０を表す黒塗り丸印の中の数字は、当該ノードのノード番号を示す。
【００４８】
分割が必要と判断されたクラスタはクラスタ分割部１６にて分割される。以下では、クラスタを２分割する場合を例にとって説明する。
【００４９】
クラスタの分割は、例えば、元のクラスタの構造を保存したままで、部分木を抜き出す形で行われる。すなわち、この例では、元のクラスタの中の一部の部分木を抜き出し、抜き出した部分木を新たなクラスタとするのである。このために、クラスタ分割部１６は、クラスタＣ０中の各ノードについて、そのノードをルートノードとした場合のクラスタＣ０内での部分木に含まれるノード数を数える。図３ＡのクラスタＣ０についての計算結果は、図３Ｂに例示するようなものとなる。この計算結果をもとに、クラスタ分割部１６は、例えば、ノード数がなるべく半分に近いところでクラスタＣ０を分割できるノードを探す。
【００５０】
図３Ａ及び図３Ｂの例ではノード番号５のノードが、クラスタＣ０のノード数１０の半分となる５つのノードからなる部分木のルートノードとなり得るので、クラスタ分割部１６は、ノード番号４とノード番号５の間でクラスタを分割すると決定する。
【００５１】
クラスタ分割部１６によりクラスタ分割位置が決定されると、クラスタ構成部１８が、その位置で分割されたクラスタを構成する。すなわち、この例ではクラスタＣ０から新たなクラスタＣ１を分割し、分割後のクラスタＣ０及びＣ１を表すクラスタ情報５２をそれぞれ構成する。また、１つの例では、クラスタ構成部１８は、そのクラスタＣ０及びＣ１の再構成と同時に、新たにクラスタＣ２を生成して、クラスタＣ０を参照するノード１０と、クラスタＣ１を参照するノード１１を登録する（図４Ａ参照）。これら参照ノード１０及び１１はクラスタを参照するものであり、データ内容は持たない。分割により新たに生成されたクラスタＣ１はノード５をルートとする。ノード４とノード５との親子関係は保存される。
【００５２】
このとき、クラスタ構成部１８は、ノード０〜４を含むクラスタＣ０のクラスタ情報５２と、ノード５〜９を含むクラスタＣ１のクラスタ情報５２とを生成し、クラスタ保持部２０に格納する。クラスタ構成部１８は、新たに生成したクラスタにはクラスタ番号を付与し、このクラスタ番号をクラスタ情報５２に含める。また、クラスタに対応する参照ノードを生成した場合は、その参照ノードのノード番号を、クラスタ情報５２の「このクラスタを参照する参照ノード番号」として含める。
【００５３】
また、クラスタ構成部１８は、クラスタＣ０を参照する参照ノード１０とクラスタＣ１を参照する参照ノード１１との参照ノード情報６２をそれぞれ生成すると共に、それら参照ノード１０及び１１を含んだクラスタＣ２のクラスタ情報５２を生成する。参照ノード１０と１１の各参照ノード情報６２には、各々に付与した一意な参照ノード番号を「自身のノード番号」として組み込むとともに、「参照するクラスタ番号」の欄に参照先のクラスタ番号Ｃ０及びＣ１をそれぞれ書き込む。また、参照ノード１１の参照ノード情報６２の「親ノード番号」の欄には、親である参照ノード１０のノード番号「１０」を記録する。参照ノード１０は、親ノードを持たないので「親ノード番号」の欄は空値となる。
【００５４】
なお、クラスタＣ２を参照する参照ノードは、クラスタＣ２を生成したときに生成してもよいし、後でそのクラスタＣ２を分割する際に生成してもよい。
【００５５】
また、以上の例では、分割前のクラスタＣ０には参照ノードを対応づけず、クラスタＣ０を分割した際に、分割後のクラスタＣ０に対応する参照ノード１０を生成したが、この代わりに、クラスタＣ０を最初に生成したとき（クラスタＣ０を分割する前）に、これを参照する参照ノードを生成しておいてもよい。
【００５６】
また、クラスタは、ノードが１つしかない時点では作成せず、ノードが２以上の予め定めた数以上になったときに生成するようにしてもよい。例えば、クラスタＣ０を生成した時点でこれを参照する参照ノードを生成したとしても、その参照ノードを含むクラスタはこの時点では作成しなくてもよい。
【００５７】
次に、以下での説明で用いるクラスタ間の関係の種類を説明する。図５Ａの例では、クラスタＣ０内の参照ノード６０ａがクラスタＣ１を参照しているが、このときクラスタＣ０をクラスタＣ１の上位クラスタといい、クラスタＣ１をクラスタＣ０の下位クラスタという。すなわち、参照ノードを含んだクラスタＣ０は、その参照ノードが参照するクラスタＣ１の上位クラスタと呼ばれる。
【００５８】
一方、図５Ｂの例では、クラスタＣ０内のノードＮ０はクラスタＣ１内のルートノードＮ１の親となっているが、このときクラスタＣ０はクラスタＣ１の親クラスタといい、クラスタＣ１はクラスタＣ０の子クラスタという。すなわち、あるクラスタＣ１のルートノードの親ノードを含んだクラスタＣ０は、クラスタＣ１の親クラスタと呼ばれる。なお、この場合、ノードＮ０とＮ１は、実ノード、参照ノードのいずれであってもよい。
【００５９】
図４Ａの例では、例えば、クラスタＣ２内の参照ノード１０からクラスタＣ０が参照されているので、クラスタＣ２はクラスタＣ０の上位クラスタであり、クラスタＣ０はクラスタＣ２の下位クラスタである。クラスタＣ２、クラスタＣ１の間にも同じ関係が成り立つ。また、クラスタＣ０内のあるノードがクラスタＣ１のルートノードの親となっている状況から、クラスタＣ０はクラスタＣ１の親クラスタであり、クラスタＣ１はクラスタＣ０の子クラスタである。
【００６０】
この実施形態では、２つのクラスタが親子（すなわち親クラスタと子クラスタ）の関係を持つ場合、それらクラスタを参照する２つの参照ノード同士も親子関係となるようにする。すなわち、親クラスタを参照する参照ノードは、子クラスタを参照する参照ノードの親となる。図４Ａの例では、クラスタＣ１はＣ０の子なので、Ｃ１を参照する参照ノード１１は、Ｃ０を参照する参照ノード１０の子とする（すなわち、参照ノード１１の参照ノード情報６２の「親ノード番号」を「１０」とする）。
【００６１】
さて、図４Ａに示した状態から、クラスタＣ０に更に実ノードが追加され、クラスタＣ０のノード数が再び上限値１０に達した場合を考える（図４Ｂ参照）。この場合、クラスタ分割部１６は、クラスタＣ０をノード２と３の間で分割すると決定し、これに応じクラスタ構成部１８が、クラスタＣ０からノード３，４，１４〜１６を削除し、それら削除されたノード群を含んだクラスタＣ３を生成する（図４Ｃ参照）。また、クラスタ構成部１８は、生成したクラスタＣ３を参照する参照ノード１７を生成する。ここで、生成したクラスタＣ３はＣ０の子であり且つＣ１の親であるので、Ｃ３を参照する参照ノード１７は、Ｃ０を参照する参照ノード１０の子、且つＣ１を参照する参照ノード１１の親となる位置に挿入される。すなわち、クラスタ構成部１８は、生成したクラスタＣ３の参照ノード情報６２の親ノード番号をＣ０とし、既存のクラスタＣ１の親ノード番号をＣ０からＣ３に書き換える。
【００６２】
さて、実ノードが更に追加されていき、参照ノードで構成されるクラスタＣ２内のノード数が上限値１０に到達したとする。この実施形態では、参照ノードを含んだクラスタについても、クラスタ内のノード数が上限値に達したら分割を行う。図６に、クラスタＣ２からクラスタＣ１１が分割され、更にＣ２とＣ１１を参照する参照ノード６０及び６２を含んだクラスタＣ１２が生成された状態を示す。図６に示すように、実ノードのなす木構造及びクラスタＣ０，Ｃ１等を第１層とすると、その第１層のクラスタを参照する参照ノードがなす木構造及びクラスタＣ２，Ｃ１１は第１層に対して一段階上位の第２層となる。そして、第２層のクラスタを参照する参照ノードがなす木構造及びクラスタＣ１２は第２層より１段階上位の第３層となる。
【００６３】
図６の状況から更に実ノードが追加され、第３層のクラスタが分割されると、第３層のクラスタを参照する参照ノードからなる第４層の木構造及びクラスタが生成される。
【００６４】
以上のように、この実施形態では、ある層（第ｎ層：ｎは１以上の整数）ＬnのあるクラスタＣLn1のノード数が上限値に達するとそのクラスタＣLn1が分割される。この分割によって生成された子クラスタＣLn2を参照する参照ノードＲLn2が、クラスタＣLn1を参照する参照ノードＲLn1の子として、１段上位の層Ｌ（n+1）内のクラスタＣL（n+1）1に追加される。この追加によりクラスタＣL（n+1）1のノード数が上限に達し、クラスタＣL（n+1）1が分割されると、分割により生成された子クラスタＣL（n+1）2を参照する参照ノードＲL（n+1）2が、クラスタＣL（n+1）1を参照する参照ノードＲL（n+1）1の子として、更に上位の層Ｌ（n+2）内のクラスタＣL（n+2）1に追加される。この実施形態では、実ノードが追加されると、以上のような処理が第１層から順に上位層に向かって、クラスタの分割が生じなくなるまで繰り返される。
【００６５】
以上の例では、第１層，第２層，第３層，・・・の各階層におけるクラスタのノード上限数をすべて同じ値（具体例としては１０）としたが、これは必須ではなく、クラスタ内のノード上限数を階層ごとに変えてもよい。
【００６６】
また、以上の例では、クラスタを２分割した場合、分割後の２つのクラスタのうちの親の方が元のクラスタのクラスタ番号を引き継いだが、これは必須ではない。この代わりに、子の方が元のクラスタのクラスタ番号を引き継ぐようにし、親の方が新たなクラスタ番号を割り当てられるようにしてもよい。また、分割後の２つのクラスタについてそれぞれ新たなクラスタ番号を付与してもよいが、この場合それら２つのクラスタのうちの一方のクラスタ情報５２の内容は、上述の例における元のクラスタの分割後のクラスタ情報５２の内容と同じものになるので、結局は、元のクラスタのクラスタ番号が変わるだけにすぎない。したがって、この明細書では、分割後のクラスタのうちの１つが元のクラスタのクラスタ番号を引き継ぐ場合の例のみを説明する。
【００６７】
また、以上の例では、クラスタを分割する場合の分割数は２分割であったが、これは必須ではない。クラスタを３以上のクラスタに分割してもよい。クラスタ（分割前クラスタと呼ぶ）をｋ個（ｋは２以上の整数）のクラスタ（分割後クラスタと呼ぶ）に分割した場合、それらｋ個のうちの１つが元のクラスタのクラスタ番号を引き継ぐ。そして、残りの（ｋ−１）個の分割後クラスタが新たに生成され、新たなクラスタ番号の割り当てを受けるとともに、それら（ｋ−１）個の分割後クラスタのそれぞれについて、当該分割後クラスタを参照する参照ノードが生成される。クラスタ構成部１８は、それら新たに生成された（ｋ−１）個の分割後クラスタと、元のクラスタのクラスタ番号を引き継いだ分割後クラスタとにそれぞれ対応する合計ｋ個の参照ノードが、それら各参照ノードに対応する各分割後クラスタ同士の分割前クラスタ内での親子関係を反映した親子関係を持つようにする。すなわち、ある分割後クラスタＣａのルートノードが別の分割後クラスタＣｂ内のノードの子である場合に、クラスタＣａを参照する参照ノードＲａがクラスタＣｂを参照する参照ノードＲｂの子になるようにする（すなわちＲａの参照ノード情報６２の親ノード番号を、Ｒｂのノード番号とする）。ｋ個の分割後クラスタは１つの分割前クラスタの木構造を分割したものなので、それら分割後クラスタを参照するｋ個の参照ノードは木構造をなす。
【００６８】
また、分割前クラスタと別のクラスタとの親子関係は、分割後クラスタにも引き継がれる。例えば、分割前クラスタが別のクラスタＣｘの子であれば、クラスタ構成部１８は、ｋ個の分割後クラスタのうち、クラスタＣｘ内のノードの子を持つ分割後クラスタを参照する参照ノード（言い換えれば、ｋ個の参照ノードがなす木構造のルートの参照ノード）を、クラスタＣｘを参照する参照ノードの子とする。また分割前クラスタが別のクラスタＣｙの親であれば、ｋ個の分割後クラスタのうちクラスタＣｙのルートノードの親のノードを含んだ分割後クラスタを参照する参照ノードを、クラスタＣｙを参照する参照ノードの親とする。
【００６９】
また、クラスタ構成部１８は、分割前クラスタの分割により新たに生成した（ｋ−１）個の参照ノードを、分割前クラスタを参照する参照ノードが属するクラスタＣｚに所属させる。すなわち、クラスタ構成部１８は、クラスタＣｚのクラスタ情報５２に、新たに生成した（ｋ−１）個の参照ノードのノード番号を追加する。この追加により、クラスタＣｚのノード数が上限値に達するか、又は上限値を超えると、クラスタ分割部１６はクラスタＣｚを分割する。
【００７０】
＜先祖・子孫関係検索＞
次に、このシステムの、先祖・子孫関係検索の機能について説明する。
【００７１】
ここで、木構造の中から任意の２つのノードＡ、Ｂを選択した場合に、一方のノードＡからルートノードに向かって木構造を辿って行く際に通る経路上にもう一方のノードＢが存在する場合これらのノードは先祖・子孫関係にあるという。この場合ノードＡが子孫、ノードＢが先祖である。
【００７２】
図１の例では、検索対象ノード入力部２２がユーザから先祖・子孫関係の有無の判定対象とする２つのノードを受け付け、クラスタ検索部２４と先祖・子孫判定部２６とが協働して、それら２つのノードが先祖・子孫関係にあるかどうかを判定する。
【００７３】
この判定のためにクラスタ検索部２４及び先祖・子孫判定部２６が実行する処理手順の例を、図７及び図８に示す。図７が先祖・子孫判定部２６の処理手順の例を、図８がクラスタ検索部２４の処理手順の例を、それぞれ示す。
【００７４】
検索対象ノード入力部２２が検索対象の２つのノード（以下、ノードＡ，Ｂと呼ぶ）の指定を受けると、クラスタ検索部２４は、それらノードＡ，Ｂについて図８の処理を開始する（Ｓ０）。まずクラスタ検索部２４は、それら２つのノードＡ，Ｂを、それぞれ順に注目ノードａ，ｂに代入する（Ｓ１０）。この処理では、クラスタ検索部２４は、まずクラスタ保持部２０に記憶された各クラスタ情報５２の「保持するノード集合の情報」を調べることにより、それら２つの注目ノードａ，ｂが同一クラスタに属しているか否かを判定する（Ｓ１１）。前述のクラスタ分割処理の例から判るように、１つのノードが複数のクラスタに属することは起こらない。
【００７５】
ノードａ，ｂが同一クラスタに属していると判った場合、クラスタ検索部２４はステップＳ１３に進む。
【００７６】
一方、ノードａ，ｂが同一クラスタに属していないと判った場合、クラスタ検索部２４はステップＳ１２の処理を行う。ステップＳ１２では、クラスタ検索部２４は、ノードａが属するクラスタを求め、そのクラスタを参照する参照ノードが属するクラスタを求め、更にこのクラスタを参照する参照ノードの属するクラスタを求め、というように、ノードａの属するクラスタを起点として１つずつ上位クラスタへと遡上する。そして、これ以上上位へと遡れなくなるまでこの遡上を繰り返し、その過程で通過するノードａの上位の各階層の参照ノード及びクラスタを記録する。ノードｂについても、同様の遡上を行い、ノードｂの上位の各階層の参照ノード及びクラスタを特定する。そして、ノードａの上位の各階層のクラスタとノードｂの上位の各階層のクラスタの中で、下位側から見て最初の共通のクラスタを求め、その共通クラスタに含まれるノードａ及びノードｂそれぞれの上位階層の参照ノードａ’，ｂ’を特定する。このように特定した参照ノードａ’，ｂ’は、同一クラスタに属している。クラスタ検索部２４は、特定した参照ノードａ’，ｂ’を、それぞれ、新たな注目ノードａ，ｂとし、ステップＳ１３の処理を行う。したがって、ステップＳ１３で操作の対象となる注目ノードａ，ｂは同一クラスタに属するものとなっている。
【００７７】
ステップＳ１３では、クラスタ検索部２４は、先祖・子孫判定部２６を呼び出し、そのノードｂがノードａの子孫であるかどうかを判定させる。
【００７８】
呼び出された先祖・子孫判定部２６は、図７の手順を実行する。図７は、判定対象の２つのノードのうちのノードｂを起点として、ノードｂがノードａの子孫であるか否かを判定する処理を示している。このように、図７自体はノードｂを起点とする処理であるが、先祖・子孫判定部２６は、ノードａを起点とした場合についても同様の処理手順を行い、ノードａがノードｂの子孫であるかどうかも確認する。以下、図７の手順を詳細に説明する。
【００７９】
図７の手順では、先祖・子孫判定部２６は、まずノードｂを、図７の手順における着目ノードとする（Ｓ１）。次に、着目ノード（現段階ではノードｂ）が、ノードａであるか否かを判定する（Ｓ２）。この判定では、着目ノードとノードａのノード番号同士が同じかどうかを調べればよい。この判定結果が肯定（ＹｅＳ）の場合、先祖・子孫判定部２６は、ノードｂはノードａの子孫であると判定する（Ｓ５）。これは、ノードａとｂとが同一ノードである場合である。
【００８０】
ステップＳ２の判定結果が否定（Ｎｏ）の場合、先祖・子孫判定部２６は、着目ノードがルート（根）ノードであるかどうかを判定する（Ｓ３）。この判定では、着目ノードの実ノード情報４２に含まれる親ノード番号を調べればよい。着目ノードの親ノード番号が空値（ＮＵＬＬ。すなわち親がない）である場合、着目ノードはルートノードであると判定される（判定結果が肯定）。この場合、先祖・子孫判定部２６は、ノードｂがノードａの子孫ではないと判定する（Ｓ６）。
【００８１】
ステップＳ３の判定結果が否定の場合、先祖・子孫判定部２６は、着目ノードを親ノードに移動する（Ｓ４）。すなわち、現在の着目ノードの親ノードを新たな着目ノードとする。この処理において、着目ノードの親ノードは、着目ノードの実ノード情報４２の親ノード番号から特定される。そして、先祖・子孫判定部２６は、再びステップＳ２に戻り、着目ノードがノードａ又はルートノードのいずれかであることが判明するまで、ステップＳ２〜Ｓ４の処理を繰り返す。この繰り返しは、ノードｂを起点に、着目ノードを１つずつ先祖に遡らせていく処理である。この繰り返しにより、着目ノードがノードａに一致したことがステップＳ２で判明すると、ノードｂはノードａの子孫であると判定することができる（Ｓ５）。一方、繰り返しにより、着目ノードが、ノードａに一致しないまま、ルートノードまで達したことがステップＳ３で判明すると、ノードｂはノードａの子孫ではないと判定することができる（Ｓ６）。
【００８２】
ノードｂを起点とする図７の処理が完了（すなわちＳ５又はＳ６のいずれかに到達）すると、先祖・子孫判定部２６は、ａとｂを読み替え、ノードａを起点として図７の処理をもう一度実行する。このように、ノードｂ，ａをそれぞれ起点とした場合の図７の処理により、（ア）ノードｂがノードａの子孫である、（イ）ノードａがノードｂの子孫である、（ウ）ノードａとノードｂは互いに先祖でも子孫でもない、のいずれかの結果が得られる。（ア）と（イ）の場合はノードａとノードｂとの間に先祖・子孫関係があるが、（ウ）の場合はノードａとノードｂとの間に先祖・子孫関係がない。
【００８３】
このようにして、注目ノードａ，ｂについての先祖・子孫判定部２６の判定処理が終わると、その結果がクラスタ検索部２４に返される。クラスタ検索部２４は、その判定処理の結果を図８ステップＳ１３の判定結果として、処理を進める。
【００８４】
再び図８の説明に戻ると、ステップＳ１３での先祖・子孫係判定部２６の判定にて、ノードａとｂの間に先祖・子孫関係がないと判定される（Ｓ１３の判定結果が否定）と、クラスタ検索部２４は、最終的にノードａとノードｂとの間に先祖・子孫関係がないと判定する。この判定結果は、検索対象ノード入力部２２に対して検索対象のノードを入力したユーザに対して提示してもよい。この提示は、例えば、検索対象ノード入力部２２を備えたコンピュータの画面上にその判定結果を表示することにより行ってもよい。
【００８５】
一方、ステップＳ１３での先祖・子孫判定部２６の判定にて、ノードａ，ｂの間に先祖・子孫関係があると判定されると、クラスタ検索部２４は、ノードａ，ｂのうちの先祖側のノードが参照ノードであるかどうかを判定する（Ｓ１４）。この判定は、当該先祖側のノードのノード番号に対応するノード情報が実ノード情報４２と参照ノード情報６２のいずれであるかに基づき行えばよい。
【００８６】
ステップＳ１４で、ノードａ，ｂのうちの先祖側のノードが参照ノードでない（判定結果が否定（Ｎｏ））、すなわち実ノードであると判定された場合、クラスタ検索部２４は、検索対象ノード入力部２２から入力された検索対象のノードＡ，Ｂ間に先祖・子孫関係があると最終的に判定する。この判定結果は、検索対象ノード入力部２２に対して検索対象のノードを入力したユーザに対して提示してもよい。この提示は、例えば、検索対象ノード入力部２２を備えたコンピュータの画面上にその判定結果を表示することにより行ってもよい。
【００８７】
ステップＳ１４で、ノードａ，ｂのうちの先祖側のノードが参照ノードであると判定された場合、クラスタ検索部２４はステップＳ１５の処理を実行する。
【００８８】
ステップＳ１５では、まずノードＡ，Ｂのうちの先祖側のノードを特定し、特定した先祖側のノードを次の処理ループにおける新たなノードＡとする。前述のステップＳ１２では、ノードＡ，Ｂを起点としてクラスタを上位階層へと遡上したが、ノードＡ，Ｂのうち、その遡上の結果現在の注目ノードａ及びｂのうちの先祖側のノードに到達した方のノードを、新たなノードＡとするのである。
【００８９】
またステップＳ１５では、現在の注目ノードａとｂ（これらは先祖・子孫関係にある）とを結ぶ木の経路上のノードの中から、注目ノードａとｂのうちの先祖側のノードの直近の子孫ノード（すなわち子）に該当するノードを特定し、特定したノードが参照するクラスタのルートノードを求める。この処理では、例えば、先祖側のノードの直近の子孫ノード（これは参照ノードである）の参照ノード情報６２の「参照するクラスタ番号」を調べ、このクラスタ番号に対応するクラスタ情報５２の「保持するノード集合の情報」から、当該クラスタのルートノードを求めればよい。そして、求めたルートノードが参照ノードであれば、そのルートノードが参照するクラスタのルートノードを求める。求めたルートノードが実ノードであることが判明するまで、この処理を繰り返す。そして、最終的に求められた実ノードであるルートノードを、次の処理ループにおける新たなノードＢとする。求められた新たなノードＢは、元のノードＡ，Ｂのうちの子孫側のノードに対する先祖に該当する。なぜなら、上述の求め方から判るように、新たなノードＢが属するクラスタは、元のノードＢが属するクラスタの先祖であり、新たなノードＢはその先祖のクラスタのルートであるからである。
【００９０】
このように、ステップＳ１５では、ノードＡ，Ｂのうちの先祖側を新たなノードＡとして残し、子孫側のノードから遡った先祖のノードを新たなノードＢとするのである。新たなノードＡが新たなノードＢの先祖であれば、新たなノードＡは、元のノードＡ，Ｂのうちの子孫側のノードの先祖である。したがって、新たなノードＡと新たなノードＢとが先祖・子孫関係を持つかどうかを判定すれば、元のノードＡと元のノードＢが先祖・子孫関係を持つかどうかが判る。
【００９１】
そこで、クラスタ検索部２４は、ステップＳ０に戻り、ステップＳ１５で求めた新たなノードＡ，Ｂを対象として図８の処理を繰り返す。
【００９２】
クラスタ検索部２４は、以上のような処理を、ステップＳ１３の判定結果が否定、又はステップＳ１４の判定結果が否定になるまで繰り返す。これにより、検索対象ノード入力部２２から入力された検索対象のノード同士が先祖・子孫関係にあるか否かが判定される。
【００９３】
次に、上述したクラスタ検索部２４及び先祖・子孫判定部２６の処理手順を、図６に例示した木構造中のノード同士の先祖・子孫関係の判定に用いた場合の具体例を説明する。
【００９４】
まず第１の例として、図６の木構造（第１層）中の実ノード４６と実ノード４３とを検索対象ノードとした場合の処理の流れを説明する。
【００９５】
この場合、実ノード４６と実ノード４３は同じクラスタＣ８に属していることがステップＳ１１で判る。同じクラスタ内の２つのノードの先祖・子孫関係判定は図７に示すように、片方のノードＡからクラスタのルートノードに向かって辿っていき、もう片方のノードＢに突き当たれば、ノードＡはノードＢの子孫であり、逆にノードＢからルートノードに向かって辿っていき、ノードＡに突き当たれば、ノードＢはノードＡの子孫である。片方のノードを起点として先祖・子孫判定部２６が図７の手順を実行し、その結果先祖・子孫関係がみつからなかった場合はもう片方を起点として同じ手順を実行する。第１の例のノード４６とノード４３はこの先祖・子孫関係判定により先祖・子孫関係にないことが明らかとなる。
【００９６】
次に、第２の例として、図６において実ノード４６と実ノード３１が先祖・子孫関係にあるか検索する。ノード４６とノード３１は、それぞれクラスタＣ８、Ｃ６と、所属するクラスタが異なる。そこでクラスタＣ８とＣ６をそれぞれ参照する参照ノードを辿り、直近の共通する先祖クラスタ中のノードを取得する。
【００９７】
クラスタ保持部２０はクラスタＣ８が参照ノード４７に参照されているという情報（クラスタ情報５２）を持っている。クラスタ検索部２４は、これを用いて参照ノード４７を特定し、参照ノード４７を保持するクラスタをクラスタ保持部２０に問い合わせてそれがクラスタＣ１１であることを知る。更に、同様にクラスタＣ１１を参照する参照ノード６２と、それを保持するクラスタがＣ１２であるという情報も取得する。このようにして、クラスタのなす階層をクラスタＣ８から上位へと遡っていった場合に得られる最上位階層のクラスタまでのクラスタの系列（連なり）はＣ８（４６）→Ｃ１１（４７）→Ｃ１２（６２）となる。括弧内の番号は、括弧の前に示したクラスタ内の参照ノードであって、その系列における１段階下位のクラスタを参照する参照ノードを示す（ただし、最下位のクラスタについての括弧内の番号は、実ノードを示す）。クラスタ検索部２４は、求めたＣ８（４６）→Ｃ１１（４７）→Ｃ１２（６２）というクラスタ系列を記憶する。
【００９８】
同様に、クラスタ検索部２４は、クラスタＣ６から上位階層へと遡上した場合のルートクラスタまでのクラスタの系列、Ｃ６（３１）→Ｃ１１（３５）→Ｃ１２（６２）、を求めて記憶する。
【００９９】
そして、クラスタ検索部２４は、それら２つのクラスタ系列同士の間で、最も下位で共通するクラスタを特定する。例えば、クラスタ検索部２４は、２つの系列の一方、例えばクラスタＣ８から開始する系列を選択し、最下位のクラスタを選択する。そして、選択したクラスタと同じものをもう一方の系列から探す。見つからなければ、選択した系列から、選択したクラスタよりも１つ上位のクラスタを選択し、この選択したクラスタと同じものをもう一方の系列から探す。選択した系列から選択したクラスタと同じものがもう一方の系列から見つかるまで、以上の処理を繰り返す。クラスタは階層構造をなしているので（図６参照）、選択した系列から選択したクラスタと同じものがもう一方の系列から必ず見つかる。
【０１００】
具体的には、Ｃ８を選択すると、もう一方の系列はＣ６、Ｃ１１、Ｃ１２であるので共通する先祖クラスタは存在しない。次にＣ１１を選択するともう一方の系列の２番目にＣ１１が存在することを発見する。これが両系列に共通する最下位のクラスタである。これより上位のクラスタＣ１２も両系列で共通のクラスタであるが、共通する最下位のクラスタが判ればよいので、処理はＣ１１が見つかった段階で終了してよい。
【０１０１】
次の注目ノードは、Ｃ１１内の参照ノード４７、３５となる（図８のＳ１２）。同じクラスタ上の２つのノードに対しては先祖・子孫関係判定処理（図７）が適用可能であるので、この処理により判定を行う。検索の結果ノード３５と４７は先祖・子孫関係にあることが判る（図８のＳ１３）。ここでノード３５、４７は参照ノードであり、実ノードではない（図８のＳ１４）。そこでクラスタ検索部２４は、両者のうちの先祖側のノード３５の直近の子孫ノードがノード４１であることを求め、そのノード４１が参照するクラスタＣ７のルートノード３６の親ノード３２を取得する（図８のＳ１５）。このノード３２は実ノードである。また、検索対象の実ノード４６と３１のうち、現在の注目ノード３５、４７のうちの先祖側のノード３５に対応するノードはノード３１である。
【０１０２】
そこで、クラスタ検索部２４は、次にノード３１，３２を新たなノードＡ，Ｂとし（図８のＳ０）、これらノードＡ，Ｂについて図８の手順を行って先祖・子孫関係を調べる。ノード３１、３２は同じクラスタに属し、先祖・子孫関係にある（図８のＳ１１、Ｓ１３）。またこれらのノードは参照ノードでない（図８のＳ１４の判定結果が否定）。したがって、ノード３１はノード３２の先祖であることが分かり、ノード３２はノード４６の先祖であるので、最終的に検査対象のノード４６とノード３１は先祖・子孫関係にあると判定される。ここで検索処理を終える。
【０１０３】
更に第３の例として、実ノード１３と実ノード４６の先祖・子孫関係の判定処理の流れを説明する。
【０１０４】
クラスタ検索部２４は、ノード１３とノード４６がそれぞれクラスタＣ０とＣ８に属し、同一のクラスタに属しないことを求める（図８のＳ１１）。そこで、ノード１３、４６が属するクラスタを参照する参照ノードを辿り、直近の共通する先祖クラスタ中のノードを取得する。それぞれクラスタの系列はＣ０（１３）→Ｃ２（１０）→Ｃ１２（６０）、及びＣ８（４６）→Ｃ１１（４７）→Ｃ１２（６２）であるので、前述同様にして直近の共通する祖先クラスタはＣ１２と判明し、Ｃ１２内での注目ノードはノード６０，６２になる（図８のＳ１２）。そして、クラスタ検索部２４は、先祖・子孫判定部２６に、ノード６０と６２を対象として先祖・子孫関係判定（図７）を行わせ、この結果ノード６０、６２は先祖・子孫関係にあることが判明する（図８のＳ１３）。ここで、先祖側のノード６０は参照ノードであるので、クラスタ検索部２４は、当該先祖側ノード６０の直近の子孫ノード６２が参照するクラスタＣ１１のルートノード３５を取得し、更にノード３５は参照ノードであるので、ノード３５が参照するクラスタＣ６のルートノード３０を取得して、その親ノード１６を取得する（図８のＳ１５）。このノード１６は実ノードであるので、これを新たなノードＢとする。また、検索対象として指定されたノード１３及び４６のうち、先祖側の注目ノード６０に対応するノード１３を、新たなノードＡとする。
【０１０５】
そして、クラスタ検索部２４は、それら新たな対象ノードＡ，Ｂであるノード１３，ノード１６について、図８の手順を実行する。ノード１３,１６はそれぞれクラスタＣ０、Ｃ３に属しており同一クラスタには属さない（図８のＳ１１）。そこでクラスタ検索部２４は、ノード１３とノード１６が属するクラスタを参照する参照ノードを辿り、直近の共通する先祖クラスタ中のノードを取得する。それぞれクラスタ系列はＣ０（１３）→Ｃ２（１０）→Ｃ１２（６０）、及びＣ３（１６）→Ｃ２（１７）→Ｃ１２（６０）であるので前述同様の方法でＣ２が直近（最下位）の共通クラスタであり、その共通クラスタ内の注目ノードがノード１０、１７であることをつきとめる（図８のＳ１２）。次に、それらノード１０，１７を対象として、先祖・子孫判定部２６が先祖・子孫関係の検索処理（図７）を実施し、その結果両ノードが先祖・子孫関係にあると判定される（図８のＳ１３）。ここで、注目ノードのうちの先祖側のノード１０は参照ノードであるので、クラスタ検索部２４は、当該ノード１０の直近の子孫ノード１７が参照するクラスタＣ３のルートノード３を取得し、ルートノード３の親ノード２を取得する。ノード２は実ノードである。
【０１０６】
次に、クラスタ検索部２４は、このノード２と、検索対象のノードのうちの先祖側であるノード１３とを対象として、図８の処理を再び行う。ここで、ノード２，１３は同一クラスタＣ０に属しているので、クラスタ検索部２４は、先祖・子孫判定部２６に判定を行わせる。この判定の結果、結果ノード１３,２は先祖・子孫関係に無いことが判明し、ステップＳ１３により、検索対象のノード１３とノード４６とは先祖・子孫関係に無いことが最終的に判明する。
【０１０７】
＜処理に要する計算量＞
ノード１３とノード４６の先祖・子孫関係判定を行うとき、階層的なクラスタ構造を用いた本実施形態の検索処理を用いず、単にノード群がなす木構造のみ（すなわち図８の第１層における実ノード間の関係のみ）を用いて検索を行う場合を考える。この場合、ノード４６から木構造のルートノードまで１４回のノード移動を行わねばならない。このようにルートノードまで移動する経路にノード１３が現れないことで、初めてノード１３がノード４６の先祖でないことが判明する。
【０１０８】
これに対し、この実施形態の仕組みを使った場合、最上位クラスタ（第３層）で１回（ノード６２→６０）、次位のクラスタ（第２層）で１回（ノード１７→１０）、最下位（第１層）のクラスタで２回（ノード２→０）と、合計４回のノード移動を行えば、先祖・子孫関係が判別される。
【０１０９】
より一般的に説明すると、この実施形態で用いるクラスタの階層数Ｌは実ノード数Ｎとクラスタあたりのノード上限数Ｔを使ってＬ=floor（log（Ｎ/Ｔ）+２）と表せる。floor（）は小数点以下を切り捨てる床関数である。ノード数Ｎの増加に対してlogＮのオーダーで階層Ｌが増加する。図８のＳ１２は、２つのノードが同一クラスタに納まるまで上位クラスタ中の参照ノード取得を繰り返す。この処理は最大で階層Ｌの回数分繰り返す。また図８のＳ１３（すなわち図７の処理）の処理時間は１クラスタ中のノード数上限数Ｔに依存する。よって、この実施形態の方法での検索時間は、階層数Ｌと、１つのクラスタ内のノード上限数Ｔにより決まる。従って、この方法は、実ノード数Ｎの増加に対して検索時間が増加しにくい方法であると言える。また、この方法では、階層Ｌとクラスタ内ノード上限数Ｔにより最遅の検索時間が決まるので、木構造上の検索対象の２ノードが近い場所にあっても、離れた場所にあっても、変動の小さい一定範囲内の検索時間が見積もられる。
【０１１０】
［変形例］
上述の実施形態ではクラスタ分割を行った際、分割により新しく生成されたクラスタを参照する参照ノードを上位クラスタに追加した。これに対し、変形例ではクラスタを分割する際、元のクラスタから分割により取り出された新たなクラスタの部分木が元のクラスタの部分木にて占めていた位置に、その新たなクラスタを参照する参照ノードを追加する。ここで、分割により取り出された新たなクラスタの部分木が元のクラスタの部分木にて占めていた位置とは、元のクラスタ内のノード位置であり、かつ当該新たなクラスタの根ノードの親ノード（これは元のクラスタ内のノードである）の子となる位置である。したがって、この実施形態では、分割により生成された新たなクラスタを参照する参照ノードは、当該新たなクラスタの親クラスタ（すなわち元のクラスタから新たなクラスタを除いたもの）に追加されることになる。
【０１１１】
この変形例のための装置構成は、図１に示したものと同様でよい。また、クラスタ保持部２０が保持する実ノード情報４２，クラスタ情報５２及び参照ノード情報６２のデータ構造は、図２に示したものと同様でよい。変形例において実施形態と異なるのは、クラスタ構成部１８の処理の内容であり、他の構成要素については実施形態の場合と同様でよい。
【０１１２】
以下、変形例における各フェーズの処理について説明する。
【０１１３】
＜ノードの登録＞
実ノードの登録処理は、上述実施形態と同じでよい。
【０１１４】
＜クラスタの分割＞
クラスタ構成部１８は、クラスタを分割する場合、元のクラスタから分割した新たなクラスタを参照する参照ノードを、元のクラスタ内の、当該新たなクラスタが占めていた位置に入れる。すなわち、クラスタ構成部１８は、新たなクラスタのクラスタ情報５２を作成すると共に、その新たなクラスタを参照する参照ノードの参照ノード情報６２を作成し、元のクラスタのクラスタ情報５２の［保持するノード集合の情報」から新たなクラスタに含まれるノードを削除し、代わりにその参照ノードを追加する。
【０１１５】
図３Ａに例示するように、実ノードの追加により、あるクラスタ中のノード数が上限値（この例では１０）に達したらクラスタを分割する（図９Ａ参照）。実施形態の場合と同様、クラスタ分割部１６が、元のクラスタ内のノード数のなるべく半分に近いところで分割する。図９Ａの例ではノード５のところで分割すると、分割後の各部分木のノード数が元のちょうど半分になる。そこで、ノード５をルートノードとする部分木を元のクラスタＣ０から分割して新たなクラスタＣ１とする。
【０１１６】
この分割の際、クラスタ構成部１８は、元のクラスタＣ０の中のノード５が存在した場所に、新たなクラスタＣ１を参照する参照ノード１０を追加する。図９Ａでは、この参照ノード１０とクラスタＣ１との対応関係が破線で示されている。また、このように分割されても、ノード４と５の間の親子関係は維持される（図では実線で示している）。
【０１１７】
このようにしてできたクラスタＣ１はクラスタＣ０の参照ノード１０に参照されているので、クラスタＣ０はクラスタＣ１の上位クラスタ、クラスタＣ１はクラスタＣ０の下位クラスタの関係になる。また、クラスタＣ１のノード５の親ノードはクラスタＣ０のノード４であるので、クラスタＣ０はクラスタＣ１の親クラスタ、クラスタＣ１はクラスタＣ０の子クラスタという関係も併せ持つ。
【０１１８】
このように、変形例では、分割により生成された子クラスタを参照する参照ノードが親クラスタに入るので、クラスタ同士の親子関係がすなわちクラスタ同士の上位・下位の関係となる。
【０１１９】
この分割の後、クラスタＣ０に更にノードが追加され、クラスタＣ０内のノード数がノード上限数１０に再び到達した状態を図９Ｂに示す。この場合、クラスタ分割部１６は、ノード３をルートとする部分木をクラスタＣ０から分割すればよいと判定する。クラスタ構成部１８は、ノード３をルートとする部分木（すなわち新たなクラスタＣ２）をクラスタＣ０から削除し、クラスタＣ０においてノード３が存在した箇所に、分割により生じた新たなクラスタＣ２を参照する参照ノード１５を挿入する。クラスタＣ２には１回目のクラスタ分割で生成された参照ノード１０が含まれる。この分割の結果を図９Ｃに示す。
【０１２０】
＜先祖・子孫関係検索＞
この変形例では、クラスタの上位・下位関係がクラスタの親子関係へと縮退しただけであり、上位・下位の関係の情報は存在しているので、先祖・子孫関係の検索には、実施形態と同じく、図８及び図７に示した手順を実行すればよい。
【０１２１】
処理の具体例を、図９Ｃの木構造を例にとって説明する。
【０１２２】
第１の例として、その木構造中の実ノード９と実ノード１２とが検索対象ノードとして指定された場合を考える。以下では簡単の為、ノード９を子孫側候補とした場合の処理の流れを説明するが、実際はノード１２を子孫側候補とした場合の処理も同様に行う。
【０１２３】
この例では、ノード９はクラスタＣ１に、ノード１２はクラスタＣ０に属しており同一のクラスタに無い（図８のＳ１１）。そこで、クラスタ検索部２４は、ノード９、１２が属するクラスタを参照する参照ノードをそれぞれ辿り、直近の共通する先祖クラスタ中の参照ノードを取得する。ここで、ノード９に対するクラスタ系列はＣ１（９）→Ｃ２（１０）→Ｃ０（１５）である。一方、ノード１２が属するクラスタＣ０を参照する参照ノードが存在しない（Ｃ０はルートクラスタ）ので、ノード１２に対応するクラスタ系列はＣ０（１２）となる。
【０１２４】
実施形態と同様にして、両系列で共通する最下位のクラスタを求める。この例では、クラスタＣ０がその最下位の共通クラスタであることが分かり、その共通クラスタ内での注目ノードは１５、１２であると求められる（図８のＳ１２）。なお、図８のＳ１２では、判定対象の実ノードのうちの一方が共通クラスタに含まれる場合、その実ノード自身を注目クラスタとする。なお、判定対象の２つの実ノードの両方が同じクラスタに含まれる場合は、Ｓ１１からＳ１３に進むので、ステップＳ１２の処理は行われない。先祖・子孫判定部２６が、それら注目ノード１５、１２に対して先祖・子孫関係の有無を判定する。この結果、先祖・子孫関係に無いことが分かる（図８のＳ１３）ので、最終的に判定対象のノード９と１２とは先祖・子孫関係に無いと判定される。
【０１２５】
＜処理に要する計算量＞
変形例で生成されるクラスタの数Ｃは、実ノード数Ｎとクラスタあたりのノード上限数Ｔを使うとＣ=floor（Ｎ/Ｔ+１）で表せる。floor（）は小数点以下を切り捨てる床関数である。この式から分かるように、ノード数Ｎの増加に対してＮのオーダーでクラスタ数Ｃが増加する。変形例では図８のＳ１２により２つの注目ノードが同じクラスタに納まるまで親（上位）クラスタ中の参照ノードの遷移を繰り返し、同じクラスタ内では図８のＳ１３によりクラスタ内のノードを遷移する。従ってクラスタ数Ｃとクラスタ内ノード数により最遅の検索時間が決まる。よって変形例と比較して木構造のノード数増加による検索時間への増加影響が大きい。また、検索対象ノード間の距離が大きくなるほど、検索時間が長くなる傾向を持つ。
【０１２６】
しかし、変形例は、クラスタの上位・下位関係を用いるので、実ノードの親子関係のみから検査対象ノード間の先祖・子孫関係を判定するよりも、計算量は少なくて済む。
【０１２７】
また、参照ノードの数に着目すると、この実施形態は、実施形態の第２層のクラスタ群がもつ参照ノードと同じ数の参照ノードを持つ。しかし、実施形態の第３層以上の階層にある参照ノードに相当するノードは、変形例では生成しない。したがって、必要な記憶容量は上記実施形態よりも少ない。
【０１２８】
［第２の変形例］
上述の変形例を改良した第２の変形例を以下に説明する。第２の変形例のための装置構成は図１に示したものでよい。この改良例は、クラスタ構成部１８の処理内容が上述の変形例と異なるが、他の要素の処理内容は上位変形例及び実施形態と同様でよい。
【０１２９】
以下、この改良例における各フェーズの処理を説明する。
【０１３０】
＜ノードの登録＞
実ノードの登録処理は、上述実施形態と同じでよい。
【０１３１】
＜クラスタの分割＞
上記変形例では、図９Ｂ及び図９Ｃに示す通り、クラスタＣ０をノード２と３の間で分割してクラスタＣ２を新たに生成する際に、ノード３をルートとする部分木に含まれる参照ノード１０を新たなクラスタＣ２に含めた。
【０１３２】
これに対し、この改良例では、図１０Ａに示す通り、参照ノード１０を分割元のクラスタＣ０に残し、新たなクラスタＣ２からは除いた。
【０１３３】
なお、この改良例では、参照ノード１０をクラスタＣ０に残すので、クラスタＣ０の分割位置の決め方が以下の２つの点で上記変形例と異なる。
（１）参照ノードをまたいで部分木のノード数をカウントしない。
（２）クラスタ内ノード上限数の半分からの距離が同じ場合は、部分木に参照ノードを含まない方を分割対象として選択する。
【０１３４】
この決め方により、図１０Ａの例では、ノード１と２の間でクラスタを分割している。
【０１３５】
分割により生成された新たなクラスタＣ２を参照する参照ノード１５は、元のクラスタＣ０においてクラスタＣ２の部分木が占めていた位置（すなわち元のクラスタＣ０内の、ノード１の子となり且つノード１０の親となる位置）に挿入される。したがって、参照ノード１０は参照ノード１５の子となる。
【０１３６】
クラスタ構成部１８は、上述のような分割後のクラスタＣ０，Ｃ２が構成されるよう、クラスタＣ２のクラスタ情報５２と参照ノード１５の参照ノード情報６２を生成し、更にクラスタＣ０のクラスタ情報５２（特に「保持するノード集合の情報」）と参照ノード１０の参照ノード情報６２（特に親ノード番号）を修正する。
【０１３７】
クラスタ分割後の図１０Ａの木構造では、参照ノード１０がクラスタＣ１を参照していることから、クラスタＣ０はクラスタＣ１の上位クラスタ、クラスタＣ１はクラスタＣ０の下位クラスタという関係にある。同様にクラスタＣ０はクラスタＣ２の上位クラスタ、クラスタＣ２はクラスタＣ０の下位クラスタの関係にある。また、ノード５の親ノードはノード４であるので、クラスタＣ２はクラスタＣ１の親クラスタ、クラスタＣ１はクラスタＣ２の子クラスタの関係にある。同様にクラスタＣ０はクラスタＣ２の親クラスタ、クラスタＣ２はクラスタＣ０の子クラスタの関係にある。従ってクラスタＣ２、Ｃ１を参照する参照ノード１５、１０の親子関係はクラスタの親子関係に対応したものになる。
【０１３８】
図１０Ｂに、更に実ノードが増えてクラスタ分割が繰り返された結果、クラスタＣ０のノードが参照ノードにより飽和（ノード上限数に到達）した状態の例を示す。この場合は参照ノードも分割対象となる。この例では、最も分割に適したノードとして参照ノード３０が選択され、クラスタＣ０内の参照ノード３０をルートとする部分木が、新たなクラスタＣ１０としてＣ０から分割される（図１０Ｃ参照）。この場合、新たなクラスタＣ１０を参照する参照ノード４５を、クラスタＣ０内でそのクラスタＣ０の部分木が占めていた位置に挿入する。
【０１３９】
＜先祖・子孫関係検索＞
この第２の変形例でも、クラスタの上位・下位関係がクラスタの親子関係へと縮退しただけであり、上位・下位の関係の情報は存在しているので、先祖・子孫関係の検索には、実施形態と同じく、図８及び図７に示した手順を実行すればよい。
【０１４０】
例えば、図１０Ａにおいて、実ノード９と実ノード１２とが先祖・子孫関係にあるか調べる場合の処理の例を以下に示す。この例では、ノード９はクラスタＣ１に、ノード１２はクラスタＣ０に属しており同一のクラスタに無い（図８のＳ１１）。そこでノード９、１２が属するクラスタを参照する参照ノードを辿り、直近の共通する先祖クラスタ中のノードを取得する。上記変形例と同様、ノード９に対応するクラスタ系列はＣ１（９）→Ｃ０（１０）であり、ノード１２に対応するクラスタ系列はＣ０（１２）であることが分かる。両系列で共通する最下位のクラスタはＣ０となる（図８のＳ１２）。また、その共通クラスタＣ０内の注目ノードはノード１０と１２であることも求められる。先祖・子孫判定部２６がそれら注目ノード１０と１２に対して先祖・子孫関係の有無を判定し、この結果それら両者には先祖・子孫関係に無いことが明らかとなる（図８のＳ１３）。以上から判定対象である実ノード９と実ノード１２は先祖・子孫関係に無いことが判定される。
【０１４１】
もう１つの例として、図１０Ａの木構造において実ノード９と実ノード１４が先祖・子孫関係にあるか調べる場合を以下に示す。ノード９、１４はそれぞれクラスタＣ１、Ｃ２に属しており同一のクラスタに無い（図８のＳ１１）。そこでノード９、１４が属するクラスタを参照する参照ノードを辿り、直近の共通する先祖クラスタ中のノードを取得する。これにより、ノード９、１４に対応するクラスタ系列はそれぞれＣ１（９）→Ｃ０（１０）、Ｃ２（１４）→Ｃ０（１５）であることが求められる。これら両系列の比較から、直近の共通する先祖クラスタはＣ０であることが分かり、注目ノードは１０、１５であることが求められる。先祖・子孫判定部２６が、それら注目ノード１０、１５に対して先祖・子孫関係の有無を判定し（図８のＳ１３）、それら注目ノード１５、１０は先祖・子孫関係にあることが判明する。そこで、クラスタ検索部２４は、注目ノード１５，１０の内先祖側であるノード１５は参照ノードであるので（図８のＳ１４）、当該注目ノード１５の直近の子孫であるノード１０が参照するクラスタＣ１のルートノード５の親ノード４を取得する（図８のＳ１５）。取得したノード４は実ノードなので、クラスタ検索部２４は、ステップＳ０に戻り、新たに取得した実ノード４と、判定対象のうちの先祖側である実ノード１４と、を判定対象として、図７及び図８に例示した処理を繰り返す。この場合、実ノード１４の方が実ノード４の先祖側であることを前提として処理を行えばよい。この例では、ノード４、１４は同一のクラスタＣ２に属しているので（図８のＳ１１）、図８のＳ１３に進み、先祖・子孫判定部２６によりそれらノード４，１４間に先祖・子孫関係があるかどうかを判定する。この場合、図１０Ａの例では、ノード４はノード１４の親なので一見先祖・子孫関係があるように見えるが、上述のようにこの繰り返しではノード１４の方がノード４よりも先祖側であることが前提であり、ノード４がノード１４の親であるという関係はこの前提に矛盾する。したがって、ノード４とノード１４とは先祖・子孫関係にないと判定される。図７の手順に即して言えば、子孫側であるノード４を起点として図７の処理により部分木を遡っていっても、ノード１４には到達できないので、ノード４と１４とは先祖・子孫関係に無いと判定されることになる。以上から判定対象であるノード９、１４は先祖・子孫関係に無いと判定される。
【０１４２】
ノード９と１２の先祖・子孫検索において、上述の変形例ではクラスタＣ１からクラスタＣ２の参照ノード１０を取得することと、更にクラスタＣ０の参照ノード１５を取得することとで、合計２回の参照ノード取得を行った。これに対し、この変形例２ではクラスタ階層が少なくなるようにクラスタ分割を行っている成果として、クラスタＣ１からクラスタＣ０の参照ノード１０の１回のみの取得で済んでいる。
【０１４３】
このように、変形例２では、クラスタの親子関係の層をなるべく増加しないようにクラスタ構成を行っているので、上記変形例よりも早く同一クラスタに到達できることが期待できる。
【０１４４】
＜コンピュータへの実装＞
以上に例示したシステムは、例えば、汎用のコンピュータに上述の各機能モジュールの処理を表すプログラムを実行させることにより実現される。ここで、コンピュータは、例えば、ハードウエアとして、ＣＰＵ等のマイクロプロセッサ、ランダムアクセスメモリ（ＲＡＭ）およびリードオンリメモリ（ＲＯＭ）等のメモリ（一次記憶）、ＨＤＤ（ハードディスクドライブ）を制御するＨＤＤコントローラ、各種Ｉ／Ｏ（入出力）インタフェース、ローカル・エリア・ネットワークなどのネットワークとの接続のための制御を行うネットワークインタフェース等が、たとえばバスを介して接続された回路構成を有する。また、そのバスに対し、例えばＩ／Ｏインタフェース経由で、ＣＤやＤＶＤなどの可搬型ディスク記録媒体に対する読み取り及び／又は書き込みのためのディスクドライブ、フラッシュメモリなどの各種規格の可搬型の不揮発性記録媒体に対する読み取り及び／又は書き込みのためのメモリリーダライタ、などが接続されてもよい。上に例示した各機能モジュールの処理内容が記述されたプログラムがＣＤやＤＶＤ等の記録媒体を経由して、又はネットワーク等の通信手段経由で、ハードディスクドライブ等の固定記憶装置に保存され、コンピュータにインストールされる。固定記憶装置に記憶されたプログラムがＲＡＭに読み出されＣＰＵ等のマイクロプロセッサにより実行されることにより、上に例示した機能モジュール群が実現される。なお、それら機能モジュール群のうちの一部又は全部を、専用ＬＳＩ(Large Scale Integration)、ＡＳＩＣ（Application Specific Integrated Circuit、特定用途向け集積回路）又はＦＰＧＡ（Field Programmable Gate Array）等のハードウエア回路として構成してもよい。
【産業上の利用可能性】
【０１４５】
情報処理分野には、例示したＸＭＬ文書などの構造化文書をはじめとして、木構造をなす複数のデータ要素からなるデータが多種多様に存在する。このようなデータの処理においては、データ要素同士の間に先祖・子孫関係があるかどうかで、それらデータ要素に対するデータ処理の内容を切り換える場合がある。例えば、先祖のデータ要素の属性や状態に応じて子孫のデータ要素の処理内容が決まる場合などである。このような場合、データ要素同士の間の先祖・子孫関係の判定の計算量（計算時間）を低減することには、産業上大きな意義がある。
【符号の説明】
【０１４６】
１０ ノード入力部、１２ ノード登録部、１４ 分割必要性判断部、１６ クラスタ分割部、１８ クラスタ構成部、２０ クラスタ保持部、２２ 検索対象ノード入力部、２４ クラスタ検索部、２６ 先祖・子孫判定部。
【特許請求の範囲】
【請求項１】
実ノード及び参照ノードを含むノード群が構成する１以上の木構造を表す木構造情報と、前記１以上の木構造の各々を分割して得られる各部分木がそれぞれ当該木構造のうちのどのノードを含むかを表す部分木情報と、前記各部分木を参照する各参照ノードを特定する参照関係情報と、を記憶する記憶手段と、
前記木構造情報に対するノードの追加により前記部分木情報が表す各部分木のうち第１の参照ノードが参照する第１の部分木のノードの数があらかじめ定めた上限数を超えた場合に、当該第１の部分木から第２の部分木を分割することにより、前記第１の部分木及び前記第２の部分木のノードの数が共に前記上限数以下となるようにし、当該分割に応じて前記記憶手段に記憶された前記部分木情報を更新する分割手段と、
前記分割手段による分割に応じて前記第２の部分木を参照する第２の参照ノードを新たに生成し、前記第２の部分木を参照する参照ノードが前記第２の参照ノードであることを示す情報を前記参照関係情報に追加すると共に、前記第２の参照ノードが前記第１の参照ノードが含まれる部分木に含まれることを表す情報を前記部分木情報に追加し、前記第１の参照ノードと前記第２の参照ノードとが前記第１の部分木と前記第２の部分木との親子関係に対応する親子関係を構成することを表す情報を前記木構造情報に追加する、情報追加手段と、
を備える木構造処理装置。
【請求項２】
実ノード及び参照ノードを含むノード群が構成する１以上の木構造を表す木構造情報と、前記１以上の木構造の各々を分割して得られる各部分木がそれぞれ当該木構造のうちのどのノードを含むかを表す部分木情報と、前記各部分木を参照する各参照ノードを特定する参照関係情報と、を記憶する記憶手段と、
前記木構造情報に対するノードの追加により前記部分木情報が表す各部分木のうち第１の参照ノードが参照する第１の部分木のノードの数があらかじめ定めた上限数を超えた場合に、当該第１の部分木から第２の部分木を分割することにより、前記第１の部分木及び前記第２の部分木のノードの数が共に前記上限数以下となるようにし、当該分割に応じて前記記憶手段に記憶された前記部分木情報を更新する分割手段と、
前記分割手段による分割に応じて前記第２の部分木を参照する第２の参照ノードを新たに生成し、前記第２の部分木を参照する参照ノードが前記第２の参照ノードであることを示す情報を前記参照関係情報に追加すると共に、前記第２の参照ノードが前記第１の部分木に含まれることを表す情報を前記部分木情報に追加し、前記第２の参照ノードが前記第２の部分木の根ノードの親ノードに該当する前記第１の部分木のノードの子であることを示す情報を前記木構造情報に追加する、情報追加手段と、
を備える木構造処理装置。
【請求項３】
前記木構造情報が表す１以上の木構造のうちのいずれかの木構造の中から、先祖と子孫の関係にあるか否かの判定対象とする第１の実ノードと第２の実ノードとの指定を受け付ける指定受付手段と、
同一の部分木内にある２つのノードについて、当該ノード同士の間に先祖と子孫の関係があるか否かを、前記記憶手段に記憶された部分木情報が表す各ノード間の親子関係をたどることで判定する第１の判定手段と、
前記指定受付手段で受け付けた前記第１の実ノードと前記第２の実ノードとの間に先祖と子孫の関係があるかどうかを判定するための判定処理を行う第２の判定手段と、
を更に備え、
前記第２の判定手段が行う前記判定処理では、ある部分木を参照する参照ノードが含まれる部分木を前記ある部分木の１階層上位の部分木と呼ぶ場合に、前記第１の実ノードが属する部分木の上位に該当する各階層の部分木からなる第１の部分木系列と前記第２の実ノードが属する部分木の上位に該当する各階層の部分木からなる第２の部分木系列とを前記記憶手段に記憶された前記部分木情報及び前記参照関係情報に基づき求め、求めた前記第１の部分木系列と前記第２の部分木系列との間で共通する部分木を特定し、特定した部分木内にノードのうち前記第１の実ノード及び前記第２の実ノードにそれぞれ対応する２つのノードを特定し、特定した２つのノード同士の間に先祖と子孫の関係があるか否かの判定を前記第１の判定手段に実行させ、この判定の結果、前記特定した２つのノード同士の間に先祖と子孫の関係がないと判定された場合に、前記指定受付手段で受け付けた前記第１の実ノードと前記第２の実ノードとの間に先祖と子孫の関係がないと判定する、
ことを特徴とする請求項１又は２に記載の木構造処理装置。
【請求項４】
前記第２の判定手段が行う前記判定処理では、
前記特定した２つのノード同士の間に先祖と子孫の関係があると前記第１の判定手段により判定された場合、前記指定受付手段で受け付けた前記第１の実ノードと前記第２の実ノードの中から、前記特定した２つのノードのうち先祖側のノードに対応するノードを新たな第１の実ノードとして特定し、前記特定した部分木内の前記特定した２つのノード同士を結ぶ経路上のノードのうちの前記先祖側のノードの子に該当する参照ノードが参照する下位の部分木の根ノードを求め、求めた根ノードが参照ノードである場合には更に当該根ノードが参照する下位の部分木の根ノードを求めるという処理を、下位の部分木の根ノードとして実ノードが求められるまで繰り返し、求められた実ノードの親の実ノードを新たな第２の実ノードとして特定する特定処理を実行し、
前記特定処理により特定された前記新たな第１の実ノードと前記新たな第２の実ノードとが同一の部分木に属する場合には、前記第１の判定手段に前記新たな第１の実ノードと前記新たな第２の実ノードとが先祖と子孫の関係にあるか否かを判定させ、その判定の結果を、前記指定受付手段で受け付けた前記第１の実ノードと前記第２の実ノードとの間に先祖と子孫の関係があるか否かの判定結果とし、
前記特定処理により特定された前記新たな第１の実ノードと前記新たな第２の実ノードとが同一の部分木に属さない場合には、前記新たな第１の実ノードと前記新たな第２の実ノードとを処理対象として前記判定処理を繰り返す、
ことを特徴とする請求項３に記載の木構造処理装置。
【請求項５】
コンピュータを、
実ノード及び参照ノードを含むノード群が構成する１以上の木構造を表す木構造情報と、前記１以上の木構造の各々を分割して得られる各部分木がそれぞれ当該木構造のうちのどのノードを含むかを表す部分木情報と、前記各部分木を参照する各参照ノードを特定する参照関係情報と、を記憶する記憶手段、
前記木構造情報に対するノードの追加により前記部分木情報が表す各部分木のうち第１の参照ノードが参照する第１の部分木のノードの数があらかじめ定めた上限数を超えた場合に、当該第１の部分木から第２の部分木を分割することにより、前記第１の部分木及び前記第２の部分木のノードの数が共に前記上限数以下となるようにし、当該分割に応じて前記記憶手段に記憶された前記部分木情報を更新する分割手段、
前記分割手段による分割に応じて前記第２の部分木を参照する第２の参照ノードを新たに生成し、前記第２の部分木を参照する参照ノードが前記第２の参照ノードであることを示す情報を前記参照関係情報に追加すると共に、前記第２の参照ノードが前記第１の参照ノードが含まれる部分木に含まれることを表す情報を前記部分木情報に追加し、前記第１の参照ノードと前記第２の参照ノードとが前記第１の部分木と前記第２の部分木との親子関係に対応する親子関係を構成することを表す情報を前記木構造情報に追加する、情報追加手段、
として機能させるためのプログラム。
【請求項６】
コンピュータを、
実ノード及び参照ノードを含むノード群が構成する１以上の木構造を表す木構造情報と、前記１以上の木構造の各々を分割して得られる各部分木がそれぞれ当該木構造のうちのどのノードを含むかを表す部分木情報と、前記各部分木を参照する各参照ノードを特定する参照関係情報と、を記憶する記憶手段、
前記木構造情報に対するノードの追加により前記部分木情報が表す各部分木のうち第１の参照ノードが参照する第１の部分木のノードの数があらかじめ定めた上限数を超えた場合に、当該第１の部分木から第２の部分木を分割することにより、前記第１の部分木及び前記第２の部分木のノードの数が共に前記上限数以下となるようにし、当該分割に応じて前記記憶手段に記憶された前記部分木情報を更新する分割手段、
前記分割手段による分割に応じて前記第２の部分木を参照する第２の参照ノードを新たに生成し、前記第２の部分木を参照する参照ノードが前記第２の参照ノードであることを示す情報を前記参照関係情報に追加すると共に、前記第２の参照ノードが前記第１の部分木に含まれることを表す情報を前記部分木情報に追加し、前記第２の参照ノードが前記第２の部分木の根ノードの親ノードに該当する前記第１の部分木のノードの子であることを示す情報を前記木構造情報に追加する、情報追加手段、
として機能させるためのプログラム。
【請求項１】
実ノード及び参照ノードを含むノード群が構成する１以上の木構造を表す木構造情報と、前記１以上の木構造の各々を分割して得られる各部分木がそれぞれ当該木構造のうちのどのノードを含むかを表す部分木情報と、前記各部分木を参照する各参照ノードを特定する参照関係情報と、を記憶する記憶手段と、
前記木構造情報に対するノードの追加により前記部分木情報が表す各部分木のうち第１の参照ノードが参照する第１の部分木のノードの数があらかじめ定めた上限数を超えた場合に、当該第１の部分木から第２の部分木を分割することにより、前記第１の部分木及び前記第２の部分木のノードの数が共に前記上限数以下となるようにし、当該分割に応じて前記記憶手段に記憶された前記部分木情報を更新する分割手段と、
前記分割手段による分割に応じて前記第２の部分木を参照する第２の参照ノードを新たに生成し、前記第２の部分木を参照する参照ノードが前記第２の参照ノードであることを示す情報を前記参照関係情報に追加すると共に、前記第２の参照ノードが前記第１の参照ノードが含まれる部分木に含まれることを表す情報を前記部分木情報に追加し、前記第１の参照ノードと前記第２の参照ノードとが前記第１の部分木と前記第２の部分木との親子関係に対応する親子関係を構成することを表す情報を前記木構造情報に追加する、情報追加手段と、
を備える木構造処理装置。
【請求項２】
実ノード及び参照ノードを含むノード群が構成する１以上の木構造を表す木構造情報と、前記１以上の木構造の各々を分割して得られる各部分木がそれぞれ当該木構造のうちのどのノードを含むかを表す部分木情報と、前記各部分木を参照する各参照ノードを特定する参照関係情報と、を記憶する記憶手段と、
前記木構造情報に対するノードの追加により前記部分木情報が表す各部分木のうち第１の参照ノードが参照する第１の部分木のノードの数があらかじめ定めた上限数を超えた場合に、当該第１の部分木から第２の部分木を分割することにより、前記第１の部分木及び前記第２の部分木のノードの数が共に前記上限数以下となるようにし、当該分割に応じて前記記憶手段に記憶された前記部分木情報を更新する分割手段と、
前記分割手段による分割に応じて前記第２の部分木を参照する第２の参照ノードを新たに生成し、前記第２の部分木を参照する参照ノードが前記第２の参照ノードであることを示す情報を前記参照関係情報に追加すると共に、前記第２の参照ノードが前記第１の部分木に含まれることを表す情報を前記部分木情報に追加し、前記第２の参照ノードが前記第２の部分木の根ノードの親ノードに該当する前記第１の部分木のノードの子であることを示す情報を前記木構造情報に追加する、情報追加手段と、
を備える木構造処理装置。
【請求項３】
前記木構造情報が表す１以上の木構造のうちのいずれかの木構造の中から、先祖と子孫の関係にあるか否かの判定対象とする第１の実ノードと第２の実ノードとの指定を受け付ける指定受付手段と、
同一の部分木内にある２つのノードについて、当該ノード同士の間に先祖と子孫の関係があるか否かを、前記記憶手段に記憶された部分木情報が表す各ノード間の親子関係をたどることで判定する第１の判定手段と、
前記指定受付手段で受け付けた前記第１の実ノードと前記第２の実ノードとの間に先祖と子孫の関係があるかどうかを判定するための判定処理を行う第２の判定手段と、
を更に備え、
前記第２の判定手段が行う前記判定処理では、ある部分木を参照する参照ノードが含まれる部分木を前記ある部分木の１階層上位の部分木と呼ぶ場合に、前記第１の実ノードが属する部分木の上位に該当する各階層の部分木からなる第１の部分木系列と前記第２の実ノードが属する部分木の上位に該当する各階層の部分木からなる第２の部分木系列とを前記記憶手段に記憶された前記部分木情報及び前記参照関係情報に基づき求め、求めた前記第１の部分木系列と前記第２の部分木系列との間で共通する部分木を特定し、特定した部分木内にノードのうち前記第１の実ノード及び前記第２の実ノードにそれぞれ対応する２つのノードを特定し、特定した２つのノード同士の間に先祖と子孫の関係があるか否かの判定を前記第１の判定手段に実行させ、この判定の結果、前記特定した２つのノード同士の間に先祖と子孫の関係がないと判定された場合に、前記指定受付手段で受け付けた前記第１の実ノードと前記第２の実ノードとの間に先祖と子孫の関係がないと判定する、
ことを特徴とする請求項１又は２に記載の木構造処理装置。
【請求項４】
前記第２の判定手段が行う前記判定処理では、
前記特定した２つのノード同士の間に先祖と子孫の関係があると前記第１の判定手段により判定された場合、前記指定受付手段で受け付けた前記第１の実ノードと前記第２の実ノードの中から、前記特定した２つのノードのうち先祖側のノードに対応するノードを新たな第１の実ノードとして特定し、前記特定した部分木内の前記特定した２つのノード同士を結ぶ経路上のノードのうちの前記先祖側のノードの子に該当する参照ノードが参照する下位の部分木の根ノードを求め、求めた根ノードが参照ノードである場合には更に当該根ノードが参照する下位の部分木の根ノードを求めるという処理を、下位の部分木の根ノードとして実ノードが求められるまで繰り返し、求められた実ノードの親の実ノードを新たな第２の実ノードとして特定する特定処理を実行し、
前記特定処理により特定された前記新たな第１の実ノードと前記新たな第２の実ノードとが同一の部分木に属する場合には、前記第１の判定手段に前記新たな第１の実ノードと前記新たな第２の実ノードとが先祖と子孫の関係にあるか否かを判定させ、その判定の結果を、前記指定受付手段で受け付けた前記第１の実ノードと前記第２の実ノードとの間に先祖と子孫の関係があるか否かの判定結果とし、
前記特定処理により特定された前記新たな第１の実ノードと前記新たな第２の実ノードとが同一の部分木に属さない場合には、前記新たな第１の実ノードと前記新たな第２の実ノードとを処理対象として前記判定処理を繰り返す、
ことを特徴とする請求項３に記載の木構造処理装置。
【請求項５】
コンピュータを、
実ノード及び参照ノードを含むノード群が構成する１以上の木構造を表す木構造情報と、前記１以上の木構造の各々を分割して得られる各部分木がそれぞれ当該木構造のうちのどのノードを含むかを表す部分木情報と、前記各部分木を参照する各参照ノードを特定する参照関係情報と、を記憶する記憶手段、
前記木構造情報に対するノードの追加により前記部分木情報が表す各部分木のうち第１の参照ノードが参照する第１の部分木のノードの数があらかじめ定めた上限数を超えた場合に、当該第１の部分木から第２の部分木を分割することにより、前記第１の部分木及び前記第２の部分木のノードの数が共に前記上限数以下となるようにし、当該分割に応じて前記記憶手段に記憶された前記部分木情報を更新する分割手段、
前記分割手段による分割に応じて前記第２の部分木を参照する第２の参照ノードを新たに生成し、前記第２の部分木を参照する参照ノードが前記第２の参照ノードであることを示す情報を前記参照関係情報に追加すると共に、前記第２の参照ノードが前記第１の参照ノードが含まれる部分木に含まれることを表す情報を前記部分木情報に追加し、前記第１の参照ノードと前記第２の参照ノードとが前記第１の部分木と前記第２の部分木との親子関係に対応する親子関係を構成することを表す情報を前記木構造情報に追加する、情報追加手段、
として機能させるためのプログラム。
【請求項６】
コンピュータを、
実ノード及び参照ノードを含むノード群が構成する１以上の木構造を表す木構造情報と、前記１以上の木構造の各々を分割して得られる各部分木がそれぞれ当該木構造のうちのどのノードを含むかを表す部分木情報と、前記各部分木を参照する各参照ノードを特定する参照関係情報と、を記憶する記憶手段、
前記木構造情報に対するノードの追加により前記部分木情報が表す各部分木のうち第１の参照ノードが参照する第１の部分木のノードの数があらかじめ定めた上限数を超えた場合に、当該第１の部分木から第２の部分木を分割することにより、前記第１の部分木及び前記第２の部分木のノードの数が共に前記上限数以下となるようにし、当該分割に応じて前記記憶手段に記憶された前記部分木情報を更新する分割手段、
前記分割手段による分割に応じて前記第２の部分木を参照する第２の参照ノードを新たに生成し、前記第２の部分木を参照する参照ノードが前記第２の参照ノードであることを示す情報を前記参照関係情報に追加すると共に、前記第２の参照ノードが前記第１の部分木に含まれることを表す情報を前記部分木情報に追加し、前記第２の参照ノードが前記第２の部分木の根ノードの親ノードに該当する前記第１の部分木のノードの子であることを示す情報を前記木構造情報に追加する、情報追加手段、
として機能させるためのプログラム。
【図１】
【図２】
【図３Ａ】
【図３Ｂ】
【図４Ａ】
【図４Ｂ】
【図４Ｃ】
【図５Ａ】
【図５Ｂ】
【図６】
【図７】
【図８】
【図９Ａ】
【図９Ｂ】
【図９Ｃ】
【図１０Ａ】
【図１０Ｂ】
【図１０Ｃ】
【図２】
【図３Ａ】
【図３Ｂ】
【図４Ａ】
【図４Ｂ】
【図４Ｃ】
【図５Ａ】
【図５Ｂ】
【図６】
【図７】
【図８】
【図９Ａ】
【図９Ｂ】
【図９Ｃ】
【図１０Ａ】
【図１０Ｂ】
【図１０Ｃ】
【公開番号】特開２０１１−１０７８１９（Ｐ２０１１−１０７８１９Ａ）
【公開日】平成２３年６月２日（２０１１．６．２）
【国際特許分類】
【出願番号】特願２００９−２５９８０２（Ｐ２００９−２５９８０２）
【出願日】平成２１年１１月１３日（２００９．１１．１３）
【出願人】（０００００５４９６）富士ゼロックス株式会社 (21,908)
【Ｆターム（参考）】
【公開日】平成２３年６月２日（２０１１．６．２）
【国際特許分類】
【出願日】平成２１年１１月１３日（２００９．１１．１３）
【出願人】（０００００５４９６）富士ゼロックス株式会社 (21,908)
【Ｆターム（参考）】
[ Back to top ]