JP5225331B2

JP5225331B2 - データ抽出装置及び方法

Info

Publication number: JP5225331B2
Application number: JP2010150011A
Authority: JP
Inventors: 圭吾町永
Original assignee: Yahoo Japan Corp
Current assignee: Yahoo Japan Corp
Priority date: 2010-06-30
Filing date: 2010-06-30
Publication date: 2013-07-03
Anticipated expiration: 2030-06-30
Also published as: JP2012014412A

Description

本発明は、データ抽出装置及び方法に関する。

近年、インターネット等の普及により、ユーザは、端末からインターネット等にアクセスし、様々なウェブページを容易に閲覧することができる。ウェブページは、ＨＴＭＬ（ＨｙｐｅｒＴｅｘｔＭａｒｋｕｐＬａｎｇｕａｇｅ）等で記述された文書と画像データとで構成され、ウェブブラウザによって閲覧される。このようなウェブページを閲覧し、検索することによって、ユーザは、求めている情報を容易に取得することができる。

ウェブページから情報を検索する技術には、ＨＴＭＬ等の記述フォーマットを利用して、特定の情報を抽出する技術等が存在する。これらの技術は、ＨＴＭＬ等におけるタグ構造を利用し、タグ構造の共通性等を利用して情報を抽出する。例えば、特許文献１から３が知られている。

特許文献１には、ＷＷＷ上で提供される情報の中から本文部分のみを特定することが可能な抽出規則を作成するシステムが開示されている。特許文献１に開示されたシステムは、予め収集されたウェブページデータから本文部分を抽出する本文抽出手段と、ウェブページデータを解析して、本文抽出手段によって抽出された本文部分が現れる箇所をデータ構造で表現した抽出規則を作成する抽出規則作成手段と、抽出規則作成手段によって作成した同一の抽出規則が適用される複数のＵＲＬをグループ化し、このグループ化されたＵＲＬと抽出規則とを関連付ける適用抽出規則作成手段とを備える。

特許文献２には、タグの解析や抽出ルールの作成をしないでも、一般のユーザが、有益な情報を持つテキストコンテンツを容易に取り出して活用することができるシステムが開示されている。特許文献２に開示されたシステムは、正規表現を持つパターンフォーマットを記憶する記憶部と、ＨＴＭＬページからパターンフォーマットと一致するテキストコンテンツを取り出す抽出ルールを生成する抽出ルール生成部と、抽出ルールから所定のフォーマットに変換するフォーマット変換部を有する。

特許文献３には、不特定のウェブサイトのページから、ある検索語に関する特定の情報をブロック単位で抽出する情報抽出装置が開示されている。特許文献１に開示された情報抽出装置は、ＨＴＭＬ等で記述された半構造化情報における検索語と検索語に関する特定情報との間の構造的位置関係を表すパターンからなるパターン集合に基づいて、ウェブページの集合から検索語に関する特定情報の候補をブロック単位で抽出し、抽出された特定情報の候補の中から情報分類技術を用いて特定情報を選択する。例えば、情報抽出装置は、取得したウェブページにおける、検索語とその検索語に関する特定情報との構造的位置関係（タグ構造に基づく木構造）から、学習処理によってパターン（パターン木、ノード間の距離等）を生成する。そして、情報抽出装置は、パターンをウェブページに当てはめ、パターン木と、ノード間の距離が制限以内であるターゲットノードとにマッチしたノードを根とする部分木に含まれる情報を抽出し、特定情報の候補とし、情報分類技術を用いて特定情報を選択する。

特開２００４−２２０２５１号公報特開２００６−２３６２６２号公報特開２００７−４７９７４号公報

しかしながら、特許文献１に開示された発明は、ウェブページデータから本文部分のみを特定し、抽出するので、ユーザが所望して指定したデータと同様のデータを抽出することができない。特許文献２に開示された発明は、ＨＴＭＬページからパターンフォーマットと一致するテキストコンテンツを取り出すので、ユーザは所望するデータを取得するために、パターンフォーマットを理解して指定する必要がある。特許文献３に開示された発明は、ウェブページから、ノード間の距離が制限以内であるノードをもマッチするノードとして抽出するので、ユーザが所望して指定したデータと異なる意味合いのデータをも抽出してしまう。さらに、特許文献３に開示された発明は、抽出した情報を候補として情報分類技術を用いて特定情報を選択するので、抽出までの時間がかかることが予想される。

そこで、ユーザが所望するデータを、容易、かつ、高速にＨＴＭＬ文書から抽出することができるデータ抽出装置及び方法が求められている。

本発明は、ユーザが所望するデータを、容易、かつ、高速にＨＴＭＬ文書から抽出することができるデータ抽出装置及び方法を提供することを目的とする。

本発明では、以下のような解決手段を提供する。

（１）ＨＴＭＬ文書を記憶するＨＴＭＬ文書記憶手段と、前記ＨＴＭＬ文書記憶手段に記憶された前記ＨＴＭＬ文書を構成するノードのうち、二つ以上の目的ノードの指定を受け付ける目的ノード受付手段と、前記目的ノード受付手段によって受け付けられた全ての前記目的ノードに共通の上位ノードである共通祖先ノードを特定する祖先ノード特定手段と、前記祖先ノード特定手段によって特定された前記共通祖先ノードから指定された前記目的ノードまでの全てのパスを抽出するパス抽出手段と、前記パス抽出手段によって抽出された前記パス及び前記ＨＴＭＬ文書を構成するノードの繰り返し構造に基づき、抽出対象となる抽出目的ノードの抽出ルールを示す、前記共通祖先ノードから当該抽出目的ノードまでの検索パスを生成する検索パス生成手段と、前記共通祖先ノードを含む前記ＨＴＭＬ文書から、前記検索パス生成手段によって生成された前記検索パスに従って抽出される前記抽出目的ノードを抽出するデータ抽出手段と、を含むデータ抽出装置。

（１）の構成によれば、本発明に係るデータ抽出装置は、ＨＴＭＬ文書を記憶するＨＴＭＬ文書記憶手段を有する。そして、データ抽出装置は、ＨＴＭＬ文書記憶手段に記憶されたＨＴＭＬ文書を構成するノードのうち、二つ以上の目的ノードの指定を受け付け、受け付けた全ての目的ノードに共通の上位ノードである共通祖先ノードを特定する。次に、データ抽出装置は、特定した共通祖先ノードから指定された目的ノードまでの全てのパスを抽出し、抽出したパス及びＨＴＭＬ文書を構成するノードの繰り返し構造に基づき、抽出対象となる抽出目的ノードの抽出ルールを示す、共通祖先ノードから当該抽出目的ノードまでの検索パスを生成する。そして、データ抽出装置は、共通祖先ノードを含むＨＴＭＬ文書から、生成した検索パスに従って抽出される抽出目的ノードを抽出する。

すなわち、本発明に係るデータ抽出装置は、指定を受け付けた全ての目的ノードの共通祖先ノードを特定し、特定した共通祖先ノードから抽出目的ノードまでの検索パスを生成し、生成した検索パスに従って抽出される抽出目的ノードを抽出する。したがって、本発明に係るデータ抽出装置は、ユーザからヒントとなる目的ノードの指定を受け付けて、当該ヒントに基づいてユーザが所望するデータを、容易、かつ、高速にＨＴＭＬ文書から抽出することができる。

（２）前記検索パス生成手段は、前記パス抽出手段が抽出した前記全てのパスに基づいて、複数のパターンにマッチするワイルドカードを一部に含む表現を有する前記検索パスを生成する（１）に記載のデータ抽出装置。

したがって、（２）に係るデータ抽出装置は、抽出した全てのパスに基づいて、複数のパターンにマッチするワイルドカードを一部に含む表現を有する検索パスを生成する。これによりＨＴＭＬ文書の繰り返し構造に揺らぎを含んでいる場合においても、ユーザが所望するデータを、容易にＨＴＭＬ文書から抽出することができる。

（３）前記検索パス生成手段は、前記パス抽出手段が抽出した前記全てのパスについてＤＰ（ＤｙｎａｍｉｃＰｒｏｇｒａｍｍｉｎｇ）マッチングを行って、前記ワイルドカードを一部に含む表現を有する検索パスを生成する（２）に記載のデータ抽出装置。

したがって、（３）に係るデータ抽出装置は、複数の抽出されたパスが完全に一致していない場合であっても、これらのパスのＤＰマッチングを行ってワイルドカードを一部に含む表現を有する検索パスを推定し生成する。これによりＨＴＭＬ文書の繰り返し構造に揺らぎを含んでいる場合においても、ユーザが所望するデータを、さらに容易にＨＴＭＬ文書から抽出することができる。

（４）前記祖先ノード特定手段は、前記指定を受け付けた二つ以上の前記目的ノードのうちの前記ＨＴＭＬ文書の下位の前記目的ノードから順に組み合わせて、二つの前記目的ノードの共通上位ノードである第１の共通ノードを求める手段と、二つの前記第１の共通ノードの共通上位ノードである第２の共通ノードを求める手段と、前記共通上位ノードが一つになるまでこれを繰り返し、当該一つの共通上位ノードを前記共通祖先ノードとして特定する手段と、を含み、前記パス抽出手段は、前記共通祖先ノードから一段下位の共通上位ノードまでのパスを抽出する手段と、前記一段下位の前記共通上位ノードが前記抽出目的ノードでない場合には、前記一段下位の共通上位ノードからさらに一段下位の共通上位ノードまでのパスを抽出する手段と、さらに、これを繰り返し、前記抽出目的ノードまでのパスを抽出する繰り返し手段と、を含み、前記検索パス生成手段は、前記共通祖先ノードから一段下位の共通上位ノードまでの検索パスを、前記抽出されたパスのＤＰマッチングを行って生成する手段と、前記一段下位の共通上位ノードが前記抽出目的ノードでない場合には、前記一段下位の共通上位ノードからさらに一段下位の共通上位ノードまでの検索パスを、前記抽出された前記パスのＤＰマッチングを行って、生成する手段と、さらに、これを繰り返し、前記抽出目的ノードまでの検索パスを生成する手段と、を含む、（１）に記載のデータ抽出装置。

（４）の構成によれば、（４）に係るデータ抽出装置は、（１）において、指定を受け付けた二つ以上の目的ノードのうちのＨＴＭＬ文書の下位の目的ノードから順に組み合わせて、二つの目的ノードの共通上位ノードである第１の共通ノードを求め、二つの第１の共通ノードの共通上位ノードである第２の共通ノードを求め、共通上位ノードが一つになるまでこれを繰り返し、当該一つの共通上位ノードを共通祖先ノードとして特定する。次に、（４）に係るデータ抽出装置は、共通祖先ノードから一段下位の共通上位ノードまでのパスを抽出し、一段下位の共通上位ノードが抽出目的ノードでない場合には、一段下位の共通上位ノードからさらに一段下位の共通上位ノードまでのパスを抽出し、さらに、これを繰り返し、抽出目的ノードまでのパスを抽出する。そして、（４）に係るデータ抽出装置は、共通祖先ノードから一段下位の共通上位ノードまでの検索パスを、抽出されたパスのＤＰマッチングを行って生成し、一段下位の共通上位ノードが抽出目的ノードでない場合には、一段下位の共通上位ノードからさらに一段下位の共通上位ノードまでの検索パスを、抽出されたパスのＤＰマッチングを行って、生成し、さらに、これを繰り返し、抽出目的ノードまでの検索パスを生成する。

すなわち、（４）に係るデータ抽出装置は、指定を受け付けた全ての目的ノードの共通祖先ノードを特定し、特定した共通祖先ノードから抽出目的ノードまでの検索パスを、一段ごとに生成し、生成した一段ごとの検索パスによって、生成した検索パスに従って抽出される抽出目的ノードを抽出する。したがって、（４）に係るデータ抽出装置は、ユーザからヒントとなる目的ノードの指定を受け付けて、当該ヒントに基づいてユーザが所望するデータを、さらに、容易、かつ、高速にＨＴＭＬ文書から抽出することができる。

（５）ＨＴＭＬ文書を記憶するＨＴＭＬ文書記憶手段を有するデータ抽出装置が実行する方法であって、前記ＨＴＭＬ文書記憶手段に記憶された前記ＨＴＭＬ文書を構成するノードのうち、二つ以上の目的ノードの指定を受け付ける目的ノード受付ステップと、前記目的ノード受付ステップにおいて受け付けられた全ての前記目的ノードに共通の上位ノードである共通祖先ノードを特定する祖先ノード特定ステップと、前記祖先ノード特定ステップにおいて特定された前記共通祖先ノードから指定された前記目的ノードまでの全てのパスを抽出するパス抽出ステップと、前記パス抽出ステップにおいて抽出された前記パス及び前記ＨＴＭＬ文書を構成するノードの繰り返し構造に基づき、抽出対象となる抽出目的ノードの抽出ルールを示す、前記共通祖先ノードから当該抽出目的ノードまでの検索パスを生成する検索パス生成ステップと、前記共通祖先ノードを含む前記ＨＴＭＬ文書から、前記検索パス生成ステップにおいて生成された前記検索パスに従って抽出される前記抽出目的ノードを抽出するデータ抽出ステップと、を含む方法。

したがって、（１）と同様に、本発明に係る方法は、ユーザからデータを受け付けて、ユーザが所望するデータを、容易、かつ、高速にＨＴＭＬ文書から抽出することができる。

本発明によれば、ユーザが所望するデータを、容易、かつ、高速にＨＴＭＬ文書から抽出することができる。

本発明の特徴を説明するためのＨＴＭＬ文書データの例を示す図である。本発明の一実施形態に係るデータ抽出装置の機能構成を示す機能ブロック図である。本発明の一実施形態に係るデータ抽出装置のＨＴＭＬ文書データの別の例を示す図である。本発明の一実施形態に係るデータ抽出装置の検索パスの生成においてＤＰマッチングを行う例を示す図である。一実施形態に係るデータ抽出装置の処理内容を示すフローチャートである。一実施形態に係るデータ抽出装置の共通祖先ノード特定処理を示すフローチャートである。一実施形態に係るデータ抽出装置の検索パス生成処理を示すフローチャートである。本発明の一実施形態に係るデータ抽出装置のデータ抽出例を示す図である。

以下、本発明の実施形態について図を参照しながら説明する。

本実施形態のデータ抽出装置１０は、コンピュータ及びその周辺装置に適用される。本実施形態における各部は、コンピュータ及びその周辺装置が備えるハードウェア並びに該ハードウェアを制御するソフトウェアによって構成される。

上記ハードウェアには、制御部としてのＣＰＵ（ＣｅｎｔｒａｌＰｒｏｃｅｓｓｉｎｇＵｎｉｔ）の他、記憶部、通信装置、表示装置及び入力装置が含まれる。記憶部としては、例えば、メモリ（ＲＡＭ：ＲａｎｄｏｍＡｃｃｅｓｓＭｅｍｏｒｙ、ＲＯＭ：ＲｅａｄＯｎｌｙＭｅｍｏｒｙ等）、ハードディスクドライブ（ＨＤＤ：ＨａｒｄＤｉｓｋＤｒｉｖｅ）及び光ディスク（ＣＤ：ＣｏｍｐａｃｔＤｉｓｋ、ＤＶＤ：ＤｉｇｉｔａｌＶｅｒｓａｔｉｌｅＤｉｓｋ等）ドライブが挙げられる。通信装置としては、例えば、各種有線及び無線インターフェース装置が挙げられる。表示装置としては、例えば、液晶ディスプレイやプラズマディスプレイ等の各種ディスプレイが挙げられる。入力装置としては、例えば、キーボード及びポインティング・デバイス（マウス、トラッキングボール等）が挙げられる。

上記ソフトウェアには、上記ハードウェアを制御するコンピュータ・プログラムやデータが含まれる。コンピュータ・プログラムやデータは、記憶部により記憶され、制御部により適宜実行、参照される。また、コンピュータ・プログラムやデータは、通信回線を介して配布されることも可能であり、ＣＤ−ＲＯＭ等のコンピュータ可読媒体に記録して配布されることも可能である。

図１は、本発明の特徴を説明するためのＨＴＭＬ文書データの例を示す図である。図１（ａ）は、「カレーライスの作り方」における素材等を具体例としたＨＴＭＬ文書データの例を示す図である。図１（ｂ）は、図１（ａ）のＨＴＭＬ文書データの例を木構造で示した図である。この例において、データ抽出装置１０は、データ抽出の目的となる抽出目的ノードのヒントである目的ノードの指定を受け付ける。具体的には、図１（ａ）の例では、詳しくは図８において後述するように、データ抽出装置１０はマウスポインタ等によって表示画面のクリック操作を受け付けることにより、「カレーライスの作り方」、「牛肉」、「２００ｇ」、「カレールー」及び「１／２パック」を、抽出目的ノードのヒントである目的ノードとして受け付ける。そして、データ抽出装置１０は、当該ＨＴＭＬ文書を構成するノードの繰り返し構造に基づき、「カレーライスの作り方」、「牛肉」、「２００ｇ」等のヒントとして直接指定を受け付けた目的ノードに加えて、例えば「ニンジン」、「１本」等を抽出目的ノードとして自動的に抽出する。

すなわち、データ抽出装置１０は、ＨＴＭＬ文書の中で、ユーザの所望するデータ（抽出目的ノード）を抽出するためのヒントである目的ノードとして、例えば、「カレーライスの作り方」、「牛肉」、「２００ｇ」、「カレールー」及び「１／２パック」の指定を受け付ける。次に、データ抽出装置１０は、当該ＨＴＭＬ文書の下位の目的ノードから順に組み合わせて、指定を受け付けた「牛肉」に対応する目的ノードと、「２００ｇ」に対応する目的ノードとを第１グループとする。さらに、データ抽出装置１０は、これらと並列の目的ノードである「カレールー」に対応する目的ノードと、「１／２パック」に対応する目的ノードとを第２グループとする。さらに、データ抽出装置１０は、これらより上位の目的ノードである「カレーライスの作り方」に対応するノードを第３グループとする。ここで、データ抽出装置１０は、第１グループと第２グループとの共通上位ノードである＜ｄｌ＞を抽出し、第１グループと第２グループとを合わせて第４グループとする。次に、データ抽出装置１０は、合わせた第４グループと、第３グループとの共通上位ノードである＜ｂｏｄｙ＞を抽出し、第４グループと第３グループとを合わせて第５グループとする。そして、データ抽出装置１０は、他に上位ノードを抽出するためのグループがないので＜ｂｏｄｙ＞を共通祖先ノードとして特定する。

次に、データ抽出装置１０は、特定した共通祖先ノード＜ｂｏｄｙ＞から、上記の処理の逆順に逐次、抽出対象となる抽出目的ノードの抽出ルールを示す、当該抽出目的ノードまでの検索パスを推定していく。すなわち、データ抽出装置１０は、第５グループとして特定した共通祖先ノード＜ｂｏｄｙ＞から、一段下位の第３グループの「カレーライスの作り方」に対応する目的ノードまでのパス＜ｂｏｄｙ＞−＜ｈ１＞と、第４グループに対応する共通上位ノードまでのパス＜ｂｏｄｙ＞−＜ｄｌ＞とから、検索パス＜ｂｏｄｙ＞−＜ｈ１＞−＜ｄｌ＞を推定して生成する。次に、データ抽出装置１０は、第４グループに対応する共通上位ノードである＜ｄｌ＞からさらに一段下位の第１グループの「牛肉」に対応する目的ノードまでのパス＜ｄｌ＞−＜ｄｔ＞及び同じく第１グループの「２００ｇ」に対応する目的ノードまでのパス＜ｄｌ＞−＜ｄｄ＞、並びに、第２グループの「カレールー」に対応する目的ノードまでのパス＜ｄｌ＞−＜ｄｔ＞及び同じく第２グループの「１／２パック」に対応する目的ノードまでのパス＜ｄｌ＞−＜ｄｄ＞から、抽出目的ノードまでの検索パス＜ｂｏｄｙ＞−＜ｈ１＞−＜ｄｌ＞−＜ｄｔ＞−＜ｄｄ＞を推定して生成する。ここで、「牛肉」、「２００ｇ」、「カレールー」及び「１／２パック」は、指定を受け付けたヒント（目的ノード）であるので、データ抽出装置１０は、ここで検索パスの推定・生成処理を完了する。

そして、データ抽出装置１０は、共通祖先ノードを含むＨＴＭＬ文書から、推定・生成した検索パスに従って特定される抽出目的ノードに対応する「ニンジン」、「１本」、「タマネギ」、「２個」、「ジャガイモ」及び「２個」を抽出する。したがって、データ抽出装置１０は、ユーザから、例えば、「カレーライスの作り方」、「牛肉」、「２００ｇ」、「カレールー」及び「１／２パック」を受け付けて、ユーザが所望するカレーライスを作るための素材及び素材の量を、容易、かつ、高速にＨＴＭＬ文書から抽出することができる。

図２は、本発明の一実施形態に係るデータ抽出装置１０の機能構成を示す機能ブロック図である。データ抽出装置１０は、インターネット７０を介して接続されているウェブサーバ５０から取得したウェブデータを格納するウェブデータ記憶手段としてのウェブデータＤＢ３１と、目的ノード受付手段としての目的ノード受付部１１と、祖先ノード特定手段としての祖先ノード特定部１２と、パス抽出手段としてのパス抽出部１３と、検索パス生成手段としての検索パス生成部１４と、データ抽出手段としてのデータ抽出部１５とを備える。このようなデータ抽出装置１０の機能について、各部ごとに詳述する。

ウェブデータＤＢ３１は、ＨＴＭＬ文書を含むウェブデータを記憶する。例えば、ＨＴＭＬ文書の記述フォーマットは、タグから構成されるタグ構造を有する（図１（ａ）を参照）。本発明において、タグと、タグに含まれるテキストとを、ノードに対応させ、ＨＴＭＬ文書に木構造を適用する。

目的ノード受付部１１は、ウェブデータＤＢ３１に記憶されたウェブデータに含まれるＨＴＭＬ文書を構成するノードのうち、二つ以上の目的ノードの指定を受け付ける。例えば、目的ノード受付部１１は、ユーザの所望するデータ（抽出目的ノード）を抽出するための目的ノードとして、例えば、「カレーライスの作り方」、「牛肉」、「２００ｇ」、「カレールー」及び「１／２パック」の指定を受け付ける。

祖先ノード特定部１２は、目的ノード受付部１１によって受け付けられた全ての目的ノードに共通の上位ノードである共通祖先ノードを特定する。すなわち、祖先ノード特定部１２は、目的ノード受付部１１によって受け付けられた二つ以上の目的ノードのうち、ＨＴＭＬ文書の下位の目的ノードから順に組み合わせて、二つの目的ノードの共通上位ノードである第１の共通ノードを求める。次に、祖先ノード特定部１２は、二つの第１の共通ノードの共通上位ノードである第２の共通ノードを求める。そして、祖先ノード特定部１２は、共通上位ノードが一つになるまで上位ノードの抽出を繰り返し、当該一つの共通上位ノードを共通祖先ノードとして特定する。

例えば、図１のようにタグの種類によって木構造を構成するＨＴＭＬ文書において、祖先ノード特定部１２は、目的ノードである「カレーライスの作り方」、「牛肉」、「２００ｇ」、「カレールー」及び「１／２パック」のうち、ＨＴＭＬ文書の下位の目的ノードから順に組み合わせて、「牛肉」と、「２００ｇ」とを第１グループとし、「カレールー」と、「１／２パック」とを第２グループとし、これらより上位の目的ノードである「カレーライスの作り方」を第３グループとする。次に、祖先ノード特定部１２は、第１グループと第２グループとの共通上位ノードである＜ｄｌ＞を抽出し、第１グループと第２グループとを合わせて第４グループとする。次に、データ抽出装置１０は、合わせた第４グループと、第３グループとの共通上位ノードである＜ｂｏｄｙ＞を抽出し、第４グループと第３グループとを合わせて第５グループとする。そして、祖先ノード特定部１２は、一つになった共通上位ノード＜ｂｏｄｙ＞を共通祖先ノードとして特定する。

パス抽出部１３は、祖先ノード特定部１２によって特定された共通祖先ノードから指定された目的ノードまでの全てのパスを抽出する。すなわち、パス抽出部１３は、共通祖先ノードから一段下位の共通上位ノードまでのパスを抽出する。次に、パス抽出部１３は、一段下位の共通上位ノードが抽出対象となる抽出目的ノードでない場合には、一段下位の共通上位ノードからさらに一段下位の共通上位ノードまでのパスを抽出する。そして、パス抽出部１３は、一段下位の共通上位ノードが抽出目的ノードになるまで、一段下位の共通上位ノードまでのパスの抽出を繰り返し、抽出目的ノードまでのパスを推定して抽出する。

例えば、パス抽出部１３は、共通祖先ノード＜ｂｏｄｙ＞から、祖先ノード特定部１２の処理の逆順に、抽出目的ノードまでのパスを抽出する。すなわち、パス抽出部１３は、共通祖先ノード＜ｂｏｄｙ＞から、一段下位の第３グループの「カレーライスの作り方」までのパス＜ｂｏｄｙ＞−＜ｈ１＞と、第４グループに対応する共通上位ノードである＜ｄｌ＞までのパス＜ｂｏｄｙ＞−＜ｄｌ＞を抽出する。次に、パス抽出部１３は、第４グループからさらに一段下位の第１グループの「牛肉」までのパス＜ｄｌ＞−＜ｄｔ＞及び「２００ｇ」までのパス＜ｄｌ＞−＜ｄｄ＞、並びに、第２グループの「カレールー」までのパス＜ｄｌ＞−＜ｄｔ＞及び「１／２パック」までのパス＜ｄｌ＞−＜ｄｄ＞を抽出する。

検索パス生成部１４は、パス抽出部１３によって抽出されたパス及びＨＴＭＬ文書を構成するノードの繰り返し構造に基づき、抽出対象となる抽出目的ノードの抽出ルールを示す、共通祖先ノードから当該抽出目的ノードまでの検索パスを生成する。例えば、検索パス生成部１４は、パス抽出部１３が抽出した全てのパスについてＤＰ（ＤｙｎａｍｉｃＰｒｏｇｒａｍｍｉｎｇ）マッチング（後述する図４参照）を行って、複数のパターンにマッチするワイルドカードを一部に含む表現を有する検索パスを生成する。すなわち、検索パス生成部１４は、共通祖先ノードから一段下位の共通上位ノードまでの検索パスを、抽出されたパスのＤＰマッチングを行って生成する。次に、検索パス生成部１４は、一段下位の共通上位ノードが抽出目的ノードでない場合には、一段下位の共通上位ノードからさらに一段下位の共通上位ノードまでの検索パスを、抽出されたパスのＤＰマッチングを行って、生成する。このように、検索パス生成部１４は、一段ごとの検索パスの生成を繰り返し、抽出目的ノードまでの検索パスを推定して生成する。

例えば、検索パス生成部１４は、共通祖先ノード＜ｂｏｄｙ＞から一段下位の共通上位ノード＜ｈ１＞及び＜ｄｌ＞までの検索パスとして、抽出されたパスである＜ｂｏｄｙ＞−＜ｈ１＞と、＜ｂｏｄｙ＞−＜ｄｌ＞とのＤＰマッチングを行って、検索パス＜ｂｏｄｙ＞−＜ｈ１＞−＜ｄｌ＞を生成する。次に、検索パス生成部１４は、一段下位の共通上位ノード＜ｄｌ＞が抽出目的ノードでないので、一段下位の共通上位ノード＜ｄｌ＞からさらに一段下位の共通上位ノード＜ｄｔ＞及び＜ｄｄ＞までの検索パスとして、抽出されたパスである＜ｄｌ＞−＜ｄｔ＞と、＜ｄｌ＞−＜ｄｄ＞とのＤＰマッチングを行って、＜ｂｏｄｙ＞−＜ｈ１＞−＜ｄｌ＞−＜ｄｔ＞−＜ｄｄ＞を生成する。検索パス生成部１４は、パスのＤＰマッチングを行うことにより、複数の抽出されたパスが完全には一致していない場合（例えば、後述する図３の場合）であっても、複数のパターンにマッチするワイルドカードとして表現し、最適な検索パスを推定して生成する。パスのＤＰマッチングは、図３及び図４において詳述する。

データ抽出部１５は、共通祖先ノードを含むＨＴＭＬ文書から、検索パス生成部１４によって生成された検索パスに従って抽出される抽出目的ノードを抽出する。例えば、データ抽出部１５は、生成した検索パス＜ｂｏｄｙ＞−＜ｄｌ＞−＜ｄｔ＞に従って検索されたノードに対応する「ニンジン」や、＜ｂｏｄｙ＞−＜ｄｌ＞−＜ｄｔ＞−＜ｄｄ＞に従って検索されたノードに対応する「１本」（図１参照）を抽出する。

図３は、本発明の一実施形態に係るデータ抽出装置１０のＨＴＭＬ文書データの別の例を示す図である。図３（ａ）は、ＨＴＭＬ文書データにおいて＜ｉｍｇ＞を有するデータの例を示す図である。

図３の例において、データ抽出装置１０は、特定した共通祖先ノード＜ｂｏｄｙ＞から、抽出目的ノードである「カレーライスの作り方」、「牛肉」、「２００ｇ」、「カレールー」及び「１／２カップ」までの検索パスである＜ｂｏｄｙ＞−＜ｄｌ＞−＜ｄｔ＞−＜ｉｍｇ＞？−＜ｄｄ＞を生成する。＜ｉｍｇ＞？は、「？」直前の＜ｉｍｇ＞が出現する場合もあるし、出現しない場合もあることを示すワイルドカードとしての表現である。

すなわち、データ抽出装置１０は、「２００ｇ」までの検索パス＜ｂｏｄｙ＞−＜ｄｌ＞−＜ｄｔ＞−＜ｄｄ＞と、「１／２カップ」までの検索パス＜ｂｏｄｙ＞−＜ｄｌ＞−＜ｄｔ＞−＜ｉｍｇ＞−＜ｄｄ＞とから検索パスの併合を行い、＜ｂｏｄｙ＞−＜ｄｌ＞−＜ｄｔ＞−＜ｉｍｇ＞？−＜ｄｄ＞を生成する。データ抽出装置１０は、例えば、ＤＰマッチングを用いて、この検索パスの併合を行う。

図４は、本発明の一実施形態に係るデータ抽出装置１０の検索パスの生成においてＤＰマッチングを行う例を示す図である。図４の例は、「１／２カップ」のように目的ノードに到達するまでに、＜ｉｍｇ＞が存在する入力１＜ｂｏｄｙ＞−＜ｄｌ＞−＜ｄｔ＞−＜ｉｍｇ＞−＜ｄｄ＞と、「２００ｇ」のように＜ｉｍｇ＞が存在しない入力２＜ｂｏｄｙ＞−＜ｄｌ＞−＜ｄｔ＞−＜ｄｄ＞とにおいて、目的ノードに達するまでのパスを示す例である。

図４の例において、データ抽出装置１０は、入力１と入力２とが合致（マッチ）するパスをスコア＋１とし、入力１を省略するパスをスコア−１、入力２を省略するパスをスコア−１とする。ここで、データ抽出装置１０は、入力１と入力２とが合致（マッチ）しないパス５３３を、経路とすることができない。データ抽出装置１０は、目的ノードに到達するパスのスコアを算出し、算出したスコアが最も高いパスを最適経路とする。

例えば、開始ノード９０１から目的ノード９０２までの検索パスにおいて、検索パスＡと、検索パスＢとについてスコアを算出する。検索パスＡは、パス５１１（スコア＋１）、パス５２２（スコア＋１）、パス５０３３（入力１の省略：スコア−１）、パス５３０４（入力２の省略：スコア−１）、パス５４０４（入力２の省略：スコア−１）、パス５５４（スコア＋１）、パス５６５（スコア＋１）によって目的ノード９０２に達するので、算出したスコアは＋１である。検索パスＢは、パス５１１（スコア＋１）、パス５２２（スコア＋１）、パス５３０３（入力２の省略：スコア−１）、パス５４３（スコア＋１）、パス５５４（スコア＋１）、パス５６５（スコア＋１）によって目的ノード９０２に達するので、算出したスコアは＋３である。よって、データ抽出装置１０は、検索パスＢを検索パスＡより優れたパスと判定する。同様にして、データ抽出装置１０は、他のパスのスコアを算出し、検索パスＢとの比較によって検索パスＢを最適経路と判定し、複数のパターンにマッチするワイルドカードとして表現した、＜ｄｌ＞−＜ｄｔ＞−＜ｉｍｇ＞？−＜ｄｄ＞を生成する。

図５は、一実施形態に係るデータ抽出装置１０の処理内容を示すフローチャートである。

ステップＳ１０１において、ＣＰＵ（目的ノード受付部１１）は、ユーザの所望するデータを抽出するための目的ノードを受け付ける。その後、ＣＰＵは、処理をステップＳ１０２に移す。

ステップＳ１０２において、ＣＰＵ（祖先ノード特定部１２）は、共通祖先ノード特定処理を行い、ステップＳ１０１において受け付けた目的ノードの共通祖先ノードを特定する。その後、ＣＰＵは、処理をステップＳ１０３に移す。

ステップＳ１０３において、ＣＰＵ（パス抽出部１３、検索パス生成部１４）は、検索パス生成処理を行い、抽出対象となる抽出目的ノードの抽出ルールを示す、共通祖先ノードから抽出目的ノードまでの検索パスを生成する。その後、ＣＰＵは、処理をステップＳ１０４に移す。

ステップＳ１０４において、ＣＰＵ（データ抽出部１５）は、ステップＳ１０３において生成した検索パスによりデータを抽出する。その後、ＣＰＵは、処理を終了する。

図６は、一実施形態に係るデータ抽出装置１０の共通祖先ノード特定処理を示すフローチャートである。

ステップＳ２０１において、ＣＰＵ（祖先ノード特定部１２）は、受け付けた目的ノードをグループ化する。より具体的には、ＣＰＵは、ウェブデータＤＢ３１から取得したＨＴＭＬ文書の木構造に基づいて下位のノードから順に組み合わせて、目的ノードをグループ化する。その後、ＣＰＵは、処理をステップＳ２０２に移す。

ステップＳ２０２において、ＣＰＵ（祖先ノード特定部１２）は、グループ同士の共通上位ノードを抽出する。より具体的には、ＣＰＵは、グループ化したグループを、タグの種類によって位置付け、位置付けられたグループのうち最も下位に位置付けられたグループと、そのグループと同じ又は次の上位に位置付けられたグループとの共通上位ノードを抽出する。その後、ＣＰＵは、処理をステップＳ２０３に移す。

ステップＳ２０３において、ＣＰＵ（祖先ノード特定部１２）は、抽出した共通上位ノードに対応付けて、一段下位のグループを記憶する。より具体的には、ＣＰＵは、抽出した共通上位ノードに対応付けて、その共通上位ノードを上位ノードとするグループを記憶する。その後、ＣＰＵは、処理をステップＳ２０４に移す。

ステップＳ２０４において、ＣＰＵ（祖先ノード特定部１２）は、共通上位ノードを抽出したグループ同士を一つとする。その後、ＣＰＵは、処理をステップＳ２０５に移す。

ステップＳ２０５において、ＣＰＵ（祖先ノード特定部１２）は、２以上のグループが存在するか否かを判断する。すなわち、ＣＰＵは、グループ同士を一つにした結果、グループが２以上存在するか否かを判断する。この判断がＹＥＳの場合、ＣＰＵは、処理をステップＳ２０２に移し、ＮＯの場合、ＣＰＵは、処理をステップＳ２０６に移す。

ステップＳ２０６において、ＣＰＵ（祖先ノード特定部１２）は、最後に抽出した共通上位ノードを共通祖先ノードとして特定する。その後、ＣＰＵは、処理を終了し、本処理に移るステップの次のステップに処理を移す。

図７は、一実施形態に係るデータ抽出装置１０の検索パス生成処理を示すフローチャートである。

ステップＳ３０１において、ＣＰＵ（パス抽出部１３）は、特定した共通祖先ノードを開始ノードとする。より具体的には、ＣＰＵは、ステップＳ２０６において特定した共通祖先ノードを開始ノードとする。その後、ＣＰＵは、処理をステップＳ３０２に移す。

ステップＳ３０２において、ＣＰＵ（パス抽出部１３）は、抽出目的ノードへのパスにおいて、開始ノードを共通上位ノードとする一段下位のグループを取得する。より具体的には、ＣＰＵは、ステップＳ２０３において、共通上位ノードに対応付けて記憶したグループのうち、開始ノードを共通上位ノードとするグループを取得する。その後、ＣＰＵは、処理をステップＳ３０３に移す。

ステップＳ３０３において、ＣＰＵ（検索パス生成部１４）は、取得したグループ同士に基づいて、ＤＰマッチングにより、グループへの最適経路を求める（図４参照）。その後、ＣＰＵは、処理をステップＳ３０４に移す。

ステップＳ３０４において、ＣＰＵ（検索パス生成部１４）は、求めた最適経路に基づいて共通祖先ノードからグループまでの、複数のパターンにマッチするワイルドカードとしての表現を含む最適経路を生成する。その後、ＣＰＵは、処理をステップＳ３０５に移す。

ステップＳ３０５において、ＣＰＵ（検索パス生成部１４）は、グループを構成するノードが抽出目的ノードか否かを判断する。この判断がＹＥＳの場合、ＣＰＵは、処理をステップＳ３０７に移し、ＮＯの場合、ＣＰＵは、処理をステップＳ３０６に移す。

ステップＳ３０６において、ＣＰＵ（検索パス生成部１４）は、グループを構成するノードを開始ノードとする。その後、ＣＰＵは、処理をステップＳ３０２に移す。

ステップＳ３０７において、ＣＰＵ（検索パス生成部１４）は、生成した最適経路を検索パスとする。その後、ＣＰＵは、処理を終了し、本処理に移るステップの次のステップに処理を移す。

図８は、本発明の一実施形態に係るデータ抽出装置１０のデータ抽出例を示す図である。図８の例において、ＨＴＭＬ文書は、「カレーライスの作り方」と、「牛肉のおろし大根ソースの作り方」とから次のように構成されている。
＜ｈｔｍｌ＞
＜ｈｅａｄ＞
＜ｔｉｔｌｅ＞牛肉を使った料理＜／ｔｉｔｌｅ＞
＜／ｈｅａｄ＞
＜ｂｏｄｙ＞
＜ｈ１＞カレーライスの作り方＜／ｈ１＞
＜ｄｌ＞
＜ｄｔ＞牛肉＜／ｄｔ＞＜ｄｄ＞２００ｇ＜／ｄｄ＞
＜ｄｔ＞＜ｉｍｇｓｒｃ＝“ｃｕｒｒｙ．ｊｐｇ”＞カレールー＜／ｄｔ＞＜ｄｄ＞１／２パック＜／ｄｄ＞
＜ｄｔ＞ニンジン＜／ｄｔ＞＜ｄｄ＞１本＜／ｄｄ＞
＜ｄｔ＞タマネギ＜／ｄｔ＞＜ｄｄ＞２個＜／ｄｄ＞
＜ｄｔ＞ジャガイモ＜／ｄｔ＞＜ｄｄ＞２個＜／ｄｄ＞
＜／ｄｌ＞
＜／ｂｏｄｙ＞
＜ｂｏｄｙ＞
＜ｈ１＞牛肉のおろし大根ソースの作り方＜／ｈ１＞
＜ｄｌ＞
＜ｄｔ＞＜ｉｍｇｓｒｃ＝“ｔｏｋｕｓａｎ＿ｇｙｕｕ．ｊｐｇ”＞牛肩ロース肉＜／ｄｔ＞＜ｄｄ＞４００ｇ＜／ｄｄ＞
＜ｄｔ＞大根＜／ｄｔ＞＜ｄｄ＞１５０ｇ＜／ｄｄ＞
＜ｄｔ＞もやし＜／ｄｔ＞＜ｄｄ＞２００ｇ＜／ｄｄ＞
＜ｄｔ＞ピーマン＜／ｄｔ＞＜ｄｄ＞２個＜／ｄｄ＞
＜／ｄｌ＞
＜／ｂｏｄｙ＞
＜／ｈｔｍｌ＞

図８（ａ）の例は、データ抽出装置１０の表示装置に表示された画像において、抽出目的ノードを抽出するためのヒントである目的ノードとして、例えば、「カレーライスの作り方」、「牛肉」、「２００ｇ」、「カレールー」及び「１／２パック」が、マウスポインタ６０１によって指定され、受け付けられたことを示す例である。そして、図８（ａ）の例は、抽出ボタン６１０によって、データ抽出処理を開始することを示している例である。

図８（ｂ）の例は、データ抽出装置１０が受け付けたヒントである目的ノードによって、ＨＴＭＬ文書から抽出すべき項目を推定して、さらに「ニンジン」及び「１本」〜「ジャガイモ」及び「２個」と、「牛肉のおろし大根ソースの作り方」と、「牛肩ロース肉」及び「４００ｇ」〜「ピーマン」及び「２個」とを、画像データ６１１（“ｃｕｒｒｙ．ｊｐｇ”）及び画像データ６１２（“ｔｏｋｕｓａｎ＿ｇｙｕｕ．ｊｐｇ”）の有無に関わらず抽出したことを示す例である。

本実施形態によれば、データ抽出装置１０は、ＨＴＭＬ文書を記憶するウェブデータＤＢ３１を有する。そして、データ抽出装置１０は、ユーザから、ウェブデータＤＢ３１に記憶されたＨＴＭＬ文書を構成するノードのうち、二つ以上の目的ノードの指定を受け付け、受け付けた全ての目的ノードに共通の上位ノードである共通祖先ノードを特定する。次に、データ抽出装置１０は、特定した共通祖先ノードから指定された目的ノードまでの全てのパスを抽出し、抽出したパス及びＨＴＭＬ文書を構成するノードの繰り返し構造に基づき、ＤＰマッチングを行って、抽出対象となる抽出目的ノードの抽出ルールを示す、共通祖先ノードから当該抽出目的ノードまでの、複数のパターンにマッチするワイルドカードを一部に含む表現を有する検索パスを推定して生成する。そして、データ抽出装置１０は、共通祖先ノードを含むＨＴＭＬ文書から、生成した検索パスに従って検索される抽出目的ノードを抽出する。したがって、データ抽出装置１０は、ユーザからヒントとなる目的ノードの指定を受け付けて、ユーザが所望するデータを、容易、かつ、高速にＨＴＭＬ文書から抽出することができる。

以上、本発明の実施形態について説明したが、本発明は上述した実施形態に限るものではない。また、本発明の実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、本発明の実施形態に記載されたものに限定されるものではない。

１０データ抽出装置
１１目的ノード受付部
１２祖先ノード特定部
１３パス抽出部
１４検索パス生成部
１５データ抽出部
３１ウェブデータＤＢ
５０ウェブサーバ
７０インターネット

Claims

ＨＴＭＬ文書を記憶するＨＴＭＬ文書記憶手段と、
前記ＨＴＭＬ文書記憶手段に記憶された前記ＨＴＭＬ文書を構成するノードのうち、二つ以上の目的ノードの指定を受け付ける目的ノード受付手段と、
前記目的ノード受付手段によって受け付けられた全ての前記目的ノードに共通の上位ノードである共通祖先ノードを特定する祖先ノード特定手段と、
前記祖先ノード特定手段によって特定された前記共通祖先ノードから指定された前記目的ノードまでの全てのパスを抽出するパス抽出手段と、
前記パス抽出手段によって抽出された前記パス及び前記ＨＴＭＬ文書を構成するノードの繰り返し構造に基づき、抽出対象となる抽出目的ノードの抽出ルールを示す、前記共通祖先ノードから当該抽出目的ノードまでの検索パスを生成する検索パス生成手段と、
前記共通祖先ノードを含む前記ＨＴＭＬ文書から、前記検索パス生成手段によって生成された前記検索パスに従って抽出される前記抽出目的ノードを抽出するデータ抽出手段と、
を含むデータ抽出装置。
前記検索パス生成手段は、前記パス抽出手段が抽出した前記全てのパスに基づいて、複数のパターンにマッチするワイルドカードを一部に含む表現を有する前記検索パスを生成する請求項１に記載のデータ抽出装置。
前記検索パス生成手段は、前記パス抽出手段が抽出した前記全てのパスについてＤＰ（ＤｙｎａｍｉｃＰｒｏｇｒａｍｍｉｎｇ）マッチングを行って、前記ワイルドカードを一部に含む表現を有する検索パスを生成する請求項２に記載のデータ抽出装置。
前記祖先ノード特定手段は、
前記指定を受け付けた二つ以上の前記目的ノードのうちの前記ＨＴＭＬ文書の下位の前記目的ノードから順に組み合わせて、二つの前記目的ノードの共通上位ノードである第１の共通ノードを求める手段と、
二つの前記第１の共通ノードの共通上位ノードである第２の共通ノードを求める手段と、
前記共通上位ノードが一つになるまでこれを繰り返し、当該一つの共通上位ノードを前記共通祖先ノードとして特定する手段と、を含み、
前記パス抽出手段は、
前記共通祖先ノードから一段下位の共通上位ノードまでのパスを抽出する手段と、
前記一段下位の前記共通上位ノードが前記抽出目的ノードでない場合には、前記一段下位の共通上位ノードからさらに一段下位の共通上位ノードまでのパスを抽出する手段と、
さらに、これを繰り返し、前記抽出目的ノードまでのパスを抽出する繰り返し手段と、を含み、
前記検索パス生成手段は、
前記共通祖先ノードから一段下位の共通上位ノードまでの検索パスを、前記抽出されたパスのＤＰマッチングを行って生成する手段と、
前記一段下位の共通上位ノードが前記抽出目的ノードでない場合には、前記一段下位の共通上位ノードからさらに一段下位の共通上位ノードまでの検索パスを、前記抽出された前記パスのＤＰマッチングを行って、生成する手段と、
さらに、これを繰り返し、前記抽出目的ノードまでの検索パスを生成する手段と、を含む、
請求項１に記載のデータ抽出装置。
ＨＴＭＬ文書を記憶するＨＴＭＬ文書記憶手段を有するデータ抽出装置が実行する方法であって、
前記ＨＴＭＬ文書記憶手段に記憶された前記ＨＴＭＬ文書を構成するノードのうち、二つ以上の目的ノードの指定を受け付ける目的ノード受付ステップと、
前記目的ノード受付ステップにおいて受け付けられた全ての前記目的ノードに共通の上位ノードである共通祖先ノードを特定する祖先ノード特定ステップと、
前記祖先ノード特定ステップにおいて特定された前記共通祖先ノードから指定された前記目的ノードまでの全てのパスを抽出するパス抽出ステップと、
前記パス抽出ステップにおいて抽出された前記パス及び前記ＨＴＭＬ文書を構成するノードの繰り返し構造に基づき、抽出対象となる抽出目的ノードの抽出ルールを示す、前記共通祖先ノードから当該抽出目的ノードまでの検索パスを生成する検索パス生成ステップと、
前記共通祖先ノードを含む前記ＨＴＭＬ文書から、前記検索パス生成ステップにおいて生成された前記検索パスに従って抽出される前記抽出目的ノードを抽出するデータ抽出ステップと、を含む方法。