(57)【特許請求の範囲】
【請求項１】
ＨＴＭＬ文書を含む、構文木が変更された構造化文書の部分を抽出する構造化文書の抽出方法において、
構造化文書が格納されている構造化文書記憶手段から構造化文書を読み込んで、表示手段に該構造化文書を表示し、
表示された前記構造化文書からユーザによって指定された部分に対応するノードの表示領域の座標と、該ノードより上位の一連のノードの表示領域の座標情報を要素とする配列によって該部分を指定し、指定された該座標情報を位置情報記憶手段に蓄積し、
更新された構造化文書を前記構造化文書記憶手段から読み込み、前記表示手段に表示し、
前記位置情報記憶手段に蓄積されている一連のノードの表示領域の座標情報を読み込み、
前記構造化文書の構文木において、ルートとなるノード及び該ノードより下位の一連のノードからなる複数のパスについて、各パスを構成する各ノードの表示領域の座標と、読み込まれた前記一連のノードの表示領域の座標の距離が最小のノードを選択する処理を前記位置情報記憶手段に蓄積されている座標情報の数だけ繰り返し、最終的に選択されたノードを抽出し、出力することを特徴とする構造化文書の抽出方法。
【請求項２】
前記構造化文書の構文木において、該構文木の隣接するノードにおいて、子ノードの表示領域を親ノードの表示領域の幅と高さで正規化した相対座標を該表示領域の座標情報とする請求項１記載の構造化文書の抽出方法。
【請求項３】
ＨＴＭＬ文書を含む、構文木が変更された構造化文書の部分を抽出する構造化文書の抽出装置であって、
構造化文書が格納されている構造化文書記憶手段から構造化文書を読み込む文書読込手段と、
読み込まれた構造化文書を表示する表示手段と、
表示された前記構造化文書からユーザによって指定された部分に対応するノードの表示領域の座標と、該ノードより上位の一連のノードの表示領域の座標情報を要素とする配列によって該部分を指定する部分指定手段と、
指定された座標情報を位置情報記憶手段に保存する位置情報保存手段と、
更新された構造化文書を前記構造化文書記憶手段から読み込む更新文書読込手段と、
読み込まれた前記構造化文書を表示手段に表示する更新文書表示手段と、
前記位置情報記憶手段に蓄積されている一連のノードの表示領域の座標情報を読み込む位置情報読込手段と、
表示された前記構造化文書の構文木において、ルートとなるノード及び該ノードより下位の一連のノードからなる複数のパスについて、各パスを構成する各ノードの表示領域の座標と、前記位置情報読込手段で読み込まれた前記一連のノードの表示領域の座標の距離が最小のノードを選択する処理を前記位置情報記憶手段に蓄積されている座標情報の数だけ繰り返し、最終的に選択されたノードを抽出する部分抽出手段と、
前記部分抽出手段で抽出されたノードを出力する部分情報出力手段と、
を有することを特徴とする構造化文書の抽出装置。
【請求項４】
前記部分抽出手段は、
前記構造化文書の構文木において、該構文木の隣接するノードにおいて、子ノードの表示領域を親ノードの表示領域の幅と高さで正規化した相対座標を該表示領域の座標情報とする手段を含む請求項３記載の構造化文書の抽出装置。
【請求項５】
請求項３乃至４のいずれか１項に記載の構造化文書の抽出装置を構成する各手段としてコンピュータを機能させる構造化文書の抽出プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、構造化文書の抽出方法及び装置及びプログラムに係り、特に、ＨＴＭＬ等の構造化文書から、所望の部分を指定・抽出し、別の構造化文書上で再利用する、あるいは、含まれるテキスト等が変更された後の、当該文書から対応部分を抽出するための構造化文書の抽出方法及び装置及びプログラムに関する。
【０００２】
【従来の技術】
日々更新されるＨＴＭＬ等の構造化文書から、ある特定の指定部分を抽出したいというニーズがある。例えば、ユーザが日常訪れるウェブサイトから注目している部分だけを集めて抽出することができれば、ページスクロール等を行うことなく、必要な情報だけを容易に一覧することができる。抽出にあたっては、この指定部分に含まれるテキスト等の変更があったとしても、変更された文書から当初の指定部分を特定した上で最新の情報を抽出することが求められる。
【０００３】
これを実現する従来技術として二つを取り上げ、以下に説明する。
【０００４】
一つは、ＷＷＷ情報抽出システムである。ＨＴＭＬ等の構造化文書の指定部分の手掛かりとするために、その開始箇所と終了箇所にあるテキストを保存しておく。文書からの指定部分の抽出は、保存されているテキストから開始箇所と終了箇所をＨＴＭＬ中に特定して両者に囲まれた部分を抽出するものである(例えば、特許文献１参照)。
【０００５】
もう一つは、WebMethods社が提案する方法や、Iocchiが提案する方法のベースとなっている方法である(例えば、非特許文献１、非特許文献２参照)。
【０００６】
HTML等の構造化文書の部分を指定するために、まず文書を図８に示すような構文木に変換し、指定部分を構文木内の位置として保存しておく。文書からの指定部分の抽出は、まず、文書を構文木に変換し、保存されている位置を構文木内に特定してこれに対応する部分を抽出するものである。
【０００７】
【特許文献１】
特許第２８６７９８６号
【０００８】
【非特許文献１】
http://www.w3.org/TR/NOTE-widl.html
【０００９】
【非特許文献２】
Luca Iocchi, “The Web-OEM approach to Web information extraction,”Journal of Network and Computer Applications, Vol.22, pp259-269, 1999
【００１０】
【発明が解決しようとする課題】
しかしながら、WWW情報抽出システムでは、開始、終了箇所にあるテキストを手掛かりとして、HTML等の構造化文書の部分を指定しているため、このテキスト自身に変更があり得る文書については、図９に示すように、適用できないという問題がある。
【００１１】
また、この方法では、図１０に示すように、指定される部分を構文木としてみたとき、一般には部分木を構成しないため、この部分を別の構造化文書中で再利用することは困難である。
【００１２】
また、WebMethods社や、Iocchiが提案する構造化文書の構文木中の位置に基づく方法では、画面表示には影響がない程度であっても、この構文木自身にある種の変更（兄弟ノードの追加や削除等）がある場合には所期の指定部分を抽出することができないという問題がある。
【００１３】
本発明は、上記の点に鑑みなされたもので、指定部分の開始、終了箇所に依存せず、上記のような構文木の変更がある場合でも確実に指定部分を抽出することが可能な構造化文書の抽出方法及び装置及びプログラムを提供することを目的とする。
【００１４】
【課題を解決するための手段】
図１は、本発明の原理を説明するための図である。
【００１５】
本発明（請求項１）は、ＨＴＭＬ文書を含む、構文木が変更された構造化文書の部分を抽出する構造化文書の抽出方法において、
構造化文書が格納されている構造化文書記憶手段から構造化文書を読み込んで、表示手段に該構造化文書を表示し（ステップ１）、
表示された構造化文書からユーザによって指定された部分に対応するノードの表示領域の座標と、該ノードより上位の一連のノードの表示領域の座標情報を要素とする配列によって該部分を指定し（ステップ２）、指定された該座標情報を位置情報記憶手段に蓄積し（ステップ３）、
更新された構造化文書を構造化文書記憶手段から読み込み、表示手段に表示し（ステップ４）、
位置情報記憶手段に蓄積されている一連のノードの表示領域の座標情報を読み込み（ステップ５）、
構造化文書の構文木において、ルートとなるノード及び該ノードより下位の一連のノードからなる複数のパスについて、各パスを構成する各ノードの表示領域の座標と、読み込まれた一連のノードの表示領域の座標の距離が最小のノードを選択する（ステップ６）処理を位置情報記憶手段に蓄積されている座標情報の数だけ繰り返し（ステップ７）、最終的に選択されたノードを抽出し（ステップ８）、出力する（ステップ９）。
【００１８】
また、本発明（請求項２）は、構造化文書の構文木において、該構文木の隣接するノードにおいて、子ノードの表示領域を親ノードの表示領域の幅と高さで正規化した相対座標を該表示領域の座標情報とする。
【００１９】
図２は、本発明の原理構成図である。
【００２０】
本発明（請求項３）は、ＨＴＭＬ文書を含む、構文木が変更された構造化文書の部分を抽出する構造化文書の抽出装置であって、
構造化文書が格納されている構造化文書記憶手段から構造化文書を読み込む文書読込手段１１０と、
読み込まれた構造化文書を表示する文書表示手段１２０と、
文書表示手段１２０に表示された構造化文書からユーザによって指定された部分に対応するノードの表示領域の座標と、該ノードより上位の一連のノードの表示領域の座標情報を要素とする配列によって該部分を指定する部分指定手段１３０と、
指定された座標情報を位置情報記憶手段３００に保存する位置情報保存手段１４０と、
更新された構造化文書を構造化文書記憶手段から読み込む更新文書読込手段２１０と、
読み込まれた構造化文書を表示手段に表示する更新文書表示手段２２０と、
位置情報記憶手段３００に蓄積されている一連のノードの表示領域の座標情報を読み込む位置情報読込手段２４０と、
表示された構造化文書の構文木において、ルートとなるノード及び該ノードより下位の一連のノードからなる複数のパスについて、各パスを構成する各ノードの表示領域の座標と、位置情報読込手段２４０で読み込まれた一連のノードの表示領域の座標の距離が最小のノードを選択する処理を位置情報記憶手段３００に蓄積されている座標情報の数だけ繰り返し、最終的に選択されたノードを抽出する部分抽出手段２３０と、
部分抽出手段２３０で抽出されたノードを出力する部分情報出力手段２５０と、を有する。
【００２３】
本発明（請求項４）は、部分抽出手段２３０において、
構造化文書の構文木において、該構文木の隣接するノードにおいて、子ノードの表示領域を親ノードの表示領域の幅と高さで正規化した相対座標を該表示領域の座標情報とする手段を含む。
【００２４】
本発明（請求項５）は、請求項３乃至４のいずれか１項に記載の構造化文書の抽出装置を構成する各手段としてコンピュータを機能させる構造化文書の抽出プログラムである。
【００２８】
上記のように、本発明は、HTML等の構造化文書の部分を指定し、抽出スルシステムにおいて、当該文書の構文木において、ユーザが指示する部分に対応するノードの表示領域の座標情報と、これより上位の一連のノードの表示領域の座標情報とを要素とする配列によって当該部分を指定し、また更新された構造化文書の構文木において、ルートとなるノード及びこれより下位の一連のノードからなる複数のパスについて、各パスを構成する各ノードの表示領域の座標情報と、前述の指定された一連のノードの表示領域の座標情報とを比較した時に最も一致するパスの最下位のノードを抽出するものであり、これにより、実際の表示領域の座標を手掛かりにして抽出部分を特定することを特徴としている。
【００２９】
【発明の実施の形態】
以下、図面と共に本発明の実施の形態を説明する。
【００３０】
図３は、本発明の一実施の形態における構造化文書の部分指定・抽出装置の構成を示す。同図に示す装置は、指定部１００と抽出部２００及び、位置情報蓄積部３００から構成される。なお、本実施の形態では、部分指定・抽出装置として説明するが、部分指定装置及び抽出装置の２つの装置から構成されてもよい。
指定部１００は、文書読込部１１０、文書表示部１２０、部分指定部１３０、及び位置情報保存部１４０から構成される。
【００３１】
以下に、上記の構成における動作を説明する。
【００３２】
図４は、本発明の一実施の形態における構造化文書の部分指定の動作のフローチャートであり、図５は、本発明の一実施の形態における部分指定の例を示す。
【００３３】
ステップ１０１）  文書読込部１１０は、データーベース等の記憶手段に格納されている構造化文書を読み込み、文書表示部１２０に表示する。
【００３４】
ステップ１０２）  ユーザは、文書表示部１２０に表示されたブラウザ上で構造化文書から選択したい部分を指定する。
【００３５】
ステップ１０３）  部分指定部１３０において、ユーザから指定された部分に対応するノードの表示領域を検出する。検出する方法としては、例えば、Java（登録商標）Script（『Java（登録商標） Script The Definitive Guide, Fourth Edition』David Flanagan O’reilly & Associates, Inc. USA, Dec. 15,2001）を用いるものとする。
【００３６】
ステップ１０４）  次に、部分指定部１３０は、検出されたノードの表示位置を計算する。
【００３７】
ステップ１０５）  さらに、部分指定部１３０は、構文木に従って、検出されたノードの親ノードの表示領域（座標情報）を検出する。
【００３８】
ステップ１０４，１０５の処理を最上位ノードまで繰り返す。なお、「Java（登録商標）Script」には、構文木に従ってノードを検索するための方法が用意されている。
【００３９】
ステップ１０６）  次に、位置情報保存部１４０は、計算された全てのノードの表示位置を位置情報蓄積部３００に蓄積する。
【００４０】
なお、保存すべきノードの表示領域の座標を、ノードに対応するタグ名等によって予め指定しておくことにより、位置情報蓄積部３００に保存される情報量と全体の計算量を削減することができる。
【００４１】
また、位置情報蓄積部３００に保存する座標情報は、親ノードの表示領域の座標で正規化された相対座標としてもよいし、例えば、構文木中、親ノードの表示領域をその左上、右下の座標を用いて（left0, top0, right0, bottom0）、子ノードの表示領域を同様に（left1, top1, right1, bottom1）とするとき、相対座標は
(left1/(right0-left0), top1/(bottom0-top0), right1/(right0-left0), bottom1/
(bottom0-top0)）
などとすることができる。
【００４２】
次に、構造化文書の部分指定・抽出装置の抽出部２００について説明する。
【００４３】
抽出部２００は、文書読込部２１０、文書表示部２２０、部分抽出部２３０、位置情報読込部２４０、及び、部分情報出力部２５０から構成される。
【００４４】
以下に、上記の構成における動作を説明する。
【００４５】
図６は、本発明の一実施の形態における指定部分の抽出動作のフローチャートであり、図７は、本発明の一実施の形態における抽出の例を示す。
【００４６】
ステップ２０１）  更新された処理対象とする構造化文書がデーターベース等の記憶手段から、文書読込部２１０によって読み込まれ、文書表示部２２０のブラウザ画面上に表示される。
【００４７】
ステップ２０２）  部分抽出部２３０において、表示されている最上位ノードの表示領域を検出する。具体的には、図７に示す「htmlノード」が選択される。
【００４８】
ステップ２０３）  部分抽出部２３０は、構文木に従って、当該ノードの子ノードの表示領域を検出する。
【００４９】
ステップ２０４）  位置情報読込部２４０が、位置情報蓄積部３００から位置情報を読み込み、部分抽出部２３０に渡す。これにより、部分抽出部２３０は、保存されていた位置情報の表示位置に最もよく一致する子ノードを選択する。
【００５０】
なお、上記の子ノードや、直近にある指定されたタグ名を持つノードは、通常複数存在するが、これらの複数のノードから以下の手順によって位置情報蓄積部３００に保存されている座標情報に最もよく一致するノードを選択する。
【００５１】
ここで、保存されている座標情報を(left2, top2, right2, bottom2)、複数ノードのうち、ｉ番目のものの表示領域の座標情報を、（left(i), top(i), right(i), bottom(i)）とする。選択すべきノードを、この両者の距離
｜left2-left(i)｜＋｜top2-top(i)｜+｜right2-right(i)｜+｜bottom2-bottom(i)｜を最小にするｉに対応するノードとする。ここで用いる座標情報は、上記で定義される相対座標を用いることができる。さらに、領域に対応する矩形の重心の座標、及び、幅、高さの差
｜（left2+right2）/2−（left(i)+right(i)）/2｜
＋｜（top2+bottom2）/2−（top(i)+bottom(i)）/2｜
＋｜（right2-left2）−(right(i)-left(i))｜
＋｜（bottom2-top2）−（bottom(i)−top(i)）｜
として、両者の距離を比較すれば、文書の更新によって位置のズレが生じたとしても確実に所期の指定部分を抽出できる。
【００５２】
ステップ２０５）  上記のようにして選択されたノードの子ノード（もしくは、直近にある指定されたタグ名を持つノード）について同じ操作を行う。以上の操作を位置情報蓄積部３００に保存されている座標情報の数だけ繰り返す。最終的に選択されたノードを抽出し、部分情報出力部２５０より出力する。
【００５３】
また、上記の構造化文書の部分指定部１００、抽出部２００の構成による処理をプログラムとして構築し、部分指定装置、抽出装置として利用されるコンピュータにインストールし、ＣＰＵ等の制御手段により実行させることも可能である。また、構築されたプログラムをネットワークを介して流通させることも可能である。
【００５４】
また、構築されたプログラムを部分指定装置、抽出装置として利用されるコンピュータに接続されるハードディスク装置や、フレキシブルディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納しておき、実行時にコンピュータにインストールして実行させることも可能である。
【００５５】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【００５６】
【発明の効果】
上述のように、本発明によれば、構造化文書について、実際の表示領域の座標情報を手掛かりにして抽出部分が特定されるため、指定部分の開始、終了箇所に依存せず、構文木の変更がある場合でも確実に指定部分を抽出できる。
【００５７】
【図面の簡単な説明】
【図１】本発明の原理を説明するための図である。
【図２】本発明の原理構成図である。
【図３】  本発明の一実施の形態における構造化文書の部分指定・抽出装置の構成図である。
【図４】本発明の一実施の形態における部分指定の動作のフローチャートである。
【図５】本発明の一実施の形態におけるにおける部分指定の例である。
【図６】本発明の一実施の形態における指定部分の抽出動作のフローチャートである。
【図７】本発明の一実施の形態における抽出の例である。
【図８】ＨＴＭＬのソースと対応する構文木の例である。
【図９】開始・終了箇所のテキストを手掛かりに部分指定、抽出した例である。
【図１０】開始、終了を指示するテキストを手掛かりにしてＨＴＭＬの対応部分を抽出した例である。
【符号の説明】
１００  指定部
１１０  文書読込手段、文書読込部
１２０  文書表示手段、文書表示部
１３０  部分指定手段、部分指定部
１４０  位置情報保持手段、位置情報保持部
２００  抽出装置、抽出部
２１０  更新文書読込手段、文書読込部
２２０  更新文書表示手段、文書表示部
２３０  部分抽出手段、部分抽出部
２４０  位置情報読込手段、位置情報読込部
２５０  部分情報出力手段、部分情報出力部
３００  位置情報蓄積手段、位置情報蓄積部
【図１】
0004046000.tif 000002
【図２】
0004046000.tif 000003
【図３】
0004046000.tif 000004
【図４】
0004046000.tif 000005
【図５】
0004046000.tif 000006
【図６】
0004046000.tif 000007
【図７】
0004046000.tif 000008
【図８】
0004046000.tif 000009
【図９】
0004046000.tif 000010
【図１０】
0004046000.tif 000011