(57)【要約】【課題】構造化文書における複数の要素をクラスタリングすることにより、構造化文書の要素を精度良くクラスタリングでき、抽出したい部分を得ることができるようにする。【解決手段】階層構造解析部１０により、解析対象となる少なくとも１つの構造化文書の各々について、構造化文書の要素の階層構造を解析する。位置情報解析部１２によって、解析された構造化文書を表示したときの構造化文書の各要素の表示位置を解析する。そして、構造類似度計算部１４によって、要素の構造に関する構造類似度を算出する。そして、位置類似度計算部１６によって、要素の表示位置に関する位置類似度を算出する。そして、クラスタリング部２０によって、構造類似度計算部１４によって算出された構造類似度と、位置類似度計算部１６によって算出された位置類似度とに基づいて、少なくとも１つの構造化文書における複数の要素をクラスタリングする。【選択図】図１
2014049088.tif 000002
【特許請求の範囲】
【請求項１】
解析対象となる少なくとも１つの構造化文書の各々について、前記構造化文書の要素の階層構造を解析する階層構造解析手段と、
前記階層構造解析手段によって解析された構造化文書を表示したときの前記構造化文書の各要素の表示位置を解析する位置情報解析手段と、
前記階層構造解析手段によって解析された解析結果に基づいて、前記少なくとも１つの構造化文書における複数の要素のうちの第１要素と第２要素との間の各々について、前記第１要素及び前記第１要素の子孫の要素と、前記第２要素及び前記第２要素の子孫の要素とを比較して、要素の構造に関する構造類似度を算出する構造類似度計算手段と、
前記位置情報解析手段によって解析された解析結果に基づいて、前記少なくとも１つの構造化文書における複数の要素のうちの２つの要素間の各々について、要素の表示位置に関する位置類似度を算出する位置類似度計算手段と、
前記構造類似度計算手段によって算出された構造類似度と、前記位置類似度計算手段によって算出された位置類似度とに基づいて、前記少なくとも１つの構造化文書における複数の要素をクラスタリングするクラスタリング手段と
を含む文書構造解析装置。
【請求項２】
前記構造類似度計算手段は、前記階層構造解析手段によって解析された解析結果に基づいて、前記少なくとも１つの構造化文書における各要素について、該要素及び該要素の子孫の要素の属性名のヒストグラムを算出し、前記第１要素と第２要素との間の各々について、前記第１要素のヒストグラムと前記第２要素のヒストグラムとの類似度を前記構造類似度として算出する請求項１記載の文書構造解析装置。
【請求項３】
前記位置類似度計算手段は、前記位置情報解析手段によって解析された解析結果に基づいて、前記２つの要素間の各々について、前記構造化文書を表示したときの前記２つの要素の表示位置及び大きさに基づく類似度を、前記位置類似度として算出する請求項１又は２記載の文書構造解析装置。
【請求項４】
前記クラスタリング手段によってクラスタリングされたクラスタの各々について、前記クラスタに属する各要素に含まれる単語と予め定められたキーワードとに基づいて、前記クラスタの優先度を算出する優先度計算手段を更に含む請求項１〜請求項３の何れか１項記載の文書構造解析装置。
【請求項５】
前記構造類似度計算手段によって算出された構造類似度に基づいて、前記少なくとも１つの構造化文書における複数の要素のうちの同一のクラスタにクラスタリングされる２つの要素を含む複数のクラスタ候補を探索する候補探索手段を更に含み、
前記クラスタリング手段は、前記候補探索手段によって探索された各クラスタ候補に含まれる要素間の前記構造類似度及び前記位置類似度に基づいて、前記少なくとも１つの構造化文書における複数の要素をクラスタリングする請求項１〜請求項４の何れか１項記載の文書構造解析装置。
【請求項６】
前記候補探索手段は、前記少なくとも１つの構造化文書における複数の要素の各々について、該要素とクラスタ候補に含まれる要素を、親子関係にある要素のうち前記構造類似度が最大となる要素とする請求項５記載の文書構造解析装置。
【請求項７】
前記候補探索手段は、前記構造化文書を表示したときの表示位置の距離が所定値以下であって、かつ同一のクラスタにクラスタリングされる２つの要素を含む前記複数のクラスタ候補を探索する請求項５又は６記載の文書構造解析装置。
【請求項８】
コンピュータを、請求項１〜請求項７の何れか１項記載の文書構造解析装置の各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文書構造解析装置及びプログラムに係り、特に、構造化文書の要素の階層構造を解析する文書構造解析装置及びプログラムに関する。
【背景技術】
【０００２】
非特許文献１では、ウェブラッパーと呼ばれる、ＨＴＭＬ文書と抽出したい部分の組を学習例として与えると機械学習の手法を用いて文書構造抽出プログラムを自動生成する手法が提案されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】I. Muslea, S. Minton, and C. Knoblock, ”A Hierarchical Approach to Wrapper Induc-tion,” pp.190-197, AGENTS '99, 1999.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、上述した非特許文献１の手法では、同様の情報を含むページであっても、ｗｅｂページはサイト毎にＨＴＭＬ構造が異なるため、様々なサイトから包括的に情報を取得するためには、ＨＴＭＬ文書と抽出したい部分の組からなる大量の学習例が必要となり、人手による作業が大きい。また、ＥＣサイトのリニューアルなどでテンプレートが更新されると、商品ページのＨＴＭＬ構造が変わり、学習したルールが適用できなくなるため、ＨＴＭＬ文書と抽出したい部分の組からなる学習例を作り直して再学習する必要がある。
【０００５】
本発明は、上記の事情を鑑みてなされたもので、構造化文書における複数の要素をクラスタリングすることにより、構造化文書の要素を精度良くクラスタリングでき、抽出したい部分を得ることができる文書構造解析装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
上記の目的を達成するために本発明に係る文書構造解析装置は、解析対象となる少なくとも１つの構造化文書の各々について、前記構造化文書の要素の階層構造を解析する階層構造解析手段と、前記階層構造解析手段によって解析された構造化文書を表示したときの前記構造化文書の各要素の表示位置を解析する位置情報解析手段と、前記階層構造解析手段によって解析された解析結果に基づいて、前記少なくとも１つの構造化文書における複数の要素のうちの第１要素と第２要素との間の各々について、前記第１要素及び前記第１要素の子孫の要素と、前記第２要素及び前記第２要素の子孫の要素とを比較して、要素の構造に関する構造類似度を算出する構造類似度計算手段と、前記位置情報解析手段によって解析された解析結果に基づいて、前記少なくとも１つの構造化文書における複数の要素のうちの２つの要素間の各々について、要素の表示位置に関する位置類似度を算出する位置類似度計算手段と、前記構造類似度計算手段によって算出された構造類似度と、前記位置類似度計算手段によって算出された位置類似度とに基づいて、前記少なくとも１つの構造化文書における複数の要素をクラスタリングするクラスタリング手段とを含んで構成されている。
【０００７】
本発明によれば、階層構造解析手段によって、解析対象となる少なくとも１つの構造化文書の各々について、構造化文書の要素の階層構造を解析する。位置情報解析手段によって、階層構造解析手段によって解析された構造化文書を表示したときの構造化文書の各要素の表示位置を解析する。
【０００８】
そして、構造類似度計算手段によって、階層構造解析手段によって解析された解析結果に基づいて、少なくとも１つの構造化文書における複数の要素のうちの第１要素と第２要素との間の各々について、第１要素及び第１要素の子孫の要素と、第２要素及び第２要素の子孫の要素とを比較して、要素の構造に関する構造類似度を算出する。
【０００９】
そして、位置類似度計算手段によって、位置情報解析手段によって解析された解析結果に基づいて、少なくとも１つの構造化文書における複数の要素のうちの２つの要素間の各々について、要素の表示位置に関する位置類似度を算出する。
【００１０】
そして、クラスタリング手段によって、構造類似度計算手段によって算出された構造類似度と、位置類似度計算手段によって算出された位置類似度とに基づいて、少なくとも１つの構造化文書における複数の要素をクラスタリングする。
【００１１】
これにより、構造化文書の要素の階層構造を解析し、解析された構造化文書を表示したときの構造化文書の各要素の表示位置を解析し、構造化文書における複数の要素のうちの２つの要素間の各々について、要素の構造に関する構造類似度及び要素の表示位置に関する位置類似度を算出し、構造類似度と、位置類似度とに基づいて、構造化文書における複数の要素をクラスタリングすることにより、構造化文書の要素を精度良くクラスタリングでき、抽出したい部分を得ることができる。
【００１２】
また、前記構造類似度計算手段は、前記階層構造解析手段によって解析された解析結果に基づいて、前記少なくとも１つの構造化文書における各要素について、該要素及び該要素の子孫の要素の属性名のヒストグラムを算出し、前記第１要素と第２要素との間の各々について、前記第１要素のヒストグラムと前記第２要素のヒストグラムとの類似度を前記構造類似度として算出することができる。
【００１３】
また、前記位置類似度計算手段は、前記位置情報解析手段によって解析された解析結果に基づいて、前記２つの要素間の各々について、前記構造化文書を表示したときの前記２つの要素の表示位置及び大きさに基づく類似度を、前記位置類似度として算出することができる。
【００１４】
また、前記クラスタリング手段によってクラスタリングされたクラスタの各々について、前記クラスタに属する各要素に含まれる単語と予め定められたキーワードとに基づいて、前記クラスタの優先度を算出する優先度計算手段を更に含むことができる。
【００１５】
また、前記構造類似度計算手段によって算出された構造類似度に基づいて、前記少なくとも１つの構造化文書における複数の要素のうちの同一のクラスタにクラスタリングされる２つの要素を含む複数のクラスタ候補を探索する候補探索手段を更に含み、前記クラスタリング手段は、前記候補探索手段によって探索された各クラスタ候補に含まれる要素間の前記構造類似度及び前記位置類似度に基づいて、前記少なくとも１つの構造化文書における複数の要素をクラスタリングすることができる。
【００１６】
また、前記候補探索手段は、前記少なくとも１つの構造化文書における複数の要素の各々について、該要素とクラスタ候補に含まれる要素を、親子関係にある要素のうち前記構造類似度が最大となる要素とすることができる。
【００１７】
また、前記候補探索手段は、前記構造化文書を表示したときの表示位置の距離が所定値以下であって、かつ同一のクラスタにクラスタリングされる２つの要素を含む前記複数のクラスタ候補を探索することができる。
【００１８】
本発明に係るプログラムは、コンピュータを、上記の文書構造解析装置の各手段として機能させるためのプログラムである。
【発明の効果】
【００１９】
以上説明したように、本発明の文書構造解析装置及びプログラムによれば、構造化文書の要素の階層構造を解析し、解析された構造化文書を表示したときの構造化文書の各要素の表示位置を解析し、構造化文書における複数の要素のうちの２つの要素間の各々について、要素の構造に関する構造類似度及び要素の表示位置に関する位置類似度を算出し、構造類似度と、位置類似度とに基づいて、構造化文書における複数の要素をクラスタリングすることにより、構造化文書の要素を精度良くクラスタリングでき、抽出したい部分を得ることができる、という効果が得られる。
【図面の簡単な説明】
【００２０】
【図１】本発明の実施の形態に係る文書構造解析装置の構成を示す概略図である。
【図２】本発明の実施の形態で用いるキーワードリストＫＷ＾の概略図である。
【図３】本発明の実施の形態で用いる階層構造情報テーブルＫ＾の概略図である。
【図４】本発明の実施の形態で用いる位置情報テーブルＰ＾の概略図である。
【図５】本発明の実施の形態で用いるクラスタテーブルＣ＾の概略図である。
【図６】本発明の実施の形態で用いる構造類似度テーブルＬｓｔｒ＾の概略図である。
【図７】本発明の実施の形態で用いる位置類似度テーブルＬｐｏｓ＾の概略図である。
【図８】本発明の実施の形態の説明で用いた動作例１のｗｅｂページを示す図である。
【図９】本発明の実施の形態の説明で用いた動作例１のｗｅｂページのＨＴＭＬタグ構造を示す図である。
【図１０】本発明の実施の形態の説明で用いた動作例１のＤＯＭツリー構造を示す図である。
【図１１】本発明の実施の形態の説明で用いた動作例１の階層構造情報テーブルを示す図である。
【図１２】本発明の実施の形態に係る文書構造解析装置における構造化文書情報抽出処理ルーチンの内容を示すフローチャートである。
【図１３】構造化文書情報抽出処理ルーチン内で呼び出される候補探索処理ルーチンの前半部分の内容を示すフローチャートである。
【図１４】構造化文書情報抽出処理ルーチン内で呼び出される候補探索処理ルーチンの後半部分の内容を示すフローチャートである。
【図１５】構造化文書情報抽出処理ルーチン内で呼び出される候補探索処理ルーチンの前半部分を示すアルゴリズムである。
【図１６】構造化文書情報抽出処理ルーチン内で呼び出される候補探索処理ルーチンの後半部分を示すアルゴリズムである。
【図１７】候補探索処理ルーチン内で呼び出されるfirstChildルーチンの内容を示すアルゴリズムである。
【図１８】候補探索処理ルーチン内で呼び出されるnextSiblingルーチンの内容を示すアルゴリズムである。
【図１９】候補探索処理ルーチン内で呼び出されるnextNodeルーチンの内容を示すアルゴリズムである。
【図２０】構造化文書情報抽出処理ルーチン内で呼び出されるクラスタリング処理ルーチンの内容を示すフローチャートである。
【図２１】構造化文書情報抽出処理ルーチン内で呼び出されるクラスタリング処理ルーチンのアルゴリズムである。
【図２２】構造化文書情報抽出処理ルーチン内で呼び出される優先度計算処理ルーチンの内容を示すアルゴリズムである。
【図２３】本発明の実施の形態の説明で用いた動作例１のキーワードリストＫＷ＾を示す図である。
【図２４】本発明の実施の形態の説明で用いた動作例１の位置情報テーブルＰ＾を示す図である。
【図２５】本発明の実施の形態の説明で用いた動作例１の構造類似度テーブルＬｓｔｒ＾を示す図である。
【図２６】本発明の実施の形態の説明で用いた動作例１の位置類似度テーブルＬｐｏｓ＾を示す図である。
【図２７】本発明の実施の形態の説明で用いた動作例１のクラスタテーブルＣ＾を示す図である。
【図２８】本発明の実施の形態の説明で用いた動作例１のクラスタリング結果を示す図である。
【図２９】本発明の実施の形態の説明で用いた動作例１の出力結果を示す図である。
【図３０】本発明の実施の形態の説明で用いた動作例２のｗｅｂページを示す図である。
【図３１】本発明の実施の形態の説明で用いた動作例２のｗｅｂページのＨＴＭＬタグ構造を示す図である。
【図３２】本発明の実施の形態の説明で用いた動作例２のキーワードリストＫＷ＾を示す図である。
【図３３】本発明の実施の形態の説明で用いた動作例２の出力結果を示す図である。
【図３４】構造化文書情報抽出処理ルーチン内で呼び出される優先度計算処理ルーチンの他の構成例１を示すアルゴリズムである。
【図３５】構造化文書情報抽出処理ルーチン内で呼び出される優先度計算処理ルーチンの他の構成例２を示すアルゴリズムである。
【図３６】構造化文書情報抽出処理ルーチン内で呼び出される優先度計算処理ルーチンの他の構成例３を示すアルゴリズムである。
【発明を実施するための形態】
【００２１】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００２２】
＜システム構成＞
【００２３】
本実施の形態に係る文書構造解析装置は、ＣＰＵと、ＲＡＭと、後述する構造化文書情報抽出装置処理ルーチンを実行するためのプログラムを記憶したＲＯＭとを備えたコンピュータで構成され、機能的には次に示すように構成されている。
【００２４】
本実施の形態に係る文書構造解析装置は、図１に示すように、入力部１と、記憶部２と、演算部３と、出力部４とを備えている。また、演算部３は、階層構造解析部１０と、位置情報解析部１２と、構造類似度計算部１４と、位置類似度計算部１６と、候補探索部１８と、クラスタリング部２０と、優先度計算部２２とを備えている。
【００２５】
なお、記憶部２は、外部に設けられ、文書構造解析装置とネットワークで接続されていてもよい。
【００２６】
入力部１は、外部からの入力を受け付ける。入力部１は、例えば、ネットワーク、又はファイルなどを経由して、ｗｅｂページ群、後述するパラメータ（構造類似度閾値θｓｔｒ、位置類似度閾値θｐｏｓ、探索範囲閾値γ０、γ１）、及び後述するキーワードリストＫＷ＾の入力を受け付ける。
【００２７】
記憶部２は、入力部１により入力された各種データを記憶する。具体的には、入力部１により入力されたｗｅｂページ群、パラメータ（構造類似度閾値θｓｔｒ、位置類似度閾値θｐｏｓ、探索範囲閾値γ０、γ１）、及び図２に示すキーワードリストＫＷ＾を記憶する。また記憶部２は、後述する各処理での結果等を記憶し、具体的には、図３に示す階層構造情報テーブルＫ＾、図４に示す位置情報テーブルＰ＾、図５に示すクラスタテーブルＣ＾、図６に示す構造類似度テーブルＬｓｔｒ＾、及び図７に示す位置類似度テーブルＬｐｏｓ＾などを記憶する。なお、記号に付された「＾」は、当該記号が行列または多次元配列またはベクトルであることを表わしている。また記憶部２は、後述するその他の各処理での結果等を記憶する。
【００２８】
階層構造解析部１０は、入力部１により入力され、記憶部２に記憶されているｗｅｂページの各々について、ＨＴＭＬタグが示す要素の階層構造を解析する。具体的には、ｗｅｂページからＨＴＭＬタグが示す各要素に対応する各ノードを含むＤＯＭ（Document Object Model）ツリーを生成すると共に、ＤＯＭツリー中の各ノードについて、自ノードと子孫の各ノードのノード名（属性名）でヒストグラムを作成し、上記図３に示す階層構造情報テーブルＫ＾を作成する。
例えば、図８に示す、後述する動作例１のｗｅｂページが入力された場合には、図９に示すようなＨＴＭＬタグが示す要素の階層構造を解析し、図１０に示すツリーを生成する。そして、ＤＯＭツリー中の各ノードについて、図１１に示すようなヒストグラムを作成する。
【００２９】
位置情報解析部１２は、入力部１により入力され、記憶部２に記憶されているｗｅｂページの各々について、ＨＴＭＬタグが示す要素の、ｗｅｂブラウザ上での表示位置及び表示領域の幅と高さを計算し、上記図４に示す位置情報テーブルＰ＾を作成する。なお、要素の表示領域の幅と高さは、要素を表示したときの大きさの一例である。
【００３０】
構造類似度計算部１４は、階層構造解析部１０で算出される各ノードのヒストグラムに基づいて、２つのノードのペア各々について２つの要素間の階層構造に関する類似度を計算する。例えば、ノードＡとノードＢが与えられた場合に、それらの構造類似度Ｓｓｔｒ（Ａ、Ｂ）を以下の（１）式に従って計算する。
【００３１】
【数１】
2014049088.tif 000003
【００３２】
ここで、ｈｉｓｔＡ、ｈｉｓｔＢは階層構造解析部１０で算出されるノードＡ、Ｂのヒストグラムである。
【００３３】
位置類似度計算部１６は、位置情報解析部１２で算出される位置情報に基づいて、２つのノードのペア各々について２つの要素間の位置関係の類似度を計算する。例えば、ノードＡとノードＢが与えられた場合に、ノードＡ、Ｂの位置類似度Ｓｐｏｓ＾（Ａ、Ｂ）を以下の（２）式に従って計算する。
【００３４】
【数２】
2014049088.tif 000004
【００３５】
ここで、（ｘＡ，ｙＡ，ｗＡ，ｈＡ）、（ｘＢ，ｙＢ，ｗＢ，ｈＢ）は、位置情報解析部１２で算出されるノードＡ、Ｂの位置情報である。また、（ＷＡ，ＨＡ）、（ＷＢ，ＨＢ）は、ｗｅｂブラウザ上での、Ａ、Ｂを含むｗｅｂページの表示領域（スクロール分を含む）の幅および高さである。
【００３６】
候補探索部１８は、入力部１により入力されたパラメータ（構造類似度閾値θｓｔｒ、探索範囲閾値γ０、γ１）、構造類似度計算部１４で算出された構造類似度、及び位置情報解析部１２で算出されたノードの位置情報に基づいて、階層構造解析部１０で生成されたＤＯＭツリーの各ノードからクラスタ候補となるノードの組を探索する。そして、候補探索の結果として、上記（１）式で算出される構造類似度Ｓｓｔｒ（Ａ、Ｂ）をクラスタ候補のノードの組（ｉ,ｊ）の各々について格納した、上記図６に示す構造類似度テーブルＬｓｔｒ＾を作成する。また、上記（２）式で算出される位置類似度Ｓｐｏｓ（Ａ、Ｂ）をクラスタ候補のノードの組（ｉ,ｊ）の各々について格納した、上記図７に示す位置類似度テーブルＬｐｏｓ＾を作成する。そして、上記図５に示す、少なくとも１つのクラスタ候補に属する各ノードを各クラスタとするクラスタテーブルＣ＾を作成する。
具体的には、ＤＯＭツリーのノードを辿って、構造類似度計算部１４で算出された構造類似度が閾値以上で、位置情報解析部１２で算出されたノードの表示位置が、探索範囲内の２つのノードのペアを検出する。そして、検出されたノードのペアの一方のノードに対して、他方のノードとなるノード群内で親子関係がないように、親子関係があるノードのうちの、当該一方のノードとの間の構造類似度が最大となるノードを当該他方のノードとして選択し、クラスタ候補とする。そして、各クラスタ候補の構造類似度、及び位置類似度を格納して、構造類似度テーブルＬｓｔｒ＾、位置類似度テーブルＬｐｏｓ＾を作成し、記憶部２へ格納する。
【００３７】
クラスタリング部２０は、候補探索部１８で作成された構造類似度テーブルＬｓｔｒ＾、位置類似度テーブルＬｐｏｓ＾、及びクラスタテーブルＣ＾に基づいて、クラスタテーブルＣ＾のクラスタを統合して、クラスタテーブルＣ＾を更新することを繰り返して、ノードをクラスタリングする。ここで、位置類似度計算部１６で算出された位置類似度および構造類似度計算部１４で算出された構造類似度が指定した閾値以上のクラスタ候補のうち、構造類似度が最大のクラスタ候補のノードペアに対応する２つのクラスタを統合してクラスタテーブルＣ＾を更新することを繰り返す。
【００３８】
優先度計算部２２は、クラスタリング部２０で生成されたクラスタの優先度を計算する。具体的には、入力部１により入力されたキーワードリストＫＷ＾、階層構造解析部１０により作成された階層構造情報テーブルＫ＾、及びクラスタリング部２０で得られたクラスタテーブルＣ＾に基づいて、各クラスタについて、当該クラスタに属する各ノード毎に、当該ノードが含むキーワードの重みの和を算出し、その最大値を当該クラスタの優先度として計算する。
【００３９】
出力部４は、優先度計算部２２で算出した各クラスタの優先度に基づいて、クラスタリング部２０で生成されたクラスタリング結果を優先度順に出力する。
【００４０】
＜作用＞
次に、本実施の形態に係る文書構造解析装置の作用について説明する。まず、ｗｅｂページ群、パラメータ（構造類似度閾値θｓｔｒ、位置類似度閾値θｐｏｓ、探索範囲閾値γ０、γ１）、及びキーワードリストＫＷ＾が文書構造解析装置に入力され、記憶部２に格納される。そして、文書構造解析装置において、図１２に示す構造化文書情報抽出装置処理ルーチンが実行される。
【００４１】
まず、ステップＳ１００において、記憶部２から、入力部１により入力されたｗｅｂページ群、パラメータ（構造類似度閾値θｓｔｒ、位置類似度閾値θｐｏｓ、探索範囲閾値γ０、γ１）、及びキーワードリストＫＷ＾を読み込む。
【００４２】
次に、ステップＳ１０２において、ｗｅｂページに対して階層構造の解析を行う。具体的には、記憶部２から、入力部１により入力されたｗｅｂページを１つ読み出し、ＨＴＭＬタグが示す各要素に対応する各ノードを含むＤＯＭ（Document Object Model）ツリーを生成すると共に、ＤＯＭツリー中の各ノードについて、自ノードと子孫の各ノードのノード名（属性名）でヒストグラムを作成し、上記図３に示す階層構造情報テーブルＫ＾を作成し、記憶部２に格納する。
【００４３】
次に、ステップＳ１０４において、ｗｅｂページに対して、位置情報の解析を行う。具体的には、記憶部２から、入力部１により入力されたｗｅｂページを１つ読み出し、ＨＴＭＬタグが示す各要素の、ｗｅｂブラウザ上での表示位置を各々計算し、上記図４に示す位置情報テーブルＰ＾を作成し、記憶部２に格納する。
【００４４】
ステップＳ１０６では、記憶部２に記憶されているｗｅｂページ群の全てについて、上記ステップＳ１０２の構造情報解析、及び上記ステップＳ１０４の位置情報解析が終了したか否かを判定する。ｗｅｂページ群の全てについて解析が終了していない場合には、ステップＳ１０２へ移行する。ｗｅｂページ群の全てについて解析が終了している場合には、ステップＳ１０８へ移行する。
【００４５】
ステップＳ１０８では、各ノードから、クラスタ候補となるノードの組を探索するため、図１３及び図１４に示す候補探索処理ルーチンが実行される。また、上記図１３及び上記図１４に示す候補探索処理ルーチンに対応するアルゴリズムを図１５及び図１６に示す。
【００４６】
＜候補探索処理ルーチン＞
候補探索処理ルーチンでは、各ノードからクラスタ候補となるノードの組を探索する処理が実行される。また、候補探索処理ルーチンは、ｗｅｂページ群から得られるｗｅｂページのペアの各々について実行される。また、同じｗｅｂページからなる各ペアについて、候補探索処理ルーチンが実行される。
【００４７】
はじめに、ステップＳ２００において、処理対象となるｗｅｂページのペア（ｐａｇｅＡ，ｐａｇｅＢ）、パラメータ（構造類似度の閾値θｓｔｒ、探索範囲を指定するパラメータγ０、γ１）及び上記ステップＳ１０４において作成された位置情報テーブルＰ＾が再度読み込まれる。
【００４８】
次に、ステップＳ２０２において、ｐａｇｅＡとｐａｇｅＢが同一であるか否かが判定される。そして、ｐａｇｅＡとｐａｇｅＢが同一である場合には、ステップＳ２０４へ移行する。ｐａｇｅＡとｐａｇｅＢが同一でない場合には、ステップＳ２０６へ移行する。
【００４９】
ステップＳ２０４では、探索範囲を指定する閾値γにγ０の値が入力される。ステップＳ２０６では、γにγ１の値が入力される。ここで、γ０、γ１は各々、同一ページ・異なるページでの探索範囲を指定するパラメータである。
【００５０】
次に、ステップＳ２０８では、図１７に示すfirstChildルーチンが呼び出され、firstChildルーチンにｐａｇｅＡが入力される。そして、firstChildルーチンの返す値が、クラスタ候補となりうるノードの組の一方のノードを示すノード番号ｎ１に代入される。なお、firstChildルーチンは、ｐａｇｅＡが子ノードを有している場合には、ｐａｇｅＡの最初の子ノードのノード番号を返す。ｐａｇｅＡが子ノードを有していない場合には、φ（空）を返す。
【００５１】
次に、ステップＳ２１０では、上記ステップＳ２０８で算出されたｎ１の値がφ（空）であるか否かが判定される。ｎ１の値がφ（空）でない場合には、ステップＳ２１２へ移行する。ｎ１の値がφ（空）である場合には、ステップＳ３０６へ移行する。
【００５２】
次に、ステップＳ２１２では、クラスタ候補の他方のノードの候補となるノードを示すノード番号bnodeにφ（空）が代入され、scoreに−１が代入される。
【００５３】
次に、ステップＳ２１４では、ｐａｇｅＡについての位置情報テーブルＰＡ＾のｎ１番目のノード番号に対応する位置情報が、（ｘ１，ｙ１，ｗ１，ｈ１）に代入される。
【００５４】
ステップＳ２１６では、ｐａｇｅＡとｐａｇｅＢが同一であるか否かが判定される。そして、ｐａｇｅＡとｐａｇｅＢが同一である場合には、ステップＳ２１８へ移行する。ｐａｇｅＡとｐａｇｅＢが同一でない場合には、ステップＳ２２０へ移行する。
【００５５】
ステップＳ２１８では、図１８に示すnextSiblingルーチンが呼び出され、nextSiblingルーチンにｎ１が入力される。そして、nextSiblingルーチンの返す値がクラスタ候補となりうるノードの組の他方のノードを示すノード番号ｎ２に代入される。なお、nextSiblingルーチンは、入力されたノード番号ｎ１に対応するノードが、兄弟ノードを有している場合には、ノード番号ｎ１に対応するノードの最初の兄弟ノードのノード番号を返す。ノード番号ｎ１に対応するノードが、兄弟ノードを有していない場合には、φ（空）を返す。
【００５６】
ステップＳ２２０では、上記図１７に示すfirstChildルーチンが呼び出され、firstChildルーチンにｐａｇｅＢが入力される。そして、firstChildルーチンの返す値がｎ２に代入される。
【００５７】
次に、ステップＳ２２２では、上記ステップＳ２１８若しくは上記ステップＳ２２０で算出されたｎ２の値、又は後述するステップＳ２４０で前回算出されたｎ２の値がφ（空）であるか否かが判定される。ｎ２の値がφ（空）でない場合には、ステップＳ２２４へ移行する。ｎ１の値がφ（空）である場合には、ステップＳ３００へ移行する。
【００５８】
次に、ステップＳ２２４では、上記ステップＳ２０８又は後述するステップＳ３０４で前回算出されたｎ１と、上記ステップＳ２１８若しくは上記ステップＳ２２０又は後述するステップＳ２４０で前回算出されたｎ２に基づいて、構造類似度Ｓｓｔｒ（ｎ１，ｎ２）を算出し、構造類似度Ｓｓｔｒ（ｎ１，ｎ２）を比較用の構造類似度値ｓｉｍへ代入する。
【００５９】
次に、ステップＳ２２６では、上記ステップＳ２２４で算出されたｓｉｍが、上記ステップＳ２００で入力されたパラメータ（構造類似度の閾値θｓｔｒ）以上であるか否かを判定する。そして、ｓｉｍが構造類似度の閾値θｓｔｒ以上であればステップＳ２２８へ移行する。ｓｉｍが構造類似度の閾値θｓｔｒ未満であればステップＳ２４０へ移行する。
【００６０】
次に、ステップＳ２２８では、ｐａｇｅＢについての位置情報テーブルＰＢ＾のｎ２番目のノード番号に対応する位置情報が、（ｘ２，ｙ２，ｗ２，ｈ２）に代入される。
【００６１】
次に、ステップＳ２３０では、上記ステップＳ２０４又はステップＳ２０６で入力されたγの値、上記ステップＳ２１４で代入された（ｘ１，ｙ１，ｗ１，ｈ１）、及び上記ステップＳ２２８で代入された（ｘ２，ｙ２，ｗ２，ｈ２）に基づいて、判定が行われる。具体的には、ｘ２−ｘ１≦γｗ１であって、かつｘ１−ｘ２≦γｗ２であって、かつｙ２−ｙ１≦γｈ１であって、かつｙ１−ｙ２≦γｈ２と判定される場合には、ステップＳ２３２へ移行する。それ以外の場合には、ステップＳ２４０へ移行する。
【００６２】
次に、ステップＳ２３２では、上記ステップＳ２１２で値が代入されたbnode又は後述するステップＳ２３４若しくはステップＳ２３８で前回値が代入されたbnode、及び上記ステップＳ２１８若しくはステップＳ２２０で値が代入されたｎ２又は後述するステップＳ２４０で前回値が代入されたｎ２に基づいて、判定が行われる。具体的には、bnode≠φ（空）であって、かつｎ２がbnodeと親子関係にないと判定される場合には、ステップＳ２３４へ移行する。それ以外の場合には、ステップＳ２３６へ移行する。
【００６３】
ステップＳ２３４では、構造度類似度テーブルＬｓｔｒ＾のＬｓｔｒ（｛ｎ１，bnode｝）に、前回本ステップＳ２３４で算出された親子関係にあるbnodeにおける構造類似度の最大値scoreの値、又は後述するステップＳ２３８で前回算出されたscoreの値を代入する。そして、位置類似度テーブルＬｐｏｓ＾のＬｐｏｓ（｛ｎ１，bnode｝）に、位置類似度Ｓｐｏｓ（ｎ１，bnode）の値を代入する。また、クラスタテーブルＣ＾のＣ（ｎ１）に、上記ステップＳ２０８で値が代入されたｎ１、又は後述するステップＳ３０４で前回算出されたｎ１の値を代入する。そして、クラスタテーブルＣ＾のＣ（bnode）に、前回本ステップＳ２３４で算出されたbnodeの値、又は後述するステップＳ２３８で前回算出されたbnodeの値を代入する。また、bnodeに、上記ステップＳ２１８若しくはステップＳ２２０で算出されたｎ２の値、又は後述するステップＳ２４０で前回算出されたｎ２の値を代入する。そして、scoreに上記ステップＳ２２４で算出されたsimの値を代入する。
【００６４】
ステップＳ２３６では、上記ステップ２１２で算出されたscoreの値、又はステップＳ２３４で前回算出されたscoreの値若しくは後述するステップＳ２３８で前回算出されたscoreの値と、上記ステップＳ２２４で算出されたsimの値に基づいて、判定が行われる。具体的には、scoreの値がsimの値よりも小さいと判定された場合には、ステップＳ２３８へ移行する。scoreの値がsimの値以上であると判定された場合には、ステップＳ２４０へ移行する。
【００６５】
次にステップＳ２３８では、bnodeに、上記ステップＳ２１８若しくはステップＳ２２０で算出されたｎ２の値、又は後述するステップＳ２４０で前回算出されたｎ２の値が代入される。そして、親子関係にあるbnodeにおける構造類似度の最大値scoreに上記ステップＳ２２４で算出されたsimの値を代入する。
【００６６】
次にステップＳ２４０では、図１９に示すnextNodeルーチンが呼び出され、nextNodeルーチンにｐａｇｅＢと、ｎ２が入力される。そして、nextNodeルーチンの返す値がｎ２に代入される。なお、nextNodeルーチンは、入力されたｐａｇｅＢ内のノードｎ２が、子ノードを有している場合には、ノードｎ２の最初の子ノードのノードを示すノード番号を返す。ノードｎ２が、子ノードを有していない場合には、ノードｎ２の最初の兄弟ノードを示すノード番号を返す。ノードｎ２が、兄弟ノードを有していない場合には、ノードｎ２の親ノードの次の兄弟ノードを示すノード番号を返す。それ以外の場合には、φ（空）を返す。
【００６７】
ステップＳ３００では、上記ステップＳ２１２で算出されたbnodeの値、又は上記ステップＳ２３４若しくはステップＳ２３８で算出されたbnodeの値がφ（空）であるか否かを判定する。bnodeの値がφ（空）でない場合には、ステップＳ３０２へ移行する。bnodeの値がφ（空）である場合には、ステップＳ３０４へ移行する。
【００６８】
ステップＳ３０２では、構造度類似度テーブルＬｓｔｒ＾のＬｓｔｒ（｛ｎ１，bnode｝）に、上記ステップＳ２３４で算出されたscoreの値又は上記ステップＳ２３８で算出されたscoreの値を代入する。そして、位置類似度テーブルＬｐｏｓ＾のＬｐｏｓ（｛ｎ１，bnode｝）に、位置類似度Ｓｐｏｓ（ｎ１，bnode）の値を代入する。また、クラスタテーブルＣ＾のＣ（ｎ１）に、上記ステップＳ２０８で算出されたｎ１の値又は後述するステップＳ３０４で前回算出されたｎ１の値を代入する。そして、クラスタテーブルＣ＾のＣ（bnode）に、上記ステップＳ２３４又は上記ステップＳ２３８で算出されたbnodeの値を代入する。
【００６９】
次に、ステップＳ３０４では、上記図１９に示すnextNodeルーチンが呼び出され、nextNodeルーチンにｐａｇｅＡと、ｎ１が入力される。そして、nextNodeルーチンの返す値がｎ１に代入される。
【００７０】
ステップＳ３０６では、候補探索処理ルーチンの処理結果として、クラスタテーブルＣ＾、構造類似度テーブルＬｓｔｒ＾、位置類似度テーブルＬｐｏｓ＾が結果として出力され、記憶部２へ格納される。
【００７１】
＜クラスタリング処理ルーチン＞
候補探索処理ルーチンの処理が終了した後には、上記図１２に示す構造化文書情報抽出処理ルーチンのステップＳ１１０に戻る。ステップＳ１１０では、上記ステップＳ１０８の候補探索処理ルーチンで作成されたクラスタテーブルＣ＾、構造類似度テーブルＬｓｔｒ＾、位置類似度テーブルＬｐｏｓ＾に基づいて、クラスタテーブルＣ＾のクラスタを統合することを繰り返し行う。ステップＳ１１０では、図２０に示すクラスタリング処理ルーチンが実行される。また、上記図２０に示すクラスタリング処理ルーチンに対応するアルゴリズムを図２１に示す。
【００７２】
ステップＳ４００では、上記ステップＳ１０８で算出されたクラスタテーブルＣ＾、構造度類似度テーブルＬｓｔｒ＾、位置類似度テーブルＬｐｏｓ＾、及びパラメータ（構造類似度閾値θｓｔｒ、位置類似度閾値θｐｏｓ）が記憶部２から読み出される。
【００７３】
次にステップＳ４０２では、統合される候補となるクラスタを示すクラスタ番号ｐ、ｑ、統合される候補となるクラスタのペアにおける構造類似度の最大値ｍａｘＳｓｔｒに初期値として−１が代入される。
【００７４】
ステップＳ４０３では、構造類似度テーブルＬｓｔｒ＾に基づいて、処理対象となるクラスタのペア（｛ｉ,ｊ｝, Ｓｓｔｒ）を設定する。
【００７５】
次にステップＳ４０４では、ｍａｘＳｓｔｒと構造類似度Ｓｓｔｒを比較する。そして、ｍａｘＳｓｔｒがＳｓｔｒ未満であれば、ステップＳ４０６へ移行する。ｍａｘＳｓｔｒがＳｓｔｒより大きいならば、ステップＳ４１２へ移行する。
【００７６】
ステップＳ４０６では、位置類似度Ｓｐｏｓ＾に、上記ステップＳ４００で読み出された位置類似度テーブルＬｐｏｓ＾の値Ｌｐｏｓ（｛ｉ,ｊ｝）が代入される。ここで、位置類似度Ｓｐｏｓ＾＝（Ｓxｐｏｓ，Ｓyｐｏｓ，Ｓwｐｏｓ，Ｓhｐｏｓ）である。
【００７７】
次にステップＳ４０８では、上記ステップＳ４０６で代入された位置類似度Ｓｐｏｓ＾＝（Ｓxｐｏｓ，Ｓyｐｏｓ，Ｓwｐｏｓ，Ｓhｐｏｓ）と、位置類似度閾値θｐｏｓを比較する。そして、Ｓxｐｏｓ≧θｐｏｓであって、かつＳwｐｏｓ≧θｐｏｓであるか、又はＳyｐｏｓ≧θｐｏであって、かつＳhｐｏｓ≧θｐｏｓである場合には、ステップＳ４１０へ移行する。それ以外の場合には、ステップＳ４１２へ移行する。
【００７８】
ステップＳ４１０では、上記ステップＳ４０２で初期値が代入されたｐ、ｑ、ｍａｘＳｓｔｒに（ｉ，ｊ，Ｓｓｔｒ）の値が代入される。
【００７９】
次に、ステップＳ４１２では、構造類似度テーブルＬｓｔｒ＾に含まれる全てのデータ（｛ｉ,ｊ｝、Ｓｓｔｒ）について、ステップＳ４０４〜ステップＳ４１０の処理が終了しているか否かを判定する。終了している場合には、ステップＳ４１４へ移行する。終了していない場合には、ステップＳ４０３へ移行する。
【００８０】
次に、ステップＳ４１４では、上記ステップＳ４１０で値が更新されたｍａｘＳｓｔｒと、構造類似度閾値θｓｔｒとを比較する。ｍａｘＳｓｔｒがθｓｔｒ未満である場合には、ステップＳ４３４へ移行する。ｍａｘＳｓｔｒがθｓｔｒ以上である場合には、ステップＳ４１６へ移行する。
【００８１】
ステップＳ４１６では、クラスタテーブルＣ＾に格納されたクラスタＣ＾（ｐ）に、クラスタＣ＾（ｑ）を統合して、記憶部２に記憶されたクラスタＣ＾（ｐ）を更新する。
【００８２】
次にステップＳ４１８では、クラスタテーブルＣ＾のＣ（ｑ）にφ（空）を格納する。
【００８３】
次にステップＳ４２０では、統合されたクラスタのペアｐ、ｑについての、記憶部２に記憶されている構造度類似度テーブルＬｓｔｒ＾のＬｓｔｒ（｛ｐ, ｑ｝）にφ（空）を格納する。
【００８４】
次にステップＳ４２２では、統合されたクラスタのペアｐ、ｑについての、記憶部２に記憶されている位置類似度テーブルＬｐｏｓ＾のＬｐｏｓ（｛ｐ, ｑ｝）にφ（空）を格納する。
【００８５】
ステップＳ４２３では、クラスタテーブルＣ＾に基づいて、処理対象となるクラスタＣｉを設定する。
【００８６】
次にステップＳ４２４では、構造類似度テーブルＬｓｔｒ＾の値Ｌｓｔｒ（｛ｐ, ｉ｝）及びＬｓｔｒ（｛ｑ, ｉ｝）のうち大きい値の方を、記憶部２に記憶された構造類似度テーブルＬｓｔｒ＾のＬｓｔｒ（｛ｐ, ｉ｝）に格納する。
【００８７】
次にステップＳ４２６では、記憶部２に記憶されている構造類似度テーブルＬｓｔｒ＾のＬｓｔｒ｛ｑ, ｉ｝）にφ（空）を格納する。
【００８８】
次にステップＳ４２８では、位置類似度テーブルＬｐｏｓ＾の値Ｌｐｏｓ（｛ｐ, ｉ｝）及びＬｐｏｓ（｛ｑ, ｉ｝）のうち大きい値の方を、記憶部２に記憶された構造類似度テーブルＬｐｏｓ＾のＬｐｏｓ（｛ｐ, ｉ｝）に格納する。
【００８９】
次にステップＳ４３０では、記憶部２に記憶されている位置類似度テーブルＬｓｔｒ＾のＬｓｔｒ（｛ｑ, ｉ｝）にφ（空）を格納する。
【００９０】
次にステップＳ４３２では、空でない全てのクラスタＣｉについてステップＳ４２４〜ステップＳ４３０の処理が終了しているか判定する。終了している場合には、ステップＳ４０２へ移行する。終了していない場合には、ステップＳ４２３へ移行する。
【００９１】
ステップＳ４３４では、クラスタリング処理ルーチンの処理結果として、記憶部２に記憶されているクラスタテーブルＣ＾が結果として出力される。
【００９２】
クラスタリング処理ルーチンの処理が終了した後には、上記図１２に示す構造化文書情報抽出処理ルーチンのステップＳ１１２に戻る。ステップＳ１１２では、上記ステップＳ１００で入力されたキーワードリストＫＷ＾、上記ステップＳ１０２で得られた階層構造情報テーブルＫ＾、及び上記ステップＳ１１０のクラスタリング処理ルーチンで得られたクラスタテーブルＣ＾に基づいて、クラスタの優先度を算出する。図２２にステップＳ１１２で実行される優先度計算のアルゴリズムを示す。
【００９３】
ステップＳ１１２では、上記ステップＳ１００で入力されたキーワードリストＫＷ＾、上記ステップＳ１０２で得られた階層構造情報テーブルＫ＾、及び上記ステップＳ１１０で作成されたクラスタテーブルＣ＾に基づいて、各クラスタについて、当該クラスタに属する各ノード毎に、当該ノードが含むキーワードの重みの和を算出し、その最大値を当該クラスタの優先度として計算する。
【００９４】
次にステップＳ１１４では、上記ステップＳ１１２で算出された優先度順に、上記ステップＳ１１０で算出したクラスタリング結果を出力部４により出力する。
【００９５】
次に、本実施の形態に係る文書構造解析装置の実際の動作例を以下で説明する。
【００９６】
＜動作例１＞
動作例１では、同一ページ内の繰り返し部分の抽出例について説明する。動作例１では、上記図８に示すｗｅｂページが文書構造解析装置に入力される。また、上記図８に示すｗｅｂページのｂｏｄｙ以下のＨＴＭＬタグ構造を上記図９に示す。また、入力部１には、図２３に示すキーワードリストが入力される。また、入力部１に入力されるパラメータとして、構造類似度閾値θｓｔｒ＝０．７、位置類似度閾値θｐｏｓ＝０．８、探索範囲閾値γ０＝１．５のデータが入力部１に入力される。
【００９７】
ステップＳ１０２では、上記図１０に示すＤＯＭ（Document Object Model）ツリーが生成され、上記図１１に示す階層構造情報テーブルＫ＾が作成される。
【００９８】
ステップＳ１０４では、図２４に示す位置情報テーブルＰ＾が作成される。
【００９９】
次にステップＳ１０８において、上記図１３及び上記図１４に示す候補探索処理ルーチンが実行される。
【０１００】
最初のステップＳ２０８では、ｎ１←１が代入される。
【０１０１】
次に、ステップＳ２１６で、入力されたｗｅｂページのペアが同一であるか否かを判定する。動作例１では、ペアとなるｗｅｂページが同一であり、ステップＳ２１８へ移行する。
【０１０２】
次のステップＳ２１８で、ｎ１のsibling（兄弟ノード）はいないので、ｎ２←φ（空）が代入される。
【０１０３】
そして、ステップＳ３０４では、ｎ１←２が代入される。
【０１０４】
そして、２回目のステップＳ２１８では、ｎ２←１４が代入される。
【０１０５】
そして、ステップＳ２２４において、構造類似度計算部１６が呼び出される。構造類似度計算部１６では、ステップＳ１０２において階層構造解析部１０により算出された上記図１１に示す階層構造情報テーブルＫ＾から、Ｋ＾（２）＝（０，１０，２），Ｋ＾（１４）＝（０，９，２）が読み込まれる。そして、階層構造情報テーブルＫ＾から読み込まれた値を上記（１）式に代入して計算すると、以下のように構造類似度が算出される。
【０１０６】
【数３】
2014049088.tif 000005
【０１０７】
上記（３）式で算出された構造類似度Ｓｓｔｒは、ｓｉｍへ代入される。
【０１０８】
そして次のステップＳ２２６において、上記（３）式で算出された構造類似度Ｓｓｔｒが構造類似度閾値θｓｔｒ以上であるか否かが判定される。上記（３）式で算出された構造類似度Ｓｓｔｒ（２，１４）≒０．９２で、構造類似度閾値θｓｔｒ＝０．７であるため、構造類似度Ｓｓｔｒ（２，１４）の値が代入されたｓｉｍとθｓｔｒの関係は、ｓｉｍ≧とθｓｔｒとなる。従って、ステップＳ２２８へ移行する判定がされる。
【０１０９】
次に、ステップＳ２２８では、上記ステップＳ２１８でｎ２←１４が代入されているため、位置情報テーブルＰＢ＾の１４番のノード番号に対応する位置情報が（ｘ２，ｙ２，ｗ２，ｈ２）に代入される。
【０１１０】
次に、ステップＳ２３０では、上記図２４に示す動作例１の位置情報テーブルＰ＾から、（ｘ１，ｙ１，ｗ１，ｈ１）＝（０．５６，０．３７，１２，８．５）、（ｘ２，ｙ２，ｗ２，ｈ２）＝（０．５６，９．２５，４，０．７）であり、又上記ステップＳ２０４で、γ＝１．５が代入されているので、ステップＳ２３０の判定式に照らすと、範囲内であると判定される。
【０１１１】
そして、候補bnode←φ（空）が代入されているので、ステップＳ２３８で、候補bnode←１４が代入され、score←０．９２の値が代入され、候補が更新される。
【０１１２】
次にステップＳ２４０では、ｎ２←１５が代入される。
【０１１３】
次に２回目のステップＳ２２４では、ｎ１（＝２）とｎ２（＝１５）について、上記の処理が行われる。ここで、ｎ１（＝２）とｎ２（＝１５）の構造類似度Ｓｓｔｒ（２，１５）≒０．４１であり、構造類似度閾値θｓｔｒ＝０．７未満であるので、何もせずに次のノードを調べる。ノード２４までは、構造類似度Ｓｓｔｒが構造類似度閾値θｓｔｒ＝０．７未満であるので、何もしない。
【０１１４】
そして、ｎ２がノード２５になったときに、ｎ１＝２とｎ２＝２５の構造類似度Ｓｓｔｒ（２，２５）≒０．９２で、かつ上記ステップＳ２３０で判定される表示位置も範囲内なので、ステップＳ２３２へ移行する。
【０１１５】
そして、ステップＳ２３２では、現在の候補bnode（＝１４）と、ノード２５を比較する。ノード２５はノード１４と親子関係にないので、ステップＳ２３４へ移行する。
【０１１６】
そして、ステップＳ２３４では、ノード２とノード１４の組の構造類似度の値が代入されているscoreの値を構造類似度テーブルＬｓｔｒ＾に格納する。さらに、ノード２とノード１４の組の位置類似度を計算し、位置類似度テーブルＬｓｔｒ＾に格納する。そして現在の候補bnode←２５として、更新する。
【０１１７】
同様に、上記の処理を進めると、ｎ１＝５とｎ２＝８に進んだときに、ステップＳ２２６の構造類似度の条件と、ステップＳ２３０の表示位置の条件が満たされるので、ステップＳ２３８において候補bnodeを更新する。
【０１１８】
次に、ｎ１＝５とｎ２＝１０のときに、再度、ステップＳ２２６の構造類似度の条件とステップＳ２３０の表示位置の条件が満たされるが、ノード８と１０は親子関係にありノード１０の方が構造類似度が高いので、ステップ２３６へ移行し、ノード５とノード８の組は保存されないことになる。
【０１１９】
以上のように処理がされた結果、上記図１２に示すステップＳ１０８の候補探索処理ルーチンの実行結果として、図２５に示すような構造類似度テーブルＬｓｔｒ＾、図２６に示すような位置類似度テーブルＬｐｏｓ＾、及び図２７に示すようなクラスタテーブルＣ＾が作成される。
【０１２０】
次に、上記図１２に示すステップＳ１１０において、上記図２０に示すクラスタリング処理ルーチンが実行される。
【０１２１】
例えば、ノード２と２５については、上記図２５に示すように構造類似度Ｓｓｔｒ（２，２５）≒０．９２であって、閾値（θｓｔｒ＝０．７）以上であるが、上記図２６に示すように、位置類似度Ｓｐｏｓ（２，２５）≒（０．３６，１，０．６７，０．６７）であって、上記図２０に示すクラスタリング処理ルーチンのステップＳ４０８の条件を満たさないので統合されない。
【０１２２】
以上のような処理の結果、クラスタリング結果は図２８に示すような結果となる。
【０１２３】
クラスタリング処理ルーチンの処理が終了した後には、上記図１２に示す構造化文書情報抽出処理ルーチンのステップＳ１１２に戻る。ステップＳ１１２では、上記ステップＳ１１０のクラスタリング処理ルーチンで作成されたクラスタテーブルＣ＾に基づいて、クラスタの優先度を算出する。
【０１２４】
従って、ステップＳ１１２では、上記図２８に示す各クラスタについて、上記図２２に示すアルゴリズムの処理を繰り返す。例えば、上記図２８に示すクラスタ２は{２，１４}のノードを含んでおり、上記図１１に示すように、ノード２は上記図２３に示すキーワード”タイトル”，および，”著者”を共に含んでいるので、優先度は２となる。同様に、ノード１４も優先度は２となる。クラスタの優先度は各ノードの優先度の最大値なので、クラスタ２の優先度は２となる。また、クラスタ６は、ノード６が”タイトル”を、ノード７が”著者”を含んでいるので、それらの最大値がクラスタの優先度となるので、優先度は１となる。
【０１２５】
次のステップＳ１１４では、上記ステップＳ１１２で算出された優先度順に、上記ステップＳ１１０で算出したクラスタリング結果を出力する。
従って、ステップＳ１１２では、図２９に示すように、優先度順にクラスタが出力される。
【０１２６】
図８及び上記図２９を参照すると、階層構造のある繰り返しが正しく抽出されていることがわかる。
【０１２７】
＜動作例２＞
動作例２では、異なるページの繰り返し部分の抽出例について説明する。動作例２では、図３０に示すｐａｇｅＡ，ｐａｇｅＢが、ｗｅｂページとして文書構造解析装置に入力される。また、上記図３０に示すｗｅｂページのｂｏｄｙ以下のＨＴＭＬタグ構造を図３１に示す。また、入力部１には、図３２に示すキーワードリストが入力される。また、入力部１に入力されるパラメータとして、構造類似度閾値θｓｔｒ＝０．７、位置類似度閾値θｐｏｓ＝０．８、探索範囲閾値γ１＝０．５のデータが入力部１に入力される。
【０１２８】
動作例２における各データが入力されると、上記図１２に示す構造化文書情報抽出処理ルーチンが実行され、図３３に示す結果が出力される。
【０１２９】
上記図３０及び上記図３３を参照すると、ページ間の要素の対応が正しく抽出されていることがわかる。
【０１３０】
以上説明したように、本実施の形態に係る文書構造解析装置によれば、構造化文書の要素の階層構造を解析し、解析された構造化文書を表示したときの構造化文書の各要素の表示位置を解析し、構造化文書における複数の要素のうちの２つの要素間の各々について、要素の構造に関する構造類似度及び要素の表示位置に関する位置類似度を算出し、構造類似度と、位置類似度とに基づいて、構造化文書における複数の要素をクラスタリングすることにより、構造化文書の要素を精度良くクラスタリングできる。
【０１３１】
また、本実施の形態に係る文書構造解析装置によれば、人間にとって意味がありそうな（すなわち，表やリスト等の様に隣接して配置される）繰り返し構造を抽出することができる。
【０１３２】
また、本実施の形態によれば、候補探索部がクラスタの候補を親子関係にないものに制限できるため、階層的な繰り返し構造がある場合でも効率的に抽出できる。
【０１３３】
また、繰り返し構造に優先度が付けられるので、多数のクラスタが生成された場合でも効率的に提示できる。
【０１３４】
また、構造類似度計算にノード名のヒストグラムを使うことで、子ノードの数に依らず、常に一定の計算量(タグ名の数) で高速に構造の比較を行うことができる。
【０１３５】
また、ＨＴＭＬ文書と抽出したい部分の組からなる学習データをゼロから作成する際には、想定されるデータとしてキーワードを変更して、クラスタリング結果の提示順序を変えることもできる。
【０１３６】
また、サイトの更新による再学習においては、既に抽出されたデータをキーワードに設定することで、クラスタリング結果から効率よく学習データとなる要素を取得することができる。
【０１３７】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【０１３８】
本実施の形態では、構造類似度計算部１４は、階層構造解析部１０で算出されるノードのヒストグラムに基づいて、２つのノードのペア各々について２つの要素間の階層構造に関する類似度を計算したが、他の構成としても良い。
【０１３９】
例えば、構造類似度計算部１４について、ノードＡとノードＢが与えられた場合に、それらのノードをルートとする部分木のＨＴＭＬ開始タグ、終了タグを一つの文字とし、２つの文字列間のnormalized edit distance（ＮＤ）を計算し、構造類似度として１−ＮＤを返す構成としても良い。normalized edit distanceについては例えば、B. Liu, "Web Data Mining," pp.384-386, Springer, 2007に記述がある．
【０１４０】
また、本実施の形態では、優先度計算部２２は、キーワードリストＫＷ＾に基づいて、１つのクラスタに含まれるノードについて、各ノードの優先度を各ノードが含むキーワードの重みの和とし、その最大値を優先度として算出したが、他の構成としても良い。
【０１４１】
例えば、優先度計算部２２は、キーワードのリスト、およびクラスタが指定され、クラスタの構成要素（ノード）について、いずれか一つのノードにすべてのキーワードが含まれていれば１、そうでなければ０を返すようにすることができる。このアルゴリズム例を図３４に示す。
【０１４２】
また、優先度計算部２２は、クラスタが指定され、クラスタの構成要素（ノード）の数を優先度として返すようにすることができる。このアルゴリズム例を図３５に示す。
【０１４３】
また、優先度計算部２２は、クラスタが指定され、クラスタに含まれる各ノードについて、ｗｅｂページのリーフノードの数をＮ、クラスタに含まれるノードをルートとする部分木が含むリーフノードの数をｎ、各ノードの優先度を
【０１４４】
【数４】
2014049088.tif 000006
【０１４５】
として、その平均値をクラスタの優先度として返すようにすることができる。このアルゴリズム例を図３６に示す。
【０１４６】
また、上述の文書構造解析装置は、内部にコンピュータシステムを有しているが、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
【０１４７】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能である。
【符号の説明】
【０１４８】
１０   階層構造解析部
１２   位置情報解析部
１４   構造類似度計算部
１６   位置類似度計算部
１６   構造類似度計算部
１８   候補探索部
２０   クラスタリング部
２２   優先度計算部
【図１】
2014049088.tif 000007
【図２】
2014049088.tif 000008
【図３】
2014049088.tif 000009
【図４】
2014049088.tif 000010
【図５】
2014049088.tif 000011
【図６】
2014049088.tif 000012
【図７】
2014049088.tif 000013
【図８】
2014049088.tif 000014
【図９】
2014049088.tif 000015
【図１０】
2014049088.tif 000016
【図１１】
2014049088.tif 000017
【図１２】
2014049088.tif 000018
【図１３】
2014049088.tif 000019
【図１４】
2014049088.tif 000020
【図１５】
2014049088.tif 000021
【図１６】
2014049088.tif 000022
【図１７】
2014049088.tif 000023
【図１８】
2014049088.tif 000024
【図１９】
2014049088.tif 000025
【図２０】
2014049088.tif 000026
【図２１】
2014049088.tif 000027
【図２２】
2014049088.tif 000028
【図２３】
2014049088.tif 000029
【図２４】
2014049088.tif 000030
【図２５】
2014049088.tif 000031
【図２６】
2014049088.tif 000032
【図２７】
2014049088.tif 000033
【図２８】
2014049088.tif 000034
【図２９】
2014049088.tif 000035
【図３０】
2014049088.tif 000036
【図３１】
2014049088.tif 000037
【図３２】
2014049088.tif 000038
【図３３】
2014049088.tif 000039
【図３４】
2014049088.tif 000040
【図３５】
2014049088.tif 000041
【図３６】
2014049088.tif 000042