(57)【特許請求の範囲】
【請求項１】
データ構造を表わす有向木のノードを一意に識別可能に識別番号を付与する識別番号付与装置であって、
前記有向木をすべてのノードが含まれるように、上位の部分木が下位の部分木の根を含んで分割して部分木を生成し、前記生成された部分木の中から一の部分木を識別可能な大域番号を、前記生成された部分木毎に、当該部分木の下位の部分木の根であるノード以外の当該部分木に含まれるすべてのノードに付与する大域分割手段と、
前記部分木毎に、当該部分木に含まれるノードの中から一のノードを識別可能な局所番号を、当該部分木に含まれるすべてのノードに付与する局所番号付与手段と、
前記ノード毎に、当該ノードの大域番号と、当該ノードの局所番号とを含む前記識別番号を付与する識別番号付与手段とを備え、
前記大域分割手段は、前記有向木のノードの中から前記有向木の根を含む２つ以上のノードを選択して核ノードとする核ノード選択手段と、
前記核ノードの中から一の核ノードを識別可能な大域番号を前記すべての核ノードに付与する大域番号付与手段と、
前記核ノード毎に、当該核ノードから見て深い階層に他の核ノードがない場合には、当該核ノードを根として当該核ノードから見て深い階層にあるすべてのノードからなる部分木を生成して当該部分木のすべてのノードに当該核ノードの前記大域番号を付与し、当該核ノードから見て深い階層に他の核ノードがある場合には、当該核ノードから見て深い階層にあり他の核ノードを経由せずになぞることができるすべてのノードと当該核ノードから見て深い階層にある最初の他の核ノードとからなる部分木を生成して当該部分木に含まれる核ノード以外のノードに当該核ノードの前記大域番号を付与する部分木生成手段とを備え、
前記大域分割手段は、前記核ノードと前記核ノードから見て深い階層にある最初の前記核ノードとを枝で接続して核木を生成すると共に、前記核木に含まれる核ノードの出次数の最大値である核木出次最大値を算出する核木生成手段をさらに備え、
前記大域番号付与手段は、前記核木出次最大値を出次数としてＵＩＤを用いて前記核木のすべての核ノードに前記大域番号を付与するものであり、
前記大域分割手段は、前記部分木毎に、当該部分木に含まれるノードの出次数の最大値である部分木出次最大値を算出する部分木最大出次数算出手段をさらに備え、
前記局所番号付与手段は、前記部分木毎に、当該部分木の部分木出次最大値を出次数として、ＵＩＤを用いて前記局所番号を算出し、当該部分木の根である核ノード以外のノードには前記算出した局所番号を付与し、前記有向木の根以外の当該部分木の根である核ノードには、当該部分木の根である核ノードが属する上位の部分木で前記算出した局所番号を付与し、前記有向木の根である核ノードには、当該核ノードが属する部分木の前記局所番号を付与するものであり、
前記識別番号付与手段は、前記有向木のノード毎に、当該ノードの大域番号と、当該ノードの局所番号と、当該ノードが核ノードであるか否かを示すノード種別情報とを含む前記識別番号を付与することを特徴とする識別番号付与装置。
【請求項２】
前記識別番号付与手段は、前記識別番号に前記識別番号で識別されるノードの親を示す情報を含んで、前記ノード毎に前記識別番号を付与するものであり、
前記ノードの識別番号から当該ノードの親を示す前記識別番号を算出する親識別番号算出手段をさらに備えることを特徴とする請求項１記載の識別番号付与装置。
【請求項３】
前記核ノード選択手段は、前記有向木のノードの中から当該ノードは所定の数以上の数の子孫を持ち、かつ当該ノードのすべての子について、当該ノードの子が持っている子孫の数は前記所定の数未満である条件を満足するノードをすべて選択する特定ノード選択手段と、
前記選択されたすべてのノードの子孫を前記有向木からすべて削除した新たな有向木を生成する特定有向木生成手段と、
前記新たな有向木が前記有向木の根のみになるまで、前記新たな有向木を前記有向木として、前記特定ノード選択手段に前記条件を満足するノードをさらに選択させ、さらに前記特定有向木生成手段に新たな有向木を生成させると共に、前記新たな有向木が前記有向木の根のみになった場合に、前記選択されたすべてのノードを核ノードとする核ノード選択制御手段とを備えることを特徴とする請求項１又は２記載の識別番号付与装置。
【請求項４】
前記有向木に関連付けた前記核木出次最大値と、前記核ノード毎に、当該核ノードの前記大域番号、当該核ノードの前記局所番号及び当該核ノードが根である部分木の前記部分木出次最大値を関連付けた情報とを含む核木情報を記憶する核木情報記憶手段をさらに備え、
前記親識別番号算出手段は、前記有向木の根以外のノードであって、前記識別番号が付与された一のノードについて、
当該ノードの前記ノード種別情報が核ノードであることを示す情報である場合には、当該ノードの大域番号から２を減算し、当該減算した値を前記核木出次最大値で除算し、当該除算した値に１を加算し、さらに当該加算した値の小数点以下を切り捨てた第一の番号を、当該ノードの親を示す前記大域番号とし、当該ノードの前記ノード種別情報が核ノードではないことを示す情報である場合には、当該ノードの前記大域番号を、当該ノードの親を示す前記大域番号とする親大域番号算出手段と、
当該ノードの局所番号から２を減算し、当該減算した値を前記部分木出次最大値で除算し、当該除算した値に１を加算し、当該加算した値の小数点以下を切り捨てた第二の番号が１ではない場合には、前記第二の番号を当該ノードの親を示す前記局所番号にすると共に、当該ノードの親のノード種別情報を核ノードではないことを示す情報とし、前記第二の番号が１である場合には、前記記憶した核木情報によって当該ノードの前記大域番号と関連付けられた前記局所番号を当該ノードの親を示す前記局所番号にすると共に、当該ノードの親のノード種別情報を核ノードであることを示す情報とする親局所番号算出手段とを有することを特徴とする請求項１〜３のいずれか１項に記載の識別番号付与装置。
【請求項５】
前記大域番号が付与された前記部分木を基に、前記部分木を分割した新たな部分木を再帰部分木とし、前記大域番号を前記再帰部分木の再帰大域番号とし、前記再帰部分木の前記大域番号を新たに生成し、前記再帰大域番号と前記新たな大域番号とを前記再帰部分木のノードに付与する再帰大域番号付与手段と、
前記再帰部分木のノードに対して前記局所番号を生成し、前記再帰大域番号と、前記新たな大域番号と、前記局所番号とを含む識別番号を付与する再帰的識別制御手段とをさらに備えることを特徴とする請求項１〜４のいずれか１項に記載の識別番号付与装置。
【請求項６】
データ構造を表わす有向木のノードを一意に識別可能に識別番号を付与する識別番号付与方法であって、
大域分割手段が、前記有向木をすべてのノードが含まれるように、上位の部分木が下位の部分木の根を含んで分割して部分木を生成し、前記生成された部分木の中から一の部分木を識別可能な大域番号を、前記生成された部分木毎に、当該部分木の下位の部分木の根であるノード以外の当該部分木に含まれるすべてのノードに付与するステップと、
局所番号付与手段が、前記部分木毎に、当該部分木に含まれるノードの中から一のノードを識別可能な局所番号を、当該部分木に含まれるすべてのノードに付与するステップと、
識別番号付与手段が、前記ノード毎に、当該ノードの大域番号と当該ノードの局所番号とを含む前記識別番号を付与するステップとから構成され、
前記大域分割手段は、
核ノード選択手段が、前記有向木のノードの中から前記有向木の根を含む２つ以上のノードを選択して核ノードとするステップと、
大域番号付与手段が、前記核ノードの中から一の核ノードを識別可能な大域番号を前記すべての核ノードに付与するステップと、
部分木生成手段が、前記核ノード毎に、当該核ノードから見て深い階層に他の核ノードがない場合には、当該核ノードを根として当該核ノードから見て深い階層にあるすべてのノードからなる部分木を生成して当該部分木のすべてのノードに当該核ノードの前記大域番号を付与し、当該核ノードから見て深い階層に他の核ノードがある場合には、当該核ノードから見て深い階層にあり他の核ノードを経由せずになぞることができるすべてのノードと当該核ノードから見て深い階層にある最初の他の核ノードとからなる部分木を生成して当該部分木に含まれる核ノード以外のノードに当該核ノードの前記大域番号を付与するステップとから構成され、
前記大域分割手段は、核木生成手段が、前記核ノードと前記核ノードから見て深い階層にある最初の前記核ノードとを枝で接続して核木を生成すると共に、前記核木に含まれる核ノードの出次数の最大値である核木出次最大値を算出するステップをさらに含み、
前記大域番号付与手段は、前記核木出次最大値を出次数としてＵＩＤを用いて前記核木のすべての核ノードに前記大域番号を付与するステップを含み、
前記大域分割手段は、部分木最大出次数算出手段が、前記部分木毎に、当該部分木に含まれるノードの出次数の最大値である部分木出次最大値を算出するステップをさらに含み、
前記局所番号付与手段が、前記部分木毎に、当該部分木の部分木出次最大値を出次数として、ＵＩＤを用いて前記局所番号を算出し、当該部分木の根である核ノード以外のノードには前記算出した局所番号を付与し、前記有向木の根以外の当該部分木の根である核ノードには、当該部分木の根である核ノードが属する上位の部分木で前記算出した局所番号を付与し、前記有向木の根である核ノードには、当該核ノードが属する部分木の前記局所番号を付与するステップを含み、
前記識別番号付与手段が、前記有向木のノード毎に、当該ノードの大域番号と、当該ノードの局所番号と、当該ノードが核ノードであるか否かを示すノード種別情報とを含む前記識別番号を付与するステップを含むこと
を特徴とする識別番号付与方法。
【請求項７】
データ構造を表わす有向木のノードを一意に識別可能に識別番号を付与する識別番号付与プログラムであって、
前記有向木をすべてのノードが含まれるように、上位の部分木が下位の部分木の根を含んで分割して部分木を生成し、前記生成された部分木の中から一の部分木を識別可能な大域番号を、前記生成された部分木毎に、当該部分木の下位の部分木の根であるノード以外の当該部分木に含まれるすべてのノードに付与する大域分割手段、
前記部分木毎に、当該部分木に含まれるノードの中から一のノードを識別可能な局所番号を、当該部分木に含まれるすべてのノードに付与する局所番号付与手段、
前記ノード毎に、当該ノードの大域番号と当該ノードの局所番号とを含む前記識別番号を付与する識別番号付与手段としてコンピュータを機能させ、
前記大域分割手段は、
前記有向木のノードの中から前記有向木の根を含む２つ以上のノードを選択して核ノードとする核ノード選択手段、
前記核ノードの中から一の核ノードを識別可能な大域番号を前記すべての核ノードに付与する大域番号付与手段、
前記核ノード毎に、当該核ノードから見て深い階層に他の核ノードがない場合には、当該核ノードを根として当該核ノードから見て深い階層にあるすべてのノードからなる部分木を生成して当該部分木のすべてのノードに当該核ノードの前記大域番号を付与し、当該核ノードから見て深い階層に他の核ノードがある場合には、当該核ノードから見て深い階層にあり他の核ノードを経由せずになぞることができるすべてのノードと当該核ノードから見て深い階層にある最初の他の核ノードとからなる部分木を生成して当該部分木に含まれる核ノード以外のノードに当該核ノードの前記大域番号を付与する部分木生成手段としてコンピュータを機能させ、
前記大域分割手段は、前記核ノードと前記核ノードから見て深い階層にある最初の前記核ノードとを枝で接続して核木を生成すると共に、前記核木に含まれる核ノードの出次数の最大値である核木出次最大値を算出する核木生成手段としてさらにコンピュータを機能させ、
前記大域番号付与手段は、前記核木出次最大値を出次数としてＵＩＤを用いて前記核木のすべての核ノードに前記大域番号を付与するようにコンピュータを機能させ、
前記大域分割手段は、前記部分木毎に、当該部分木に含まれるノードの出次数の最大値である部分木出次最大値を算出する部分木最大出次数算出手段としてさらにコンピュータを機能させ、
前記局所番号付与手段は、前記部分木毎に、当該部分木の部分木出次最大値を出次数として、ＵＩＤを用いて前記局所番号を算出し、当該部分木の根である核ノード以外のノードには前記算出した局所番号を付与し、前記有向木の根以外の当該部分木の根である核ノードには、当該部分木の根である核ノードが属する上位の部分木で前記算出した局所番号を付与し、前記有向木の根である核ノードには、当該核ノードが属する部分木の前記局所番号を付与するようにコンピュータを機能させ、
前記識別番号付与手段は、前記有向木のノード毎に、当該ノードの大域番号と、当該ノードの局所番号と、当該ノードが核ノードであるか否かを示すノード種別情報とを含む前記識別番号を付与するようにコンピュータを機能させることを特徴とする識別番号付与プログラム。
【請求項８】
データ構造を表わす有向木のノードを一意に識別可能に識別番号を付与する識別番号付与プログラムを記録したコンピュータ読み取り可能な記録媒体であって、
前記有向木をすべてのノードが含まれるように、上位の部分木が下位の部分木の根を含んで分割して部分木を生成し、前記生成された部分木の中から一の部分木を識別可能な大域番号を、前記生成された部分木毎に、当該部分木の下位の部分木の根であるノード以外の当該部分木に含まれるすべてのノードに付与する大域分割手段、
前記部分木毎に、当該部分木に含まれるノードの中から一のノードを識別可能な局所番号を、当該部分木に含まれるすべてのノードに付与する局所番号付与手段、
前記ノード毎に、当該ノードの大域番号と当該ノードの局所番号とを含む前記識別番号を付与する識別番号付与手段としてコンピュータを機能させ、
前記大域分割手段は、
前記有向木のノードの中から前記有向木の根を含む２つ以上のノードを選択して核ノードとする核ノード選択手段、
前記核ノードの中から一の核ノードを識別可能な大域番号を前記すべての核ノードに付与する大域番号付与手段、
前記核ノード毎に、当該核ノードから見て深い階層に他の核ノードがない場合には、当該核ノードを根として当該核ノードから見て深い階層にあるすべてのノードからなる部分木を生成して当該部分木のすべてのノードに当該核ノードの前記大域番号を付与し、当該核ノードから見て深い階層に他の核ノードがある場合には、当該核ノードから見て深い階層にあり他の核ノードを経由せずになぞることができるすべてのノードと当該核ノードから見て深い階層にある最初の他の核ノードとからなる部分木を生成して当該部分木に含まれる核ノード以外のノードに当該核ノードの前記大域番号を付与する部分木生成手段としてコンピュータを機能させ、
前記大域分割手段は、前記核ノードと前記核ノードから見て深い階層にある最初の前記核ノードとを枝で接続して核木を生成すると共に、前記核木に含まれる核ノードの出次数の最大値である核木出次最大値を算出する核木生成手段としてさらにコンピュータを機能させ、
前記大域番号付与手段は、前記核木出次最大値を出次数としてＵＩＤを用いて前記核木のすべての核ノードに前記大域番号を付与するようにコンピュータを機能させ、
前記大域分割手段は、前記部分木毎に、当該部分木に含まれるノードの出次数の最大値である部分木出次最大値を算出する部分木最大出次数算出手段としてさらにコンピュータを機能させ、
前記局所番号付与手段は、前記部分木毎に、当該部分木の部分木出次最大値を出次数として、ＵＩＤを用いて前記局所番号を算出し、当該部分木の根である核ノード以外のノードには前記算出した局所番号を付与し、前記有向木の根以外の当該部分木の根である核ノードには、当該部分木の根である核ノードが属する上位の部分木で前記算出した局所番号を付与し、前記有向木の根である核ノードには、当該核ノードが属する部分木の前記局所番号を付与するようにコンピュータを機能させ、
前記識別番号付与手段は、前記有向木のノード毎に、当該ノードの大域番号と、当該ノードの局所番号と、当該ノードが核ノードであるか否かを示すノード種別情報とを含む前記識別番号を付与するようにコンピュータを機能させることを特徴とする識別番号付与プログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、データ構造を表わす有向木のノードを一意に識別可能に識別番号を付与する識別番号付与装置、識別番号管理方法、識別番号管理プログラム及び同プログラムを記録したコンピュータ読み取り可能な記録媒体に関するものである。
【０００２】
【従来の技術】
従来、データ構造を表わす有向木のノードに一意に識別が可能な識別番号を付与する方法として、ＵＩＤ（unique  element  identifier）が知られている。ＵＩＤでは、対象となる木に含まれるノードの出次数の最大値を基に、まず木の根からの距離でノードを列挙し、距離が等しいもの同士は長兄から列挙し、出次数が前記出次数の最大値に満たない場合であっても前記出次数の最大値の数だけ子が存在すると仮定して、前記列挙した順に番号を付与する（図２２参照）。ＵＩＤによって識別番号を付与した場合、その識別番号にノードの親子関係を示す情報が含まれるため、ノードの識別番号から親ノードの識別番号を算出可能になり、効率よくデータを検索することができる。
【０００３】
【発明が解決しようとする課題】
しかしながら、ＵＩＤを用いた識別番号は、実際には存在しないノードにも番号を付与するため、識別番号が非常に大きな数字となる。そのため、ＵＩＤを用いた識別番号を大規模な木構造に適用した場合には、その識別番号が一般的なコンピュータで整数表現できる上限の値を超えてしまい、処理できなくなる問題が発生する。
【０００４】
例えば、木構造を持ったデータとして、汎用のデータ交換フォーマットであるＸＭＬ（extensible markup language）が注目されている。ＸＭＬで記述されたデータや文書は、有向木で表現することが可能である。図２３はＸＭＬ文書の一例で、図２３のＸＭＬ文書を有向木で表現すると、図２４に記載の有向木となる。しかし、ＸＭＬで記述されたテキスト文書は出次数が大きくなる傾向があるため、比較的小さな文書でも、ＵＩＤを用いた識別番号を適用することが出来ない。一方で、ノードの親子関係を示す情報が含まれる識別番号をＸＭＬで記述されたデータや文書に適用し、データや文書の検索効率を向上させることが、近年ＸＭＬの普及に伴いますます望まれている。
【０００５】
本発明の目的は、木構造データのノードに対して、より小さな数値の範囲で一意に識別が可能な識別番号を付与する識別番号付与装置、識別番号管理方法、識別番号管理プログラム及び同プログラムを記録したコンピュータ読み取り可能な記録媒体を提供することである。
【０００６】
【課題を解決するための手段】
請求項１記載の発明は、データ構造を表わす有向木のノードを一意に識別可能に識別番号を付与する識別番号付与装置であって、前記有向木をすべてのノードが含まれるように、上位の部分木が下位の部分木の根を含んで分割して部分木を生成し、前記生成された部分木の中から一の部分木を識別可能な大域番号を、前記生成された部分木毎に、当該部分木の下位の部分木の根であるノード以外の当該部分木に含まれるすべてのノードに付与する大域分割手段と、前記部分木毎に、当該部分木に含まれるノードの中から一のノードを識別可能な局所番号を、当該部分木に含まれるすべてのノードに付与する局所番号付与手段と、前記ノード毎に、当該ノードの大域番号と、当該ノードの局所番号とを含む前記識別番号を付与する識別番号付与手段とを備え、前記大域分割手段は、前記有向木のノードの中から前記有向木の根を含む２つ以上のノードを選択して核ノードとする核ノード選択手段と、前記核ノードの中から一の核ノードを識別可能な大域番号を前記すべての核ノードに付与する大域番号付与手段と、前記核ノード毎に、当該核ノードから見て深い階層に他の核ノードがない場合には、当該核ノードを根として当該核ノードから見て深い階層にあるすべてのノードからなる部分木を生成して当該部分木のすべてのノードに当該核ノードの前記大域番号を付与し、当該核ノードから見て深い階層に他の核ノードがある場合には、当該核ノードから見て深い階層にあり他の核ノードを経由せずになぞることができるすべてのノードと当該核ノードから見て深い階層にある最初の他の核ノードとからなる部分木を生成して当該部分木に含まれる核ノード以外のノードに当該核ノードの前記大域番号を付与する部分木生成手段とを備え、前記大域分割手段は、前記核ノードと前記核ノードから見て深い階層にある最初の前記核ノードとを枝で接続して核木を生成すると共に、前記核木に含まれる核ノードの出次数の最大値である核木出次最大値を算出する核木生成手段をさらに備え、前記大域番号付与手段は、前記核木出次最大値を出次数としてＵＩＤを用いて前記核木のすべての核ノードに前記大域番号を付与するものであり、前記大域分割手段は、前記部分木毎に、当該部分木に含まれるノードの出次数の最大値である部分木出次最大値を算出する部分木最大出次数算出手段をさらに備え、前記局所番号付与手段は、前記部分木毎に、当該部分木の部分木出次最大値を出次数として、ＵＩＤを用いて前記局所番号を算出し、当該部分木の根である核ノード以外のノードには前記算出した局所番号を付与し、前記有向木の根以外の当該部分木の根である核ノードには、当該部分木の根である核ノードが属する上位の部分木で前記算出した局所番号を付与し、前記有向木の根である核ノードには、当該核ノードが属する部分木の前記局所番号を付与するものであり、前記識別番号付与手段は、前記有向木のノード毎に、当該ノードの大域番号と、当該ノードの局所番号と、当該ノードが核ノードであるか否かを示すノード種別情報とを含む前記識別番号を付与することを特徴としている。
【０００７】
請求項１記載の発明によれば、前記有向木のすべてのノードが含まれ、上位の部分木が下位の部分木の根を含むように分割されて部分木が生成され、前記分割されて生成された部分木の中から一の部分木を識別可能な前記大域番号が、当該部分木の下位の部分木の根を除く当該部分木に含まれるすべてのノードに対して、前記大域分割手段によって付与される。
【０００８】
また、前記局所番号付与手段によって前記部分木に含まれるノードの中から一のノードを識別可能な前記局所番号が、前記部分木毎に、当該部分木に含まれるすべてのノードに付与される。
【０００９】
また、前記識別番号付与手段によって、前記有向木のノード毎に、当該ノードの大域番号と、当該ノードの局所番号とを含み、前記有向木のノードを一意に識別可能な前記識別番号が付与される。この場合、前記有向木のノードを一意に識別することが可能になる。また、前記大域番号及び前記局所番号をより小さな数字で表わすことが可能になり、一般的なコンピュータで整数表現することがより容易になる。
【００１０】
また、前記有向木のノードの中から前記有向木の根を含む２つ以上のノードが、核ノード選択手段によって核ノードとして選択され、前記核ノードの中から一の核ノードを識別可能な大域番号が、前記大域番号付与手段によって前記すべての核ノードに付与され、前記核ノード毎に、当該核ノードを根とし、当該核ノードから見て深い階層に他の核ノードがない場合には、部分木生成手段によって、当該核ノードから見て深い階層にあるすべてのノードからなる部分木が生成され、当該部分木のすべてのノードに、当該部分木の根である核ノードの前記大域番号が付与される。
【００１１】
また、当該核ノードから見て深い階層に他の核ノードがある場合には、当該核ノードから見て深い階層にあり他の核ノードを経由せずになぞることができるすべてのノードと、当該核ノードから見て深い階層にある最初の他の核ノードとからなる部分木が、前記部分木生成手段によって生成され、前記生成された部分木に含まれる核ノード以外のノードに当該部分木の根である核ノードの前記大域番号が、前記部分木生成手段によって付与される。
【００１２】
また、前記大域分割手段は、前記核ノード選択手段と、前記大域番号付与手段と、前記部分木生成手段とを備えるので、前記有向木を前記部分木に分割し、前記部分木のすべてのノードに、前記大域番号を付与することが可能になる。
【００１３】
また、前記核木生成手段によって、前記核ノードと前記核ノードから見て深い階層にある最初の前記核ノードとが枝で接続されて核木が生成されると共に、前記核木に含まれる核ノードの出次数の最大値である核木出次最大値が算出される。また、前記大域番号付与手段によって、前記核木出次最大値を出次数としてＵＩＤを用いて前記核木のすべての核ノードに前記大域番号が付与される。また、前記部分木最大出次数算出手段によって、前記部分木毎に、当該部分木に含まれるノードの出次数の最大値である部分木出次最大値が算出される。
【００１４】
この場合、前記大域分割手段は、前記核木生成手段、前記大域番号付与手段及び前記部分木最大出次数算出手段を備えるので、ＵＩＤを用いて前記大域番号が付与されると共に、前記部分木出次最大値が算出される。
【００１５】
また、前記局所番号付与手段によって、前記部分木毎に、当該部分木の部分木出次最大値を出次数として、ＵＩＤを用いて前記局所番号が算出され、当該部分木の根である核ノード以外のノードには前記算出された局所番号が付与され、前記有向木の根以外の当該部分木の根である核ノードには、当該部分木の根である核ノードが属する上位の部分木で前記算出された局所番号が付与され、前記有向木の根である核ノードには、当該核ノードが属する部分木の前記局所番号が付与されるので、前記局所番号として、ＵＩＤを用いて算出された番号が付与される。
【００１６】
また、前記識別番号付与手段によって、前記有向木のノード毎に、当該ノードの大域番号と、当該ノードの局所番号と、当該ノードが核ノードであるか否かを示すノード種別情報とを含む前記識別番号が付与されるので、前記有向木のノードを一意に識別することが可能になる。この場合、前記大域番号と局所番号をより小さな数字で表わすことが可能になり、一般的なコンピュータで整数表現することがより容易になる。
【００１７】
請求項２記載の発明は、請求項１記載の識別番号付与装置において、前記識別番号付与手段は、前記識別番号に前記識別番号で識別されるノードの親を示す情報を含んで、前記ノード毎に前記識別番号を付与するものであり、前記ノードの識別番号から当該ノードの親を示す前記識別番号を算出する親識別番号算出手段をさらに備えることを特徴としている。
【００１８】
請求項２記載の発明によれば、前記識別番号付与手段によって、前記識別番号は、前記識別番号で識別されるノードの親を示す情報を含んで前記ノード毎に前記識別番号を付与され、前記親識別番号算出手段によって、前記ノードの識別番号から当該ノードの親を示す前記識別番号が算出される。例えば、前記識別番号を付与された木構造データの検索を行うときに、前記識別番号で識別されたノードの親を当該ノードの識別番号から算出可能になるので、当該ノードの親を検索する処理を効率よく行うことが可能になる。
【００１９】
請求項３記載の発明は、請求項１又は２記載の識別番号付与装置において、前記核ノード選択手段は、前記有向木のノードの中から当該ノードは所定の数以上の数の子孫を持ち、かつ当該ノードのすべての子について、当該ノードの子が持っている子孫の数は前記所定の数未満である条件を満足するノードをすべて選択する特定ノード選択手段と、前記選択されたすべてのノードの子孫を前記有向木からすべて削除した新たな有向木を生成する特定有向木生成手段と、前記新たな有向木が前記有向木の根のみになるまで、前記新たな有向木を前記有向木として、前記特定ノード選択手段に前記条件を満足するノードをさらに選択させ、さらに前記特定有向木生成手段に新たな有向木を生成させると共に、前記新たな有向木が前記有向木の根のみになった場合に、前記選択されたすべてのノードを核ノードとする核ノード選択制御手段とを備えることを特徴としている。
【００２０】
請求項３記載の発明によれば、前記有向木のノードの中から当該ノードは所定の数以上の数の子孫を持ち、かつ当該ノードのすべての子について、当該ノードの子が持っている子孫の数は前記所定の数未満である条件を満足するすべてのノードが、前記核ノードとして特定ノード選択手段によって選択され、前記選択されたすべてのノードの子孫がすべて削除された新たな有向木が特定有向木生成手段によって生成される。
【００２１】
また、前記特定ノード選択手段は、核ノード選択制御手段の制御に従い、前記新たな有向木が前記有向木の根のみになるまで、前記新たな有向木を前記有向木として、前記条件を満足するノードをさらに選択し、特定有向木生成手段は、前記核ノード選択制御手段の制御に従い、さらに新たな有向木を生成し、前記核ノード選択制御手段は、前記新たな有向木が前記有向木の根のみになった場合に、前記選択されたすべてのノードを核ノードとする。
【００２２】
また、前記核ノード選択手段は、前記特定ノード選択手段と、前記特定有向木生成手段と、前記核ノード選択制御手段とを備えているので、例えばユーザー等の操作等によって入力された所定の数に応じて核ノードが選択される。
【００２３】
請求項４記載の発明は、請求項１〜３のいずれか１項に記載の識別番号付与装置において、前記有向木に関連付けた前記核木出次最大値と、前記核ノード毎に、当該核ノードの前記大域番号、当該核ノードの前記局所番号及び当該核ノードが根である部分木の前記部分木出次最大値を関連付けた情報とを含む核木情報を記憶する核木情報記憶手段をさらに備え、前記親識別番号算出手段は、前記有向木の根以外のノードであって、前記識別番号が付与された一のノードについて、当該ノードの前記ノード種別情報が核ノードであることを示す情報である場合には、当該ノードの大域番号から２を減算し、当該減算した値を前記核木出次最大値で除算し、当該除算した値に１を加算し、さらに当該加算した値の小数点以下を切り捨てた第一の番号を、当該ノードの親を示す前記大域番号とし、当該ノードの前記ノード種別情報が核ノードではないことを示す情報である場合には、当該ノードの前記大域番号を、当該ノードの親を示す前記大域番号とする親大域番号算出手段と、当該ノードの局所番号から２を減算し、当該減算した値を前記部分木出次最大値で除算し、当該除算した値に１を加算し、当該加算した値の小数点以下を切り捨てた第二の番号が１ではない場合には、前記第二の番号を当該ノードの親を示す前記局所番号にすると共に、当該ノードの親のノード種別情報を核ノードではないことを示す情報とし、前記第二の番号が１である場合には、前記記憶した核木情報によって当該ノードの前記大域番号と関連付けられた前記局所番号を当該ノードの親を示す前記局所番号にすると共に、当該ノードの親のノード種別情報を核ノードであることを示す情報とする親局所番号算出手段とを有することを特徴としている。
【００２４】
請求項４記載の発明によれば、前記有向木に関連付けられた前記核木出次最大値と、前記核ノードについて、当該核ノードの前記大域番号、当該核ノードの前記局所番号及び当該核ノードが根である部分木の前記部分木出次最大値が関連付けられた情報とを含む核木情報が、核木情報記憶手段によって、記憶される。
【００２５】
また、前記親大域番号算出手段によって、前記有向木の根以外のノードであって、前記識別番号が付与された一のノードについて、当該ノードの前記ノード種別情報が核ノードであることを示す情報である場合には、当該ノードの大域番号から２を減算し、当該減算した値を前記核木出次最大値で除算し、当該除算した値に１を加算し、さらに当該加算した値の小数点以下を切り捨てた第一の番号が、当該ノードの親を示す前記大域番号とされ、当該ノードの前記ノード種別情報が核ノードではないことを示す情報である場合には、当該ノードの大域番号が、当該ノードの親を示す前記大域番号とされる。
【００２６】
また、前記親局所番号算出手段によって、前記有向木の根以外のノードであって、前記識別番号が付与された一のノードについて、当該ノードの局所番号から２を減算し、当該減算した値を前記部分木出次最大値で除算し、当該除算した値に１を加算し、当該加算した値の小数点以下を切り捨てた第二の番号が１ではない場合には、前記第二の番号が当該ノードの親を示す前記局所番号とされると共に、当該ノードの親を示すノード種別情報が核ノードではないことを示す情報とされ、前記第二の番号が１である場合には、前記記憶した核木情報によって当該ノードの大域番号と関連付けられた前記局所番号が当該ノードの親を示す前記局所番号であるとされると共に、当該ノードの親を示すノード種別情報が核ノードであることを示す情報とされる。
【００２７】
また、前記親識別番号算出手段は、前記親大域番号算出手段と前記親局所番号算出手段とを備えるので、前記ノードのＵＩＤを用いて算出された前記大域番号と前記局所番号及び前記ノード種別情報とからなる前記識別番号からＵＩＤを用いて算出された当該ノードの親を示す前記大域番号と前記局所番号、及び前記ノード種別情報とを含んだ前記識別番号を算出可能になる。例えば、前記ＵＩＤを用いて算出された前記大域番号と前記局所番号、及び前記ノード種別情報とを含んだ識別番号を付与された木構造データの検索を行う時に、当該ノードの親を当該ノードの識別番号から算出可能になるので、当該ノードの親を検索する処理を効率よく行うことが可能になる。
【００２８】
請求項５記載の発明は、請求項１〜４のいずれか１項に記載の識別番号付与装置において、前記大域番号が付与された前記部分木を基に、前記部分木を分割した新たな部分木を再帰部分木とし、前記大域番号を前記再帰部分木の再帰大域番号とし、前記再帰部分木の前記大域番号を新たに生成し、前記再帰大域番号と前記新たな大域番号とを前記再帰部分木のノードに付与する再帰大域番号付与手段と、前記再帰部分木のノードに対して前記局所番号を生成し、前記再帰大域番号と、前記新たな大域番号と、前記局所番号とを含む識別番号を付与する再帰的識別制御手段とをさらに備えることを特徴としている。
【００２９】
請求項５記載の発明によれば、前記大域番号が付与された前記部分木を基に、
再帰大域番号付与手段によって、前記部分木が分割されて新たな部分木が再帰部分木とされ、前記大域番号が前記再帰部分木の再帰大域番号とされ、前記再帰部分木の前記大域番号が新たに生成され、前記再帰大域番号と前記新たな大域番号とが前記再帰部分木のノードに付与される。
【００３０】
また、再帰的識別制御手段によって、前記再帰部分木のノードに対して前記局所番号が生成され、前記再帰大域番号と、前記新たな大域番号と、前記局所番号とを含む識別番号が、前記再帰部分木のノードに付与される。この場合、前記大域番号が付与された前記部分木は、さらに分割され、大域番号を再帰的に生成した再帰大域番号が付与されるので、前記識別番号をより小さな数字で表わすことが可能になる。
【００３１】
請求項６記載の発明は、データ構造を表わす有向木のノードを一意に識別可能に識別番号を付与する識別番号付与方法であって、大域分割手段が、前記有向木をすべてのノードが含まれるように、上位の部分木が下位の部分木の根を含んで分割して部分木を生成し、前記生成された部分木の中から一の部分木を識別可能な大域番号を、前記生成された部分木毎に、当該部分木の下位の部分木の根であるノード以外の当該部分木に含まれるすべてのノードに付与するステップと、局所番号付与手段が、前記部分木毎に、当該部分木に含まれるノードの中から一のノードを識別可能な局所番号を、当該部分木に含まれるすべてのノードに付与するステップと、識別番号付与手段が、前記ノード毎に、当該ノードの大域番号と当該ノードの局所番号とを含む前記識別番号を付与するステップとから構成され、前記大域分割手段は、核ノード選択手段が、前記有向木のノードの中から前記有向木の根を含む２つ以上のノードを選択して核ノードとするステップと、大域番号付与手段が、前記核ノードの中から一の核ノードを識別可能な大域番号を前記すべての核ノードに付与するステップと、部分木生成手段が、前記核ノード毎に、当該核ノードから見て深い階層に他の核ノードがない場合には、当該核ノードを根として当該核ノードから見て深い階層にあるすべてのノードからなる部分木を生成して当該部分木のすべてのノードに当該核ノードの前記大域番号を付与し、当該核ノードから見て深い階層に他の核ノードがある場合には、当該核ノードから見て深い階層にあり他の核ノードを経由せずになぞることができるすべてのノードと当該核ノードから見て深い階層にある最初の他の核ノードとからなる部分木を生成して当該部分木に含まれる核ノード以外のノードに当該核ノードの前記大域番号を付与するステップとから構成され、前記大域分割手段は、核木生成手段が、前記核ノードと前記核ノードから見て深い階層にある最初の前記核ノードとを枝で接続して核木を生成すると共に、前記核木に含まれる核ノードの出次数の最大値である核木出次最大値を算出するステップをさらに含み、前記大域番号付与手段は、前記核木出次最大値を出次数としてＵＩＤを用いて前記核木のすべての核ノードに前記大域番号を付与するステップを含み、前記大域分割手段は、部分木最大出次数算出手段が、前記部分木毎に、当該部分木に含まれるノードの出次数の最大値である部分木出次最大値を算出するステップをさらに含み、前記局所番号付与手段が、前記部分木毎に、当該部分木の部分木出次最大値を出次数として、ＵＩＤを用いて前記局所番号を算出し、当該部分木の根である核ノード以外のノードには前記算出した局所番号を付与し、前記有向木の根以外の当該部分木の根である核ノードには、当該部分木の根である核ノードが属する上位の部分木で前記算出した局所番号を付与し、前記有向木の根である核ノードには、当該核ノードが属する部分木の前記局所番号を付与するステップを含み、前記識別番号付与手段が、前記有向木のノード毎に、当該ノードの大域番号と、当該ノードの局所番号と、当該ノードが核ノードであるか否かを示すノード種別情報とを含む前記識別番号を付与するステップを含むことを特徴としている。
【００３２】
請求項６記載の発明によれば、前記有向木のすべてのノードが含まれ、上位の部分木が下位の部分木の根を含むように分割されて部分木が生成され、前記分割されて生成された部分木の中から一の部分木を識別可能な前記大域番号が、当該部分木の下位の部分木の根を除く当該部分木に含まれるすべてのノードに対して、前記大域分割手段によって付与される。
【００３３】
また、前記局所番号付与手段によって前記部分木に含まれるノードの中から一のノードを識別可能な前記局所番号が、前記部分木毎に、当該部分木に含まれるすべてのノードに付与される。
【００３４】
また、前記識別番号付与手段によって、前記有向木のノード毎に、当該ノードの大域番号と、当該ノードの局所番号とを含み、前記有向木のノードを一意に識別可能な前記識別番号が付与される。この場合、前記有向木のノードを一意に識別することが可能になる。また、前記大域番号及び前記局所番号をより小さな数字で表わすことが可能になり、一般的なコンピュータで整数表現することがより容易になる。
【００３５】
また、前記有向木のノードの中から前記有向木の根を含む２つ以上のノードが、核ノード選択手段によって核ノードとして選択され、前記核ノードの中から一の核ノードを識別可能な大域番号が、前記大域番号付与手段によって前記すべての核ノードに付与され、前記核ノード毎に、当該核ノードを根とし、当該核ノードから見て深い階層に他の核ノードがない場合には、部分木生成手段によって、当該核ノードから見て深い階層にあるすべてのノードからなる部分木が生成され、当該部分木のすべてのノードに、当該部分木の根である核ノードの前記大域番号が付与される。
【００３６】
また、当該核ノードから見て深い階層に他の核ノードがある場合には、当該核ノードから見て深い階層にあり他の核ノードを経由せずになぞることができるすべてのノードと、当該核ノードから見て深い階層にある最初の他の核ノードとからなる部分木が、前記部分木生成手段によって生成され、前記生成された部分木に含まれる核ノード以外のノードに当該部分木の根である核ノードの前記大域番号が、前記部分木生成手段によって付与される。
【００３７】
また、前記大域分割手段は、前記核ノード選択手段と、前記大域番号付与手段と、前記部分木生成手段とを備えるので、前記有向木を前記部分木に分割し、前記部分木のすべてのノードに、前記大域番号を付与することが可能になる。
【００３８】
また、前記核木生成手段によって、前記核ノードと前記核ノードから見て深い階層にある最初の前記核ノードとが枝で接続されて核木が生成されると共に、前記核木に含まれる核ノードの出次数の最大値である核木出次最大値が算出される。また、前記大域番号付与手段によって、前記核木出次最大値を出次数としてＵＩＤを用いて前記核木のすべての核ノードに前記大域番号が付与される。また、前記部分木最大出次数算出手段によって、前記部分木毎に、当該部分木に含まれるノードの出次数の最大値である部分木出次最大値が算出される。
【００３９】
この場合、前記大域分割手段は、前記核木生成手段、前記大域番号付与手段及び前記部分木最大出次数算出手段を備えるので、ＵＩＤを用いて前記大域番号が付与されると共に、前記部分木出次最大値が算出される。
【００４０】
また、前記局所番号付与手段によって、前記部分木毎に、当該部分木の部分木出次最大値を出次数として、ＵＩＤを用いて前記局所番号が算出され、当該部分木の根である核ノード以外のノードには前記算出された局所番号が付与され、前記有向木の根以外の当該部分木の根である核ノードには、当該部分木の根である核ノードが属する上位の部分木で前記算出された局所番号が付与され、前記有向木の根である核ノードには、当該核ノードが属する部分木の前記局所番号が付与されるので、前記局所番号として、ＵＩＤを用いて算出された番号が付与される。
【００４１】
また、前記識別番号付与手段によって、前記有向木のノード毎に、当該ノードの大域番号と、当該ノードの局所番号と、当該ノードが核ノードであるか否かを示すノード種別情報とを含む前記識別番号が付与されるので、前記有向木のノードを一意に識別することが可能になる。この場合、前記大域番号と局所番号をより小さな数字で表わすことが可能になり、一般的なコンピュータで整数表現することがより容易になる。
【００４２】
請求項７記載の発明は、データ構造を表わす有向木のノードを一意に識別可能に識別番号を付与する識別番号付与プログラムであって、前記有向木をすべてのノードが含まれるように、上位の部分木が下位の部分木の根を含んで分割して部分木を生成し、前記生成された部分木の中から一の部分木を識別可能な大域番号を、前記生成された部分木毎に、当該部分木の下位の部分木の根であるノード以外の当該部分木に含まれるすべてのノードに付与する大域分割手段、前記部分木毎に、当該部分木に含まれるノードの中から一のノードを識別可能な局所番号を、当該部分木に含まれるすべてのノードに付与する局所番号付与手段、前記ノード毎に、当該ノードの大域番号と当該ノードの局所番号とを含む前記識別番号を付与する識別番号付与手段としてコンピュータを機能させ、前記大域分割手段は、前記有向木のノードの中から前記有向木の根を含む２つ以上のノードを選択して核ノードとする核ノード選択手段、前記核ノードの中から一の核ノードを識別可能な大域番号を前記すべての核ノードに付与する大域番号付与手段、前記核ノード毎に、当該核ノードから見て深い階層に他の核ノードがない場合には、当該核ノードを根として当該核ノードから見て深い階層にあるすべてのノードからなる部分木を生成して当該部分木のすべてのノードに当該核ノードの前記大域番号を付与し、当該核ノードから見て深い階層に他の核ノードがある場合には、当該核ノードから見て深い階層にあり他の核ノードを経由せずになぞることができるすべてのノードと当該核ノードから見て深い階層にある最初の他の核ノードとからなる部分木を生成して当該部分木に含まれる核ノード以外のノードに当該核ノードの前記大域番号を付与する部分木生成手段としてコンピュータを機能させ、前記大域分割手段は、前記核ノードと前記核ノードから見て深い階層にある最初の前記核ノードとを枝で接続して核木を生成すると共に、前記核木に含まれる核ノードの出次数の最大値である核木出次最大値を算出する核木生成手段としてさらにコンピュータを機能させ、前記大域番号付与手段は、前記核木出次最大値を出次数としてＵＩＤを用いて前記核木のすべての核ノードに前記大域番号を付与するようにコンピュータを機能させ、前記大域分割手段は、前記部分木毎に、当該部分木に含まれるノードの出次数の最大値である部分木出次最大値を算出する部分木最大出次数算出手段としてさらにコンピュータを機能させ、前記局所番号付与手段は、前記部分木毎に、当該部分木の部分木出次最大値を出次数として、ＵＩＤを用いて前記局所番号を算出し、当該部分木の根である核ノード以外のノードには前記算出した局所番号を付与し、前記有向木の根以外の当該部分木の根である核ノードには、当該部分木の根である核ノードが属する上位の部分木で前記算出した局所番号を付与し、前記有向木の根である核ノードには、当該核ノードが属する部分木の前記局所番号を付与するようにコンピュータを機能させ、前記識別番号付与手段は、前記有向木のノード毎に、当該ノードの大域番号と、当該ノードの局所番号と、当該ノードが核ノードであるか否かを示すノード種別情報とを含む前記識別番号を付与するようにコンピュータを機能させることを特徴としている。
【００４３】
請求項８記載の発明は、データ構造を表わす有向木のノードを一意に識別可能に識別番号を付与する識別番号付与プログラムを記録したコンピュータ読み取り可能な記録媒体であって、前記有向木をすべてのノードが含まれるように、上位の部分木が下位の部分木の根を含んで分割して部分木を生成し、前記生成された部分木の中から一の部分木を識別可能な大域番号を、前記生成された部分木毎に、当該部分木の下位の部分木の根であるノード以外の当該部分木に含まれるすべてのノードに付与する大域分割手段、前記部分木毎に、当該部分木に含まれるノードの中から一のノードを識別可能な局所番号を、当該部分木に含まれるすべてのノードに付与する局所番号付与手段、前記ノード毎に、当該ノードの大域番号と当該ノードの局所番号とを含む前記識別番号を付与する識別番号付与手段としてコンピュータを機能させ、前記大域分割手段は、前記有向木のノードの中から前記有向木の根を含む２つ以上のノードを選択して核ノードとする核ノード選択手段、前記核ノードの中から一の核ノードを識別可能な大域番号を前記すべての核ノードに付与する大域番号付与手段、前記核ノード毎に、当該核ノードから見て深い階層に他の核ノードがない場合には、当該核ノードを根として当該核ノードから見て深い階層にあるすべてのノードからなる部分木を生成して当該部分木のすべてのノードに当該核ノードの前記大域番号を付与し、当該核ノードから見て深い階層に他の核ノードがある場合には、当該核ノードから見て深い階層にあり他の核ノードを経由せずになぞることができるすべてのノードと当該核ノードから見て深い階層にある最初の他の核ノードとからなる部分木を生成して当該部分木に含まれる核ノード以外のノードに当該核ノードの前記大域番号を付与する部分木生成手段としてコンピュータを機能させ、前記大域分割手段は、前記核ノードと前記核ノードから見て深い階層にある最初の前記核ノードとを枝で接続して核木を生成すると共に、前記核木に含まれる核ノードの出次数の最大値である核木出次最大値を算出する核木生成手段としてさらにコンピュータを機能させ、前記大域番号付与手段は、前記核木出次最大値を出次数としてＵＩＤを用いて前記核木のすべての核ノードに前記大域番号を付与するようにコンピュータを機能させ、前記大域分割手段は、前記部分木毎に、当該部分木に含まれるノードの出次数の最大値である部分木出次最大値を算出する部分木最大出次数算出手段としてさらにコンピュータを機能させ、前記局所番号付与手段は、前記部分木毎に、当該部分木の部分木出次最大値を出次数として、ＵＩＤを用いて前記局所番号を算出し、当該部分木の根である核ノード以外のノードには前記算出した局所番号を付与し、前記有向木の根以外の当該部分木の根である核ノードには、当該部分木の根である核ノードが属する上位の部分木で前記算出した局所番号を付与し、前記有向木の根である核ノードには、当該核ノードが属する部分木の前記局所番号を付与するようにコンピュータを機能させ、前記識別番号付与手段は、前記有向木のノード毎に、当該ノードの大域番号と、当該ノードの局所番号と、当該ノードが核ノードであるか否かを示すノード種別情報とを含む前記識別番号を付与するようにコンピュータを機能させることを特徴とする識別番号付与プログラムを記録していることを特徴としている。
【００４４】
請求項７記載の識別番号付与プログラム、及び請求項８記載の識別番号付与プログラムを記録したコンピュータ読み取り可能な記録媒体によれば、前記有向木のすべてのノードが含まれ、上位の部分木が下位の部分木の根を含むように分割されて部分木が生成され、前記分割されて生成された部分木の中から一の部分木を識別可能な前記大域番号が、当該部分木の下位の部分木の根を除く当該部分木に含まれるすべてのノードに対して、前記大域分割手段によって付与されるように、コンピュータが機能する。
【００４５】
また、前記局所番号付与手段によって前記部分木に含まれるノードの中から一のノードを識別可能な前記局所番号が、前記部分木毎に、当該部分木に含まれるすべてのノードに付与されるように、コンピュータが機能する。
【００４６】
また、前記識別番号付与手段によって、前記有向木のノード毎に、当該ノードの大域番号と、当該ノードの局所番号とを含み、前記有向木のノードを一意に識別可能な前記識別番号が付与される。この場合、前記有向木のノードを一意に識別することが可能になる。また、前記大域番号及び前記局所番号をより小さな数字で表わすことが可能になり、一般的なコンピュータで整数表現することがより容易になる。
【００４７】
また、前記有向木のノードの中から前記有向木の根を含む２つ以上のノードが、核ノード選択手段によって核ノードとして選択され、前記核ノードの中から一の核ノードを識別可能な大域番号が、前記大域番号付与手段によって前記すべての核ノードに付与され、前記核ノード毎に、当該核ノードを根とし、当該核ノードから見て深い階層に他の核ノードがない場合には、部分木生成手段によって、当該核ノードから見て深い階層にあるすべてのノードからなる部分木が生成され、当該部分木のすべてのノードに、当該部分木の根である核ノードの前記大域番号が付与されるように、コンピュータが機能する。
【００４８】
また、当該核ノードから見て深い階層に他の核ノードがある場合には、当該核ノードから見て深い階層にあり他の核ノードを経由せずになぞることができるすべてのノードと、当該核ノードから見て深い階層にある最初の他の核ノードとからなる部分木が、前記部分木生成手段によって生成され、前記生成された部分木に含まれる核ノード以外のノードに当該部分木の根である核ノードの前記大域番号が、前記部分木生成手段によって付与されるように、コンピュータが機能する。
【００４９】
また、前記大域分割手段は、前記核ノード選択手段と、前記大域番号付与手段と、前記部分木生成手段とを備えるので、前記有向木を前記部分木に分割し、前記部分木のすべてのノードに、前記大域番号を付与するようにコンピュータが機能することが可能になる。
【００５０】
また、前記核木生成手段によって、前記核ノードと前記核ノードから見て深い階層にある最初の前記核ノードとが枝で接続されて核木が生成されると共に、前記核木に含まれる核ノードの出次数の最大値である核木出次最大値が算出される。また、前記大域番号付与手段によって、前記核木出次最大値を出次数としてＵＩＤを用いて前記核木のすべての核ノードに前記大域番号が付与される。また、前記部分木最大出次数算出手段によって、前記部分木毎に、当該部分木に含まれるノードの出次数の最大値である部分木出次最大値が算出されるように、コンピュータが機能する。
【００５１】
この場合、前記大域分割手段は、前記核木生成手段、前記大域番号付与手段及び前記部分木最大出次数算出手段を備えるので、ＵＩＤを用いて前記大域番号が付与されると共に、前記部分木出次最大値が算出される。
【００５２】
また、前記局所番号付与手段によって、前記部分木毎に、当該部分木の部分木出次最大値を出次数として、ＵＩＤを用いて前記局所番号が算出され、当該部分木の根である核ノード以外のノードには前記算出された局所番号が付与され、前記有向木の根以外の当該部分木の根である核ノードには、当該部分木の根である核ノードが属する上位の部分木で前記算出された局所番号が付与され、前記有向木の根である核ノードには、当該核ノードが属する部分木の前記局所番号が付与されるようにコンピュータが機能するので、前記局所番号として、ＵＩＤを用いて算出された番号が付与される。
【００５３】
また、前記識別番号付与手段によって、前記有向木のノード毎に、当該ノードの大域番号と、当該ノードの局所番号と、当該ノードが核ノードであるか否かを示すノード種別情報とを含む前記識別番号が付与されるようにコンピュータが機能するので、前記有向木のノードを一意に識別することが可能になる。この場合、前記大域番号と局所番号をより小さな数字で表わすことが可能になり、一般的なコンピュータで整数表現することがより容易になる。
【００５４】
【発明の実施の形態】
以下、本発明の一実施の形態による識別番号付与プログラムについて、図面を参照しながら説明する。図１は、本発明の一実施形態による識別番号付与プログラムを用いた識別番号付与装置の構成例を示すブロック図である。
【００５５】
図１に示す識別番号付与装置１は、通常のコンピュータ等から構成され、ＲＯＭ（リードオンリメモリ）１１、ＣＰＵ（中央演算処理装置）１２、ＲＡＭ（ランダムアクセスメモリ）１３、外部記憶装置１４、入力部１５及び表示部１６の各ブロックを備える。各ブロックは内部のバスに接続され、このバスを介して種々のデータ等が入出力され、ＣＰＵ１２の制御の下、種々の処理が実行される。
【００５６】
ＲＯＭ１１には、後述する識別番号付与プログラム等が予め記憶される。ＣＰＵ１２は、ＲＯＭ１１から識別番号付与プログラム等を読み出し、後述する識別番号を付与、管理する処理等を実行し、各ブロックの動作を制御する。ＲＡＭ１３は、ＣＰＵ１２の作業領域等として用いられる。
【００５７】
外部記憶装置１４は、ハードディスクドライブ等の外部記憶装置から構成され、入力部１５等から入力されるＸＭＬ文書等の木構造で表現することが出来るデータを記憶する。
【００５８】
なお、外部記憶装置１４に識別番号付与プログラムを予めインストールし、外部記憶装置１４から識別番号付与プログラムを読み出して実行するようにしても良い。また、ＣＤ−ＲＯＭドライブ、フロッピィディスクドライブ等の他の外部記憶装置を付加し、ＣＤ−ＲＯＭ、フロッピィディスク等のコンピュータ読み取り可能な記録媒体に識別番号付与プログラム又はＸＭＬ文書等のデータを記録し、この記録媒体から識別番号付与プログラムやＸＭＬ文書等のデータを読み出して実行するようにしても良い。また、識別番号付与プログラムやＸＭＬ文書等のデータが所定のネットワークを介して図１に示す識別番号付与装置に接続された他のコンピュータに記憶されている場合、当該コンピュータからネットワークを介して識別番号付与プログラム等をダウンロードして実行するようにしても良い。
【００５９】
入力部１５は、キーボード、マウス等から構成され、ユーザーが後述する核ノードを選択する処理において使用する選択閾値、ＸＭＬ文書等のデータを入力したり、種々の操作を行うために用いられる。
【００６０】
表示部１６は、ＣＲＴ（陰極線管）又は液晶表示装置等から構成され、ＣＰＵ１２に制御され、ユーザーが入力部１５を操作して入力した文字等を表示する。
【００６１】
図２は、本発明の一実施形態による識別番号付与プログラムを用いた識別番号付与装置の主な機能を示したブロック図である。本識別番号付与装置は、主にＲＯＭ１１とＣＰＵ１２より構成される制御部１００、及び主にＲＡＭ１３と外部記憶装置１４より構成される記憶部２００を備える。
【００６２】
記憶部２００は、ＸＭＬ文書記憶部２０１と核木情報記憶部２０２とから構成されている。ＸＭＬ文書記憶部２０１は、ＸＭＬ文書等のデータを記憶する。核木情報記憶部２０２は、ＲＡＭ１３等により構成され、後述する核木情報処理部１０４で生成された核木情報記憶テーブルを記憶する。前記核木情報記憶テーブルは、核木出次最大値ｋ、大域番号ｇ、局所番号ｌ及び部分木出次最大値ｆを含んで生成されたデータテーブルであり、前記大域番号ｇ、局所番号ｌ及び部分木出次最大値ｆは、後述する核ノード選択制御部１１４で選択された核ノード毎に関連付けられている。
【００６３】
制御部１００は、ＸＭＬデータ読み出し部１１８、大域分割部１０１、局所番号付与部１０２、識別番号付与部１０３、核木情報処理部１０４、親識別番号算出部１０５、再帰大域番号付与部１０６及び再帰的識別制御部１０７を備え、ＸＭＬ文書等のデータ構造を表した有向木のノードに前記識別番号の付与等を行う。
【００６４】
ＸＭＬデータ読み出し部１１８は、ＸＭＬ文書記憶部２０１に記憶されているＸＭＬ文書等を読み出して、前記読み出したＸＭＬ文書等のデータ構造を表した有向木を生成する。
【００６５】
大域分割部１０１は、核ノード選択部１０８、核木生成部１１１、大域番号付与部１０９、部分木生成部１１０及び部分木最大出次数算出部１１５を備え、ＸＭＬデータ読み出し部１１８で生成された前記有向木を上位の部分木が下位の部分木の根を含むように分割して部分木を生成する。この場合、前記有向木のすべてのノードが前記分割された部分木のいずれかに含まれる。また、前記生成された部分木の中から一の部分木を識別可能な大域番号ｇを、前記生成された部分木毎に、当該部分木の下位の部分木の根を除く当該部分木のすべてのノードに付与する。
【００６６】
核ノード選択部１０８は、特定ノード選択部１１２、特定有向木生成部１１３、核ノード選択制御部１１４を備え、ＸＭＬデータ読み出し部１１８で生成された前記有向木のノードの中から当該有向木の根を含む二つ以上のノードを選択して核ノードとする。
【００６７】
親識別番号算出部１０５は、親大域番号算出部１１６及び親局所番号算出部１１７を備え、前記有向木のノードの前記識別番号から、当該ノードの親の前記識別番号を算出する。
【００６８】
特定ノード選択部１１２は、例えばユーザーが入力部１５のキーボードから数字を入力することによって入力された数を、選択閾値ｘとする。また、ＸＭＬデータ読み出し部１１８で生成された前記有向木または、特定有向木生成部１１３で生成された特定有向木を処理対象木とする。また、前記処理対象木のノードについて、前記選択閾値ｘ以上の数の子孫を持ち、かつ当該ノードのすべての子について、当該ノードの子が持っている子の数は前記選択閾値ｘ未満である条件を満足するノードを選択して核ノードとし、前記処理対象木に含まれるすべての核ノードのノード番号を表わす核ノード集合Ｃを生成し、また、すでに前記核ノード集合Ｃが生成されている場合には、前記処理対象木に含まれるすべての前記核ノードのノード番号を前記核ノード集合Ｃに追加して新たな核ノード集合Ｃを生成する。
【００６９】
特定有向木生成部１１３は、特定ノード選択部１１２で生成された、前記処理対象木及び前記核ノード集合Ｃに基づき、前記核ノード集合Ｃで示されるすべての核ノードについて、当該核ノードの子孫であるノードをすべて前記処理対象木から削除して新たな有向木を生成する。
【００７０】
核ノード選択制御部１１４は、特定有向木生成部１１３で生成された前記新たな有向木が根のノードのみであるか否かを判断し、前記新たな有向木が根のノードのみではなかった場合には、さらに前記新たな有向木を処理対象木として、特定ノード選択部１１２に処理させる。一方、前記新たな有向木が根のノードのみであった場合には、特定ノード選択部１１２で最後に生成された核ノード集合ＣにはＸＭＬデータ読み出し部１１８で生成された前記有向木のすべての核ノードのノード番号が格納されていると判断し、前記核ノード集合Ｃにノード番号が格納されているノードを、当該有向木の核ノードとして選択する。
【００７１】
核木生成部１１１は、ＸＭＬデータ読み出し部１１８で生成された前記有向木を基にして、前記核ノード集合Ｃに含まれた核ノードと当該核ノードから見て深い階層にある最初の前記核ノードとを枝で接続し、すべての前記核ノードが枝で接続された核木を生成する。さらに前記核木のすべてのノードの出次数を数えてその最大の数を核木出次最大値ｋとする。
【００７２】
大域番号付与部１０９は、核木生成部１１１で生成された前記核木と核木出次最大値ｋとに基づき、前記核木について、前記核ノード毎に核木出次最大値ｋを出次数としてＵＩＤを用いて番号を算出し、前記算出した番号を大域番号ｇとして当該核ノードに付与する。
【００７３】
部分木生成部１１０は、ＸＭＬデータ読み出し部１１８で生成された前記有向木において、前記核ノード集合Ｃに含まれた核ノード毎に、当該核ノードから見て深い階層に他の核ノードがない場合には、当該核ノードを根として当該核ノードから見て深い階層にあるすべてのノードからなる部分木を生成して当該部分木のすべてのノードに当該核ノードの前記大域番号ｇを付与する。
【００７４】
また、当該核ノードから見て深い階層に他の核ノードがある場合には、当該核ノードから見て深い階層にあり他の核ノードを経由せずになぞることができるすべてのノードと当該核ノードから見て深い階層にある最初の他の核ノードとからなる部分木を生成して当該部分木に含まれる核ノード以外のノードに当該核ノードの前記大域番号を付与する。
【００７５】
部分木最大出次数算出部１１５は、部分木生成部１１０で生成された前記部分木毎に、当該部分木に含まれるノードの出次数の最大値である部分木出次最大値ｆを生成する。
【００７６】
局所番号付与部１０２は、部分木生成部１１０で生成された前記部分木毎に、部分木最大出次数算出部１１５で生成された当該部分木の部分木出次最大値ｆを出次数として、ＵＩＤを用いて局所番号ｌを算出し、当該部分木の根である核ノード以外のノードには前記算出した局所番号ｌを付与し、前記有向木の根以外の当該部分木の根である核ノードには、当該部分木の根である核ノードが属する上位の部分木で前記算出した局所番号ｌを付与し、前記有向木の根である核ノードには、当該核ノードが属する部分木の前記算出した局所番号ｌを付与する。
【００７７】
識別番号付与部１０３は、ＸＭＬデータ読み出し部１１８で生成された前記有向木のノード毎に、大域番号付与部１０９で付与された当該核ノードの大域番号ｇと、局所番号付与部１０２で付与された当該核ノードの局所番号ｌと、当該核ノードが核ノードであるか否かを示す情報であるノード種別情報ｒとからなる前記識別番号を付与する。
【００７８】
核木情報処理部１０４は、核木生成部１１１で生成された核木出次最大値ｋ、及び前記核ノード集合Ｃに含まれる前記核ノード毎に、大域番号付与部１０９で付与された当該核ノードの前記大域番号ｇと、局所番号付与部１０２で付与された当該核ノードの前記局所番号ｌと、部分木最大出次数算出部１１５で生成された当該核ノードが根である部分木の前記部分木出次最大値ｆとを関連付けた情報を核木情報記憶テーブルとして核木情報記憶部２０２に記憶する。
【００７９】
親大域番号算出部１１６は、ＸＭＬデータ読み出し部１１８で生成された前記有向木のノードの前記識別番号が入力されると、前記核木情報記憶部２０２に記憶されている核木情報記憶テーブルから読み出した核木出次最大値ｋと、前記入力された識別番号とから当該ノードの親の前記大域番号ｇを算出する。また、以下の説明において、前記大域番号がｇ、前記局所番号がｌ、前記ノード種別情報がｒであるノードの前記識別番号を（ｇ，ｌ，ｒ）として表記する。
【００８０】
ここで、親大域番号算出部１１６に前記識別番号（ｇｉ，ｌｉ，ｒｉ）が入力されると、親大域番号算出部１１６は、ノード種別情報ｒｉが核ノードであることを示す情報である場合には、前記核木情報記憶部２０２に記憶されている核木情報記憶テーブルから核木出次最大値ｋを読み出して、（ｇｉ−２）／ｋ＋１を計算し、さらに前記計算結果の小数部を切り捨てて整数部を算出し、前記算出した値を当該ノードの親を示す前記大域番号ｇpとし、ノード種別情報ｒｉが核ノードではないことを示す情報である場合には、大域番号ｇｉを、当該ノードの親を示す大域番号ｇpとする。
【００８１】
親局所番号算出部１１７は、前記核木情報記憶部２０２に記憶されている核木情報記憶テーブルから、前記大域番号ｇpに関連付けられた部分木出次最大値ｆを読み出す。また、以下の説明において、前記大域番号ｇに関連付けられた局所番号ｌをｌ(ｇ)、部分木出次最大値ｆをｆ（ｇ）で表記する。したがって、前記大域番号ｇpに関連付けられた部分木出次最大値ｆは、ｆ（ｇp）と表記される。
【００８２】
また、親局所番号算出部１１７は、親大域番号算出部１１６で算出された前記大域番号ｇpと、前記識別番号（ｇｉ，ｌｉ，ｒｉ）とから、（ｌｉ−２）／ｆ(ｇp)＋１を計算し、さらに前記計算結果の小数部を切り捨てて整数部を算出して前記整数部が１ではない場合には、前記整数部を当該ノードの親を示す前記局所番号ｌpにすると共に、当該ノードの親のノード種別情報ｒpを核ノードではないことを示す０とし、前記整数部が１である場合には、核木情報記憶部２０２に記憶された核木情報記憶テーブルから大域番号ｇpと関連付けられた局所番号ｌ(ｇp)を読み出して、当該ノードの親を示す局所番号ｌpにすると共に、当該ノードの親のノード種別情報ｒpを核ノードであることを示す１とする。
【００８３】
再帰大域番号付与部１０６は、部分木生成部１１０で生成されて大域番号ｇが付与された前記部分木を分割した新たな部分木を再帰部分木とし、前記大域番号ｇを前記再帰部分木の再帰大域番号ｓとし、前記再帰部分木の前記大域番号ｇを新たに生成し、前記再帰部分木のノードに対して前記局所番号ｌを生成し、前記再帰部分木のノードに再帰大域番号ｓ、大域番号ｇ、局所番号ｌを含む識別番号を付与する。
【００８４】
再帰的識別制御部１０７は、再帰大域番号付与部１０６の処理を制御することによって、再帰大域番号付与部１０６に、再帰大域番号ｓｉ、大域番号ｇｉ、局所番号ｌｉを含む前記識別番号を付与された前記再帰部分木を入力して分割させ、新たな再帰部分木を生成させ、前記新たな再帰部分木に対して前記再帰大域番号ｓｉ、前記大域番号ｇｉを含む新たな再帰大域番号ｓを生成させ、前記再帰部分木のノードに対して新たに大域番号ｇを生成して付与し、以上の制御を一以上の回数繰り返して再帰大域番号付与部１０６に前記部分木を再帰的に分割させ、前記大域番号を再帰的に付与させる。また、最後に生成された前記再帰部分木のノードについて前記局所番号ｌを生成し、前記最後に生成された再帰部分木のノードに前記再帰大域番号ｓ、前記大域番号ｇ、前記局所番号ｌを含む識別番号を付与する。
【００８５】
次に、上記のように構成された識別番号付与装置の動作について説明する。図３は、図２に示す識別番号付与装置が木構造で表わされたデータのノードに前記識別番号を付与する動作を説明するためのフローチャートである。
【００８６】
まず、ステップＳ１において、ＣＰＵ１２は、ＸＭＬ文書記憶部２０１に記憶されているＸＭＬ文書を読み出して、前記読み出したＸＭＬ文書を有向木で表現する。ここでは、説明を容易にするため、ＸＭＬ文書記憶部２０１から読み出されたＸＭＬ文書から、図４に記載の有向木Ｔが得られたものとする。以下の例では、前記有向木Ｔに基づいて説明を行う。なお、図４では、説明のため前記有向木Ｔのノードにノード番号を付与し、前記ノード番号によってノードを特定しているが、ノード番号を付与せずに、例えば長男次弟表現等の木構造をなぞることによってノードを指定する等の公知の方法を用いてもよい。また、本実施形態では、ＸＭＬ文書から有向木を得ることとしているが、木構造を持ったデータであれば、ＸＭＬ文書でなくても良い。
【００８７】
次に、ステップＳ２において、ＣＰＵ１２は、図５、図６のフロー図に従い、以下のようにして核ノードを選択する。
【００８８】
ステップＳ２０１において、ＣＰＵ１２は、例えばユーザーが入力部１５のキーボードから数字を入力することによって、制御部１００に入力された数を、選択閾値ｘとする。
【００８９】
次に、ステップＳ２０２において、ＣＰＵ１２は、前記有向木Ｔを、処理対象木Ｕとする。例えば、図４の前記有向木Ｔが、処理対象木Ｕとなる。
【００９０】
次に、ステップＳ２０３において、ＣＰＵ１２は、変数ｉに１を代入する。また、以下の説明において、ノード番号がｉであるノードを、ノードｉと表記する。
【００９１】
次に、ステップＳ２０４において、ＣＰＵ１２は、前記処理対象木Ｕのノードｉが持っている子孫の数をカウントし、前記子孫の数が前記選択閾値ｘ個以上の場合はステップＳ２０５に移行し、前記子孫の数が前記選択閾値ｘ個未満の場合はステップＳ２０７に移行する。
【００９２】
ステップＳ２０５において、ＣＰＵ１２は、前記ノードｉのすべての子について、それぞれ当該子が持っている子孫の数をカウントし、前記選択閾値ｘ個以上の子孫を持つ子がなかった場合には、ステップＳ２０６に移行し、前記選択閾値ｘ個以上の子孫を持つ子があった場合には、ステップＳ２０７に移行する。
【００９３】
ステップＳ２０６において、ＣＰＵ１２は、ノードｉを核ノードとする。前記核ノードの集合を表わす核ノード集合Ｃに、ノードｉのノード番号ｉを入れて、ステップＳ２０７に移行する。
【００９４】
次に、ステップＳ２０７において、ＣＰＵ１２は、ノードｉが前記処理対象木Ｕの最後のノードである場合には、ステップＳ２０９に移行し、ノードｉが前記処理対象木Ｕの最後のノードではない場合には、ステップＳ２０８に移行する。
【００９５】
ステップＳ２０８において、ＣＰＵ１２は、ｉ＋１をｉに代入してステップＳ２０４へ戻る。このようにして、ステップＳ２０４〜Ｓ２０８を繰り返すことにより、処理対象木Ｕの全ノードについて、前記選択閾値ｘ以上の数の子孫を持ち、かつ当該ノードのすべての子について、当該ノードの子が持っている子孫の数は前記選択閾値ｘ未満である条件を満足するノードが核ノードとして選択される。
【００９６】
例えば、ステップＳ２０１においてユーザーが入力した数字が４のとき、選択閾値ｘは４になり、図７の二重丸で記載したノード２、１１、２０が選択され、前記核ノード集合Ｃにはノード番号２、１１、２０が格納される。なお、以下の説明において、図中、核ノードを二重丸で表記する。
【００９７】
次に、ステップＳ２０９において、ＣＰＵ１２は、前記核ノード集合Ｃで示されるすべての核ノードについて、当該核ノードの子孫であるノードをすべて前記処理対象木Ｕから削除して有向木Ｓを生成する。例えば、図７の処理対象木Ｕから、図８の前記有向木Ｓが生成される。
【００９８】
次に、ステップＳ２１０において、ＣＰＵ１２は、前記有向木Ｓのノードを検査し、前記有向木Ｓが、根のノードすなわちノード１のみで構成されている場合には、Ｓ２の処理を終了し、図３のステップＳ３に移行する。また、前記有向木Ｓが根のノードすなわちノード１以外のノードを含んでいた場合には、ステップＳ２１１に移行する。
【００９９】
次に、ステップＳ２１１において、ＣＰＵ１２は、前記ステップＳ２０９で生成された前記有向木Ｓを、前記処理対象木Ｕに代入してステップＳ２０３へ戻る。このようにして、前記有向木Ｓが根のノードすなわちノード１のみになるまでステップＳ２０３〜Ｓ２１１を繰り返すことにより、前記有向木Ｔの全ノードについて前記選択閾値ｘ以上の数の子孫を持ち、かつ当該ノードのすべての子について当該ノードの子が持っている子孫の数は前記選択閾値ｘ未満である条件を満足するノードが核ノードとして選択され、前記核ノード集合Ｃには、前記有向木Ｔのすべての核ノードのノード番号が格納される。例えば、図８の前記有向木Ｓからはノード７が核ノードとして選択され、核ノード集合Ｃには、ノード番号１、２、７、１１、２０が格納される。
【０１００】
なお、本実施形態では、ステップＳ２の処理を行うことによって前記核ノードを選択したが、前記核ノードは前記有向木Ｔにおいて、根のノードを含む２以上のノードを選択すればよく、他の手段によって、核ノードを選択しても良い。
【０１０１】
次に、図３のステップＳ３において、ＣＰＵ１２は、前記有向木Ｔを基に、前記核ノード集合Ｃに格納されたノード番号で指定される前記核ノードと当該核ノードから見て深い階層にある最初の前記核ノードとを枝で接続する（図９（ａ）参照）。図９で、前記核ノードを接続した枝は二重線で記載している。そして、前記核ノード以外のノードをすべて削除して核木を生成する（図９（ｂ）参照）。
【０１０２】
さらに前記核木のすべてのノードの出次数を数えてその最大の数を核木出次最大値ｋとする。例えば、図９（ｂ）の核木の場合、前記核木出次最大値ｋは３となる。
【０１０３】
次に、図３のステップＳ４において、ＣＰＵ１２は、ステップＳ３で生成された前記核木と前記核木出次最大値ｋとに基づき、前記核木のすべての核ノードに対して前記核木出次最大値ｋを出次数としてＵＩＤを用いて番号を算出し、前記算出した番号を前記核ノード毎に当該核ノードの大域番号ｇとして付与する。
【０１０４】
例えば、図９（ｂ）の核木の核ノードに付与される大域番号は、図１０の括弧で記載された番号となる。
【０１０５】
次に、ステップＳ５において、ＣＰＵ１２は、変数ｍに１を代入する。さらに、前記核ノードの数をｍＭＡＸに代入する。例えば、前記有向木Ｔの核ノード数は５個であるので、ｍＭＡＸには５が代入される。
【０１０６】
次に、ステップＳ６において、ＣＰＵ１２は、前記有向木Ｔにおいて、前記核木のｍ番目の核ノードを根とし当該核ノードから見て深い階層に他の核ノードがある場合には、当該核ノードから見て深い階層にあり他の核ノードを経由せずになぞることができるすべてのノードと、当該核ノードから見て深い階層にある最初の他の核ノードとからなる部分木を生成し、前記生成した部分木に含まれる核ノード以外のノードに当該部分木の根である核ノードの前記大域番号ｇを付与する。
【０１０７】
例えば、図１１に記載の有向木Ｔにおいて、ノード番号１の核ノードを根として点線で囲まれた領域のノードからなる部分木が生成され、ノード１７、１８、１９に大域番号１が付与される。
【０１０８】
また、前記ｍ番目の核ノードを根とし当該根の下位に他の核ノードがない場合には、当該根のノードから見て深い階層にあるすべてのノードからなる部分木を生成して当該部分木のすべてのノードに、当該部分木の根である核ノードの前記大域番号を付与する。例えば、図１１に記載の有向木Ｔにおいて、ノード番号２の核ノードを根として点線で囲まれた領域のノードからなる部分木が生成され、ノード３、４、５、６に大域番号２が付与される。
【０１０９】
なお、前記核木のｍ番目のノードを数える順番は、各ノードの順番を重複なく数える方法であれば良く、例えばプリオーダー等の公知の巡回方法による。
【０１１０】
次に、ステップＳ７において、ＣＰＵ１２は、ステップＳ６で生成された前記部分木毎にすべてのノードの出次数を数えてその最大の数を部分木出次最大値ｆとして生成すると共に、当該部分木の根である核ノードに対してステップＳ４で付与された前記大域番号ｇと前記部分木出次最大値ｆとを関連付ける。
【０１１１】
例えば、図１１の有向木Ｔにおいて、ｍが１の場合に１番目の核ノードすなわちノード１を根とする部分木の最大の出次数は４となるので、部分木出次最大値４をノード１の前記大域番号１と関連付ける。
【０１１２】
次に、ステップＳ８において、ＣＰＵ１２は、図１２のフロー図に従い、以下のようにして前記ｍ番目の核ノードを根とする部分木に含まれるすべてのノードに前記局所番号ｌを付与する。
【０１１３】
ステップＳ８０１において、ＣＰＵ１２は、１を変数ｎに代入すると共に、ステップＳ６で生成された前記ｍ番目の核ノードを根とする部分木のノードの数を数えて変数Ｎ(ｍ)に代入する。以下の説明では、変数Ｎ(ｍ)は、前記ｍ番目の核ノードを根とする部分木のノードの数を表わすものとする。例えばｍが１の場合には、局所変数Ｎ（１）に７が代入される。
【０１１４】
次に、ステップＳ８０２において、ＣＰＵ１２は、前記ｍ番目の核ノードを根とする部分木のｎ番目のノードについて、ステップＳ７で生成された前記ｍ番目の核ノードを根とする部分木の部分木出次最大値ｆを出次数としてＵＩＤを用いて番号を算出する。以下の説明では、前記ｍ番目の核ノードを根とする部分木のｎ番目のノードについて、前記ｍ番目の核ノードを根とする部分木の部分木出次最大値ｆを出次数としてＵＩＤを用いて算出した番号をｌw（ｍ，ｎ）と表記する。例えば、図１３でノード７の前記ＵＩＤを用いて算出した番号はｌw（１，３）で表わされ、ｌw（１，３）の値は３となる。
【０１１５】
次に、ステップＳ８０３において、ＣＰＵ１２は、ｌw（ｍ，ｎ）＝１であるか否かを判断する。ｌw（ｍ，ｎ）＝１ではない場合には、当該ｍ番目の核ノードを根とする部分木のｎ番目のノードは核ノードではないと判断し、ステップＳ８０４に移行する。一方、ｌw（ｍ，ｎ）＝１であった場合には、当該ｍ番目の核ノードを根とする部分木のｎ番目のノードは核ノードであると判断し、ステップＳ８０５に移行する。
【０１１６】
また、以下の説明において、前記ｍ番目の核ノードを根とする部分木のｎ番目のノードの前記局所番号ｌを、ｌ(ｍ，ｎ)と表記する。また、前記ｍ番目の核ノードを根とする部分木のｎ番目のノードのノード種別情報ｒを、ｒ（ｍ，ｎ）と表記する。
【０１１７】
次に、ステップＳ８０４において、ＣＰＵ１２は、前記ノード種別情報ｒ（ｍ，ｎ）に核ノードではないことを示す０を代入すると共に、前記局所番号ｌ(ｍ，ｎ)に、ステップＳ８０２で算出したｌw（ｍ，ｎ）を代入することによって当該ノードの局所番号としてｌw（ｍ，ｎ）を付与し、ステップＳ８０９に移行する。
【０１１８】
一方、ステップＳ８０５において、ＣＰＵ１２は、ステップＳ６で付与された前記ｍ番目の核ノードの大域番号ｇが１であるか否かを判断する。前記ｍ番目の核ノードの大域番号ｇが１であった場合には、当該ｍ番目の核ノードを根とする部分木のｎ番目のノードは前記有向木Ｔの根であると判断し、ステップＳ８０６に移行する。また、前記ｍ番目の核ノードの大域番号ｇが１でなかった場合には、当該ノードは前記有向木Ｔの根以外の核ノードであると判断し、ステップＳ８０７に移行する。
【０１１９】
次に、ステップＳ８０６において、当該ｍ番目の核ノードを根とする部分木のｎ番目のノードは前記有向木Ｔの根であるので、ＣＰＵ１２は、当該ノードの局所番号ｌ(ｍ，ｎ)にｌw（ｍ，ｎ）を代入することによって当該ノードの局所番号としてｌw（ｍ，ｎ）すなわち１を付与し、ステップＳ８０８に移行する。
【０１２０】
一方、ステップＳ８０７において、当該ｍ番目の核ノードを根とする部分木のｎ番目のノードは前記有向木Ｔの根以外の核ノードであるので、ＣＰＵ１２は、前記ステップＳ３で生成された核木において、前記ｍ番目の核ノードの親の核ノードを求め、前記有向木Ｔにおいて、前記求めた親の核ノードを根とする部分木で、当該部分木の部分木出次最大値ｆを出次数として、当該ｍ番目の核ノードを根とする部分木のｎ番目のノードの局所番号をＵＩＤを用いて算出し、前記算出したＵＩＤ番号を、ｌ（ｍ，ｎ）に代入する。
【０１２１】
この場合、前記ｍ番目の核ノードの局所番号ｌが、前記ｍ番目の核ノードを根とする部分木の上位の部分木で算出された局所番号ｌとなる。例えば、ノード７について、図１０の核木から親はノード１であり、図１３の有向木Ｔから、ノード１を根とする部分木でのノード７のＵＩＤ番号は３であるため、ノード７の局所番号として３が付与される。
【０１２２】
なお、ステップＳ８０７において、前記ｍ番目の核ノードを根とする部分木のｎ番目のノードについて、前記ｍ番目の核ノードを根とする部分木の上位の部分木でＵＩＤ番号がすでに計算された場合には、再度計算することなく前記計算されたＵＩＤ番号を当該ノードの局所番号として付与しても良い。
【０１２３】
次に、ステップＳ８０８において、ＣＰＵ１２は、当該前記ｍ番目の核ノードを根とする部分木の前記ｎ番目のノードのノード種別情報ｒ（ｍ，ｎ）に核ノードであることを示す１を代入する。
【０１２４】
なお、本実施形態においては、ノード種別情報ｒは１と０によって、核ノードであるか否かを示しているが、ノード種別情報ｒは核ノードであるか否かを示すことが出来れば他の記号、文字列等を用いてもよく、例えば核ノードの場合は”ｔｒｕｅ”核ノードではない場合は”ｆａｌｓｅ”とする等の他の方法を用いても良い。
【０１２５】
次に、ステップＳ８０９において、ＣＰＵ１２は、ｎ＝Ｎ(ｍ)であるか否かを判断する。ｎ＝Ｎ(ｍ)でなかった場合は、ステップＳ８１０に移行する。ｎ＝Ｎ(ｍ)であった場合には、前記ｍ番目の核ノードを根とする部分木のすべてのノードについて、局所番号ｌとノード種別情報ｒとが付与されているので、図３のステップＳ９に移行する。
【０１２６】
一方、ステップＳ８１０において、ＣＰＵ１２は、ｎ＋１をｎに代入してステップＳ８０２へ戻る。このようにして、ステップＳ８０２〜Ｓ８１０を繰り返すことにより、前記ｍ番目の核ノードを根とする部分木のすべてのノードについて、局所番号ｌとノード種別情報ｒとが付与され、さらに前記ｍ番目の核ノードについて、当該核ノードの大域番号ｇ、局所番号ｌ及び当該核ノードを根とする部分木の部分木出次最大値ｆが生成される。
【０１２７】
次に、図３のステップＳ９において、ＣＰＵ１２は、ｍ＝ｍＭＡＸであるか否かを判断する。ｍ＝ｍＭＡＸでなかった場合は、ステップＳ１０に移行する。ｍ＝ｍＭＡＸであった場合には、前記有向木Ｔのすべてのノードについて前記局所番号ｌが付与されているので、ステップＳ１１に移行する。
【０１２８】
次に、ステップＳ１０において、ｍ＋１をｍに代入してステップＳ６へ戻る。このようにして、ステップＳ６〜Ｓ１０を繰り返すことにより、前記有向木Ｔのすべてのノードについて大域番号ｇ、局所番号ｌ及びノード種別情報ｒが付与され、前記有向木Ｔのすべてのノードについて前記識別番号が付与されたことになり、前記有向木Ｔのノードを一意に識別可能になる。また、前記各ノード毎に、当該核ノードを根とする部分木の部分木最大出次数ｆが関連付けられる。例えば、図１４の有向木Ｔの前記識別番号は、括弧書きで記載された番号になる。
【０１２９】
また、前記有向木Ｔのすべての核ノードについて、当該核ノードの大域番号ｇ、局所番号ｌ及び当該核ノードを根とする部分木の部分木出次最大値ｆが生成されたことになる。
【０１３０】
次に、ステップＳ１１において、ＣＰＵ１２は、ステップＳ４で生成された前記核ノードの大域番号ｇ、ステップＳ８で生成された前記核ノードの局所番号ｌ及びステップＳ７で生成された前記核ノードを根とする部分木の部分木出次最大値ｆを、前記有向木Ｔのすべての核ノード毎に関連付け、さらにステップＳ３で生成された前記核木出次最大値ｋを加えて核木情報記憶テーブルを生成し、核木情報記憶部２０２に記憶する。図１５は、前記核木情報記憶テーブルの一例を示す図である。
【０１３１】
以上の動作によって、前記木構造で表わされたデータのノードに前記識別番号が付与され、さらに前記核木情報記憶テーブルが生成される。
【０１３２】
次に、前記識別番号付与装置が、前記有向木Ｔのノードの親を示す識別番号を算出する場合の動作について説明する。図１６は、図２に示す識別番号付与装置が前記識別番号を付与された有向木Ｔ（図１４参照）に含まれるノードの１について、当該ノードの親を示す前記識別番号を算出する動作を説明するためのフローチャートである。
【０１３３】
ステップＳ１２において、ＣＰＵ１２は、例えばユーザーが入力部１５のキーボード等から有向木Ｔに含まれるノードの一に付与された識別番号（ｇｉ，ｌｉ，ｒｉ）を入力することによって、前記識別番号（ｇｉ，ｌｉ，ｒｉ）を処理対象として、以降の処理をおこなう。
【０１３４】
次に、ステップＳ１３において、ＣＰＵ１２は、ｒｉ＝１であるか否かを判断する。ｒｉ＝１でなかった場合は、前記識別番号（ｇｉ，ｌｉ，ｒｉ）のノードは核ノードではないと判断し、ステップＳ１４に移行する。ｒｉ＝１であった場合には、前記識別番号（ｇｉ，ｌｉ，ｒｉ）のノードは核ノードであると判断し、ステップＳ１５に移行する。
【０１３５】
次に、ステップＳ１４において、ＣＰＵ１２は、前記識別番号（ｇｉ，ｌｉ，ｒｉ）のノードの親を示す大域番号ｇpに、ｇｉを代入し、ステップＳ１６に移行する。これにより、前記識別番号（ｇｉ，ｌｉ，ｒｉ）のノードの親を示す大域番号ｇpが求められる。例えば、識別番号（４，９，０）のノードの親を示す大域番号ｇpは、４となる。
【０１３６】
一方、ステップＳ１５において、ＣＰＵ１２は、核木情報記憶部２０２に記憶されている核木情報記憶テーブルから核木出次最大値ｋを読み出して、（ｇｉ−２）／ｋ＋１を計算し、さらに前記計算結果の小数部を切り捨てて整数部を算出し、前記算出した値を前記大域番号ｇpに代入し、ステップＳ１６に移行する。これにより、前記識別番号（ｇｉ，ｌｉ，ｒｉ）のノードの親を示す大域番号ｇpが求められる。例えば、図１５の核木情報記憶テーブルから前記核木出次最大値ｋとして３が読み出され、さらに、識別番号（８，９，１）のノードの親を示す大域番号ｇpは、（８−２）／３＋１の整数部を取って、３となる。
【０１３７】
次に、ステップＳ１６において、ＣＰＵ１２は、前記核木情報記憶テーブルから、ステップＳ１４及びステップＳ１５で求めた大域番号ｇpに対応付けられた部分木出次最大値ｆを読み出して、大域番号ｇpの核ノードを根とする部分木の部分木出次最大値ｆｐを求め、ステップＳ１７に移行する。例えば、図１５の核木情報記憶テーブルから、大域番号ｇpが４の場合にはｆｐは３となり、大域番号ｇpが３の場合にはｆｐは３となる。
【０１３８】
次に、ステップＳ１７において、ＣＰＵ１２は、ステップＳ１６で算出された大域番号ｇpと、前記識別番号（ｇｉ，ｌｉ，ｒｉ）とから、（ｌｉ−２）／ｆｐ＋１を計算し、さらに前記計算結果の小数部を切り捨てて整数部を算出し、前記識別番号（ｇｉ，ｌｉ，ｒｉ）のノードの親を示す局所番号ｌｐに前記算出した値を代入し、局所番号ｌｐが求められる。本実施形態では、例えば、識別番号（４，９，０）のノードの親を示す局所番号ｌpは、（９−２）／３＋１の整数部を取って、３となり、識別番号（８，９，１）のノードの親を示す局所番号ｌpは、（９−２）／３＋１の整数部を取って、３となる。
【０１３９】
次に、ステップＳ１８において、ＣＰＵ１２は、ステップＳ１７で算出された局所番号ｌｐが１であるか否かを判定する。局所番号ｌｐが１でない場合は、前記識別番号（ｇｉ，ｌｉ，ｒｉ）のノードの親は核ノードではないと判断し、ステップＳ１９へ移行する。また、局所番号ｌｐが１である場合は、前記識別番号（ｇｉ，ｌｉ，ｒｉ）のノードの親は核ノードであると判断し、ステップＳ２０へ移行する。
【０１４０】
次に、ステップＳ１９において、ＣＰＵ１２は、前記識別番号（ｇｉ，ｌｉ，ｒｉ）のノードの親が核ノードであるか否かを示すノード種別情報ｒｐに０を代入し、ステップＳ２２へ移行する。これにより、前記識別番号（ｇｉ，ｌｉ，ｒｉ）のノードの親は、核ノードではないことが示される。例えば、識別番号（４，９，０）のノードの親には、ノード種別情報ｒｐとして０が代入される。
【０１４１】
一方、ステップＳ２０において、ＣＰＵ１２は、前記核木情報記憶部２０２に記憶されている核木情報記憶テーブルから大域番号ｇｉに対応付けられている局所番号ｌを読み出して、ステップＳ１７で算出した局所番号ｌｐに、改めて前記読み出したｌを代入し、ステップＳ２１へ移行する。例えば、識別番号（２，２，０）のノードの親を示す識別番号は、ステップＳ１４でｇpは２となり、ステップＳ１７でｌｐは１となるため、ステップＳ２０で図１５の核木情報記憶テーブルから、大域番号２に対応付けられている局所番号２が読み出され、改めてｌｐは２となる。
【０１４２】
次に、ステップＳ２１において、ＣＰＵ１２は、ノード種別情報ｒｐに１を代入し、ステップＳ２２へ移行する。これにより、前記識別番号（ｇｉ，ｌｉ，ｒｉ）のノードの親は、核ノードであることが示される。
【０１４３】
次に、ステップＳ２２において、ＣＰＵ１２は、ステップＳ１３〜Ｓ２１で算出したｇp、ｌp、ｒpに基づいて、ステップＳ１２で入力された識別番号（ｇｉ，ｌｉ，ｒｉ）のノードの親を示す識別番号を、（ｇp，ｌp，ｒp）とする。例えば、識別番号（４，９，０）のノードの親を示す識別番号は、（４，３，０）となり、識別番号（８，９，１）のノードの親を示す識別番号は、（３，３，０）となり、識別番号（２，２，０）のノードの親を示す識別番号は、（２，２，１）となる（図１４参照）。
【０１４４】
なお、本実施形態により前記有向木Ｔのノードの親を示す識別番号を算出する場合の例として、前記大域番号ｇ、前記局所番号ｌ、前記ノード種別情報ｒとからなる識別番号を使用する例を示したが、前記識別番号は、当該ノードの親を特定する情報を備えたものであれば良く、例えば、当該ノードの番号と、当該ノードの親の番号とからなる識別番号等であってもよい。
【０１４５】
次に、本発明に係る識別番号付与装置をＸＭＬ文書の検索処理に用いた場合の動作を例として説明する。
【０１４６】
図２３は、ＸＭＬ文書の例である。ＸＭＬ文書では、開始タグから終了タグまでを要素と呼び、例えば、開始タグ＜FOOTNOTE＞から終了タグ＜／FOOTNOTE＞までがFOOTNOTE要素と呼ばれ、開始タグ＜PAPER＞から終了タグ＜／PAPER＞までがPAPER要素と呼ばれる。
【０１４７】
図２３のＸＭＬ文書で例えば、子孫にFOOTNOTE要素を持つPAPER要素を検索する場合、図２３の２行目から１０行目の部分が検索の答えとなる。このような、子孫にｂ要素を持つａ要素を検索する場合、本願発明に係る識別番号付与装置を用いて以下のように検索を行う。
【０１４８】
図１７は図２３のＸＭＬ文書を有向木で表わし、ノードに本願発明に係る識別番号付与装置を用いて前記識別番号を付与したものである。図１７の有向木を用いて、例えば、子孫にｂ要素を持つａ要素を検索する場合、まず、図１７の有向木から前記識別番号と要素名とを一覧にして図１８の格納表を作成する。
【０１４９】
図１９は、前記図１８の格納表を用いて子孫にｂ要素を持つａ要素を検索する処理を説明するフローチャートである。なお、この検索処理は、図１に示す本実施形態による識別番号付与装置を構成している同じコンピュータ等で実行してもよく、あるいは本実施形態による識別番号付与装置を用いて前記識別番号を付与した有向木を生成した後、他のコンピュータ等で検索処理を行うことにしてもよい。
【０１５０】
まず、ステップＳ１００１において、ＣＰＵ１２は、前記格納表中の要素名がａの行の識別番号を集合Ａに格納し、ステップＳ１００２に移行する。本実施例では、例えば、子孫にFOOTNOTE要素を持つPAPER要素を検索する場合、集合Ａには要素名がPAPERである計２個のノード（２，２，１）、（４，４，１）が格納される（図１８参照）。
【０１５１】
次に、ステップＳ１００２において、ＣＰＵ１２は、前記格納表中の要素名がｂの行の識別番号を集合Ｄに格納し、ステップＳ１００３に移行する。本実施例では、例えば、集合Ｄには要素名がFOOTNOTEである計８個のノード（２，８，０）、（２，９，０）、（２，１１，０）、（２，１２，０）、（３，８，０）、（３，９，０）、（３，１１，０）、（３，１２，０）が格納される。
【０１５２】
次に、ステップＳ１００３において、ＣＰＵ１２は、図１６のステップＳ１２に前記集合Ｄの識別番号を入力して親のノードの識別番号を算出し、前記集合Ａのノードに到達するまで親を遡って先祖となるノードの識別番号を算出し、前記集合Ａのノードに到達した場合、前記到達した集合Ａのノードを検索の答えとする。
【０１５３】
特に、図１７に記載した有向木で、子孫にFOOTNOTE要素を持つPAPER要素を検索する場合を示した例のように、前記集合Ａに格納されているノードが核ノードである場合には、前記集合Ｄに格納されている前記識別番号の大域番号ｇが前記集合Ａに格納されているいづれかのノードの前記大域番号ｇと同じであるか、前記識別番号を遡って算出する過程で前記集合Ａに格納されているいづれかのノードの前記大域番号ｇと同じになった場合には、その時点で前記大域番号ｇと同じになった前記集合Ａのノードが検索の答えとして求めることができ、より高速に検索を行うことが出来る。本実施例では、前記集合Ｄに格納されたノード（２，８，０）、（２，９，０）、（２，１１，０）、（２，１２，０）の大局番号２と、前記集合Ａに格納された（２，２，１）の大局番号２が同じであるため、即座にノード（２，２，１）が検索の答えとして求められる。
【０１５４】
一方、従来例による検索を行う場合には、子孫であるノードの識別番号から当該ノードの先祖を特定する識別番号を求めることができないため、有向木を巡回して検索する処理が必要になり、本願発明による例と比較して、高速に検索を行うことが容易でない。
【０１５５】
次に、本願発明に係る前記識別番号を、再帰的に生成し、付与する場合のＣＰＵ１２の動作について、図２０に記載のフローチャートを用いて説明する。本願発明に係る前記識別番号は、前記大域番号ｇ、前記局所番号ｌ、前記ノード種別情報ｒの組み合わせによって、ノードを識別するため、前記大域番号ｇ、前記局所番号ｌ、前記ノード種別情報ｒは、より小さい数字で表わすことができる。しかし、部分木が非常に大きい場合には、前記識別番号であっても、大きな数字を使用する必要がある。そこで、以下のように前記生成した部分木をさらに分割し、前記大域番号ｇを再帰的に生成した再帰大域番号を付与することによって、前記識別番号をより小さな数字で表わすことが可能になる。
【０１５６】
まず、ステップＳ３０において、ＣＰＵ１２は、前記大域番号ｇが付与された前記部分木を基に、前記部分木を分割し、前記分割した新たな部分木を再帰部分木とし、前記大域番号ｇを前記再帰部分木の再帰大域番号ｓとしてステップＳ３１に移行する。例えば、図２１の有向木Ｖに対して、前記大域番号ｇが２であるノード２を根とする部分木から、ノード３を根とする部分木とノード１０を根とする部分木とが分割され、ノード３を根とする再帰部分木及びノード１０を根とする再帰部分木となる。また、ノード３を根とする再帰部分木及びノード１０を根とする再帰部分木の再帰大域番号ｓは２となる。
【０１５７】
次に、ステップＳ３１において、ＣＰＵ１２は、前記再帰部分木に対して新たに大域番号ｇを生成し、前記再帰大域番号ｓと前記新たな大域番号ｇとを前記再帰部分木のノードに付与し、ステップＳ３２に移行する。例えば、前記有向木Ｖにおいて、ノード１０を根とする再帰部分木のノードには、前記再帰大域番号ｓとして２が、前記大域番号ｇとして３が付与される。
【０１５８】
次に、ステップＳ３２において、ＣＰＵ１２は、前記再帰部分木をさらに分割して再帰的に大域番号ｇを生成するか否かを判断する。さらに分割しない場合は、ステップＳ３３に移行し、さらに分割して前記再帰部分木のノードに対してさらに再帰的に識別番号を付与する場合は、ステップＳ３４に移行する。例えば、前記再帰部分木に新たに分割可能な部分木がない場合にはステップＳ３３に移行する等の条件に基づき判断を行う。
【０１５９】
次に、ステップＳ３３において、ＣＰＵ１２は、前記再帰部分木のノードに対して前記局所番号ｌを生成し、前記再帰大域番号ｓと、前記大域番号ｇと、前記局所番号ｌとを含む識別番号を付与し、処理を終了する。例えば、前記有向木Ｖにおいて、ノード１５には再帰大域番号ｓとして２が、大域番号ｇとして３が、局所番号ｌとして６が付与される。また、ノード１５は核ノードではないので、ノード種別情報ｒとして０を付与し、例えば、ノード１５の識別番号をｓ、ｇ、ｌ、ｒの順に並べて（２，３，６，０）のように表わすことができる。
【０１６０】
次に、ステップＳ３４において、ＣＰＵ１２は、前記再帰部分木を基に、前記再帰部分木を分割して新たな再帰部分木とし、前記再帰大域番号ｓと前記大域番号ｇとを含む番号を新たな再帰部分木の再帰大域番号ｓとし、ステップＳ３５に移行する。
【０１６１】
例えば、有向木Ｖに対して、ノード１０を根とする前記再帰部分木の前記再帰大域番号ｓは２、前記大域番号ｇは３であるので、ノード１０を根とする前記再帰部分木からノード１１を根とする前記再帰部分木とノード１４を根とする前記再帰部分木とが分割され、ノード１１を根とする前記再帰部分木及びノード１４を根とする前記再帰部分木の新たな再帰大域番号ｓは、２と３を含む番号、例えば（２，３）が前記再帰大域番号ｓとされる。
【０１６２】
次に、ステップＳ３５において、ＣＰＵ１２は、前記新たな再帰部分木に対して新たな前記大域番号ｇを生成し、前記新たな再帰大域番号ｓと前記新たな大域番号ｇを前記新たな再帰部分木のノードに付与し、ステップＳ３６に移行する。例えば、前記有向木Ｖにおいて、ノード１４を根とする前記新たな再帰部分木のノードには、再帰大域番号ｓとして（２，３）が、大域番号ｇとして３が付与される。
【０１６３】
次に、ステップＳ３６において、ＣＰＵ１２は、前記新たな再帰部分木をさらに分割して再帰的に大域番号ｇを生成するか否かを判断する。さらに分割しない場合は、ステップＳ３７に移行し、さらに分割して前記新たな再帰部分木のノードに対してさらに再帰的に識別番号を付与する場合は、ステップＳ３４に移行する。以上のように、ＣＰＵ１２は、前記再帰部分木の分割と、前記大域番号ｇの付与を繰り返し行い、再帰大域番号ｓとして新たな大域番号ｇを追加する処理を繰り返すことで、前記有向木Ｖを再帰的に分割すると共に再帰的に大域番号を付与することができる。
【０１６４】
次に、ステップＳ３７において、ＣＰＵ１２は、最後に生成された前記再帰部分木のノードに対して前記局所番号ｌを生成し、最後に生成された前記再帰大域番号ｓと、最後に生成された前記大域番号ｇと、前記局所番号ｌとを含む識別番号を最後に生成された前記再帰部分木のノードに付与し、処理を終了する。例えば、前記有向木Ｖにおいて、ノード１５には前記再帰大域番号ｓとして（２，３）が、前記大域番号ｇとして３が、前記局所番号ｌとして２が付与される。また、ノード１５は核ノードではないので、ノード種別情報ｒとして０を付与し、例えば、ノード１５の識別番号をｓ、ｇ、ｌ、ｒの順に並べて（２，３，３，２，０）のように表わすことができる。
【０１６５】
以上のようにして、前記識別番号を再帰的に生成し、より小さい数字でノードを識別可能にすることができる。
【０１６６】
【発明の効果】
本発明によれば、データ構造を表わす有向木のノードを、前記有向木を分割して生成された部分木の１を識別可能な大域番号と、前記部分木のノードの一を識別可能な局所番号とを有する識別番号によって、一意に識別可能となる。
【０１６７】
また、前記識別番号は、より小さな数字で表わすことができるので、コンピュータで整数表現することがより容易になる。
【０１６８】
また、前記識別番号で識別されたノードの親を当該ノードの識別番号から算出できるので、当該ノードの親を効率よく検索できる。
【０１６９】
また、前記有向木を再帰的に分割し、再帰的に前記大域番号を生成して、前記識別番号が前記再帰的に生成された前記大域番号を含んだ番号とすることにより、前記識別番号を、さらに小さな数字で表わすことが可能になる。
【図面の簡単な説明】
【図１】本発明の一実施形態を説明するための構成図である。
【図２】本発明の一実施形態を説明するためのブロック図である。
【図３】本発明の一実施形態に係る識別番号付与動作を説明するためのフローチャートである。
【図４】本発明の一実施形態を説明するためのデータ構造例の図である。
【図５】本発明の一実施形態に係る核ノード選択動作を説明するためのフローチャートである。
【図６】本発明の一実施形態に係る核ノード選択動作を説明するためのフローチャートである。
【図７】本発明の一実施形態を説明するためのデータ構造例の図である。
【図８】本発明の一実施形態を説明するためのデータ構造例の図である。
【図９】本発明の一実施形態を説明するためのデータ構造例の図である。
【図１０】本発明の一実施形態を説明するためのデータ構造例の図である。
【図１１】本発明の一実施形態を説明するためのデータ構造例の図である。
【図１２】本発明の一実施形態に係る局所番号付与動作を説明するためのフローチャートである。
【図１３】本発明の一実施形態を説明するためのデータ構造例の図である。
【図１４】本発明の一実施形態を説明するためのデータ構造例の図である。
【図１５】本発明の一実施形態を説明するためのデータテーブル例の図である。
【図１６】本発明の一実施形態に係る親ノードの識別番号算出動作を説明するためのフローチャートである。
【図１７】本発明の一実施形態を説明するためのデータ構造例の図である。
【図１８】本発明の一実施形態を説明するための格納表の一例の図である。
【図１９】本発明の一実施形態に係る動作を説明するためのフローチャートである。
【図２０】本発明の一実施形態に係る再帰的番号付与動作を説明するためのフローチャートである。
【図２１】本発明の一実施形態を説明するためのデータ構造例の図である。
【図２２】従来例によるデータ構造例の図である。
【図２３】従来例による木構造を持ったデータの例を示した図である。
【図２４】従来例によるデータ構造例の図である。
【符号の説明】
１１    ＲＯＭ
１２    ＣＰＵ
１３    ＲＡＭ
１４    外部記憶装置
１５    入力部
１６    表示部
１００  制御部
１０１  大域分割部
１０２  局所番号付与部
１０３  識別番号付与部
１０４  核木情報処理部
１０５  親識別番号算出部
１０６  再帰大域番号付与部
１０７  再帰的識別制御部
１０８  核ノード選択部
１０９  大域番号付与部
１１０  部分木生成部
１１１  核木生成部
１１２  特定ノード選択部
１１３  特定有向木生成部
１１４  核ノード選択制御部
１１５  部分木最大出次数算出部
１１６  親大域番号算出部
１１７  親局所番号算出部
１１８  ＸＭＬデータ読み出し部
２００  記憶部
２０１  ＸＭＬ文書記憶部
２０２  核木情報記憶部
【図１】
0003824956.tif 000002
【図２】
0003824956.tif 000003
【図３】
0003824956.tif 000004
【図４】
0003824956.tif 000005
【図５】
0003824956.tif 000006
【図６】
0003824956.tif 000007
【図７】
0003824956.tif 000008
【図８】
0003824956.tif 000009
【図９】
0003824956.tif 000010
【図１０】
0003824956.tif 000011
【図１１】
0003824956.tif 000012
【図１２】
0003824956.tif 000013
【図１３】
0003824956.tif 000014
【図１４】
0003824956.tif 000015
【図１５】
0003824956.tif 000016
【図１６】
0003824956.tif 000017
【図１７】
0003824956.tif 000018
【図１８】
0003824956.tif 000019
【図１９】
0003824956.tif 000020
【図２０】
0003824956.tif 000021
【図２１】
0003824956.tif 000022
【図２２】
0003824956.tif 000023
【図２３】
0003824956.tif 000024
【図２４】
0003824956.tif 000025