(57)【要約】【課題】  ほぼ全ての種類のウェブページに適用できる、ウェブページ情報を抽出するための方法および装置を提供する。【解決手段】  情報ブロック抽出装置は、更に細かい精度にまで及ぶ処理ユニットを用いて、ウェブページ１０１内の情報ブロックを抽出するためのルールを自動的に生じさせる。具体的には、構造レベルでの自動的な繰り返しパターン発見と、意味レベルでのクラスタリングが、本発明の装置及び方法の根幹をなし、本発明を保証するものである。【選択図】        図１
2005092889.tif 000002
【特許請求の範囲】
【請求項１】
１つのウェブページをコヒーレントコンテンツを有する複数の情報ブロックにセグメント化するための情報ブロック抽出方法であって、
前記ウェブページの構造情報ブロックツリーを生成する構造情報ブロック抽出ステップと、
構造情報ブロックをクラスタリング及びマージングし、結果として得られるブロックの意味にラベル付けする意味情報ブロック抽出ステップと、
を含む情報ブロック抽出方法。
【請求項２】
前記構造情報ブロック抽出ステップは、
ＨＴＭＬ ＤＯＭツリーおよびＨＴＭＬタグトークンストリームの両方を用いて前記ウェブページを表わすステップと、
前記ウェブページ内で繰り返しパターンを自動的に生じさせて、不適切な前記繰り返しパターンをフィルタアウトするとともに、候補パターンと対応するインスタンスとから成るセットを生成するステップと、
前記ウェブページ内で対応する領域と前記繰り返しパターンとを一致させるステップと、
検知されたページ領域にしたがってＲＳＴツリーを構成するステップと、
前記複数の情報ブロックそれぞれ内の全ての情報項目を識別するステップと、
前記ＲＳＴツリーおよび情報項目分割に基づいて、最終的な前記構造情報ブロックツリーを構成するステップと、
を含む、請求項１に記載の情報ブロック抽出方法。
【請求項３】
前記意味情報ブロック抽出ステップは、
前記構造情報ブロックツリーから適切な精度で基本情報ブロックを取得するステップと、
前記基本情報ブロックをクラスタリングして意味情報ブロックへとマージングするステップと、
前記ウェブページの意味ブロック内で主テキスト情報ブロック及び関連リンクブロックにラベル付けするステップと、
を含む、請求項１又は２に記載の情報ブロック抽出方法。
【請求項４】
１つのウェブページをコヒーレントなコンテンツを有する複数の情報ブロックに分割するための情報ブロック抽出装置であって、
前記ウェブページの構造情報ブロックツリーを生成するための構造情報ブロック抽出ユニットと、
構造情報ブロックをクラスタリング及びマージングし、結果として得られるブロックの意味にラベル付けする意味情報ブロック抽出ユニットと、
を備える情報ブロック抽出装置。
【請求項５】
前記構造情報ブロック抽出ユニットは、
ＨＴＭＬ ＤＯＭツリーおよびＨＴＭＬタグトークンストリームの両方を用いて前記ウェブページを表わすためのページ表示ユニットと、
前記ウェブページ内で繰り返しパターンを自動的に生じさせて、不適切な繰り返しパターンをフィルタアウトし、候補パターンと対応するインスタンスとから成るセットを生成するための前記繰り返しパターン発見ユニットと、
前記ウェブページ内で対応する領域と前記繰り返しパターンとを一致させるための領域検知ユニットと、
検知されたページ領域にしたがってＲＳＴツリーを構成するためのＲＳＴツリー生成ユニットと、
前記複数の情報ブロックそれぞれ内の全ての情報項目を識別するための情報項目検知ユニットと、
前記ＲＳＴツリーおよび情報項目分割に基づいて、最終的な前記構造情報ブロックツリーを構成するための構造情報ブロックツリー生成ユニットと、
を備える、請求項４に記載の情報ブロック抽出装置。
【請求項６】
前記意味情報ブロック抽出ユニットは、
前記構造情報ブロックツリーから適切な精度で基本情報ブロックを取得するための基本情報ブロック取得ユニットと、
前記基本情報ブロックをクラスタリングして意味情報ブロックへとマージングするための意味情報ブロック生成ユニットと、
前記ウェブページの意味ブロック内の主テキスト情報ブロックおよび関連リンクブロックにラベル付けするための主テキストブロック・関連リンクブロック検知ユニットと、
を備える、請求項４又は５に記載の情報ブロック抽出装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ウェブページ内でコヒーレントな領域を抽出するための装置および方法に関する。本発明の方法および装置は、コンテンツおよび機能に基づいて１つのウェブページを複数の情報ブロックに分割することができるとともに、ウェブページ処理の精度を全ページから１つの情報ブロックへと広げることができ、したがって、ウェブページの機械的処理が容易になる。
【背景技術】
【０００２】
近年、ビジネスの用途において、ウェブページのコンテンツおよび構造は、ユーザが簡単にアクセスでき且つ扱い易いように、益々複雑になってきている。ウェブページは、通常相互に大まかに結合された様々なトピックスおよび機能の集まりである。人間は、ウェブページ内の様々な意味および機能を有する情報領域を簡単に識別することができるが、それは自動処理システムにとっては非常に難しいものである。これは、ＨＴＭＬが当初においてコンテンツ記述のためではなくプレゼンテーションのために発案されたものだからである。これまで、既存の殆どのウェブＩＲ（情報検索）システム、ＩＥ（情報抽出）システム、ＤＭ（データマイニング）システムは、ウェブページ内の情報ブロックを十分に考慮することなく、ウェブページを一つの単位として扱っており、そのことで機械的処理の最中に多くの問題が生じている。
【０００３】
前述した問題のため、科学者らは、１つのウェブページを、そのコンテンツおよび機能に基づいて分割する方法を考慮し始めている。以下に、関連する研究を挙げる。
【０００４】
【非特許文献１】Xiaoli Li，Bing Liu，Tong-Heng phang，Minqing Hu，微小情報単位を用いたインターネット検索，（Using Micro Information Units for Internet Search），第１１回ＣＩＫＭ予稿集（Proceedings of the eleventh international conference on Information and knowledge management），（米国），エーシーエム・プレス（ACM Press），２００２年，ｐ．５６６−５７３
【非特許文献２】Ziv Bar-Yossef，Sridhar Rajagopalan，「データマイニングによるテンプレート検知およびその用途」（"Template Detection via Data Mining and its Applications"），第１１回ワールドワイドウェブ国際会議予稿集（Proceedings of the Eleventh International Conference on World Wide Web）,（米国），エーシーエム・プレス（ACM Press），２００２年，ｐ．５８０−５９１
【非特許文献３】Soumen Chekrabarti，Mukul Joshi，Viverk Tawde，「テキスト、マークアップ、タグ、ハイパーリンクを使用した拡張トピック蒸留」（“Enhanced Topic Distillation using Text, Markup Tags, and Hyperlinks”），（米国），ＳＩＧＩＲ Ｃｏｎｆｅｒｅｎｃｅ，２００１年
【非特許文献４】Shian-Hua Lin，Jan-Ming Ho，「ウェブドキュメントからの情報コンテンツブロックの発見」（“Discovering Informative Content Blocks from Web Documents”），（カナダ），ＳＩＧＫＤＤ’０２，２００２年
【発明の開示】
【発明が解決しようとする課題】
【０００５】
非特許文献１および非特許文献２は、１つのウェブページを意味的にコヒーレントな複数の領域に分割する、それぞれの方法を提案しているが、両者とも、非常に簡単な発見的方法を使用している。１つのウェブページ内で情報コンテンツブロックを検知する非特許文献４の方法は、普遍性を欠いている。これは、この方法が＜テーブル＞タグを含む表形式のページしか処理できないためである。非特許文献３は、ＨＴＭＬ ＤＯＭツリーをセグメント化して、他のページおよびリンクに関連する中間サブツリーの権限およびハブスコアを計算する。これは、現行ページのコヒーレントなトピック領域を見つけるという本発明の目的とは異なる。
【０００６】
本発明は、ほぼ全ての種類のウェブページに適用できる方法および装置であって、ウェブページ内の情報ブロックを抽出するためのルールを自動的に生じさせる方法および装置を提供する。
【課題を解決するための手段】
【０００７】
上述した課題を解決し、目的を達成するため、請求項１に係る、１つのウェブページをコヒーレントコンテンツを有する複数の情報ブロックにセグメント化するための情報ブロック抽出方法は、図１に示すように、前記ウェブページ（１０１）の構造情報ブロックツリー（１０３）を生成する構造情報ブロック抽出ステップと、構造情報ブロックをクラスタリング及びマージングし、結果として得られるブロックの意味にラベル付けする意味情報ブロック抽出ステップと、を含むことを特徴とする。
【０００８】
上述した課題を解決し、目的を達成するため、請求項４に係る、１つのウェブページをコヒーレントなコンテンツを有する複数の情報ブロックに分割するための情報ブロック抽出装置は、図１に示すように、前記ウェブページ（１０１）の構造情報ブロックツリー（１０３）を生成するための構造情報ブロック抽出ユニット（１０２）と、構造情報ブロックをクラスタリング及びマージングし、結果として得られるブロックの意味にラベル付けする意味情報ブロック抽出ユニット（１０４）と、を備えることを特徴とする。
【発明の効果】
【０００９】
本発明の方法は、２つの異なるレベル、すなわち、構造レベルおよび意味レベルで情報ブロック抽出を行なうため、非常に有効である。特に、構造レベルにおける自動繰り返しパターンの発見と、意味レベルにおけるクラスタリングは、本発明の抽出方法の成功の根幹をなすとともに、成功を保証するものである。
【００１０】
情報ブロックがウェブページ内で抽出された後、ＩＲ，ＩＥ，ＤＭ等の機械処理システムは、より細かい精度でウェブページを処理することができ、性能を著しく向上させることができる。
【発明を実施するための最良の形態】
【００１１】
以下に添付図面を参照して、この発明に係るウェブページのための情報ブロック抽出装置及び情報ブロック抽出方法の好適な実施の形態を詳細に説明する。まず、以下に、本発明に係る最良の形態を説明するための数式をまとめて示す。
【００１２】
【数１】
2005092889.tif 000003
【数２】
2005092889.tif 000004
【数３】
2005092889.tif 000005
【数４】
2005092889.tif 000006
【数５】
2005092889.tif 000007
【数６】
2005092889.tif 000008
【数７】
2005092889.tif 000009
【数８】
2005092889.tif 000010
【数９】
2005092889.tif 000011
【数１０】
2005092889.tif 000012
【数１１】
2005092889.tif 000013
【数１２】
2005092889.tif 000014
【数１３】
2005092889.tif 000015
【数１４】
2005092889.tif 000016
【数１５】
2005092889.tif 000017
【数１６】
2005092889.tif 000018
【数１７】
2005092889.tif 000019
【数１８】
2005092889.tif 000020
【数１９】
2005092889.tif 000021
【数２０】
2005092889.tif 000022
【数２１】
2005092889.tif 000023
【数２２】
2005092889.tif 000024
【数２３】
2005092889.tif 000025
【数２４】
2005092889.tif 000026
【数２５】
2005092889.tif 000027
【数２６】
2005092889.tif 000028
【数２７】
2005092889.tif 000029
【数２８】
2005092889.tif 000030
【数２９】
2005092889.tif 000031
【００１３】
図１は、本発明の構成を示す概略図である。装置の入力はウェブページ１０１である。最初に、繰り返しパターン発見に基づいて、構造情報ブロック抽出ユニット１０２によって構造情報ブロックツリー１０３が構成される。その後、意味情報ブロック抽出ユニット１０４は、構造情報ブロックツリー１０３から意味情報ブロック１０５を抽出し、主テキストブロックと関連リンクブロックにラベル付けする。
【００１４】
図２は、構造情報ブロック抽出ユニットを構成するブロック図である。最初に、ページ表示ユニット２０２は、入力ウェブページ２０１をＨＴＭＬ ＤＯＭツリーおよびＨＴＭＬタグトークンストリームに解析する。その後、繰り返しパターン発見ユニット２０３は、ウェブページ２０１内の全ての繰り返しパターンを自動的に生じさせ、あらゆる不適切なパターンをフィルタアウトし、候補パターンと対応するインスタンスとから成るセットを生成する。領域検知ユニット２０４は、繰り返しパターンを、ウェブページ２０１内の元の対応する領域へマッピングする。ＲＳＴツリー生成ユニット２０５は、検知されたページ領域に基づいて情報ブロックを生成し、階層構造を有するＲＳＴツリーを構成する。情報項目検知ユニット２０６は、各情報ブロック内の情報項目の全てを識別する。構造情報ブロックツリー生成ユニット２０７は、ＲＳＴツリーに基づいて、最終的な構造情報ブロックツリー２０８を構成する。
【００１５】
ページ表示ユニット２０２においては、入力ウェブページ２０１のＨＴＭＬ ＤＯＭツリーを構成するためにＨＴＭＬパーサが作成され、ＨＴＭＬタグトークンストリームを得るために、ＤＯＭツリーがプレオーダ移動される。タグトークンストリームとＤＯＭツリーとの間のマッピングテーブルも作成される。ＨＴＭＬファイル内のテキストは、特定のタグ＜ＴＥＸＴ＞として抽出される。
【００１６】
ＨＴＭＬタグトークンストリームの接尾辞トライが繰り返しパターン発見ユニット２０３内で構成され、全ての繰り返しパターンと対応するオカレンスとが接尾辞トライから検索される。
【００１７】
６つのトークン接尾辞を有する接尾辞トライの一例を図４、入力トークンストリームの一例を図５に示す。トークンストリームに使用される接尾辞トライは、（Σ，Ｃ，Ｅ，Ｎ，Ｓ，φ，π）として規定される。ここで、Σは、入力トークンアルファベット、Ｃは、入力トークンシーケンスであり、各トークンは、ｃ∈Ｃ，ｃ∈Σ、Ｅは、トライ内のアークセットである。接尾辞トライ中の各アークｅ∈Ｅは、Σ中の１つのトークンを示す。Ｎは、トライ内の内部ノードのセットであり、Ｓは、リーフノードセットであり、φは、ダミートライルートを示す。もしn2が、ルートとしてノードｎ1をとるサブトライ内のノードであれば、Ｎ∪Ｓにわたっての半順序であるπは、ｎ1πｎ2のように定義される。
【００１８】
２つのノードｎi，ｎjがｎiπｎjの関係を有している場合には、２つのノードを連結するパスｎiｅk．．．．．ｎjを接尾辞トライ内で見出すことができる。パス上のアークをｎiからｎjまで順に結び付けることによって形成される順序付けられたアークシーケンスｅk．．．．．は、ｎiからｎjまでのアークパスである。一方のノードから他方のノードまでのアークパスは、入力トークンシーケンスＣのサブシーケンスを表す。ルートからリーフノードまでのアークパスは、Ｃのトークン接尾辞である。ルートから、複数の子ノードを有するノードであるフォークノードまでのアークパスは、一群のトークン接尾辞の共通のサブシーケンスを表す。これらの接尾辞は、ルートから、ルートとしてフォークノードをとるサブトライ内に含まれるリーフノードまでのアークパスによって表わされる。
【００１９】
そのオカレンスを伴う繰り返しパターンは、繰り返しインスタンスセットである。接尾辞トライ（Σ，Ｃ，Ｅ，Ｎ，Ｓ，φ，π）が構成されると、ルートからフォークノードまでのアークパスを接尾辞トライにおいて直接に抽出することにより、繰り返しパターンを検索することができる。
【００２０】
この場合、フォークノードＮiは、繰り返しパターンとそのオカレンスの検索を例示する一例とされる。フォークノードＮ1により表わされる繰り返しパターン（数式１）は、ルートからフォークノードＮiまでのアークパスである。
【００２１】
パターンのオカレンスは、２項タプル＜ｐ1，ｐ2＞によって表わすことができる。ｐ1は、パターンである数式２の最初のトークンがトークンシーケンスＣ中に現れる位置である。ｐ2は、パターンである数式２の最後のトークンがトークンシーケンスＣ中に現れる位置である。したがって、数式２のオカレンスセットは、数式３のように表わされる。
【００２２】
Ψ（ｓ）は、入力トークンシーケンス中のリーフノードによって表わされる接尾辞の第１のトークンのインデックスを示している。
【００２３】
δ（Ｎi1，Ｎi2）は、Ｎi1からＮi2までのアークパスの長さを示している。
【００２４】
したがって、Ｎiの繰り返しインスタンスセットは、数式４である。
【００２５】
繰り返しパターンの他の属性は、繰り返しインスタンスセットから得ることができる。数式５に示すように、繰り返しパターンの長さは、アークパス中のアークの数である。
【００２６】
数式６に示すように、パターンの繰り返し数は、オカレンスセット中の要素の数を数えることによって計算される。
【００２７】
発見された繰り返しパターンのうちの幾つかは、情報ブロックに対する実際のパターンではなく、そのようなパターンは、フィルタアウトされるべきである。また、幾つかの情報ブロックの繰り返しパターンは同じであっても良い。この種の繰り返しパターンに対しては、異なる情報ブロックからのインスタンスが互いに混合される。したがって、これらのインスタンスは分離されなければならない。
【００２８】
繰り返しパターンおよびそれらのインスタンスを改良するために、“ノンオーバーラッピング”、“レフトディバース”、“コンパクトネス”なる３つの方法が立案される。パターン改良後、当初の繰り返しパターンの９０％がフィルタアウトされ、したがって、その後のステップの効率および有効性を確保できる。３つの改良基準を以下に例示する。
【００２９】
オーバーラッピングの問題は以下のように表現することができる。すなわち、オカレンスセットＲＥＰoccurrenceを伴う繰り返しパターンＲＥＰpatternの場合、少なくとも２つの隣り合うオカレンス＜ｐi,1，ｐi,2＞，＜ｐi+1,1，ｐi+1,2＞（ｐi,2≧ｐi+1,1）が存在する。そのようなオカレンスは、重複オカレンスと称され、また、そのような状況は、非重複状態を維持するために排除されなければならない。
【００３０】
繰り返しインスタンスセットがＲＥＰpattern＝ｅiｅi+1．．．．ｅi+jを伴う場合、数式７を伴う一群の繰り返しインスタンスセットが副生成物として導入されても良い。例えば、オカレンスセット｛＜４，６＞，＜１１，１３＞，＜１８，２０＞｝を伴う繰り返しパターン“＜ＴＲ＞＜ＴＤ＞＜ＴＥＸＴ＞”は、副生成物、すなわち、繰り返しパターン“＜ＴＤ＞＜ＴＥＸＴ＞”および“＜ＴＥＸＴ＞”を導入する。“＜ＴＤ＞＜ＴＥＸＴ＞”のオカレンスセットは、｛＜５，６＞，＜１２，１３＞，＜１９，２０＞｝であり、一方、“＜ＴＥＸＴ＞”のオカレンスセットは、｛＜６，６＞，＜１３，１３＞，＜２０，２０＞｝である。副生成物、すなわち繰り返しパターンセットである数式８は、当初のＲＥＰpatternより多くの情報を提供しないため、除去されなければならない。全ての副生成物パターンおよび副生成物パターンだけがレフトディバースというわけではない。「レフトディバース」とは、繰り返しパターンのそれぞれのオカレンス前の（それぞれのオカレンスの左側にある）トークンが異なるトークンクラスに属すことを意味する。例えば、前述した例では、副生成物“＜ＴＤ＞＜ＴＥＸＴ＞”のそれぞれのオカレンス前のトークンは、“ＴＲ”の同一トークンクラスに属しており、そのため、副生成物“＜ＴＤ＞＜ＴＥＸＴ＞”はレフトディバースではない。したがって、繰り返しインスタンスセットのパターンがレフトディバースでない場合には、この繰り返しインスタンスセットは、副生成物と見なされ、切り捨てられなければならない。
【００３１】
異なる情報ブロック同士の情報項目は、同じ繰り返しパターンを共有する可能性を有しているため、繰り返しパターンのオカレンスの共通の親は、１つの情報ブロックに対するノードを常に含まない可能性がある。図６は、コンパクト基準の一例を示す図である。図６に示されるように、（１）の情報項目は、常に、（２）の情報項目と同じフォーマットを有している。そのため、オカレンスがノード２およびノード３の下で現れる繰り返しパターンが存在する。ノード１は、これらのオカレンスの共通の親であるが、実際には、ノード１は、情報ブロックを示してはいない。この不確定性により、繰り返しパターンのオカレンスに対する共通の親を計算することにより情報ブロックの位置を発見するという試みが失敗する。幸いにも、１つの情報ブロック内の情報項目は、コンパクトに順序正しく配列されている。この特徴は、繰り返しパターンに基づいて情報ブロックを識別する方法の手助けをする。
【００３２】
数式９を伴う繰り返しインスタンスセットの場合、オカレンスセットをセグメント化して、それらをコンパクト基準に一致させるために、数式１０に示す閾値βを規定することができる。
【００３３】
ここで、ｋは数式１１と等価であり、λは制御パラメータである。オカレンスである数式１２とオカレンスである数式１３との間の間隔がβを超えると、オカレンスセットは、その間隔の位置で分割される。
【００３４】
領域検知ユニット２０４では、繰り返しパターンおよび対応するインスタンスは、ウェブページ２０１において対応する領域を得るために、ＨＴＭＬ ＤＯＭツリーに逆マッピングされる。ウェブ２０１ページ内の各パターンのインスタンスセットに対して、ページのＤＯＭツリー内で対応するノード（ノードの数をＮにする）を見つけることができる。このＤＯＭツリー内において、Ｎ個の全てのノードから成る最も小さいサブツリーは、パターンの最小サブツリー（ＳＳＴ）と称される。ここで、ＳＳＴのルートを使用してＳＳＴを示すことができ、また、ＳＳＴのルートを情報ＲＳＴノード（ＲＳＴ、最小サブツリーのルート）と呼ぶことができる。各ＳＳＴは、ウェブページ２０１の候補領域である。
【００３５】
ＲＳＴツリー生成ユニット２０５においては、ＨＴＭＬ ＤＯＭツリー内でのＲＳＴの位置に従って、複数のＲＳＴを１つのツリー構造に編成することができる。ＲＳＴツリーの構成プロセスは、実際には、ＨＴＭＬに適用されるトリミングプロセスである。このプロセスは、ＨＴＭＬ ＤＯＭツリーのルートから始まり、その後、非ＲＳＴノードを切り取る。最後にトリミングされたＨＴＭＬが情報ＲＳＴツリーである。
【００３６】
各情報ブロック内の全ての情報項目は、情報項目検知ユニット２０６内で識別されても良い。各情報ブロックは、常に、幾つかの情報項目から成る。図７は、情報ブロック内に含まれる情報項目の一例を示す図である。多くの場合、情報ブロック内には、図７に示される例のように、ヘッドあるいはテイル、又はこれらの両方が存在する。したがって、情報ブロックは、３つの部分、すなわち、情報項目と、ヘッドと、テイルとに更に分割される。情報項目は、情報ブロックの最も重要な部分である。各項目は、情報ブロック内の個々の構成要素であり、一方、ブロックの様々な項目は、シンタクスとプレゼンテーションの両方において同様のパターンを有している。ヘッドは、情報ブロックに属するコンテンツであり、全ての情報項目の前に来る。テイルは、情報ブロックに属するコンテンツであり、全ての情報項目の後に来る。以下、情報項目分割方法について説明する。
【００３７】
最初に、ＲＳＴツリー内のリーフノードに対応する情報ブロックをセグメント化する方法について説明する。
【００３８】
リーフＲＳＴノードの分割は、前のＲＳＴツリー構成段階で抽出された条件付きの繰り返しインスタンスセットを選択し、その後、これらを使用して情報項目を識別することから始まる。以下、適切な繰り返しパターンを評価するための基準について説明する。
【００３９】
（繰り返し数）
繰り返しインスタンスセットの繰り返し数は、数式１４に示すように、オカレンスセット中の要素の数を数えることによって計算される。
【００４０】
（パターン長）
繰り返しパターンの長さは、数式１５に示すように、アークパス内のアークの数として測定される。
【００４１】
（規則性）
繰り返しインスタンスセットの規則性は、２つの隣り合うオカレンス同士の間隔の標準偏差を計算することによって測定される。オカレンスセットである数式９を伴う繰り返しインスタンスセットＲＥＰinstanceの場合、２つの隣り合うオカレンス同士の間隔は、数式１６となる。繰り返しインスタンスセットの規則性は、間隔の標準偏差を間隔の平均で割ったものに等しい。
【００４２】
ＲＥＰinstanceが与えられ、数式１７を平均間隔とし、ｋをオカレンスセット中のオカレンスの数とすると、ＲＥＰinstanceの規則性は、数式１８によって計算することができる。
【００４３】
（カバレージ）
カバレージは、繰り返しインスタンスセット内に含まれるコンテンツの量を示すために使用される。数式９が所与のＲＥＰinstanceのオカレンスセットであるとすると、カバレージは数式１９のように計算される。
【００４４】
ここで、数式２０は、最後のオカレンスの終了位置であり、数式２１は、最初のオカレンスの開始位置であり、‖ＮRST‖は、ＲＳＴノードＮRSTで示されるＨＴＭＬ ＤＯＭツリー内の最小サブツリーの先行順でトラバースされたトークンシーケンスの長さである。
【００４５】
ランキング方法は、通常、これらの基準のうちの１つ以上を別個に或いは組み合わせて適用する。本発明では、４つの基準を取り入れたランキング方法を使用する。繰り返しインスタンスセットのランクは、図１６に示すように計算することができる。図１６は、繰り返しインスタンスセットのランクの計算を説明する説明図である。
【００４６】
特定の情報ブロック下の情報項目の識別は、実際には、単位（子サブツリー）クラスタリングのプロセスである。単位クラスタリングのプロセスは、選択された繰り返しインスタンスセットに基づく。順序付けられたセットΠ＝｛ＳＴ1，ＳＴ2，ＳＴ3…ＳＴi｝がＲＳＴノードＮRST下のサブＤＯＭツリーを表すと仮定する。識別アルゴリズムは、Π＝｛ＳＴ1，ＳＴ2，ＳＴ3…ＳＴi｝をセグメント化して、結果セットである数式２２を形成することである。項目iは、ｉ番目の情報項目を表わすサブツリーから成る。ヘッドは、最初の情報項目を表わすサブツリーの前に来るサブツリーの集まりであり、一方、テイルは、最後の情報項目を表わすサブツリーの後に来るサブツリーの集まりである。分割は、Πに対する隣接アレイＡADJを用いて行なわれる。ＡADJの各タプルは、Π内の２つの隣り合う要素の隣接関係に対応する整数である。ｉが０から始まるとすると、ＡADJ［ｉ］は、１つのオカレンスのマッピング結果にＳＴi+1，ＳＴi+2を含む繰り返しインスタンスセットの数によって測定されるΠ内のＳＴi+1，ＳＴi+2の隣接関係を示している。したがって、Π内の要素の数が‖Π‖である場合、隣接アレイＡADLの長さは‖Π‖−１となる。Ｓｃｏｐｅ（ＲＥＰinstance）は、ＲＥＰinstanceの最初のオカレンスの開始位置からのトークンおよびＲＥＰinstanceの最後のオカレンスの終了位置からのトークンを含むＤＯＭツリー内の一群のサブツリーとして定義される。ここで、数式２９を参照すると、すなわち、Πnon-itemに属し且つＳｃｏｐｅ（ＲＥＰinstance）に対応するサブツリーの前に来るサブツリーがヘッドであると定義する。Πnon-itemに属し且つＳｃｏｐｅ（ＲＥＰinstance）に対応するサブツリーの後に来るサブツリーがテイルである。
【００４７】
パラメータτは、条件付き分割点のための閾値として使用される。通常、このパラメータは数式２３のように計算される。
【００４８】
ここで、μは、１〜０．５の範囲の定数である。
【００４９】
ＡADL［ｉ］φτの場合には、ＳＴiが分割点である。
【００５０】
図８、９、及び、１０は、ＲＳＴツリー内のリーフノードの情報項目を識別する例を示す図である。この例において、ＲＳＴノードＮ（情報ＲＳＴノードＮ）のサブＤＯＭツリー（図８参照）は、５つのサブツリーＳＴ1，ＳＴ2，ＳＴ3，ＳＴ4，ＳＴ5を有している。Ｎと関連する繰り返しインスタンスセットΩinstanceの選択されたグループは、そのオカレンスセットＲＥＰinstanceがオカレンスである数式２４と数式２５から成る１つの繰り返しインスタンスセットＲＥＰinstanceだけを有している。アルゴリズムは、図１０に示される状態１から始まる。例えば、オカレンスである数式２４を＜ＳＴ2，ＳＴ3＞に対してマッピングし且つオカレンスである数式２５を[ＳＴ4，ＳＴ5]に対してマッピングするマッピングФにより、Πnon-itemおよびＡADJが得られる（図１０の状態２参照）。Ωinstanceは、オカレンスセットＲＥＰoccurrenceを伴う繰り返しインスタンスセットを１つしか含んでいないため、Ｓｃｏｐｅ（ＲＥＰinstance）の結果セット内にＳＴiだけが含まれず、すなわち、ＳＴ1だけが任意の情報項目を表わさない。そのため、Πnon-item＝｛ＳＴ1｝となる。これは、ＳＴ2，ＳＴ3が数式２６の結果セットに属し且つＳＴ4，ＳＴ5が数式２７の結果セットに属しており、ＡADJ［１］およびＡADJ［３］の値が１で且つＡADJ内の他の要素の値が０であるからである。条件付き分割点における閾値τはＡADJから計算され、この例において、それは０．５と設定される。アルゴリズムは、ＡADJ、τ、Πnon-itemを利用して、Πから結果セットである数式２２（図１０の状態３参照）を形成する。数式２８を構成するため、アルゴリズムは、まずＳＴ1をチェックし、ＳＴ1がΠnon-itemに属し且つＳＴ2がΠnon-itemに属していないため、ヘッドがＳＴ1を含んでいるだけであることを見出す。ＳＴ5がΠnon-item内に含まれていないため、テイルは空集合である。ヘッドセット内の最後の要素とテイルセット内の最初の要素との間のΠの要素は、情報項目を表す。その後、アルゴリズムは、２つの隣り合う要素の隣接関係に基づいて、情報項目を表わすこれらの要素を集める。ＡADJ［１］の値は閾値τを上回り、一方、ＡADJ［２］の値は閾値τを上回らない。したがって、ＳＴ2，ＳＴ3は項目1のメンバである。そのため、ＡADJ［３］，ＡADJ［４］により、ＳＴ4，ＳＴ5が項目2を形成する。
【００５１】
ＲＳＴツリーの内部ノードの場合、この内部ノードは、リーフＲＳＴノードとは異なる情報項目の識別を行なう子孫ＲＳＴノードを含んでいる。前の段階で抽出された内部ＲＳＴノードに関連する繰り返しインスタンスセットは、子孫ＲＳＴノードによって示される情報ブロックのパターンを含んでいても良く、したがって、そのような繰り返しインスタンスセットは、内部ノード内の情報項目の識別には適していない。その結果、子孫ＲＳＴノードの干渉を排除することにより、繰り返しパターンセットを再抽出する必要がある。
【００５２】
子孫ＲＳＴノードの影響を除去するという考えは、わかりやすく、単純である。内部ＲＳＴノードＮに対しては、最初に、各子孫ＲＳＴノードのサブＤＯＭツリーを特定の＜サブ＿ＲＳＴ＞ノードに個別に圧縮することにより、ＮのサブＤＯＭツリーを特定のサブＤＯＭツリーＴinner nodeに変換することができる。したがって、子孫ＲＳＴノードの内部構造は目に見えない。図１１は、内部ＲＳＴノードのサブＤＯＭツリーの変換の一例を示す図である。次に、特定のサブＤＯＭツリーＴinner nodeに前述したパターン発見アルゴリズムが施され、内部ＲＳＴノードＮに関連する繰り返しインスタンスセットを検索することができる。特定のサブＤＯＭツリーＴinner nodeおよびＴinner nodeの繰り返しインスタンスセットが与えられさえすれば、内部ＲＳＴノードのためのプロセスを識別する情報項目は、リーフＲＳＴノードと同じである。
【００５３】
内部ＲＳＴノード内の情報項目を識別した後、時として、現在のＲＳＴノードに対応する情報ブロックのヘッドおよびテイルがＲＳＴノードそれ自体であることに気付く。この場合、ヘッドノードおよびテイルノードは、現在のＲＳＴノードの兄弟ノードとして、更に高いレベルへと昇格されなければならない。図１２、１３、及び、１４は、ヘッドおよびテイルを昇格させる一例を示す図である。情報ブロックＡは、ＲＳＴノード１の対応する情報ブロックである。情報ブロックＢは、ＲＳＴノード２の対応する情報ブロックである。情報ブロックＣは、ＲＳＴノード３の対応する情報ブロックであり、情報ブロックＤは、ＲＳＴノード４の対応する情報ブロックである。情報ブロックＥは、ＲＳＴノード５の対応する情報ブロックである。情報ＲＳＴサブツリーに従って、情報ブロックＢは情報ブロックＡのヘッド部分の一部であり、情報ブロックＥは情報ブロックＡのテイル部分の一部である。よって、図１４に示されるように、情報ブロックＢおよび情報ブロックＥは、情報ブロックＡの兄弟として昇格される。
【００５４】
構造情報ブロックツリー生成ユニット２０７においては、ＲＳＴツリーおよび情報項目検知に基づいて、最終的な構造情報ブロックツリー２０８が構成される。
【００５５】
先に形成されたＲＳＴ内では、情報ブロックおよびそれらの関係だけがおおまかに与えられる。情報ブロック内の情報項目の検知後、ＲＳＴツリーから情報ブロックツリーを構成することができる。図１５は、構造情報ブロックツリーの一例を示す図である。情報ブロックツリー内において、この情報ブロックツリーは、図１５に示されるように、階層状に編成された情報ブロックを与えるだけでなく、各情報ブロック内に情報項目を明示する。したがって、更に高い精度でウェブページ２０１からコンテンツを抽出することができる。
【００５６】
構造情報ブロックツリー２０８の構築は、ＲＳＴツリーにおける再帰的手続であり、これを以下に述べる。
【００５７】
ＲＳＴツリーのルートノードに対するツリー上に情報ブロックノードを生成し、前述した方法を使用して現行ＲＳＴノードに対する情報項目を分割する。その後、現行情報ブロックノードの下に情報項目ノードを生成する。
【００５８】
現行ＲＳＴノードがリーフノードでない場合には、その各子ノード毎に情報ブロックノードを生成し、これらの各情報ブロックノードを適切な情報項目ノードの下のツリーに付加する。その後、これらの子情報ブロックノードを１つずつ処理する。
【００５９】
ウェブドキュメントのビジュアル・プレゼンテーションでは、通常、各情報ブロック毎に名前またはタイトルが存在する。構造プレゼンテーションの見地から、名前は、１つ以上の隣接するサブツリーに関連付けられる。情報ブロックの名前を抽出することは、情報ブロック間の構造関係を使用して情報ブロックのための名前を含むサブツリーを見つけることに対応している。
【００６０】
構造情報ブロックに対しては、情報ブロック内の情報項目の前に多くの＜ＴＥＸＴ＞ノードが存在し得る。本発明においては、情報ブロックが名前またはタイトルを有している場合、名前またはタイトルが常に最初の情報項目に先んじる最も近い＜ＴＥＸＴ＞ノードであるということが暗黙の前提である。この前提に基づいて、本発明の方法は、最初に、情報ブロックのヘッド部分を考慮し、＜ＴＥＸＴ＞が存在しない場合には、＜ＴＥＸＴ＞が見つかるまで、前兄弟情報ブロックすなわち上部の情報ブロックから上に向かって検索する。
【００６１】
図３は、意味情報ブロック抽出ユニットを構成するブロック図である。最初に、基本情報ブロック取得ユニット３０２は、構造情報ブロックツリー３０１から適切な精度で基本情報ブロックを取得する。意味情報ブロック生成ユニット３０３は、基本情報ブロックをクラスタリングし、意味情報ブロック３０４へとマージングする。主テキストブロック・関連リンクブロック検知ユニット３０５は、ウェブページ３０１の意味ブロック（意味情報ブロック）内で主テキスト情報ブロックおよび関連リンクブロックをラベル付けする。
【００６２】
基本情報ブロック取得ユニット３０２において、情報ブロックは、以下のクラスタリングに適した精度で構造情報ブロックツリー３０１から得られる。この種のブロックは、“基本情報ブロック”と称され、２つのタイプ、すなわちテキストとリンクとに分類することができる。本発明においては、構造情報ブロックツリー３０１を先行順でトラバースして基本情報ブロックを取得するために、幾つかの発見的ルールが立案されている。トラバースされる各情報ブロックに対して図１７及び１８に示すルールが適用され、必要とする基本情報ブロックであるか否かが判断される。図１７及び１８は、必要とする基本情報ブロックであるか否かを判断するルールを示す図である。
【００６３】
全ての基本情報ブロックが走査され、基本情報ブロックの長さが５０未満の場合には、それを次の隣り合う基本情報ブロックへ合併させる。
【００６４】
最後の基本情報ブロックは、ブロックの比率値にしたがって、２つのタイプ、すなわち、テキスト情報ブロックとリンク情報ブロックとに分類することができる。
【００６５】
意味情報ブロック生成ユニット３０３においては、基本情報ブロックに基づいて意味クラスタリングが行なわれ、それにより、ウェブページ３０１に対する意味情報ブロック３０４が生成される。２つのブロック間での意味的類似性を計算するため、各ブロックは、“ワードのバッグ”すなわち、＜ワード、頻度＞のセットの形態で表わされる。ストップリストも使用され、殆ど意味のない一般的なワードが除去される。
【００６６】
テキスト情報ブロックおよびリンク情報ブロックに関してそれぞれクラスタリングが行なわれる。以下に記載するような“分割クラスタリング”として知られる共通の方法が使用される。
【００６７】
ブロックのサイズにしたがって降順でブロックを配列し、最も長いブロックを現行クラスタに付加する。
【００６８】
現行クラスタ内の各ブロックに対して、未だクラスタリングされていない他のブロックに対する類似性を計算する。類似性は、ＶＳＭまたはワードオーバーラッピング等の様々な方法を用いて計算することができる。また、２つの隣り合うブロックが更に似通っている点を考慮し、２つの隣り合うブロック間の類似性が倍加される。
【００６９】
類似性が閾値を上回る場合には、未だクラスタリングされていないブロックを現行クラスタに付加する。各ブロックが処理されるまで前述したループを繰り返す。ここで、現行クラスタ内の全ての情報ブロックが１つの意味情報ブロック３０４へとグループ化される。
【００７０】
新たなクラスタの子孫として残された全ての情報ブロックから最も長いブロックを選択する。前述したループを繰り返す。基本情報ブロックの全てが１つの特定の意味情報ブロック３０４へとクラスタリングされると、手続きは終了する。
【００７１】
主テキストブロック・関連リンクブロック検知ユニット３０５においては、必要に応じて、ウェブページ３０１の意味ブロック内の、主テキスト情報ブロックおよび関連リンクブロック３０６にラベル付けすることができる。意味情報ブロック３０４の生成後、ウェブページ３０１のコンテンツが主にリンクではなくテキストである場合、主テキストブロックを抽出する必要がある。その方法を以下に説明する。
【００７２】
テキストに対するリンクの比率をチェックする。比率が閾値を下回っている場合には、殆どの場合、ウェブページ３０１はテキストページである。比率が閾値を下回っていない場合には、止める。
【００７３】
ウェブページ３０１内で最も長いテキストブロックを特定する。その長さが閾値を上回っている場合には、それを主テキストブロックと見なすことができる。長さが閾値を上回っていない場合には、テキスト情報ブロックに関して意味クラスタリング方法が適用され、それにより、主テキストブロックが形成される。
【００７４】
主テキストブロックが生成されると、主テキストブロックに最も類似する１つのブロックをリンク情報ブロックから選択する。類似性が閾値を上回っている場合には、このリンクブロックが関連リンクブロックと見なされる（主テキストブロックおよび関連リンクブロック３０６）。類似性が閾値を上回っていない場合には、関連するブロックが存在しない。
【００７５】
（効果）
上述してきたように、本実施の形態では、２つの異なるレベル、すなわち、構造レベルおよび意味レベルで情報ブロック抽出を行なうため、非常に有効である。特に、構造レベルにおける自動繰り返しパターンの発見と、意味レベルにおけるクラスタリングは、抽出方法の成功の根幹をなすとともに、成功を保証するものである。
【００７６】
以上、特定の実施形態について説明したが、当業者であれば分かるように、本発明は、前述したこれらの特定の内容に限定されない。添付の請求の範囲によって規定される本発明の範囲から逸脱せずに、多くの変更および改良を本発明に対して行なうことができる。
【図面の簡単な説明】
【００７７】
【図１】本発明の構成を示す図である。
【図２】構造情報ブロック抽出ユニットを構成するブロック図である。
【図３】意味情報ブロック抽出ユニットを構成するブロック図である。
【図４】接尾辞トライの一例を示す図である。
【図５】図４の入力トークンストリームの一例を示す図である。
【図６】コンパクト基準の一例を示す図である。
【図７】情報ブロック内に含まれる情報項目の一例を示す図である。
【図８】ＲＳＴツリー内のリーフノードの情報項目を識別する一例を示す図である。
【図９】ＲＳＴツリー内のリーフノードの情報項目を識別する一例を示す図である。
【図１０】ＲＳＴツリー内のリーフノードの情報項目を識別する一例を示す図である。
【図１１】内部ＲＳＴノードのサブＤＯＭツリーの変換の一例を示す図である。
【図１２】ヘッドおよびテイルを昇格させる一例を示す図である。
【図１３】ヘッドおよびテイルを昇格させる一例を示す図である。
【図１４】ヘッドおよびテイルを昇格させる一例を示す図である。
【図１５】構造情報ブロックツリーの一例を示す図である。
【図１６】繰り返しインスタンスセットのランクの計算を説明する説明図である。
【図１７】必要とする基本情報ブロックであるか否かを判断するルールを示す図である。
【図１８】必要とする基本情報ブロックであるか否かを判断するルールを示す図である。
【符号の説明】
【００７８】
１０１，２０１  ウェブページ
１０２  構造情報ブロック抽出ユニット
１０３，２０８，３０１  構造情報ブロックツリー
１０４  意味情報ブロック抽出ユニット
１０５  意味情報ブロックおよびラベル
２０２  ページ表示ユニット
２０３  繰り返しパターン発見ユニット
２０４  領域検知ユニット
２０５  ＲＳＴツリー生成ユニット
２０６  情報項目検知ユニット
２０７  構造情報ブロックツリー生成ユニット
３０２  基本情報ブロック取得ユニット
３０３  意味情報ブロック生成ユニット
３０４  意味情報ブロック
３０５  主テキストブロック・関連リンクブロック検知ユニット
３０６  主テキストブロックおよび関連リンクブロック
【図１】
2005092889.tif 000032
【図２】
2005092889.tif 000033
【図３】
2005092889.tif 000034
【図４】
2005092889.tif 000035
【図５】
2005092889.tif 000036
【図６】
2005092889.tif 000037
【図７】
2005092889.tif 000038
【図８】
2005092889.tif 000039
【図９】
2005092889.tif 000040
【図１０】
2005092889.tif 000041
【図１１】
2005092889.tif 000042
【図１２】
2005092889.tif 000043
【図１３】
2005092889.tif 000044
【図１４】
2005092889.tif 000045
【図１５】
2005092889.tif 000046
【図１６】
2005092889.tif 000047
【図１７】
2005092889.tif 000048
【図１８】
2005092889.tif 000049