(57)【要約】【課題】ハイパーテキスト構造に対応する木構造の作成において、木構造にできるだけ多くの文書が現れるようにする。【解決手段】部分木処理部１６は木構造要求２００に従い根ノードを選択し、木構造データ作成部１６４はその根ノードを起点に、ハイパーテキスト構造記憶部１２内のハイパーテキスト構造をたどることで部分木の木構造データを作成し、木構造データ記憶部１８に格納する。未出現文書検出部１６６は、ハイパーテキスト構造内の文書のうち木構造データ記憶部１８内の木構造データ群に含まれない文書を検出する。根ノード選択部１６２がその未出現の文書群の中から次の根ノードを選択し、木構造データ作成部１６４がその根ノードについての部分木を作成する。これを繰り返した後、統合制御部２０が木構造データ記憶部１８内の各部分木の木構造データを統合し、統合木構造データを作成する。【選択図】図１
2005157859.tif 000002
【特許請求の範囲】
【請求項１】
文書群が構成するハイパーテキスト構造の情報を記憶するハイパーテキスト構造記憶部と、
与えられた文書群から、根ノードとする文書を選択する根ノード選択部と、
前記根ノード選択部で選択された文書を起点としてそれぞれ前記ハイパーテキスト構造のリンクをたどることにより、該文書を根ノードとする木構造データを作成し、木構造記憶部に記憶する木構造作成部と、
前記ハイパーテキスト構造に含まれる文書群から、前記木構造記憶部に記憶された木構造データ中に含まれない未出現文書を検出し、検出した未出現文書群を根ノードの選択範囲として前記根ノード選択部に与える未出現文書検出部と、
所定の終了条件が満足されるまで前記根ノード選択部及び前記木構造作成部及び前記未出現文書検出部に処理を繰り返し実行させ、前記終了条件が満足されたときに前記木構造記憶部に記憶されている各木構造データを統合して、統合木構造データを作成し出力する統合制御部と、
を備える木構造データ作成装置。
【請求項２】
前記所定の終了条件は、前記未出現文書検出部で前記未出現文書が検出されなくなることである、ことを特徴とする請求項１記載の木構造データ作成装置。
【請求項３】
前記根ノード選択部が前記選択範囲として与えられた未出現文書群から選択する根ノードの数は１であることを特徴とする請求項１記載の木構造データ作成装置。
【請求項４】
前記ハイパーテキスト構造を構成する文書群のうち、基準とすべき基準文書の指定を受け付けるための基準文書指定部、を更に備え、前記統合制御部は、前記根ノード選択部に、前記基準文書指定部で受け付けた基準文書を最初の根ノードとして選択させることを特徴とする請求項１記載の木構造データ作成装置。
【請求項５】
前記統合制御部は、前記統合木構造データに含まれる前記各木構造データが、前記基準文書を根ノードとする木構造データであるか、前記基準文書以外の文書を根ノードとする木構造データであるか、を示す情報を前記統合木構造データに組み込むことを特徴とする請求項４記載の木構造データ作成装置。
【請求項６】
前記木構造作成部は、作成中の木構造データに組み込もうとする文書が、前記木構造記憶部内に既存の木構造データの根ノードである場合に、該既存の木構造データを前記木構造データ記憶部から削除する、
ことを特徴とする請求項１記載の木構造データ作成装置。
【請求項７】
前記木構造作成部は、前記作成中の木構造データにおける該文書の位置に前記既存の木構造データを組み込む、
ことを特徴とする請求項６記載の木構造データ作成装置。
【請求項８】
前記統合制御部は、前記木構造記憶部に記憶された各木構造データの根ノードの文書のＵＲＬに基づき、それら各文書のＵＲＬの階層構造を示す上部木構造データを作成し、前記木構造記憶部に記憶された各木構造データを該上部木構造データと併合することにより前記統合木構造データを作成する、
ことを特徴とする請求項１記載の木構造データ作成装置。
【請求項９】
前記統合制御部が前回作成した統合木構造データにおける、各文書の木構造上の深さを記憶する深さ記憶部を更に備え、今回の統合木構造データの作成する際に、前記根ノード選択部が、前記与えられた文書群のうち前記深さ記憶部に記録された深さの最も浅いものの中から前記根ノードを選択する、
ことを特徴とする請求項１記載の木構造データ作成装置。
【請求項１０】
（ａ）文書群が構成するハイパーテキスト構造の情報を収集し、ハイパーテキスト構造記憶部に記憶するステップと
（ｂ）根ノード選択部が、与えられた文書群のうち、根ノードとする文書を選択するステップと、
（ｃ）根ノードとして選択された文書を起点としてそれぞれ前記ハイパーテキスト構造のリンクをたどることにより、該文書を根ノードとする木構造データを作成し、木構造記憶部に記憶するステップと、
（ｄ）前記ハイパーテキスト構造に含まれる文書群から、前記木構造記憶部に記憶された木構造データ中に含まれない未出現文書を検出し、検出した未出現文書群を根ノードの選択範囲として前記根ノード選択部に与えるステップと、
（ｅ）所定の終了条件が満足されるまで前記ステップ（ｂ），（ｃ），（ｄ）を繰り返し実行し、前記終了条件が満足されたときに前記木構造記憶部に記憶されている各木構造データを統合して、統合木構造データを作成し出力するステップと、
を含む木構造データ作成方法。
【請求項１１】
コンピュータシステムに、
（ａ）文書群が構成するハイパーテキスト構造の情報を収集し、ハイパーテキスト構造記憶部に記憶するステップと
（ｂ）根ノード選択部が、与えられた文書群のうち、根ノードとする文書を選択するステップと、
（ｃ）根ノードとして選択された文書を起点としてそれぞれ前記ハイパーテキスト構造のリンクをたどることにより、該文書を根ノードとする木構造データを作成し、木構造記憶部に記憶するステップと、
（ｄ）前記ハイパーテキスト構造に含まれる文書群から、前記木構造記憶部に記憶された木構造データ中に含まれない未出現文書を検出し、検出した未出現文書群を根ノードの選択範囲として前記根ノード選択部に与えるステップと、
（ｅ）所定の終了条件が満足されるまで前記ステップ（ｂ），（ｃ），（ｄ）を繰り返し実行し、前記終了条件が満足されたときに前記木構造記憶部に記憶されている各木構造データを統合して、統合木構造データを作成し出力するステップと、
を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ハイパーリンク構造をなす文書群の関係を木構造で表現するための方法及び装置に関する。
【背景技術】
【０００２】
ＷＷＷ（ワールド・ワイド・ウェブ）上の文書群は、文書をノードとし、文書間のリンクをアークとするグラフ構造をなしている。このグラフ構造は、ハイパーテキスト構造或いはハイパーリンク構造とも呼ばれる。ハイパーテキスト構造は、リンクにより任意の文書を容易に結びつけることができるという利点があるが、基本的にネットワーク構造であるため、文書数が増えて文書間の関係が複雑になると、人間が文書間の関係を把握することが困難となる。
【０００３】
これに対し、ハイパーテキスト構造を木（ツリー）構造に簡素化して表示する方法が従来より用いられている。特許文献１及び２には、文書群が構成するハイパーテキスト構造を、文書をノードとしリンクをエッジとした木構造の形式で表示するシステムが開示されている。
【０００４】
また、アドビシステムズ社のウェブサイト管理ツールである「GoLive」は、ＷＷＷ上で始点文書を指定すると、その文書から順にリンクをたどって行くことでハイパーテキスト構造を調べ、そのハイパーテキスト構造中の１文書を指定すると、そのハイパーテキスト構造からその文書を根ノードとする木構造を作成して表示する機能を備えている。
【０００５】
【特許文献１】特開平４−３２１１４４号公報
【特許文献２】特開平１０−２２２４１５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
上記従来技術はいずれも、グラフ構造であるハイパーテキスト構造を、指定された１つの文書を根（ルート）ノードとする木構造に変換するものである。しかしながら、一般にグラフ構造は、「あるノードＡを起点としてリンクを辿っていったときに、該グラフ構造のすべてのノードに到達できる」という条件を満たすノードＡが存在するとは限らない。例えば、図５に示すようなハイパーテキスト構造（この構造ではノードＡ〜Ｇが文書を示し、矢印のアークがリンクを示す。矢印の向きがリンクの方向を示す）の場合、どの文書を起点（根ノード）に選んでも、全文書を網羅する木構造を作成することはできない。
【０００７】
例えば、ウェブサイトや企業のイントラネット上に存在するＨＴＭＬ(HyperText Markup Language)文書群のなすハイパーテキスト構造を木構造表示する場合、ウェブサイトやイントラネット上に存在する文書群ができるだけ網羅的に現れる木構造表示が好ましいが、上記従来技術ではこのような網羅的な木構造表示が実現できるとは限らなかった。
【課題を解決するための手段】
【０００８】
本発明に係る装置は、文書群が構成するハイパーテキスト構造の情報を記憶するハイパーテキスト構造記憶部と、与えられた文書群のうち、根ノードとする文書を選択する根ノード選択部と、前記根ノード選択部で選択された文書を起点としてそれぞれ前記ハイパーテキスト構造のリンクをたどることにより、該文書を根ノードとする木構造データを作成し、木構造記憶部に記憶する木構造作成部と、前記ハイパーテキスト構造に含まれる文書群から、前記木構造記憶部に記憶された木構造データ中に含まれない未出現文書を検出し、検出した未出現文書群を根ノードの選択範囲として前記根ノード選択部に与える未出現文書検出部と、所定の終了条件が満足されるまで前記根ノード選択部及び前記木構造作成部及び前記未出現文書検出部に処理を繰り返し実行させ、前記終了条件が満足されたときに前記木構造記憶部に記憶されている各木構造データを統合して、統合木構造データを作成し出力する統合制御部と、を備える。
【０００９】
ここで、根ノード選択部が一度に選択する根ノードの数は複数であってもよい。
【００１０】
また、前記所定の終了条件は、例えば、前記未出現文書検出部で前記未出現文書が検出されなくなることである。
【００１１】
好適な態様では、前記根ノード選択部が前記選択範囲として与えられた未出現文書群から選択する根ノードの数である前記所定数は、１である。
【００１２】
別の好適な態様では、木構造データ作成装置は、前記ハイパーテキスト構造を構成する文書群のうち、基準とすべき基準文書の指定を受け付けるための基準文書指定部、を更に備え、前記統合制御部は、前記根ノード選択部に、前記基準文書指定部で受け付けた基準文書を最初の根ノードとして選択させる。
【００１３】
更に好適な態様では、前記統合制御部は、前記統合木構造データに含まれる前記各木構造データが、前記基準文書を根ノードとする木構造データであるか、前記基準文書以外の文書を根ノードとする木構造データであるか、を示す情報を前記統合木構造データに組み込む。
【００１４】
別の好適な態様では、前記木構造作成部は、作成中の木構造データに組み込もうとする文書が、前記木構造記憶部内に既存の木構造データの根ノードである場合に、該既存の木構造データを前記木構造データ記憶部から削除する。
【００１５】
更に好適な態様では、前記木構造作成部は、前記作成中の木構造データにおける該文書の位置に前記既存の木構造データを組み込む。
【００１６】
別の好適な態様では、前記統合制御部は、前記木構造記憶部に記憶された各木構造データの根ノードの文書のＵＲＬに基づき、それら各文書のＵＲＬの階層構造を示す上部木構造データを作成し、前記木構造記憶部に記憶された各木構造データを該上部木構造データと併合することにより前記統合木構造データを作成する。
【００１７】
別の好適な態様では、前記統合制御部が前回作成した統合木構造データにおける、各文書の木構造上の深さを記憶する深さ記憶部を更に備え、今回の統合木構造データの作成する際に、前記根ノード選択部が、前記与えられた文書群のうち前記深さ記憶部に記録された深さの最も浅いものの中から前記根ノードを選択する。
【発明を実施するための最良の形態】
【００１８】
以下、本発明を実施するための最良の形態（以下、実施形態と呼ぶ）を、図面を参照して説明する。
【００１９】
図１は、本発明に係る統合木構造データ作成装置の機能ブロック図である。この構成において、リンク情報収集部１０は、ＨＴＭＬ等のハイパーテキスト記述言語で記述されたウェブ文書群のハイパーテキスト構造を求める機能モジュールである。リンク情報収集部１０は、例えば、インターネット上にあるウェブ文書中のリンク記述をたどって行くことで、ウェブ文書間のリンク関係の情報（すなわちハイパーテキスト構造）を求める。
【００２０】
すなわちリンク情報収集部１０は、ウェブ文書を解析してアンカータグ（『<A HREF="...(リンク先のURLを示す文字列）">』）などの、ＨＴＭＬのリンク記述を検出し、リンク記述を見つけるとそのリンク記述に示されるリンク先ＵＲＬ(Uniform Resource Locator)の文書の取得処理を実行する。この取得処理では、該リンク先ＵＲＬで示される文書を要求する取得要求（GETリクエストなど）を発行する。この取得要求に対し、要求に係るＵＲＬの文書を管理するウェブサーバから該文書を取得できた場合、リンク情報収集部１０は、取得した文書に対して、上述したリンク記述の検出処理及びそのリンク先の取得処理を実行する。リンク情報収集部１０は、スタート地点として与えられた１以上のウェブ文書から解析を始め、上記のリンク記述の検出処理及びそのリンク先の取得処理を繰り返していくことで、ウェブ文書やそれらのリンク関係の情報を収集する。この繰り返しが、リンク情報収集部１０によるウェブの「巡回」である。リンク情報収集部１０は、この巡回の過程で取得したウェブ文書の実体データ（すなわちＨＴＭＬで記述された文書データ）を図示省略する文書格納装置へと格納し、同じく巡回処理の過程で検出したウェブ文書間のリンクの情報をハイパーテキスト構造記憶部１２へと格納する。これまでに説明したリンク情報収集部１０の機能は、ロボット検索型のサーチエンジンがウェブ文書を収集するために用いている既存のクローラー乃至スパイダーと同等のものである。
【００２１】
以上のようなリンク情報収集部１０による巡回処理により、ハイパーテキスト構造記憶部１２には、巡回処理の過程で検出したウェブ文書についての管理情報が登録された文書テーブルと、検出したリンクについての管理情報が登録されたリンクテーブルとが形成される。文書テーブルのデータ内容の一例を図２に、リンクテーブルのデータ内容の一例を図３に示す。
【００２２】
文書テーブルには、図２に示すように、検出したウェブ文書ごとに、その文書に割り当てた一意的な文書ＩＤ１０２、その文書のＵＲＩ(Uniform Resource Identifier)１０４（ＵＲＬでももちろんよい）、その文書が存在するか否かを示す状態情報１０６、及び文書格納装置に格納された文書データへのポインタ１０８が登録される。状態情報１０６が存在するのは、次のような理由からである。すなわち、リンク情報収集部１０の巡回処理の過程では、ウェブ文書が検出されるのは、スタート地点として与えられたウェブ文書を除き、他のウェブ文書中のリンク記述に示されるＵＲＬ（又はＵＲＩ）からである。しかし、そのＵＲＬには実際にはウェブ文書が存在しない（すなわち、取得要求に対してウェブサーバからウェブ文書が返されない）こともあり得る。したがって、リンク記述のＵＲＬから文書が取得できた場合は、状態情報１０６は「存在」となり、そうでない場合は「非存在」となる。
【００２３】
リンクテーブルには、図３に示すように、検出されたリンクごとに、そのリンクのリンク元のウェブ文書の文書ＩＤ（リンク元ＩＤ１１２）と、リンク先のウェブ文書の文書ＩＤ（リンク先ＩＤ１１４）が登録される。図３の例は、例えば、文書Ａの中から文書Ｂ及びＣへのリンク記述、文書Ｃの中から文書Ｅへのリンク記述が検出された場合のものである。リンク情報収集部１０は、ウェブ文書中からリンク記述を検出した場合、リンクテーブルに１つのエントリを追加し、当該ウェブ文書の文書ＩＤをそのエントリのリンク元に、そのリンク記述のＵＲＬが示すウェブ文書の文書ＩＤをリンク先に、それぞれ登録する。
【００２４】
リンク情報収集部１０は、定期的に、あるいは所定の収集開始条件が満足される毎に、リンク情報の収集処理を実行する。リンク情報収集部１０に対しては、収集処理の終了条件が設定可能であり、収集を開始した後その終了条件が満足されると、収集部１０は収集処理を終える。終了条件は、例えば、リンク探索の起点として指定された１乃至複数の文書から、リンクを介して辿りうるすべての文書を検出し終わった時、収集を終了する、等の条件である。なお、リンク情報の収集を行う範囲を限定（例えば予め登録された１乃至複数のドメインに限定するなど）することもできる。
【００２５】
要求処理部１４は、この統合木構造データ作成装置に対してＬＡＮ（ローカルエリアネットワーク）やインターネットなどのデータ通信ネットワークを介して接続されたクライアント装置から、木構造データの要求（木構造要求２００）を受け付けて処理する機能モジュールである。要求処理部１４は、クライアント装置から木構造要求２００を受け取った場合、統合制御部２０に対して統合木構造データ２０２の作成を命令する。
【００２６】
統合制御部２０は、その命令に応じ、部分木処理部１６を制御して統合木構造データ２０２を作成する。要求処理部１４は、統合制御部２０が作成した統合木構造データ２０２を受け取り、要求元のクライアント装置へ提供する。
【００２７】
部分木処理部１６は、統合木構造データ２０２が示す１つの大きな木構造（統合木構造）を構成する、個々の部分木の木構造データを作成するための機能モジュールである。部分木処理部１６は、根ノード選択部１６２，木構造データ作成部１６４，及び未出現文書検出部１６６を含む。
【００２８】
根ノード選択部１６２は、ハイパーテキスト構造記憶部１２の文書テーブルに登録されている文書の中から、部分木の根ノードとする文書を選択する機能モジュールである。
【００２９】
木構造データ作成部１６４は、根ノード選択部１６２が選択した根ノードの文書を起点に、ハイパーテキスト構造記憶部１２に記憶されたハイパーテキスト構造のリンクを探索することにより、その文書を根ノードとした木構造を示す木構造データを作成する。すなわち木構造データ作成部１６４は、根ノードのウェブ文書から順に、ハイパーテキスト構造記憶部１２のリンクテーブルに登録されたリンクを深さ優先探索又は幅優先探索でたどっていくことで、ウェブ文書群がなす木構造を求め、その木構造を示す木構造データを作成する。なお、ハイパーリンク構造から木構造を作成する方法は、上述の特許文献をはじめとして様々なものが提案されており、木構造データ作成部１６４はそれら従来手法を用いたものでよい。木構造データ作成部１６４が作成した木構造データは、木構造データ記憶部１８に蓄積される。
【００３０】
未出現文書検出部１６６は、次に作成する木構造データ（部分木）の根ノードの候補となる未出現文書を検出する機能モジュールである。未出現文書とは、ハイパーテキスト構造記憶部１２に記憶されたハイパーテキスト構造を構成する文書（すなわち文書テーブルに登録された文書）のうち、それまで木構造データ作成部１６４が作成した木構造データ群の中に１度も出現していない文書のことである。未出現文書検出部１６６で検出された未出現文書群は、根ノードの選択範囲の文書群として、根ノード選択部１６２に提供される。
【００３１】
この部分木処理部１６の処理手順を、図４を参照して説明する。
【００３２】
統合制御部２０から木構造データ群の生成を指示された場合、まず根ノード選択部１６２が、基準文書を根ノードとして選択する（Ｓ１０）。基準文書は、ハイパーテキスト構造の文書群の中でユーザが目印とする文書であり、ユーザが任意に選ぶことができる。例えばウェブサイトならばトップページが基準文書とされるであろう。基準文書は、複数選ぶこともできる。基準文書が複数ある場合、根ノード選択部１６２はそのすべてを根ノードに選択する。基準文書はＵＲＬ乃至ＵＲＩで特定することができる。この基準文書の情報は、予め根ノード選択部１６２に登録しておくこともできるし、統合木構造データ作成装置に対して作成要求を行う都度クライアント装置にてユーザが指定するようにすることもできる。後者の場合、ユーザが指定した基準文書の情報は、木構造要求２００に組み込まれ、要求処理部１４に送られ、統合制御部２０を介して根ノード選択部１６２に提供される。根ノード選択部１６２は、基準文書の文書ＩＤ又はＵＲＬを、根ノードを示す情報として木構造データ作成部１６４に提供する。
【００３３】
次に木構造データ作成部１６４が、その根ノードを起点として、ハイパーテキスト構造のリンクを辿ることで木構造データを作成し（Ｓ１２）、その木構造データを木構造データ記憶部１８に記憶する（Ｓ１４）。根ノード選択部１６２で複数の文書が根ノードとして選択された場合は、それら各文書を根ノードとした木構造データをそれぞれ作成し、木構造データ記憶部１８に記憶する。木構造データ記憶部１８への木構造データの記憶が完了すると、次に未出現文書検出部１６６が、ハイパーテキスト構造記憶部１２の文書テーブルに登録された文書群のうち、その時点で木構造データ記憶部１８に記憶されている木構造データ群の中に含まれない未出現文書を抽出する（Ｓ１６）。
【００３４】
この抽出処理で未出現文書が見つかった場合は（Ｓ１８の判定結果が肯定（Ｙ））、次に根ノード選択部１６２が、未出現文書検出部１６６が抽出した未出現文書群の中から、次の部分木の根ノードとする文書を、Ｎ個（Ｎは根ノード選択部１６２に予め設定された数）選択する（Ｓ２０）。極端な例としては、この選択処理は、与え得られた選択範囲のノードからランダムに選ぶものでもよい。もっと好適な選択方式については、後に改めて説明する。この処理で選択された根ノードの文書は木構造データ作成部１６４に渡され、Ｓ１２以降の処理が繰り返される。この繰り返しのループを一度通過するごとに、木構造データ記憶部１８には、Ｓ１２で作成されたＮ個の木構造データが追加されていくことになる。
【００３５】
このようにして、未出現文書が検出されなくなるまで（すなわちＳ１８の判定結果が否定（Ｎ）になるまで）、Ｓ１２〜Ｓ２０のループを繰り返す。未出現文書が検出されなくなるということは、ハイパーテキスト構造記憶部１２に記憶されたハイパーテキスト構造中のすべての文書が、木構造データ記憶部１８内の木構造データ群の中に含まれているということである。このような状態になった場合、部分木処理部１６は、統合制御部２０に部分木の木構造データ群の作成処理が完了した旨を通知する（Ｓ２２）。
【００３６】
以上、部分木処理部１６の処理手順の一例を説明した。部分木処理部１６から木構造データ群の作成完了の通知を受けた統合制御部２０は、木構造データ記憶部１８に記憶された木構造データ群を統合することで、統合木構造データを作成する。この統合木構造データの作成は、例えば、木構造データ記憶部１８内の各木構造データの根ノードを、１つの上位根ノード（スーパールートと呼ぶ）の子として接続するという方式などで可能である。
【００３７】
次に、本実施の形態による統合木構造データの作成処理について、具体例を挙げて説明する。
【００３８】
図５に示す、Ａ〜Ｇの７個の文書が構成するハイパーテキスト構造を例にとる。図２，３に例示した文書テーブル、リンクテーブルは、この構造の一部を示したものである。このハイパーテキスト構造のうち、文書Ａが基準文書として指定されていたとすると、木構造データ作成部１６４により、まず文書Ａを根とした部分木１８２（図６参照）を示す木構造データが作成され、木構造データ記憶部１８に格納される。すると、次に未出現文書検出部１６６が、ハイパーテキスト構造記憶部１２から、部分木１８２の中に現れていない文書（未出現文書）Ｄ，Ｆ，Ｇを検出する。これを受けて根ノード選択部１６２がその中から所定数の根ノードを選択する。ここでは、所定数は１であるとし、仮に文書Ｄが選択されたとする。すると、木構造データ作成部１６４が部分木１８４（文書Ｄのみからなる）を作成し、木構造データ記憶部１８に格納する。このような処理を、未出現文書が検出されなくなるまで繰り返すと木構造データ記憶部１８内には３つの部分木１８２，１８４，１８６の各木構造データが蓄積されることになる。そして、統合制御部２０は、これら３つの部分木を１つのスーパールートの子とした統合木構造を作成する。
【００３９】
この統合木構造のデータ内容を図７に示す。このデータは、統合木構造の各ノードごとに、ノードＩＤ３０２，ＵＲＬ３０４，表示データ３０６，及び子ノード情報３０８を含んでいる。ノードＩＤ３０２は、当該ノードの識別情報である。スーパールート以外は当該ノードに対応する文書の文書ＩＤをそのままノードＩＤとして用いることもできる。ＵＲＬ３０４は、当該ノードに対応する文書のＵＲＬである。これは、文書のデータにアクセスするための情報であればよく、ＵＲＬの代わりに、ＵＲＩなど他のタイプの情報を用いてもよい。表示データ３０６は、統合木構造を表示するに当たり、当該ノードを表す情報として表示するデータであり、例えばウェブ文書の場合はタイトルタグで示されたタイトルの文字列を表示データ３０６として用いることができる。スーパールートについては、表示データ３０６は無しでもよいし、ユーザが自分の希望する名前等を表示データ３０６として入力できるようにしてもよい。子ノード情報３０８は、当該ノードが持つ子ノードのＩＤのリストである。なお、図７に示す統合木構造データのデータ構造はあくまで一例に過ぎず、図７に示す以外のデータ項目を含めてもよい。
【００４０】
クライアント装置は、木構造要求２００に対する応答として、統合制御部２０からこのような統合木構造データ２０２を受け取り、このデータに基づき統合木構造の表示を行う。図７の統合木構造データに対応する木構造を表示した表示画面４００の表示例を図８に示す。表示される木構造は、スーパールートのノード４０４に対し、文書Ａ，Ｄ，Ｆに対応するノード４０２を根とする部分木が接続されたものであり、各ノードには、そのノードの表示データ３０６が表示される。また、表示画面４００上の各ノードは、それぞれ対応する文書のＵＲＬに関連づけられているので、ユーザが該画面上で所望のノードを選択すると、該表示画面を管理するクライアント装置のプログラムは、そのノードに対応するＵＲＬにより文書のデータを取得し、この文書を画面表示することができる。
【００４１】
なお、統合木構造データに基づく木構造表示は図８のようにすべてのノードを表示する形態に限らず、例えば図９に示す表示画面４１０のように、ファイルシステムのグラフィカルユーザインタフェースに採用されているようなものでもよい。図９の例では、あるノードが子ノードを持つ場合は、子ノードがある旨のマーク４１２を当該ノードに関連づけて表示し、子ノード以下のノードを表示しない。そして、マーク４１２付きのノードに対する展開指示をユーザが入力すると、そのノードの子ノード群を表示する。このような表示方式でも、木構造の情報をユーザに知らせることができる。
【００４２】
以上、好適な実施の形態を説明した。この実施の形態によれば、ハイパーテキスト構造中に現れる文書を網羅した統合木構造データを作成することができる。
【００４３】
以上の例では、根ノード選択部１６２は、未出現文書群から所定数の根ノードを選択したが、この所定数は、好適には１である。すなわち、根ノードを起点とする部分木を１つ作成しては、未出現文書を検出して次の部分木の根ノードを１つ選択する、という処理の流れである。一度に複数の根ノードを選択した場合、それら各根ノードごとにそれぞれ部分木が作成されるので、全体として、規模の小さな部分木が多数作成される傾向となる。これは、一つには、選択した根ノード群の中に、同時に選択した他の根ノードの子孫になるようなものがあった場合でも、その根ノードについての部分木が作成されるためである。これに対し、一度に選択する根ノードの数を１つにすれば、そのような無駄な部分木は作成されにくくなり、全体として少ない数の部分木により統合木構造を作成することができる。なお、最初の根ノードとして選ばれる基準文書については、部分木処理部１６に予め登録しておく場合にせよ、木構造要求を発行する都度指定する場合にせよ、文書群の関係を把握する上での基準としてユーザが意図的に選択するものであるので、複数ある場合もある。
【００４４】
また、以上の例では、部分木処理部１６で作成した各部分木を、１つスーパールートノードの子孫として接続することで統合木構造を作成したが、これはあくまで一例であり、他の統合の仕方もある。他の方式の一例として、図１０にあげるものがある。図１０に示す表示画面４２０の例では、最上位のノードであるスーパールート４０４の子として「注目」ノード４２２と「非注目」ノード４２４とが接続されている。「注目」ノード４２２は、文書に対応したノードではなく、基準文書を根ノードとする部分木を束ねるために特別に設けたノードである。この例では基準文書は文書Ａひとつだけなので、「注目」ノード４２２には子孫として文書Ａを根とする部分木が接続される。「非注目」ノード４２４は、基準文書以外の文書を根ノードとする部分木を束ねるために特別に設けたノードである。この例では文書Ｄ，Ｆが基準文書以外の根ノードなので、「非注目」ノード４２４には子孫として文書Ｄ，Ｆをそれぞれ根とする部分木が接続される。このように図１０の例では、基準文書を根ノードとする部分木と、それ以外の文書を根ノードとする部分木とが、それぞれ別のノード４２２、４２４の子孫となるように統合木構造を作成したので、この統合木構造を表示すれば、ユーザが指定した基準文書からリンクを辿って行き着くことができる文書群と、そうでない文書群とを区別して示すことができる。
【００４５】
このような統合木構造を示すデータは、次のようにして作成することができる。すなわち、根ノード選択部１６２は、自らが選択する根ノードが基準文書であるか、そうでないかは認識しているので、この認識結果を根ノードの情報と共に木構造データ作成部１６４に提供する。そして木構造データ作成部１６４が、作成する部分木の木構造データの根ノードに対し、その根ノードが基準文書であるか否かの情報を付加する。統合制御部２０は、各根ノードに付加された、基準文書であるか否かを示す情報に従って、各根ノードを「注目」ノードか「非注目」ノードに子として接続する。
【００４６】
なお、図１０の例では基準文書を根ノードとする部分木とそれ以外の根ノードの部分木とを、木構造上での位置の違いで区別したが、別の方法でそれら両者を区別してもよい。例えば、両者をノードの色の違いなどといった表示形態の違いで区別することもできる。この方式によれば、図８のように部分木をすべて共通のスーパールート４０４に接続した統合木構造でも、上述と同様の区別を行うことができる。なお、このような表示形態の区別は、明らかなように、図１０の統合木構造を作成するのと同様の情報に基づき実現できる。また、この表示形態の区別を実現するための統合木構造データは、図７に示した統合木構造データのデータ構造に、更に各ノードの表示形態を示すデータ項目を加えたものとなる。
【００４７】
以上に説明した実施の形態では、根ノード選択部１６２の選択の仕方について特に規定をしていない。このため、根ノードの選択順序によっては、ある根ノードからの部分木の木構造データの作成ためにリンクを辿っていくうちに、既に木構造データ記憶部１８内に記憶されている別の木構造データの根ノードの文書にたどり着いたり、同時に選択されたがまだ木構造データは作成していない他の根ノードにたどり着いたりすることが起こりうる。例えば、図３のハイパーテキスト構造についての統合木構造の作成の際、文書Ａより前に文書Ｃ，Ｄを根ノードを選んだ場合、木構造データ記憶部１８には図１１に示すような部分木１８７及び１８８の木構造データが保持されることになる。この後、文書Ａが根ノードに選ばれた場合、図１２に示すように、文書Ａからのリンクをたどると、文書Ｂの他に更に文書Ｃにたどり着く。この文書Ｃは、既に木構造データ記憶部１８に保持された部分木１８７の根ノードである。
【００４８】
このような場合、たどり着いた根ノード及びこれから伸びる部分木は今作成している木構造に包含してしまった方が、統合する部分木の数を減らすことができ、見通しのよい統合木構造が得られる。そこで、このような場合に対処するための好適な変形例として、次の手法がある。
【００４９】
すなわち、この手法では、木構造データ作成部１６４が、選択された根ノードを起点とする部分木を作成するためにリンクをたどって文書群を巡回していく際、文書にたどり着くたびにその文書が木構造データ記憶部１８に記憶されている、既存の木構造データの根ノードのいずれかに該当するかどうかを判定する。そして、該当すると判定した場合は、当該既存の木構造データを木構造データ記憶部１８から削除する。例えば、図１２の例では、部分木１８７の木構造データを木構造データ記憶部１８から削除する。木構造データ作成部１６４は、この判定及び削除以外では上述の実施の形態と同じ動作を行うようにすれば、削除した既存木構造データが示していたリンクの情報は、現在作成している木構造データに自動的に組み込まれることになる。例えば、図１２の例では、削除した部分木１８７が示す文書Ｃから文書Ｅへのリンクは、文書Ａを根ノードとする部分木に組み込まれることになる。
【００５０】
なお、部分木作成の際に到達した文書が、木構造データ記憶部１８内に既存の部分木の根ノードである場合、上述のように単にその部分木の木構造データを削除するだけではなく、削除した木構造データを現在作成している部分木の木構造データに自動的に組み込む処理手順とすることも好適である。例えば、図１２の例では、文書Ａを根ノードとする部分木１８９を作成している際に、文書Ｃにたどり着いた場合、既存の部分木１８７を部分木１８９の一部に組み込む。こうすることにより、今作成している部分木の木構造データの作成処理に係る時間が短くなる。
【００５１】
この変形例によれば、部分木を自動的にまとめることができ、見通しのよい統合木構造を作成することができる。
【００５２】
更に別の変形例について説明する。以上の実施の形態では、木構造データ記憶部１８に蓄積された各木構造データを、１つのスーパールートに接続するか、或いは「注目」ノード４２２及び「非注目」ノード４２４といった予め定められた固定的な分類のノードに接続することにより、統合木構造を構成した。これに対し、この変形例では、根ノード選択部１６２で選択された各根ノードの、ディレクトリ階層構造上での関係を示す上位木構造を作成し、この上位木構造にそれら各根ノードを起点とする部分木を接続することで、統合木構造を作成する。
【００５３】
この変形例を、図６に示すような部分木群を統合する場合を例にとって説明する。これら各部分木１８２，１８４，１８６の根ノードの文書Ａ，Ｄ，ＦのＵＲＬは図７に示されるようなものであったとする。この場合、この変形例では、各根ノードの文書Ａ，Ｄ，Ｆの所属ディレクトリ“http://abcd.co.jp/”，“http://abcd.co.jp/d/”，“http://abcd.co.jp/f/”をそれぞれノードとし、それらディレクトリ間の階層構造を表す上位木構造を作成する。すなわち、図１３に示す表示画面４３０で、破線の囲み４３２内に示される３つのノード４３４，４３６，４３８が形成する木構造が、この上位木構造である。統合制御部２０は、木構造データ記憶部１８内の部分木の木構造データ群を統合する際、各部分木の根ノードのＵＲＬを調べ、このような上位木構造を作成する。そして、この上位木構造と木構造データ記憶部１８内の各部分木とを統合する際には、各部分木の根ノードを、当該根ノードの文書が属するディレクトリに該当する上位木構造のノードの子として接続する。例えば、文書Ａはノード４３４の子に、文書Ｄはノード４３６の子に、文書Ｆはノード４３８の子になるようにする。図１３に表示される統合木構造を示す統合木構造データは、図１４に示すようなものとなる。図１４のデータ内容では、Ｓ１〜Ｓ３の３つのノードが上位木構造のノードであり、他のノードについてのデータ内容は図７に示した例と同様である。なお、図１３の表示画面４３０の例では、ディレクトリに該当するノード４３４，４３６，４３８には、当該ディレクトリを示すＵＲＬを表示することで、ユーザに各ディレクトリがどのようなものであるかを分かるようにしている。
【００５４】
図８の例のように部分木群を１つのスーパールートに接続したのでは、それら部分木の根ノード同士の関係が同列になってしまうのに対し、この変形例によれば、各部分木の根ノード同士の関係がディレクトリ構造（ＵＲＬ階層構造）から求められ、上位木構造として表現されるので、部分木の根ノード同士の間の階層関係も表現することができる。
【００５５】
次に、上記実施の形態に対する変形例として、根ノード選択部１６２が根ノードを選択する際の、好適な選択方式の例を説明する。
【００５６】
この例は、過去に作成した統合木構造の情報を利用して根ノードを選択するというものである。
【００５７】
すなわち、実際のウェブやイントラネットでは、各文書が各々の所有者により随時更新されるため、文書群が構成するハイパーテキスト構造は変化していく。このため、リンク情報収集部１０は、定期的にウェブ巡回行うことで、ハイパーテキスト構造記憶部１２内のハイパーテキスト構造の情報を、常に最新に近くなるように更新している。そして、統合制御部２０は、木構造要求２００を受けた場合、ハイパーテキスト構造記憶部１２内の最新の情報を用いて統合木構造を作成している。このような構成において、この好適な値ノード選択方式では、ある文書を基準文書（すなわち統合木構造作成における最初の根ノード）として指定した木構造要求２００がクライアント装置から入力された場合、同じ文書を基準文書として前回に作成された統合木構造の情報を用いて、根ノードの選択を行う。より具体的には、未出現文書検出部１６６で検出された未出現文書群のうち、前回の統合木構造において最上位ノード、すなわちスーパールートからの深さが最も浅いもののなかから根ノードを選択する。
【００５８】
この変形例を実現する装置構成の機能ブロック図を図１５に示す。図１５において、図１に示されたものと同じ構成要素については、同一符号を付してその説明を省略する。
【００５９】
この変形例は、図１の構成に対し、深さ情報記憶部２２を追加したものである。統合制御部２０ａは、上記実施の形態の統合制御部２０の機能に加え、作成した統合木構造の各ノードの、スーパールートからの深さを求め、この深さ情報を深さ情報記憶部２２に登録する機能を備える。
【００６０】
図１６は、深さ情報記憶部２２に記憶されるデータの例である。この例では、統合木構造を構成する各ノードについて、ノードＩＤ３１０，ＵＲＬ３１２，及びスーパールートからの深さ３１４がそれぞれ登録されている。図１６の例は、図８に例示した統合木構造に対応したものである。
【００６１】
深さ情報記憶部２２は、統合制御部２０ａから登録された情報を、次の木構造要求に対する統合木構造作成時まで保持する。そして、木構造要求２００に応えて統合木構造を作成する際、根ノード選択部１６２ａは、未出現文書検出部１６６で検出された各未出現文書のノードＩＤ又はＵＲＬを用いて、それら各未出現文書のスーパールートからの深さを深さ情報記憶部２２から求め、深さの値が最も小さいもの（すなわち最も浅いもの）を根ノードに選択する。深さ値が最小の未出現文書が複数存在する場合は、そのなかから根ノードを選択する。なお、複数の候補から１つ所定数の根ノードを選択する際の優先順位付けのルールを決めておき、深さ値が最小の未出現文書が複数存在する場合には、そのルールに従って上位から所定数の文書を根ノードに選択するようにすることも好適である。そのようなルールとしては、例えば、ＵＲＬの階層が浅いものから順に選択するルールや、ＵＲＬ又は文書タイトルの文字順（例えばアルファベット順、五十音順、文字コード順など）に選択するルール、及びそれらの組合せなどがある。統一したルールを定めておくことで、規則性のある統合木構造が作成できる。
【００６２】
このように、図１５及び図１６の変形例では、前回に作成した統合木構造上で浅いノードから順に根ノードを選択するようにしたので、木構造データ作成部１６４での部分木の作成処理を効率化することができる。
【００６３】
これを、図８の統合木構造を例にとって説明すれば、次のようになる。例えば図８の統合木構造をなしている文書群において、文書Ａの中から文書Ｃへのリンクを示す記述が削除されたとする。このリンク削除の後に統合木構造を作成する場合、文書Ａ，Ｄ，Ｆをそれぞれ根ノードにした部分木を作成した時点で、文書Ｃ，Ｅが未出現文書として残ることになる。この状況でランダムに根ノードを選択したのでは、文書Ｅが先に根ノードに選ばれる場合も出てくるが、その後で文書Ｃを根ノードとする部分木を作成する時点で、文書Ｅはその部分木に吸収すべきことが判明する。根ノードをランダムに選んだのでは、このように文書Ｅを根ノードに選択した処理が無駄になってしまう。これに対し、この変形例のごとく、リンク記述変更前の統合木構造において木の深さが浅いノードを優先的に根ノードに選択するようにすれば、文書Ｃの方が先に根ノードに選ばれるので、上述のような無駄は回避できる。
【００６４】
ハイパーテキスト構造の変更は、個々の文書での局地的なリンク記述の変更によるものが一般的であり、この場合変更されたリンク記述のリンク先の文書から先のリンク状況は、そのリンク記述の変更とは基本的に無関係であり、影響を受けないことが多い。このようなことから、この変形例の手法は有益であると言える。
【００６５】
また、以上では、ハイパーテキスト構造中から未出現文書が検出されなくなるまで部分木の作成処理を繰り返したが（図４参照）、別の終了条件を設定し、この終了条件が満足された時点で部分木作成を停止し、統合木構造を作成するようにすることもできる。終了条件としては、処理開始から所定時間が経過したこと、作成した部分木の数が所定数に達したこと、図４のＳ１２からＳ２０までのループ処理の実行回数が所定数に達したこと、などが考えられる。このように、未出現文書がなくならない段階で統合木構造を作成した場合でも、従来の木構造作成装置よりも網羅性の高い（すなわち木構造中に出現する文書数が多い）木構造を作成することができる。
【００６６】
以上、本発明に係る統合木構造データ作成装置の機能面での構成の例を説明した。このような装置は、一般的なコンピュータシステムを利用して構築することができる。例えば、典型的なコンピュータシステムは、図１７に示すように、ＣＰＵ（中央演算ユニット）３０、ＲＡＭ（ランダムアクセスメモリ）３２、ＨＤＤ（ハードディスクドライブ）３４及びＬＡＮインタフェース３６が、バス３８を介して相互接続されている。図１７のコンピュータシステムのＨＤＤ３４に、図１の各機能モジュール１０，１４，１６，２０の機能を記述したプログラムをインストールすれば、図１の装置が得られる。ＣＰＵ３０が、ＲＡＭ３２を利用してそのプログラムを実行することで、上述の各機能が実現される。この装置は、ＬＡＮインタフェース３６を介して、ローカルエリアネットワークへ、そしてインターネットへと接続されており、ＬＡＮ又はインターネット上にあるクライアント装置から木構造要求２００を受け付けることができる。
【図面の簡単な説明】
【００６７】
【図１】本発明に係る統合木構造データ作成装置の構成を示す機能ブロック図である。
【図２】文書テーブルの一例を示す図である。
【図３】リンクテーブルの一例を示す図である。
【図４】部分木処理部の処理手順の一例を示すフローチャートである。
【図５】文書群が構成するハイパーテキスト構造の一例を示す図である。
【図６】図５のハイパーテキスト構造から作成された、各部分木の木構造の集合を示す図である。
【図７】図６の部分木群を統合した統合木構造を示す統合木構造データ内容の例を示す図である。
【図８】図７の統合木構造データに基づく統合木構造の表示例を示す図である。
【図９】統合木構造の別の表示方式を例示した図である。
【図１０】部分木を統合する方式の別の例を示す図である。
【図１１】別の部分木に包含されてしまうはずの文書が先に根ノードに選ばれる場合を考慮した変形例の処理を説明するための図である。
【図１２】別の部分木に包含されてしまうはずの文書が先に根ノードに選ばれる場合を考慮した変形例の処理を説明するための図である。
【図１３】ＵＲＬ階層構造を反映した統合木構造の例を示す図である。
【図１４】ＵＲＬ階層構造を反映した統合木構造のデータ内容の例を示す図である。
【図１５】統合木構造データ作成装置の変形例の構成を示す機能ブロック図である。
【図１６】深さ情報記憶部に記憶されるデータ内容の一例を示す図である。
【図１７】統合木構造データ作成装置のベースとなるハードウエア構成の一例を示す図である。
【符号の説明】
【００６８】
１０  リンク情報収集部、１２  ハイパーテキスト構造記憶部、１４  要求処理部、１６  部分木処理部、１８  木構造データ記憶部、２０  統合制御部、１６２  根ノード選択部、１６４  木構造データ作成部、１６６  未出現文書検出部。
【図１】
2005157859.tif 000003
【図２】
2005157859.tif 000004
【図３】
2005157859.tif 000005
【図４】
2005157859.tif 000006
【図５】
2005157859.tif 000007
【図６】
2005157859.tif 000008
【図７】
2005157859.tif 000009
【図８】
2005157859.tif 000010
【図９】
2005157859.tif 000011
【図１０】
2005157859.tif 000012
【図１１】
2005157859.tif 000013
【図１２】
2005157859.tif 000014
【図１３】
2005157859.tif 000015
【図１４】
2005157859.tif 000016
【図１５】
2005157859.tif 000017
【図１６】
2005157859.tif 000018
【図１７】
2005157859.tif 000019