(57)【特許請求の範囲】
【請求項１】
構造化文書の任意の部分を事前に指定し、更新された文書から指定部分を特定するために、文書を木構造に変換し、部分文書を参照するために対応する部分木の識別子を生成する情報抽出装置における、構造化文書からの情報抽出方法であって、
部分指定手段が、
木構造に変換された更新前の文書について、部分木識別子生成手段に部分木識別子を生成させる第１の手順と、
指定した部分文書に対応する部分木の部分木識別子を当該部分文書の部分文書ＩＤとともに部分情報記憶手段に格納する手順と、
部分特定手段が、
前記部分情報記憶手段から、特定すべき部分文書の部分文書ＩＤに基づき対応する部分木識別子を取得する手順と、
木構造に変換された更新後の文書について、前記部分木識別子生成手段に部分木識別子を生成させる第２の手順と、
前記更新された文書に存在する部分木の部分木識別子のリストを生成する手順と、
前記部分木識別子のリストから、前記部分情報記憶手段から取得した部分木識別子と同一の部分木識別子を持つ部分木を、指定部分として特定する手順と、
を有し、
前記部分木識別子を生成させる第１及び第２の手順は、
前記部分木識別子生成手段が、
木構造に変換された文書について、部分木の根に対応するタグ名、タグの書式属性名、書式属性の値の組み合わせをタグ識別子とする手順と、
該タグ識別子に書式属性が複数存在する場合は、前記書式属性名の順番で書式属性を整列させてタグ識別子を正規化する手順と、
前記タグ識別子と木構造の同一階層における当該タグ識別子の順番を示す数値索引の組を生成する手順と、
前記タグ識別子と前記数値索引の組を、木構造の根から当該部分木の根まで入れ子状に連鎖させた文字列を、当該部分木の部分木識別子として生成する手順とからなり、
前記指定部部分として特定する手順は、
前記部分木特定手段が、
前記部分木識別子の照合を、最初に該部分木識別子の末端の当該部分木の根に対応するタグ識別子だけで照合を行う手順と、
照合された部分木の候補が複数ある場合に、次に該タグ識別子の数値索引の照合を行うことで候補を絞る手順と、
タグ識別子の数値索引により候補を絞っても複数の候補が残っている場合に、最後に親のタグに遡って再帰的に照合を繰り返す手順と、
いずれかの照合を取った結果、候補の部分木が一つしかなくなった時点で、該候補を指定した部分木として特定する手順とからなる
ことを特徴とする構造化文書からの情報抽出方法。
【請求項２】
構造化文書の任意の部分を事前に指定し、更新された文書から指定部分を特定するために、文書を木構造に変換し、部分文書を参照するために対応する部分木の識別子を生成する情報抽出装置であって、
部分木識別子を生成する部分木識別子生成手段と、
木構造に変換された更新前の文書について、前記部分木識別子生成手段に部分木識別子を生成させる手段と、指定した部分文書に対応する部分木の部分木識別子を当該部分文書の部分文書ＩＤとともに部分情報記憶手段に格納する手段と、
を有する部分指定手段と、
前記部分情報記憶手段から、特定すべき部分文書の部分文書ＩＤに基づき対応する部分木識別子を取得する手段と、木構造に変換された更新後の文書について、前記部分木識別子生成手段に部分木識別子を生成させる手段と、更新された文書に存在する部分木の部分木識別子のリストを生成する手段と、該部分木識別子のリストから、前記部分情報記憶手段から取得した部分木識別子と同一の部分木識別子を持つ部分木を、指定部分として特定する手段と、を有する部分特定手段と、からなり、
前記部分木識別子生成手段は、
木構造に変換された文書について、部分木の根に対応するタグ名、タグの書式属性名、書式属性の値の組み合わせをタグ識別子とする手段と、
該タグ識別子に書式属性が複数存在する場合は、前記書式属性名の順番で書式属性を整列させてタグ識別子を正規化する手段と、
前記タグ識別子と木構造の同一階層における当該タグ識別子の順番を示す数値索引の組を生成する手段と、
前記タグ識別子と前記数値索引の組を、木構造の根から当該部分木の根まで入れ子状に連鎖させた文字列を、当該部分木の部分木識別子として生成する手段と、を有し、
前記部分木特定手段は、
前記部分木識別子の照合を、最初に該部分木識別子の末端の当該部分木の根に対応するタグ識別子だけで照合を行う手段と、
照合された部分木の候補が複数ある場合に、次に該タグ識別子の数値索引の照合を行うことで候補を絞る手段と、
タグ識別子の数値索引により候補を絞っても複数の候補が残っている場合に、最後に親のタグに遡って再帰的に照合を繰り返す手段と、
いずれかの照合を取った結果、候補の部分木が一つしかなくなった時点で、該候補を指定した部分木として特定する手段と、を有する
ことを特徴とする構造化文書からの情報抽出装置。
【請求項３】
構造化文書の任意の部分を事前に指定し、更新された文書から指定部分を特定するために、文書を木構造に変換し、部分文書を参照するために対応する部分木識別木を生成する処理をコンピュータに実行させる、情報抽出プログラムであって、
コンピュータを請求項２記載の各手段として機能させることを特徴とする情報抽出プログラム。
【請求項４】
請求項３に記載の情報抽出プログラムを格納したことを特徴とするコンピュータ読み取り可能な記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、構造化文書からの情報抽出方法及び装置及び情報抽出プログラム及びコンピュータ読み取り可能な記録媒体に係り、特に、日々更新されるＨＴＭＬ等の構造化文書から、事前に所望の部分を指定し、将来更新された文書から、指定した部分を特定するための、構造化文書からの情報抽出方法及び装置及び情報抽出プログラム及びコンピュータ読み取り可能な記録媒体に関する。
【０００２】
【従来の技術】
日々更新されるＨＴＭＬ等の構造化文書から、一部分だけを指定したいというニーズがある。例えば、ユーザが馴染みのウェブサイトの注目している部分だけを集めて、スクラップすることで、必要な情報だけを容易に一覧することができる。また、そのスクラップされた部分の情報源が日々更新される場合、更新された文書から指定した部分を特定し、再度スクラップすることが求められる。
【０００３】
このために、ＷＷＷ情報抽出システムに関する「特願平８−３５６２１８」では、事前に指定した部分の開始箇所と終了箇所を保存しておき、更新された文書から開始箇所と終了箇所を特定し、両者に挟まれた部分を特定部分として抽出する方法が提案されている。
【０００４】
また、webMethods社が提案するシステム(http://www.w3.org/TR/NOTE-widl)や、Luca Iocchi が提案するシステム(Luca Iocchi:The Web-OEM approach to Web information extraction, Journal of Network and Computer Applications, Vol.22, pp.259-269 (1999)) では、ＨＴＭＬを木構造に変換し、事前に指定した部分に対応する部分木の情報を保存しておき、更新された文書の中から保存してある部分木の情報に対応する部分を特定する方法を提案している。なお、この部分木の情報とは、タグ名をタグの識別子とし、木構造内の同一階層におけるタグ名の数値索引を付与した文字列を、木構造の根から指定した部分の部分木の根まで入れ子状に連鎖させた文字列を、当該部分の識別子としている。図１７（ａ）の例では、“doc ”を木構造の根とした場合、指定した「社会ニュース」の部分を参照するための識別子は、doc.table[0].table[0] のように表現される。
【発明が解決しようとする課題】
しかしながら、上記従来のＷＷＷ情報抽出システムに関する「特願平８−３５６２１８」の方法では、事前に登録している部分の開始、終了箇所をもとに特定部分を抽出しているため、文書が更新されても位置がずれないような開始、終了箇所が存在しない場合には適用できない。
【０００５】
また、更新後も位置がずれないような開始、終了箇所が存在したとしても、どの部分が更新後も位置がずれない部分かを判断することが困難である。更新される部分の上下にはタイトルや区切り線が存在する確率が高いという知識を利用したとしても、デザインが作者の一存で決められているインターネット上のホームページでは、例外が多く存在する。このため、この方法の適用領域は、限定されてしまうという問題がある。
【０００６】
また、webMethods社やLuca Iocchi が提案する指定部分の部分木の識別子に基づく方法は、更新前後で文書の構造が変わらないことを前提にしている。このため、更新前後で文書の構造が若干変化することで、事前に指定した部分木の識別子の整合性がとれなくなるという問題がある。
【０００７】
例えば、文書の指定部分と木構造の同一階層に同じタグの文書ブロックが挿入されると、部分木の識別子に含まれるタグの数値索引がずれる。図１７の例では、（ａ）から（ｂ）に文書が更新されるときに、指定部分の上部にtable タグで囲まれた「広告２」に関する文書が挿入されることで、指定している社会ニュースのtable タグのタグ名によるタグ識別子の数値索引が、table[0]からtable[1]にずれてしまう。バナー広告や、緊急ニュースの挿入、削除が行われるサイトのトップページでは、このようなフォーマットの微細な変更が行われる可能性が高い。しかも、ユーザが指定したいのは、情報が頻繁に更新されるこのようなサイトのトップページが多く、微細な変更による指定部分の抽出精度の低下は問題である。
【０００８】
また、指定部分より文書の前方に、部分指定時には存在しなかったタグの閉じ忘れが存在する場合、見かけ上、指定部分の親のノードとして閉じ忘れたタグが存在してしまう。図１７の例では（ａ）から（ｂ）に文書が更新されるときに、指定部分の上部の「広告１」を囲むtable タグを閉じ忘れた場合、doc.table[0].table[0] という指定部分の情報が、doc.table[0].table[0].table[1]のように、社会ニュースの親ノードにこのtable タグに該当するノードが挿入されてしまう。これにより、更新前後における指定部分の部分木の識別子がずれてしまう。現在一般的に普及しているＷＷＷブラウザは、タグの閉じ忘れを許容して表示する場合が多く、ページ制作者は、タグの閉じ忘れの存在に気付かないで情報をアップデートすることが頻繁に行われている。
【０００９】
上記の、同一タグの文書ブロックが指定部分と同じ階層に挿入されること、タグの閉じ忘れにより、図１７の例では、（ａ）から（ｂ）に文書が更新されるときに、指定部分を参照する部分木の識別子が、doc.table[0].table[0]から、doc.table[0].table[0].table[1]に変わってしまう。
本発明は、上記の点に鑑みなされたもので、同一タグの文書ブロックが指定部分と同じ階層に挿入された場合や、タグの閉じ忘れが存在する場合でも、指定部分の開始、終了箇所に依存しない方法で、指定部分の抽出精度を低下させないことが可能な構造化文書からの情報抽出方法及び装置及び情報抽出プログラム及びコンピュータ読み取り可能な記録媒体を提供することを目的とする。
【００１０】
【課題を解決するための手段】
図１は、本発明の原理を説明するための図である。
【００１１】
本発明（請求項１）は、構造化文書の任意の部分を事前に指定し、更新された文書から指定部分を特定するために、文書を木構造に変換し、部分文書を参照するために対応する部分木の識別子を生成する情報抽出装置における、構造化文書からの情報抽出方法であって、
部分指定手段が、
木構造に変換された更新前の文書について、部分木識別子生成手段に部分木識別子を生成させる第１の手順と、
指定した部分文書に対応する部分木の部分木識別子を当該部分文書の部分文書ＩＤとともに部分情報記憶手段に格納する手順と、
部分特定手段が、
部分情報記憶手段から、特定すべき部分文書の部分文書ＩＤに基づき対応する部分木識別子を取得する手順と、
木構造に変換された更新後の文書について、部分木識別子生成手段に部分木識別子を生成させる第２の手順と、
更新された文書に存在する部分木の部分木識別子のリストを生成する手順と、
部分木識別子のリストから、部分情報記憶手段から取得した部分木識別子と同一の部分木識別子を持つ部分木を、指定部分として特定する手順と、
を有し、
部分木識別子を生成させる第１及び第２の手順は、
部分木識別子生成手段が、
木構造に変換された文書について、部分木の根に対応するタグ名、タグの書式属性名、書式属性の値の組み合わせをタグ識別子とする手順（ステップ１）と、
該タグ識別子に書式属性が複数存在する場合は、書式属性名の順番で書式属性を整列させてタグ識別子を正規化する手順（ステップ２）と、
タグ識別子と木構造の同一階層における当該タグ識別子の順番を示す数値索引の組を生成する手順と、
タグ識別子と数値索引の組を、木構造の根から当該部分木の根まで入れ子状に連鎖させた文字列を、当該部分木の部分木識別子として生成する手順とからなり、
指定部部分として特定する手順は、
部分木特定手段が、
部分木識別子の照合を、最初に該部分木識別子の末端の当該部分木の根に対応するタグ識別子だけで照合を行う手順と、
照合された部分木の候補が複数ある場合に、次に該タグ識別子の数値索引の照合を行うことで候補を絞る手順と、
タグ識別子の数値索引により候補を絞っても複数の候補が残っている場合に、最後に親のタグに遡って再帰的に照合を繰り返す手順と、
いずれかの照合を取った結果、候補の部分木が一つしかなくなった時点で、該候補を指定した部分木として特定する手順（ステップ３）とからなる。
【００１２】
本発明（請求項２）は、構造化文書の任意の部分を事前に指定し、更新された文書から指定部分を特定するために、文書を木構造に変換し、部分文書を参照するために対応する部分木の識別子を生成する情報抽出装置であって、
部分木識別子を生成する部分木識別子生成手段と、
木構造に変換された更新前の文書について、部分木識別子生成手段に部分木識別子を生成させる手段と、指定した部分文書に対応する部分木の部分木識別子を当該部分文書の部分文書ＩＤとともに部分情報記憶手段に格納する手段と、
を有する部分指定手段と、
部分情報記憶手段から、特定すべき部分文書の部分文書ＩＤに基づき対応する部分木識別子を取得する手段と、木構造に変換された更新後の文書について、部分木識別子生成手段に部分木識別子を生成させる手段と、更新された文書に存在する部分木の部分木識別子のリストを生成する手段と、該部分木識別子のリストから、部分情報記憶手段から取得した部分木識別子と同一の部分木識別子を持つ部分木を、指定部分として特定する手段と、を有する部分特定手段と、からなり、
部分木識別子生成手段は、
木構造に変換された文書について、部分木の根に対応するタグ名、タグの書式属性名、書式属性の値の組み合わせをタグ識別子とする手段と、
該タグ識別子に書式属性が複数存在する場合は、書式属性名の順番で書式属性を整列させてタグ識別子を正規化する手段と、
タグ識別子と木構造の同一階層における当該タグ識別子の順番を示す数値索引の組を生成する手段と、
タグ識別子と数値索引の組を、木構造の根から当該部分木の根まで入れ子状に連鎖させた文字列を、当該部分木の部分木識別子として生成する手段と、を有し、
部分木特定手段は、
部分木識別子の照合を、最初に該部分木識別子の末端の当該部分木の根に対応するタグ識別子だけで照合を行う手段と、
照合された部分木の候補が複数ある場合に、次に該タグ識別子の数値索引の照合を行うことで候補を絞る手段と、
タグ識別子の数値索引により候補を絞っても複数の候補が残っている場合に、最後に親のタグに遡って再帰的に照合を繰り返す手段と、
いずれかの照合を取った結果、候補の部分木が一つしかなくなった時点で、該候補を指定した部分木として特定する手段と、を有する。
【００１４】
本発明（請求項３）は、構造化文書の任意の部分を事前に指定し、更新された文書から指定部分を特定するために、文書を木構造に変換し、部分文書を参照するために対応する部分木識別木を生成する処理をコンピュータに実行させる、情報抽出プログラムであって、
コンピュータを請求項２記載の各手段として機能させる情報抽出プログラムである。
【００１７】
本発明（請求項４）は、請求項３に記載の情報抽出プログラムを格納したコンピュータ読み取り可能な記憶媒体である。
【００２０】
上記のように、本発明では、「部分木の識別子＝タグの識別子」となっている。従来の方法と比較すると、従来は、「タグの識別子＝タグ名」であるのに対し、本発明では、「タグの識別子＝タグ名＋書式属性名と値（複数可）」となる。つまり、従来、タグの識別子をタグ名にしていたものを、本発明では、タグ名と書式属性名とその値の組合せで表現するということである。
【００２１】
これにより、指定部分の部分木の根に対応するタグと同一のタグの文書ブロックが、指定文と同じ階層に挿入されても、タグの書式属性が異なれば、開始、終了箇所に依存しない方法で、指定部分の抽出精度を低下させないことが可能となる。
【００２２】
さらに、本発明は、「部分木の識別子＝（タグの識別子＋数値索引）←（文書全体の根から部分木の根まで入れ子状に連鎖）」となっている。
【００２３】
これにより、指定した部分木の根に対応するタグと書式属性の組合せが、特定対象文書中に複数存在する場合でも、指定部分を一意に特定することが可能となる。
【００２４】
また、従来は、文書全体の中の絶対的な位置をもとに指定した部分を特定するのに対し、本発明では、指定部分とその周辺部分と相対的な位置関係をもとに指定した部分を特定する。これにより、指定部分の前方にタグの閉じ忘れが存在した場合でも、指定部分の抽出精度を低下させないことが可能となる。
【００２５】
【発明の実施の形態】
以下、図面と共に本発明の実施の形態について説明する。
【００２６】
本発明は、構造化文書の任意の部分を事前に指定し、更新された文書から指定部分を特定するために、文書を木構造に変換し、部分文書を参照するために対応する部分木の識別子を生成する際に、部分木の根に対応するタグ名、タグの書式属性名、書式属性の値の組合せをタグの識別子とし、これを部分木の識別子とし、タグの識別子に書式属性が複数存在する場合は、書式属性名の順番で書式属性を整列させてタグの識別子を正規化し、木構造に変換された文書に存在する部分木の識別子のリストから事前に取得した部分木の識別子と同一の部分木の識別子を持つ部分木を、指定部分として特定する。
【００２７】
さらに、指定した部分木の根に対応するタグと書式属性の組合せが、図２のように、特定対象文書中に複数存在刷る場合に、特に、タグの識別子と木構造の内の同一階層におけるタグの識別子の順番を示す数値索引の組を生成し、タグ識別子と数値索引の組を、木構造の根から指定した部分木の根まで入れ子状に連鎖させた文字列を、当該部分木の識別子とする。
【００２８】
また、木構造に変換された文書に存在する部分木の識別子のリストから、事前に取得した部分木の識別子と同一の識別子を持つ部分木を特定する際に、特に、部分木の識別子の照合を、部分木の根に対応するタグの識別子だけで照合を行い、照合された部分木の候補が複数ある場合に、当該タグ識別子の数値索引の照合を行うことで、候補を絞り、タグ識別子の数値索引により候補を絞っても、複数の候補が残っている場合に、親のタグに遡って再帰的に照合を繰り返し、照合を取った結果、候補の部分木が一つしかない場合に、この候補を指定した部分木として特定する。
【００２９】
【実施例】
以下、図面と共に本発明の実施例を説明する。
【００３０】
［第１の実施例］
図３は、本発明の第１の実施例の構造化文書から情報抽出するシステムの構成を示す。
【００３１】
同図に示すシステムは、指定部分の部分木の根に対応するタグと同一のタグの文書ブロックが指定部分と同じ階層に挿入されても、タグの書式属性が異なれば、開始・終了箇所に依存しない方法で、指定部分の抽出精度を低下させない。
【００３２】
同図に示すシステムは、ユーザから構造化文書の任意部分の指定を受け付ける部分指定部１、指定した部分の情報を記憶する部分情報記憶部２、タグとその書式属性で木構造の部分木を識別する文書構造解析部３、部分特定要求に対して、対応する部分文書を返す部分特定部４から構成される。
【００３３】
部分指定部１は、文書取得部１１、部分指定部１２、文書構造化部１３から構成される。
【００３４】
部分取得部１１は、部分指摘部１２から文書の識別子であるＵＲＬによる文書取得要求を受けると、インターネットから該当する文書を取得し、返す。
【００３５】
部分指定部１２は、文書取得部１１に任意のＵＲＬと共に、文書取得要求を出し、対応する文書を取得する。次に、取得した文書を構造化するよう文書構造化部１３に要求し、木構造に変換された文書を取得する。さらに、図４に示すように、取得した文書の部分を、容易に指定できるようなユーザインタフェースを提供する。指定部分の領域の座標等から対応する部分木の識別子を取得し、ＵＲＬと共に、図５に示すように部分情報記憶部２に記録する。
【００３６】
文書構造化部１３は、部分指定部１２から渡された文書を構造化するように文書構造解析部３に依頼する。そして、図６に示すように、木構造に変換された文書を、木構造の親子関係を表現したデータ構造として受信する。例えば、木構造を構成するタグあるいは、テキストの要素を、要素ＩＤ、ラベル、子ノードのリスト、部分木識別子で表示し、これらのリストを取得する。
【００３７】
部分情報記憶部２は、図７に示すように、部分指摘部１２からＵＲＬと部分木識別子を取得し、このペアが識別可能なＩＤを部分文書ＩＤとして割り当て、記憶し、部分文書ＩＤを返す。
【００３８】
文書構造解析部３は、木構造変換部３１、部分木識別子生成部３２から構成される。
【００３９】
木構造変換部３１は、文書構造化部１３あるいは、文書構造化部４３より構造化文書と共に文書構造化要求を受けると、文書中に存在するタグとテキストを要素として木構造に文書を変換し、部分木識別子生成部３２に渡す。
【００４０】
部分木識別子生成部３２は、木構造変換部３１で木構造に変換された文書を構成するタグに対応するタグ識別子を、タグ名と書式属性名と書式属性値の組合せにより生成する。図６の１番目のtable タグの例では、table タグと、書式属性と値である「border="0" cellpadding="1"」を組み合わせたもの(table＿border=0&cellpadding=1) をタグ識別子とする。また、書式属性が複数ある場合は、書式属性名の順番で書式属性を整列させてタグの識別子を正規化する。このタグ識別子を、当該タグを根とする部分木の識別子とし、木構造の要素に対応付ける。こうして部分木の識別子が付与された図６のような木構造のデータを、文書構造化部１３あるいは、文書構造部４３へ返す。
【００４１】
部分特定部４は、文書取得部４１、部分木識別子特定部４２、文書構造化部４３からなる。
【００４２】
文書取得部４１は、部分木識別子特定部４２から文書の識別子であるＵＲＬによる文書取得要求を受けると、インターネットから該当する文書を取得し、返す。
【００４３】
部分木識別子特定部４２は、ユーザから部分文書ＩＤと共に、部分取得要求を受け付け、部分情報記憶部２に部分文書ＩＤを渡し、対応するＵＲＬと部分木識別子を取得する。文書取得部４１にそのＵＲＬを渡し、該当する文書を取得する。取得した文書を構造化するよう文書構造化部４３に要求し、木構造に変換された図８のような要素リストを取得する。取得した要素リストから部分木識別子に該当するタグを取得し、そのタグの配下に存在する部分木の範囲の文書を、部分文書としてユーザに返す。
【００４４】
文書構造化部４３は、部分木識別子特定部４２から渡された文書を構造化するように文書構造解析部３に依頼する。そして、木構造に変換された文書を、図９に示すような木構造の親子関係を表現したデータ構造として受信する。例えば、木構造を構成するタグあるいはテキストの要素を、要素ＩＤ、ラベル、子ノードのリスト、部分木識別子で表現し、これらのリストを取得する。
【００４５】
次に、上記の構成における動作を説明する。
【００４６】
図１０は、本発明の第１の実施例の構造化文書からの情報抽出方法のフローチャートである。
【００４７】
以下の動作では、Ａ：部分指定、Ｂ：部分特定、Ｍ：文書構造化の３つから構成される。以下の各ステップには、これらのＡ，Ｂ，Ｍを付与して説明する。
【００４８】
まず、Ａ：部分指定のフローについて説明する。
【００４９】
ステップ−Ａ１０）ユーザのＵＲＬの指示に従い、部分指定部１２が文書取得部１１にＵＲＬに対応する文書をインターネットから取得する。部分指定部１２が取得した文書を文書構造化部１３に渡し、文書の構造化要求を出し、Ｍ１０に移行する。
【００５０】
ステップ−Ｍ１０）木構造変換部３１が、文書構造化部１３より構造化文書を受け取り、文書中に存在するタグとテキストを要素として木構造に文書を変換し、部分木識別子生成部３２に渡し、Ｍ２０に移行する。
【００５１】
ステップ−Ｍ２０）部分木識別子生成部３２が、木構造変換部３１で木構造に変換された文書を構成するタグに対応するタグ識別子を、タグ名と書式属性名と書式属性の値の組合せにより生成する。図６の例では、table タグと、その書式属性とその値である「border="0",cellpadding="1"」を組み合わせたもの(table＿border=0&cellpadding=1) をタグ識別子とする。また、書式属性が複数ある場合は、書式属性名で順番で書式属性を整列させてタグの識別子を正規化する。このタグ識別子を、部分木識別子とし、木構造の要素に対応付ける。こうして部分木識別子が付与された図５のような木構造データを文書構造化部１３に返す。
【００５２】
ステップ−Ａ２０）部分指定部１２が、文書の部分を、図４に示すような容易に指定できるようなユーザインタフェースら、ユーザが指定したい部分を取得し、ステップ−Ａ３０に移行する。
【００５３】
ステップ−Ａ３０）部分指定部１２が、指定部分に対応する部分木識別子を図５に示す指定部分の領域の座標等から取得する。取得した部分木識別子と、文書に対応するＵＲＬを、部分情報記憶部２に追加し、この対を識別する部分文書ＩＤを取得する。
【００５４】
次に、ステップ−Ｂ：部分特定のフローについて説明する。
【００５５】
ステップ−Ｂ１０）部分木識別子特定部４２が、ユーザから部分文書ＩＤと共に、部分取得要求を受け付ける。部分情報記憶部２に部分文書ＩＤを渡し、対応するＵＲＬと部分木識別子を取得し、ステップ−Ｂ２０に移行する。
【００５６】
ステップ−Ｂ２０）部分木識別子特定部４２が、取得したＵＲＬに対応する文書を、文書取得部４１を介して取得する。部分木識別子特定部４２が、取得した文書を文書構造化部４３に渡し、文書の構造化要求を発行し、Ｍ１０に移行する。
【００５７】
ステップ−Ｍ１０）木構造変換部３１が、文書構造化部４３より構造化文書を受け取り、文書中に存在するタグとテキストによる木構造に文書を変換し、部分木識別子生成部３２に渡し、Ｍ２０に移行する。
【００５８】
ステップ−Ｍ２０）部分木識別子生成部３２が、木構造変換部３１で木構造に変換された文書を構成するタグに対応するタグ識別子を、タグ名と書式属性名と書式属性の値の組合せにより生成する。図６の例では、table タグと、その書式属性とその値である「border="0"cellpadding="1" 」を組み合わせたもの(table＿border=0&cellpadding=1) をタグ識別子とする。また、書式属性が複数ある場合は、書式属性名で順番で書式属性を整列させてタブの識別子を正規化する。このタグ識別子を、部分木識別子とし、木構造の要素に対応付ける。こうして、部分木識別子が付与された図６のような木構造のデータを、文書構造化部４３に返す。その後ステップ−Ｂ３０へ移行する。
【００５９】
ステップ−Ｂ３０）部分木識別子特定部４２が、取得した木構造に変換された図８のような要素リストから、取得した部分木識別子に該当するタグを探し、該当する部分木識別子が存在しなかったらそのまま終了し、存在したらステップ−Ｂ４０に移行する。
【００６０】
ステップ−Ｂ４０）部分識別子特定部４２が、取得した部分識別子に対応する部分木の範囲の文書を、部分文書としてユーザに返す。
【００６１】
［第２の実施例］
図１１は、本発明の第２の実施例の構造化文書からの情報を抽出するシステムの構成図である。
【００６２】
同図に示すシステムは、指定した部分木の根に対応するタグと書式属性の組合せが、特定対象文書中に複数存在する場合でも、指定部分を一意に特定することが可能な構成を示す。
【００６３】
文書構造解析部３の、部分木識別子生成部３２’以外は、前述の第１の実施例と同様であるので、説明を省略する。
【００６４】
部分木識別子生成部３２’は、木構造変換部３１で木構造に変換された文書を構成するタグに対応するタグ識別子を、タグ名と書式属性名と書式属性の値の組合せにより生成する。図６の１番目のtable タグの例では、table タグと、書式属性と値である「border="0" cellpadding="1"」を組み合わせたもの(table＿border=0&ceppladding=1) をタグ識別子とする。また、書式属性が複数ある場合は、書式属性名の順番で書式属性を整列させてタグの識別子を正規化する。
このタグの識別子と木構造内の同一階層におけるタグの識別子の順番を示す数値索引の組を生成し、この組を、木構造の根から指定した部分木の根まで入れ子状に連鎖させた文字列を、図１２に示すような当該部分木識別子とし、木構造の要素に対応付ける。こうして、部分木の識別子が付与された図１３のような木構造データを、文書構造化部１３、あるいは、文書構造化部４３に返す。
【００６５】
図１４は、本発明の第２の実施例の構造化文書からの情報抽出方法のフローチャートである。
【００６６】
以下において、Ｍ２０’以外は、前述の第１の実施例と同様であるため、説明を省略する。
【００６７】
ステップ−Ｍ２０’）部分木識別子生成部３２’が、木構造変換部３１で木構造に変換された文書を構成するタグに対応するタグ識別子を、タグ名と書式属性名と書式属性の値の組合せにより生成する。図６の１番目のtable タグの例では、table タグと、書式属性と値である「border"0"cellpadding="1"」を組み合わせたもの(table＿border=0&cellpadding=1) をタグ識別子とする。また、書式属性が複数ある場合は、書式属性名の順番で書式属性を整列させてタグの識別子を正規化し、Ｍ３０’に移行する。
【００６８】
ステップ−Ｍ３０’）部分木識別子生成部３２’が生成したタグの識別子と木構造内の同一階層におけるタグの識別子の順番を示す数値索引の組を生成し、この組を、木構造の根から指定した部分木の根まで入れ子状に連鎖させた文字列を、図１２に示すような当該部分木の識別子とし、木構造の要素に対応付ける。こうして部分木の識別子が付与された図１３のような木構造のデータを、文書構造化部１３あるいは、文書構造化部４３へ返し、ステップ−Ａ２０あるは、ステップ−Ｂ３０に移行する。
【００６９】
［第３の実施例］
図１５は、本発明の第３の実施例の構造化文書からの情報を抽出するシステムの構成図である。
【００７０】
同図に示すシステムは、指定部分の前方にタグの閉じ忘れが存在した場合でも、指定部分の抽出精度を低下させないことが可能な構成を示す。
【００７１】
部分木識別子特定部４２’以外は、前述の第１の実施例と同様であるため、説明を省略する。
【００７２】
部分木識別子特定部４２’は、ユーザから部分文書ＩＤと共に、部分取得要求を受け付け、部分情報記憶部２に部分文書ＩＤを渡し、対応するＵＲＬと部分木識別子を取得する。文書取得部４１にそのＵＲＬを渡し、該当する文書を取得する。取得した文書を構造化するよう文書構造化部４３に要求し、木構造に変換された図１３のような要素リストを取得する。
【００７３】
取得した要素の部分木識別子のリストから、部分情報記憶部２から取得した部分木識別子を特定するために、識別子の末端のタグ識別子だけで照合を行う。例えば、「doc.table ＿border=1&cellpadding=1[0].table ＿border=0&cellpadding=1[1] 」という部分木識別子の末端のタグ識別子とは、最も右端の「tableborder=0&cellpadding=1 」に相当する。照合された部分木の候補が複数ある場合、当該タグ識別子の数値索引の照合をとることで候補を絞る。
【００７４】
また、タグ識別子の数値索引により候補を絞っても、複数の候補が残っている場合に、親のタグにさかのぼって再帰的に照合を繰り返す。その結果、候補の部分木が一つしかない場合に、この部分木を指定した部分木として特定する。特定した部分木識別子に対応する部分木の範囲の文書を、部分文書としてユーザに返す。
【００７５】
図１６は、本発明の第３の実施例の構造化文書からの情報抽出方法のフローチャートである。ステップ−Ｂ３０’からステップ−Ｂ９０’以外は、前述の第１の実施例と同様であるため、説明を省略する。
【００７６】
ステップ−Ｂ３０’）部分木識別子特定部４２が、取得した木構造に変換された図１３のような要素リストから、部分情報記憶部２から取得した部分木識別子を特定するために、識別子の末端のタグ識別子を、照合対象として設定する。例えば、「doc.table ＿border=1&cellpadding=1[0].table ＿boder=0&cellpadding=1[1]」という部分木識別子の末端のタグ識別子とは、最も右端の「table ＿border=0&cellpadding=1」に相当する。設定後、ステップ−Ｂ４０’に移行する。
ステップ−Ｂ４０’）現在照合対象となっているタグ識別子同士の照合を行い、照合された部分木の候補が複数ある場合に、ステップ−Ｂ５０’に移行し、一つに決まったらステップ−Ｂ６０’へ進み、候補がない場合は終了する。
【００７７】
ステップ−Ｂ５０’）照合された部分木の候補が複数ある場合に、当該タグ識別子の数値索引の照合を行うことで、候補を絞る。さらに照合された候補が複数ある場合に、ステップ−Ｂ８０’に移行し、一つに決まったら、ステップ−Ｂ６０’に移行し、候補がない場合には終了する。
【００７８】
ステップ−Ｂ６０’）照合された部分木の候補が一つにきまったらその部分木を指定した部分木として特定し、ステップ−Ｂ７０’へ移行する。
【００７９】
ステップ−Ｂ７０’）部分木識別子特定部４２が、取得した部分識別子に対応する部分木の範囲の文書を、部分文書としてユーザに返す。
【００８０】
ステップ−Ｂ８０’）タグ識別子の数値索引により候補を絞っても、複数の候補が残っている場合に、照合対象を上位にずらす。「doc.table ＿border=1&cellpadding=1[0]. table＿border=0&cellpadding=1[1] 」において、まず、末端のタグ識別子「table ＿border=0&cellpadding=1」を評価したら、その次に、その親のタグ識別子である「table ＿border=1&cellpadding=1[0] 」を照合対象とする。その後、ステップ−Ｂ９０’に移行する。
【００８１】
ステップ−Ｂ９０’）ステップ−Ｂ８０’で再帰的に照合対象を上位にずらした結果、最上位のタグを照合対象とした後に、もうこれ以上照合する対象が存在しない場合に終了し、そうでない場合は、ステップ−Ｂ４０’に戻る。
【００８２】
なお、本発明は、上記の各実施例の方法をプログラムとして構築し、情報抽出装置として利用されるコンピュータにインストールする、または、ネットワークを介して流通させることも可能である。
【００８３】
また、構築されたプログラムを情報抽出装置として利用されるコンピュータに接続されるハードディスク装置や、フレキシブルディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納しておき、本発明を実施する際にインストールすることも可能である。
【００８４】
なお、本発明は、上記の実施例に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【００８５】
【発明の効果】
上述のように、本発明によれば、構造化文書の任意の部分を事前に指定し、更新された文書から指定部分を特定するために、文書を木構造に変換し、部分文書を参照するために対応する部分木の識別子を生成する段階において、特に、部分木の根に対応するタグ名、タグの書式属性名、書式属性の値の組合せをタグの識別子とし、これを部分木の識別子とし、タグの識別子に書式属性が複数存在する場合は、書式属性名の順番で書式属性を整列させてタグの識別子を正規化し、木構造に変換された文書に存在する部分木の識別子のリストから、事前に取得した部分木の識別子と同一の部分木の識別子を持つ部分木を、指定部分として特定する。これにより、指定部分の部分木の根に対応するタグと同一のタグの文書ブロックが、指定部分と同じ階層に挿入されても、タグの書式属性が異なれば、開始、終了箇所に依存しない方法で、指定部分の抽出精度を低下させないことが可能となる。
【００８６】
また、指定した部分木の根に対応するタグと書式属性の組合せが、特定対象文書中に複数存在する場合に、特に、タグの識別子と木構造内の同一階層におけるタグの識別子の順番を示す数値索引の組を生成し、タグ識別子と数値索引の組を、木構造の根から指定した部分木の根まで入れ子状に連鎖させた文字列を、当該部分木の識別子とすることにより、指定した部分木の根に対応するタグと書式属性の組合せが、特定対象文書中に複数存在する場合でも、指定部分を一意に特定することが可能となる。
【００８７】
さらに、木構造に変換された文書に存在する部分木の識別子のリストから、事前に取得した部分木の識別子と同一の識別子を持つ部分木を特定する段階において、特に、部分木の識別子の照合を、部分木の根に対応するタグの識別子だけで照合を行い、照合された部分木の候補が複数ある場合に、当該タグ識別子の数値索引の照合を行うことで候補を絞り、タグ識別子の数値索引を絞っても、複数の候補が残っている場合に、親のタグに遡って再帰的に照合を繰り返し、照合を取った結果、候補の部分木が一つしかない場合に、この候補を指定した部分木として特定することにより、指定部分の前方にタグの閉じ忘れが存在した場合でも、指定部分の抽出精度を低下させないことが可能となる。
【図面の簡単な説明】
【図１】本発明の原理を説明するための図である。
【図２】本発明の一実施の形態における同一タグで同一書式属性を持つものが複数存在する場合を説明するための図である。
【図３】本発明の第１の実施例の構造化文書から情報を抽出するシステムの構成図である。
【図４】本発明の第１の実施例の文書指定のための提供画面の例である。
【図５】本発明の第１の実施例の部分情報記憶部に記録される情報の例である。
【図６】本発明の第１の実施例の文書構造解析で変換された木構造データの例である。
【図７】本発明の第１の実施例の部分情報記憶部の内容を示す図である。
【図８】本発明の第１の実施例の要素リストの例である。
【図９】本発明の第１の実施例における変換された木データ構造の例である。
【図１０】本発明の第１の実施例の構造化文書からの情報抽出方法のフローチャートである。
【図１１】本発明の第２の実施例の構造化文書からの情報を抽出するシステムの構成図である。
【図１２】本発明の第２の実施例の指定部分の部分木識別子の生成を示す図である。
【図１３】本発明の第２の実施例の木構造データの生成を示す図である。
【図１４】本発明の第２の実施例の構造化文書からの情報抽出方法のフローチャートである。
【図１５】本発明の第３の実施例の構造化文書からの情報を抽出するシステム構成図である。
【図１６】本発明の第３の実施例の構造化文書からの情報抽出方法のフローチャートである。
【図１７】従来の技術を説明するための図である。
【符号の説明】
１  部分指定部
２  部分情報記憶部
３  文書構造解析部
４  部分特定部
１１  文書取得部
１２  部分指定部
１３  文書構造化部
３１  木構造変換部
３２，３２’  部分木識別子生成部
４１  文書取得部
４２，４２’  部分木識別子特定部
４３  文書構造化部
【図１】
0003937944.tif 000002
【図２】
0003937944.tif 000003
【図３】
0003937944.tif 000004
【図４】
0003937944.tif 000005
【図５】
0003937944.tif 000006
【図６】
0003937944.tif 000007
【図７】
0003937944.tif 000008
【図８】
0003937944.tif 000009
【図９】
0003937944.tif 000010
【図１０】
0003937944.tif 000011
【図１１】
0003937944.tif 000012
【図１２】
0003937944.tif 000013
【図１３】
0003937944.tif 000014
【図１４】
0003937944.tif 000015
【図１５】
0003937944.tif 000016
【図１６】
0003937944.tif 000017
【図１７】
0003937944.tif 000018