(57)【要約】【課題】構造化文書の構造及び繰り返しパターンが比較的複雑で、情報ブロックが完全には互いに整合していなくても、構造化文書中の情報ブロックの識別と分割とを正確に実行することを課題する。【解決手段】構造化文書の分割装置は、構造化文書を受け取って、当該構造化文書の文書構造情報を当該構造化文書に基づいて生成する文書構造情報生成ユニット１と、文書構造情報生成ユニット１によって生成された文書構造情報に基づいて、情報ブロックの範囲を判定する情報ブロック範囲判定ユニット２と、文書構造情報生成ユニット１によって生成された文書構造情報と、情報ブロック範囲判定ユニット２によって判定された範囲とに基づいて、分割基準を生成する分割基準生成ユニット３と、この分割基準生成ユニット３によって生成された分割基準に基づいて、構造化文書を分割してその結果を出力する分割ユニット４とを備える。【選択図】図１
2005025763.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータを、
前記構造化文書を受け取って、当該構造化文書の文書構造情報を当該構造化文書に基づいて生成する文書構造情報生成手段と、
前記文書構造情報生成手段によって生成された前記文書構造情報に基づいて、前記情報ブロックの範囲を判定する情報ブロック範囲判定手段と、
前記文書構造情報生成手段によって生成された前記文書構造情報と、前記情報ブロック範囲判定手段によって判定された前記範囲とに基づいて、分割基準を生成する分割基準生成手段と、
前記分割基準生成手段によって生成された前記分割基準に基づいて、前記構造化文書を分割してその結果を出力する分割手段と、
として機能させるための構造化文書分割プログラム。
【請求項２】
前記コンピュータを、前記文書構造情報生成手段として機能させた際に生成された前記文書構造情報は文書構造ツリーであり、
幅優先アルゴリズムを用いて前記文書構造ツリーを探索することにより、最大の有効子ノードを有し、かつ、有効テキスト量と文書全体の有効テキスト量との比率が所定の閾値より大きいノードを発見し、
前記ノードが対応する範囲が、全ての情報ブロックを含む最小の範囲であり、前記ノードをルートとするサブツリーが、全ての情報ブロックを含む最小のサブツリーであること、
を特徴とする請求項１に記載の構造化文書分割プログラム。
【請求項３】
前記コンピュータを、前記文書構造情報生成手段として機能させた際に生成された前記文書構造情報は文書構造ツリーであり、
前記分割基準生成手段は、前記情報ブロックが置かれているサブツリーのルートノードの子ノードと孫ノードとのタグシーケンスを利用して、最適繰り返しパターンを計算すること、
を特徴とする請求項１又は２に記載の構造化文書分割プログラム。
【請求項４】
前記分割基準生成手段は、最初に、前記ルートノードの子ノードのシーケンスへの第一の繰り返しパターンを計算し、次に、ルートノードの子ノードと孫ノードとのシーケンスへの第二の繰り返しパターンを計算し、最後に、最適繰り返しパターンを前記第一の繰り返しパターンと前記第二の繰り返しパターンとから選択することにより、最適繰り返しパターンを計算すること、
を特徴とする請求項３に記載の構造化文書分割プログラム。
【請求項５】
構造化文書に含まれる情報ブロックを分割する分割装置であって、
前記構造化文書を受け取って、当該構造化文書の文書構造情報を当該構造化文書に基づいて生成する文書構造情報生成手段と、
前記文書構造情報生成手段によって生成された前記文書構造情報に基づいて、前記情報ブロックの範囲を判定する情報ブロック範囲判定手段と、
前記文書構造情報生成手段によって生成された前記文書構造情報と、前記情報ブロック範囲判定手段によって判定された前記範囲とに基づいて、分割基準を生成する分割基準生成手段と、
前記分割基準生成手段によって生成された前記分割基準に基づいて、前記構造化文書を分割してその結果を出力する分割手段と、
を備えることを特徴とする構造化文書の分割装置。
【請求項６】
構造化文書に含まれる情報ブロックを分割する分割方法であって、
前記構造化文書を受け取って、当該構造化文書の文書構造情報を当該構造化文書に基づいて生成する文書構造情報生成工程と、
前記文書構造情報生成工程において生成された前記文書構造情報に基づいて、前記情報ブロックの範囲を判定する情報ブロック範囲判定工程と、
前記文書構造情報生成工程において生成された前記文書構造情報と、前記情報ブロック範囲判定工程において判定された前記範囲とに基づいて、分割基準を生成する分割基準生成工程と、
前記分割基準生成工程において生成された前記分割基準に基づいて、前記構造化文書を分割してその結果を出力する分割工程と、
を含むことを特徴とする構造化文書の分割方法。
【請求項７】
文書構造情報生成工程において生成された前記文書構造情報は文書構造ツリーであり、
幅優先アルゴリズムを用いて前記文書構造ツリーを探索することにより、最大の有効子ノードを有し、かつ、有効テキスト量と文書全体の有効テキスト量との比率が所定の閾値より大きいノードを発見し、
前記ノードが対応する範囲が、全ての前記情報ブロックを含む最小の範囲であり、前記ノードをルートとするサブツリーが、全ての前記情報ブロックを含む最小のサブツリーであること、
を特徴とする請求項６に記載の構造化文書の分割方法。
【請求項８】
前記文書構造情報生成工程において生成された前記文書構造情報は文書構造ツリーであり、
前記分割基準生成工程において、前記情報ブロックが置かれているサブツリーのルートノードの子ノードと孫ノードとのタグシーケンスを利用して最適繰り返しパターンを計算すること、
を特徴とする請求項６又は７に記載の構造化文書の分割方法。
【請求項９】
前記分割基準生成工程において、最初に、前記ルートノードの子ノードのシーケンスへの第一の繰り返しパターンを計算し、次に、ルートノードの子ノードと孫ノードとのシーケンスへの第二の繰り返しパターンを計算し、最後に、最適繰り返しパターンを前記第一の繰り返しパターンと前記第二の繰り返しパターンとから選択することにより、最適繰り返しパターンを計算すること、
を特徴とする請求項８に記載の構造化文書の分割方法。
【請求項１０】
前記分割基準生成工程において、
オリジナルのタグシーケンスの第一の繰り返しシーケンスを計算し、
前記第一の繰り返しシーケンスに基づいて、当該第一の繰り返しシーケンスの指定された記号をタグシーケンスに代入して、オリジナルのタグシーケンスの修正済みシーケンスを取得し、
前記修正済みシーケンスの第二の繰り返しシーケンスを計算し、さらに、
前記第二の繰り返しシーケンスが前記第一の繰り返しシーケンスを含むかどうかに基づいて、最終的な繰り返しパターンを判定することにより、
前記第一の繰り返しパターンと前記第二の繰り返しパターンとから少なくともひとつの前記分割基準を計算すること、
を特徴とする請求項９に記載の構造化文書の分割方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、構造化された文書に含まれる情報ブロックを自動的に分割するための分割プログラム、分割装置、及び分割方法に関する。
【背景技術】
【０００２】
ネットワーク技術が急速に発達するにつれて、インターネットなどのネットワークからより多くの情報を得ることが可能となってきている。このように得た情報を効果的に利用するためには、情報の抽出、分類、あるいは、記憶といった各種の情報処理を行うことが必要である。
【０００３】
ここで、インターネット上などの情報は、ほとんどの場合には構造化文書という形態で示されるが、直接的にアクセス可能な文書は、所望される実際のコンテンツ情報を含んでいるだけではなく、文書構造を示す多くの情報を含んでいる。これら構造化文書中には、通常、形式又は形態が同一又は類似の単位が存在するが、これら単位はその各々が意味を持つ実体、すなわち、本発明で定義されるような情報ブロックである。
【０００４】
このような情報ブロックは、それぞれ意味を持つという点では互いに独立しているため、これら情報ブロックに対する処理を行う前には、これらの情報ブロックを、構造化文書中で識別して分割しておく必要がある。例えば、情報検索処理を行うためには、情報ブロック毎にインデックスを作成するなどの処理を行う前に、情報ブロックを構造化文書中で識別して分割しておく必要がある。
【０００５】
ここで、情報ブロックはその構造が互いに類似しているため、最初に、情報に対するラベル付けと情報の抽出とをある特定の情報ブロックに対して行い、次に、当該情報ブロックに類似する他の情報ブロックに対する情報抽出を行う。したがって、これらの情報ブロックを、構造化文書から識別して分割する技術が必要とされる。
【０００６】
なお、本明細書で言及される「構造化文書」とは、例えば、文書構造を示す情報を含むＨＴＭＬ（HyperText Markup Language）やＸＭＬ（Extensible Markup Language）などの文書を指し、また、「情報ブロック」とは、他の情報ブロックから独立している情報単位（セル）を意味する。
【０００７】
例えば、自動車広告リストを含んだＨＴＭＬファイルの場合、この広告の各情報が情報ブロックである。あるいは、そのＢＢＳフォーラム上には、通常、トピックリストがあり、各トピックが情報ブロックを構成している。又は、検索エンジンによる検索結果を示すページ上では、各検索結果が情報ブロックとなっている。
【０００８】
このような構造化文書の情報ブロックを自動的に識別して分割することは、情報を抽出して検索するためには非常に重要である。例えば、ＨＴＭＬファイルにおいて、Ｗｅｂページ上の情報ブロックをどのように自動的に分割するかは、Ｗｅｂページの情報を抽出するために非常に重要である。
【０００９】
このように構造化文書から情報ブロックを識別して分割する方法は、その自動化の程度に応じて、具体的に次の三つのカテゴリに分割することが可能である。すなわち、手動識別分割方法と、半自動的識別分割方法（例えば、最初に、情報ブロックを観察してその中の分割タグを半自動的に識別し、次に、これらの分割タグを用いて分割を行うためのプログラムを記述する方法）と、自動的識別分割方法とである。
【００１０】
構造化文書の情報ブロックを自動的に識別して分割する方法として、従来から、D. W. Embley等は、ＨＴＭＬ文書の中で情報ブロックを自動的に分割する方法を提案している（例えば、非特許文献１参照）。この方法では、最初に、ＨＴＭＬファイルのタグに基づいてタグ解析ツリーを設定し、次に、情報ブロックを含んでいるサブツリーを判定し、最後に、自己学習アルゴリズムを用いて、情報ブロックの分割タグ候補中から分割タグを選択する。
【００１１】
また、構造化文書の情報ブロックを自動的に識別して分割する別の方法として、Chia-hui changは、以下のような方法を提案している（例えば、非特許文献２参照）。すなわち、ＨＴＭＬ文書をキャラクタストリームとして受け取り、パトリシアツリー（ＰＡＴ:Patricia tree）アルゴリズムを用いて繰り返しタグシーケンスを計算し、各繰り返しタグシーケンスの全てのサブツリーのコンテンツを情報ブロックとする。
【００１２】
【非特許文献１】D. W. Embley, Y. S. Jiang, 及び, Y. -K. Ng.、Ｗｅｂ文書中における記録境界の認識（Record-boundary discovery in web documents)、SIGMOD'99, 1999年
【非特許文献２】C. H. Chang, 及び, S. C. Lui.、パターン発見に基づいた情報抽出（IEPAD: Information Extraction based on Pattern Discovery）、the Proceedings of the tenth International Conference on World Wide Web、第６８１頁から第６８８頁、２００１年５月２日から６日、香港
【発明の開示】
【発明が解決しようとする課題】
【００１３】
しかしながら、上述のD. W. Embley等による方法では、情報ブロックのサブツリーの判定に際して、選択性タグ（例えば、「ｏｐｔｉｏｎ」や「ｄｉｖ」）を考慮していないため、このような選択性タグが存在する場合にはエラーになる可能性がある。さらに、分割タグが選択される際に、より深いレベルの情報が考慮されていないことも、エラーの原因になり得る。
【００１４】
また、上述のChia-hui changによる方法では、ＨＴＭＬ文書の構造的特徴を考慮していないため、情報ブロックが互いに整合していないとエラーになる可能性がある。
【００１５】
このような問題を解決するために、本発明は、構造化文書中の選択性タグに対する処理を可能とし、深いレベルの情報と構造化文書の構造的特徴とを考慮して識別と分割を実行し、たとえ構造化文書の構造と繰り返しパターンとが比較的複雑で、また、情報ブロックが完全には互いに整合していなくても、構造化文書中の情報ブロックに対して正確な識別と分割を実行する、構造化文書の分割プログラム、分割方法及び分割装置を提供する。
【課題を解決するための手段】
【００１６】
本発明の目的を達成するために、請求項１に記載の構造化文書プログラムは、コンピュータを、前記構造化文書を受け取って、当該構造化文書の文書構造情報を当該構造化文書に基づいて生成する文書構造情報生成ユニット（１）と、前記文書構造情報生成ユニット（１）によって生成された前記文書構造情報に基づいて、前記情報ブロックの範囲を判定する情報ブロック範囲判定ユニット（２）と、前記文書構造情報生成ユニット（１）によって生成された前記文書構造情報と、前記情報ブロック範囲判定ユニット（２）によって判定された前記範囲とに基づいて、分割基準を生成する分割基準生成ユニット（３）と、前記分割基準生成ユニット（３）によって生成された前記分割基準に基づいて、前記構造化文書を分割してその結果を出力する分割ユニット（４）として機能させるためのプログラムである。
【００１７】
この請求項１の発明によれば、構造化文書の文書構造情報が当該構造化文書に基づいて生成され、この文書構造情報に基づいて、情報ブロックの範囲が判定される。そして、これら文書構造情報と範囲とに基づいて分割基準が生成され、この分割基準に基づいて構造化文書が分割されて、その結果が出力される。
【００１８】
また、請求項２に記載の構造化文書分割プログラムは、請求項１に記載の構造化文書分割プログラムにおいて、コンピュータを、文書構造情報生成手段として機能させた際に生成された前記文書構造情報は文書構造ツリーであり、幅優先アルゴリズムを用いて前記文書構造ツリーを探索することにより、最大の有効子ノードを有し、かつ、有効テキスト量と文書全体の有効テキスト量との比率が所定の閾値より大きいノードを発見し、前記ノードが対応する範囲が、全ての情報ブロックを含む最小の範囲であり、前記ノードをルートとするサブツリーが、全ての情報ブロックを含む最小のサブツリーであることを特徴とする。
【００１９】
この請求項２の発明によれば、有効子ノード番号及び有効テキスト量と文書全体の有効テキスト量との比率を用いて、全ての前記情報ブロックを含む最小のサブツリーのルートノードが判定される。
【００２０】
また、請求項３に記載の構造化文書分割プログラムは、請求項１又は２に記載の構造化文書分割プログラムにおいて、コンピュータを、前記文書構造情報生成手段として機能させた際に生成された前記文書構造情報は文書構造ツリーであり、前記分割基準生成手段は、前記情報ブロックが置かれているサブツリーのルートノードの子ノードと孫ノードとのタグシーケンスを利用して、最適繰り返しパターンを計算することを特徴とする。
【００２１】
この請求項３の発明によれば、情報ブロックが置かれているサブツリーのルートノードの子ノードに関する情報が利用されるだけではなく、サブツリーのルートノードの孫ノードに関するタグシーケンスが、最適繰り返しパターンの計算に利用される。
【００２２】
また、請求項４に記載の構造化文書分割プログラムは、請求項３に記載の構造化文書分割プログラムにおいて、前記分割基準生成手段は、最初に、前記ルートノードの子ノードのシーケンスへの第一の繰り返しパターンを計算し、次に、ルートノードの子ノードと孫ノードとのシーケンスへの第二の繰り返しパターンを計算し、最後に、最適繰り返しパターンを前記第一の繰り返しパターンと前記第二の繰り返しパターンとから選択することにより、最適繰り返しパターンを計算することを特徴とする。
【００２３】
この請求項４の発明によれば、ルートノードの子ノードのシーケンスへの第一の繰り返しパターンが計算され、さらに、ルートノードの子ノードと孫ノードとのシーケンスへの第二の繰り返しパターンが計算され、これら第一の繰り返しパターンと第二の繰り返しパターンとから最適繰り返しパターンが選択される。
【００２４】
また、請求項５に記載の分割装置は、構造化文書に含まれる情報ブロックを分割する分割装置であって、前記構造化文書を受け取って、当該構造化文書の文書構造情報を当該構造化文書に基づいて生成する文書構造情報生成ユニット（１）と、前記文書構造情報生成ユニット（１）によって生成された前記文書構造情報に基づいて、前記情報ブロックの範囲を判定する情報ブロック範囲判定ユニット（２）と、前記文書構造情報生成ユニット（１）によって生成された前記文書構造情報と、前記情報ブロック範囲判定ユニット（２）によって判定された前記範囲とに基づいて、分割基準を生成する分割基準生成ユニット（３）と、前記分割基準生成ユニット（３）によって生成された前記分割基準に基づいて、前記構造化文書を分割してその結果を出力する分割ユニット（４）とを備えることを特徴とする。
【００２５】
この請求項５の発明によれば、構造化文書の文書構造情報が当該構造化文書に基づいて生成され、この文書構造情報に基づいて、情報ブロックの範囲が判定される。そして、これら文書構造情報と範囲とに基づいて分割基準が生成され、この分割基準に基づいて構造化文書が分割されて、その結果が出力される。
【００２６】
また、請求項６に記載の分割方法は、構造化文書に含まれる情報ブロックを分割する分割方法であって、前記構造化文書を受け取って、当該構造化文書の文書構造情報を当該構造化文書に基づいて生成する文書構造情報生成工程と、前記文書構造情報生成工程において生成された前記文書構造情報に基づいて、前記情報ブロックの範囲を判定する情報ブロック範囲判定工程と、前記文書構造情報生成工程において生成された前記文書構造情報と、前記情報ブロック範囲判定工程において判定された前記範囲とに基づいて、分割基準を生成する分割基準生成工程と、前記分割基準生成工程において生成された前記分割基準に基づいて、前記構造化文書を分割してその結果を出力する分割工程とを含むことを特徴とする。
【００２７】
この請求項６の発明によれば、構造化文書の文書構造情報が当該構造化文書に基づいて生成され、この文書構造情報に基づいて、情報ブロックの範囲が判定される。そして、これら文書構造情報と範囲とに基づいて分割基準が生成され、この分割基準に基づいて構造化文書が分割されて、その結果が出力される。
【００２８】
また、請求項７に記載の分割方法は、請求項６に記載の構造化文書の分割方法において、文書構造情報生成工程において生成された前記文書構造情報は文書構造ツリーであり、幅優先アルゴリズムを用いて前記文書構造ツリーを探索することにより、最大の有効子ノードを有し、かつ、有効テキスト量と文書全体の有効テキスト量との比率が所定の閾値より大きいノードを発見し、前記ノードが対応する範囲が、全ての前記情報ブロックを含む最小の範囲であり、前記ノードをルートとするサブツリーが、全ての前記情報ブロックを含む最小のサブツリーであることを特徴とする。
【００２９】
この請求項７の発明によれば、有効子ノード番号及び有効テキスト量と文書全体の有効テキスト量との比率を用いて、全ての前記情報ブロックを含む最小のサブツリーのルートノードが判定される。
【００３０】
また、請求項８に記載の分割方法は、請求項６又は７に記載の構造化文書の分割方法において、前記文書構造情報生成工程において生成された前記文書構造情報は文書構造ツリーであり、前記分割基準生成工程において、前記情報ブロックが置かれているサブツリーのルートノードの子ノードと孫ノードとのタグシーケンスを利用して最適繰り返しパターンを計算することを特徴とする。
【００３１】
この請求項８の発明によれば、情報ブロックが置かれているサブツリーのルートノードの子ノードに関する情報が利用されるだけではなく、サブツリーのルートノードの孫ノードに関するタグシーケンスが、最適繰り返しパターンの計算に利用される。
【００３２】
また、請求項９に記載の分割方法は、請求項８に記載の構造化文書の分割方法において、前記分割基準生成工程において、最初に、前記ルートノードの子ノードのシーケンスへの第一の繰り返しパターンを計算し、次に、ルートノードの子ノードと孫ノードとのシーケンスへの第二の繰り返しパターンを計算し、最後に、最適繰り返しパターンを前記第一の繰り返しパターンと前記第二の繰り返しパターンとから選択することにより、最適繰り返しパターンを計算することを特徴とする。
【００３３】
この請求項９の発明によれば、ルートノードの子ノードのシーケンスへの第一の繰り返しパターンが計算され、さらに、ルートノードの子ノードと孫ノードとのシーケンスへの第二の繰り返しパターンが計算され、これら第一の繰り返しパターンと第二の繰り返しパターンとから最適繰り返しパターンが選択される。
【００３４】
また、請求項１０に記載の分割方法は、請求項９に記載の構造化文書の分割方法において、前記分割基準生成工程において、オリジナルのタグシーケンスの第一の繰り返しシーケンスを計算し、前記第一の繰り返しシーケンスに基づいて、当該第一の繰り返しシーケンスの指定された記号をタグシーケンスに代入して、オリジナルのタグシーケンスの修正済みシーケンスを取得し、前記修正済みシーケンスの第二の繰り返しシーケンスを計算し、さらに、前記第二の繰り返しシーケンスが前記第一の繰り返しシーケンスを含むかどうかに基づいて、最終的な繰り返しパターンを判定することにより、前記第一の繰り返しパターンと前記第二の繰り返しパターンとから少なくともひとつの前記分割基準を計算することを特徴とする。
【００３５】
この請求項１０の発明によれば、オリジナルのタグシーケンスの第一の繰り返しシーケンスが計算され、この第一の繰り返しシーケンスに基づいて修正済みシーケンスが取得される。そして、修正済みシーケンスの第二の繰り返しシーケンスを計算し、さらに、この第二の繰り返しシーケンスが第一の繰り返しシーケンスを含むかどうかに基づいて、最終的な繰り返しパターンが判定される。
【発明の効果】
【００３６】
このような本発明によれば、構造化文書中の選択性タグに対する処理を可能とし、深いレベルの情報と構造化文書の構造的特徴とを考慮して識別と分割を実行し、たとえ構造化文書の構造と繰り返しパターンとが比較的複雑で、また、情報ブロックが完全には互いに整合していなくても、構造化文書中の情報ブロックに対して正確な識別と分割を実行する。したがって、構造化文書の情報ブロックを正しく自動的に分割することが可能となる。
【００３７】
また、本発明によれば、有効子ノード番号及び有効テキスト量と文書全体の有効テキスト量との比率を用いて、全ての前記情報ブロックを含む最小のサブツリーのルートノードを判定すると、ある特定のノードと特定のテキストとによってもたらされた全ての情報ブロックを含む最小のサブツリーのルートノードの判定に対する影響を排除することが可能となり、また、幅優先アルゴリズムを用いて上記文書構造を探索すると、文書構造ツリーのルートノードの近傍にあるノードを優先的に考慮することが可能となる。
【００３８】
また、本発明によれば、情報ブロックが置かれているサブツリーのルートノードの子ノードに関する情報が利用されるだけではなく、サブツリーのルートノードの孫ノードに関するタグシーケンスも利用され、これによって、情報ブロックが置かれているサブツリーのルートノードの子ノードのタグシーケンスだけでは解決できない問題に対処することが可能となる。
【００３９】
また、本発明によれば、ルートノードの子ノードのシーケンスへの第一の繰り返しパターンが計算され、さらに、ルートノードの子ノードと孫ノードとのシーケンスへの第二の繰り返しパターンが計算され、これら第一の繰り返しパターンと第二の繰り返しパターンとから最適繰り返しパターンが選択される。すなわち、子ノードに関する情報が利用されるだけではなく、孫ノードに関するタグシーケンスも利用され、これによって、情報ブロックが置かれているサブツリーのルートノードの子ノードのタグシーケンスだけでは解決できない問題に対処することが可能となる。
【００４０】
また、本発明によれば、オリジナルのタグシーケンスの第一の繰り返しシーケンスが計算され、この第一の繰り返しシーケンスに基づいて修正済みシーケンスが取得される。そして、修正済みシーケンスの第二の繰り返しシーケンスを計算し、さらに、この第二の繰り返しシーケンスが第一の繰り返しシーケンスを含むかどうかに基づいて、最終的な繰り返しパターンが判定される。したがって、これら第一の繰り返しパターンと第二の繰り返しパターンとを用いて、最適繰り返しパターンを容易に選択することができる。
【発明を実施するための最良の形態】
【００４１】
以下に、本発明の最良の実施形態を、図面を参照して詳細に説明する。図１は、本実施の形態にかかる分割装置の構成を概念的に例示する図である。この図１に示すように分割装置は、文書構造情報生成ユニット１と、情報ブロック範囲判定ユニット２と、分割基準生成ユニット３と、分割ユニット４との四つのユニットを備えて構成されている。以下に、これら四つのユニットを詳細に説明する。
【００４２】
（文書構造情報生成ユニット１）
文書構造情報生成ユニット１は、特許請求の範囲における文書構造情報生成手段に対応するもので、最初に、構造化文書を受け取り、上記文書のタグ情報を利用することによって、文書構造情報を作成する。この文書構造情報は、構造化文書の内容と構造、すなわち、文書を構成する各要素（エレメント名、エレメントコンテンツ、及び、エレメントに含まれる属性）と、これら要素間の構成関係とを反映している。
【００４３】
例えば、ＨＴＭＬファイルを受取った場合、このＨＴＭＬファイル中において、タグ（ＨＴＭＬ，ｔｒ，ｔｄ等）が、ＨＴＭＬの定義にしたがってテキストに結合されている。このタグには「＜」および「＞」が含まれ、また、タグ名は「＜」および「＞」の間に示される。このようなタグは通常は一対になっており、その一方は開始タグであり、他方は終了タグである。ここで、終了タグは「／」で開始するが、開始タグは「／」では開始しない。なお、タグは単独でも使用され得る。
【００４４】
このようなＨＴＭＬファイル中における特定のタグは、離散的な領域を区画する。上記離散的な領域の始めが開始タグの開始位置であり、上記離散的な領域の終わりが、開始タグに対応する終了タグの位置である。上記離散的な領域は、特定のタグによって、さらに小さい領域に分割される。これらのタグは、互いに入り子になって入り子構造を形成する。これらの情報に基づいて、上記文書の構造情報を記述するために、上記ＨＴＭＬファイルの文書構造ツリーが作成される。
【００４５】
（情報ブロック範囲判定ユニット２）
次に、情報ブロック範囲判定ユニット２は、特許請求の範囲における情報ブロック範囲判定手段に対応するもので、文書構造情報生成ユニット１によって生成された文書構造情報に基づいて、全ての情報ブロックを含む最小の範囲を算出する。ここで、文書構造情報は文書構造グラフを用いて示されるものとすると、情報ブロック範囲判定ユニット２は、全ての情報ブロックを含む最小のサブグラフを決定する。
【００４６】
例えば、ＨＴＭＬファイルを例にとって説明すると、ＨＴＭＬファイルを最初に受け取って、文書構造ツリーを用いて文書構造情報が示される。ここで、対応する領域のタグ名は、文書構造ツリーのノード名である。
【００４７】
いわゆる有効子ノード番号とは次のことを意味する。子ノードに「ＦＯＲＭ」という名称を持つノードが存在しない場合、有効子ノード番号は、有効テキスト量が０であるような子ノード番号であり、子ノードに「ＦＯＲＭ」という名称を持つノードが存在する場合、有効子ノード番号は、「ＦＯＲＭ」という名称を持つ二つの連続したノード間で、有効テキスト量が０でない子モード番号の内の最大の番号である。
【００４８】
ノードの有効テキスト量は、その全ての子ノードの有効テキスト文章の総和であり、上記ノードがテキストノードであれば、上記ノードの有効テキスト量は、このノードのテキストの長さであり、上記ノードが「ｏｐｔｉｏｎ」であれば、上記ノードの有効テキスト量は０であり、上記ノードが「ｄｉｖ」であれば、上記ノードの有効テキスト量は０である。
【００４９】
幅優先アルゴリズムを採用して上記文書構造ツリーを探索することにより、最大の有効子ノードを有するノードであって、その有効テキスト量と文書全体の有効テキスト量との比率が所定の閾値、例えば、４０パーセントより大きいノードを見つける。上記ノードをルートノードとするサブツリーは、全ての情報ブロックを含む最小のサブツリーである。上記ノードが対応する範囲は、全ての情報ブロックを含む最小の範囲である。
【００５０】
（分割基準生成ユニット３）
分割基準生成ユニット３は、特許請求の範囲における分割基準生成手段に対応するものである。ここでは、情報ブロックを含むサブツリーのルートノードＡの子ノードの順序が、Ａ1，Ａ2，Ａ3，．．．，Ａnであるとする。分割タスクにおいては、これらの子ノードをその順序に応じていくつかのグループに分割し、各グループをその他のグループと類似のものにする。各グループの子ノードシーケンスに対応する領域が、分割される情報ブロックである。
【００５１】
分割基準生成ユニット３は、これらの子ノードをグループ化するためのルール、すなわち、分割基準を計算して、この基準を、分割ユニット４が使用可能になるように記憶するために出力する。
【００５２】
この分割基準生成ユニット３における主たる処理は以下の通りである。
工程１：特殊な分割タグを用いて分割を実行することが可能であるか判断し、可能であれば、上記特殊な分割タグを返して、この処理は終了する。
工程２：ノードＡの子ノードシーケンスに対して、繰り返しパターン１を計算する。
工程３：ノードＡの子ノードシーケンスと孫ノードシーケンスと対して、繰り返しパターン２を計算する。
工程４：繰り返しパターン１と繰り返しパターン２中の評価関数を利用して、最適繰り返しパターンを選択する。この最適繰り返しパターンが分割基準になる。
【００５３】
上記の処理の工程２及び工程３において、ＰＡＴなどの従来技術によるアルゴリズムを用いたり、後述する二次ＰＡＴアルゴリズム方法を用いることで、繰り返しパターンを計算することが可能である。工程４では、評価関数としてカバレージ度を用いることができる。ここで、あるシーケンスに対するあるパターンのカバレージ度とは、上記シーケンス中の上記パターンと一致するエレメント集合体の全体分量と上記シーケンスの分量との比率を意味する。このカバレージ度に基づいて、最適繰り返しパターンを計算して選択することが可能である。
【００５４】
以下、このカバレージ度の概念と計算方法とを詳細に説明する。
ここでは、キャラクタストリングをＸ、パターンをＹ、パターンＹに対するＸのｋ個の分割ポイントがｐ1，ｐ2，ｐ3，．．．，ｐkの順序で存在し、ｓｔｒ（ｐi）（０≦ｉ≦ｋ）は、Ｘ中のｐiから始まるパターンＹと一致するサブストリングであり、ｌｅｎｇｔｈ（ｓｔｒ（ｐi））はｓｔｒ（ｐi）の長さであるとする。カバレージ度、すなわち、ｓｃｏｒｅは次式で計算される。
【００５５】
【数１】
2005025763.tif 000003
【００５６】
ここで、ｓｃｏｒｅの値が大きいほど、Ｘへの全てのｓｔｒ（ｐi）（０≦ｉ≦ｋ）のカバレージ度が高くなり、パターンはより良好となる。最適パターンは、カバレージ度が最大のパターンである。
【００５７】
以下に、二次ＰＡＴ（パトリシアツリー）方法を説明する。二次ＰＡＴ方法は、タグシーケンスを受け取って、計算後にタグシーケンスの最適繰り返しパターンを得るものである。例えば、タグシーケンスが「Ｂ，Ｉ，Ａ，Ｂ，Ｉ，Ａ，Ｂ，Ｉ，Ａ，Ｂ，Ｉ，Ａ，」である場合、最適繰り返しパターンは、「Ｂ，Ｉ，Ａ，」になる。また、例えば、タグシーケンスが「Ａ，ｃ，ｄ，Ｂ，Ａ，ｃ，ｄ，ｃ，ｄ，ｃ，ｄ，Ｂ，」であるとすると、最適繰り返しパターンは、「Ａ，（ｃ，ｄ，）*Ｂ，」になる。以後、（Ｘ）*は、シーケンスＸ（ｓ）をＮ（Ｎはゼロ又は正の整数）だけ含むストリングを示すものとする。
【００５８】
具体的には、次のような手順が取られる。
受け取られたタグシーケンスはＮであると仮定する、
工程１：Ｎ中の繰り返しシーケンスを計算する。例えば、Ｎは「Ａ，ｃ，ｄ，Ｂ，Ａ，ｃ，ｄ，ｃ，ｄ，ｃ，ｄ，Ｂ，」であり、繰り返しシーケンスは「ｃ，ｄ，」である。
工程２：タグシーケンスＮを、Ｎの繰り返しシーケンスにしたがって修正する。この修正は、Ｎ中に出現する繰り返しシーケンス又は複数の繰り返しシーケンスを、Ｘのような特定の指定された文字と交換するものである。したがって、上記例でのＮは「Ａ，Ｘ，Ｂ，Ａ，Ｘ，Ｂ，」と修正される。
工程３：修正されたシーケンスＮの繰り返しシーケンスを計算する。この例における修正されたシーケンスＮの繰り返しシーケンスは「Ａ，Ｘ，Ｂ，」である。
工程４：修正された繰り返しシーケンスＮの上記繰り返しシーケンスがＸを含んでいる場合には、繰り返しシーケンス中のＸを（Ｘ）*と交換する。これにより、交換された繰り返しシーケンスが最適パターンになる。一方、修正された繰り返しシーケンスＮの繰り返しシーケンスがＸを含まない場合、繰り返しシーケンスＮの繰り返しシーケンスが、Ｎの最適パターンとなる。
【００５９】
上述したように、分割基準生成ユニット３は、情報ブロックが置かれているサブツリーのルートノードの子ノードに関する情報を利用するだけではなく、サブツリーのルートノードの孫ノードに関するタグシーケンス情報をも用いるので、情報ブロックが置かれているサブツリーのルートノードの子ノードのタグシーケンスだけでは解決できない問題に対処することが可能となる。詳細については実施例２を参照されたい。
【００６０】
（分割ユニット４）
次に、分割ユニット４は、特許請求の範囲における分割手段に対応するものである。ここで、情報ブロックを含むサブツリーのルートノードＡの子ノードがＡ1，Ａ2，Ａ3，．．．，Ａnの順序で存在するものとする。分割基準に基づいて、分割ユニット４はこれらの子ノードシーケンスをその順序に応じていくつかのグループに分類する。各グループ中のノードによって示される領域の組み合わせが、分割された情報ブロックである。
【００６１】
以下に、３つの実施例をあげて、本分割装置の処理を説明する。
【実施例１】
【００６２】
図２から５を参照して、本発明にかかる構造化文書を識別して分割する分割装置について説明する。ここでは、分割装置をＨＴＭＬファイルの識別及び分割に適用した場合について説明する。図２は、実施例１で分割対象とするＨＴＭＬファイルを示す図、図３は、図２のＨＴＭＬファイルのソースファイルを示す図、図４は、図２のＨＴＭＬファイルの構造ツリーを示す図である。
【００６３】
最初に、文書構造情報生成ユニット１は、上記ファイルを解析して、図４に示すような構造グラフを得る。ここでは、この構造グラフは、具体的には構造ツリーである。
【００６４】
次に、情報ブロック範囲判定ユニット２は、上記構造ツリーを分析して、各ノードの有効子ノード番号と有効テキスト量を計算する。そして、幅優先アルゴリズムを用いてルートノードから順に構造ツリーの走査を行い、有効テキスト量が上記ＨＴＭＬファイルの全有効テキスト量の所定の閾値、例えば４０％より大きく、また、最大の有効子ノード番号を有するノードＳを見つける。図４に示すように、Ｓの全てのノードが有効子ノードであり、合計１１個である。Ｓをルートとするサブツリーは、情報ブロックを含む最小のサブツリーである。
【００６５】
更に、分割基準生成ユニット３は、ルートノードＳの子ノードシーケンスを計算し、それが複数の特殊タグ「ＨＲ」を有するかを判断して、有していれば、「ＨＲ」は分割基準であるとする。
【００６６】
分割ユニット４は、分割基準にしたがって次のように分割する。ルートノードＳの子ノードシーケンスは「ｐ，ｂｒ，ｈｒ，ｐ，ｈｒ，ｐ，ｈｒ，ｐ，ｈｒ，ｐ，ｈｒ，ｐ，ｈｒ」であるので、六個のグループ、すなわち「ｐ，ｂｒ，ｈｒ」と、「ｐ，ｈｒ」と、「ｐ，ｈｒ」と、「ｐ，ｈｒ」と、「ｐ，ｈｒ」と、「ｐ，ｈｒ」とに分割され、各グループがある領域、すなわち、情報ブロックに対応している。このように識別され分割された情報ブロックを図５に示す。
【実施例２】
【００６７】
次に、図６から１０を参照して、本発明にかかる分割装置の実施例２を説明する。ここでは、分割装置をＨＴＭＬファイルの識別と分割とに適用した場合について説明する。図６は、実施例２で分割対象とするＨＴＭＬファイルを示す図、図７は、図６のＨＴＭＬファイルのソースファイルを示す図、図８は、図６のＨＴＭＬファイルの構造ツリーを示す図である。
【００６８】
最初に、文書構造情報生成ユニット１は、上記ファイルを解析して、図８に示すような構造グラフを得る。ここで、構造グラフは、具体的には構造ツリーである。
【００６９】
次に、情報ブロック範囲判定ユニット２は、上記構造ツリーを分析し、各ノードの有効子ノード番号と有効テキスト量を計算する。そして、幅優先アルゴリズムを用いてルートノードから順に構造ツリーを走査して、有効テキスト量が上記ＨＴＭＬファイルの全有効テキスト量の所定の閾値、例えば、４０％より大きく、また、最大の有効子ノード番号を有するノードＳを発見する。図８に示すように、Ｓの全てのノードが有効子ノードであり、合計１０個である。Ｓをルートするサブツリーは、情報ブロックを含む最小のサブツリーである。ここでは、有効テキスト量という概念を採用しているので、ノード「ｏｐｔｉｏｎ」中のテキスト量は無視する。
【００７０】
ここで、上述した非特許文献２において提案されている方法を採用した場合には、ノード「ｓｅｌｅｃｔ」が最大の子ノードとなり、合計１２個となり、サブツリー「ｓｅｌｅｃｔ」上のテキスト量と文書全体のテキスト量の比率は４０％を超えるため、「ｓｅｌｅｃｔ」をルートとするサブツリーが、情報ブロックを含む最小のサブツリーであると判定される。しかしながら、図７に示すように、ノード「ｓｅｌｅｃｔ」に対応する領域はなんら情報ブロックを含んでいない。
【００７１】
次に、分割基準生成ユニット３は、情報ブロック「ｔｒ，ｔｒ，ｔｒ，ｔｒ，ｔｒ，ｔｒ，ｔｒ，ｔｒ，ｔｒ」を含む最小のサブツリーのルートノードＳの子ノードシーケンスを計算して、二次ＰＡＴアルゴリズムを呼び出す。そして、分割基準生成ユニット３は、第一の繰り返しパターンが「ｔｒ」であり、第一の繰り返しパターンのカバレージ度が１であり、情報ブロックを含む最小のサブツリーのルートノードＳの子と孫のノードシーケンスが「ｔｒ＿ｔｄ，ｔｒ＿ｔｄ＿ｔｄ，ｔｒ＿ｔｄ，ｔｒ＿ｔｄ＿ｔｄ，ｔｒ＿ｔｄ，ｔｒ＿ｔｄ＿ｔｄ，ｔｒ＿ｔｄ，ｔｒ＿ｔｄ＿ｔｄ，ｔｒ＿ｔｄ，ｔｒ＿ｔｄ＿ｔｄ，」であるものと判断する。また、分割基準生成ユニット３は、二次ＰＡＴアルゴリズムを呼び出すことによって、第二の繰り返しパターンが「ｔｒ＿ｔｄ，ｔｒ＿ｔｄ＿ｔｄ，」であり、第二の繰り返しパターンのカバレージ度が１であるものと判断する。そして、第一と第二の繰り返しパターンのカバレージ度の大きさを比較することによって、第一の繰り返しパターンのカバレージ度が第二の繰り返しパターンのカバレージ度と同じ又はそれ以下であることから、第二の繰り返しパターンが最適パターンであるものと判断する。この最適パターンが分割基準になる。
【００７２】
この例において、情報ブロックを含む最小のサブツリーのルートノードＳの子ノードに加えて、その子ノードの情報も用いているが、上述した非特許文献１の方法の場合のように、子ノード情報のみを用いた場合、「ｔｒ，ｔｒ，ｔｒ，ｔｒ，ｔｒ，ｔｒ，ｔｒ，ｔｒ，ｔｒ，」という子ノードシーケンス中の「ｔｒ」が最適パターンとなり、この最適パターンを用いて分割を実行して、一つの情報ブロックであったはずの部分を二つの部分に分割するため、図９に示すような誤った分割結果となる。
【００７３】
しかしながら、本発明によれば、分割基準生成ユニット３は上記のような分割基準を用いて分割を実行するため、ルートノードＳの子と孫のノードシーケンス「ｔｒ＿ｔｄ，ｔｒ＿ｔｄ＿ｔｄ，ｔｒ＿ｔｄ，ｔｒ＿ｔｄ＿ｔｄ，ｔｒ＿ｔｄ，ｔｒ＿ｔｄ＿ｔｄ，ｔｒ＿ｔｄ，ｔｒ＿ｔｄ＿ｔｄ，ｔｒ＿ｔｄ，ｔｒ＿ｔｄ＿ｔｄ，」は、五つのグループ「ｔｒ＿ｔｄ，ｔｒ＿ｔｄ＿ｔｄ」、「ｔｒ＿ｔｄ，ｔｒ＿ｔｄ＿ｔｄ」、「ｔｒ＿ｔｄ，ｔｒ＿ｔｄ＿ｔｄ」、「ｔｒ＿ｔｄ，ｔｒ＿ｔｄ＿ｔｄ」、「ｔｒ＿ｔｄ，ｔｒ＿ｔｄ＿ｔｄ」に分割され、各グループがある領域、すなわち、情報ブロックに対応する。このように識別され分割された情報ブロックを図１０に示す。
【実施例３】
【００７４】
次に、図１１から１４を参照して、本発明にかかる分割装置の実施例３を説明する。ここでは、分割装置をＨＴＭＬファイルの識別と分割とに適用した場合について説明する。図１１は、実施例３で分割対象とするＨＴＭＬファイルを示す図、図１２は、図１１のＨＴＭＬファイルのソースファイルを示す図、図１３は、図１１のＨＴＭＬファイルの構造ツリーを示す図である。
【００７５】
最初に、文書構造情報生成ユニット１は、上記ファイルを解析して、図１１に示すような構造グラフを得る。ここで、構造グラフは、具体的には構造ツリーである。
【００７６】
次に、情報ブロック範囲判定ユニット２は、上記構造ツリーを分析し、各ノードの有効子ノード番号と有効テキスト量を計算する。そして、幅優先アルゴリズムを用いてルートノードから順に構造ツリーを走査し、有効テキスト量が上記ＨＴＭＬファイルの全有効テキスト量の所定の閾値、例えば４０％より大きく、また、最大の有効子ノード番号を有するノードＳを発見する。図１３に示すように、Ｓの全てのノードが有効子ノードであり、合計１２個である。Ｓをルートとするサブツリーは、情報ブロックを含む最小のサブツリーである。
【００７７】
次に、分割基準生成ユニット３は、情報ブロック「ｂ，ｂ，ｐ，ｐ，ｐ，ｂ，ｐ，ｐ，ｐ，ｂ，ｐ，ｐ，」を含む最小のサブツリーのルートノードＳの子ノードシーケンスを計算して、二次ＰＡＴ方法を利用することによって、第一の繰り返しパターンが「ｂ（ｐ）*」であり、第一の繰り返しパターンのカバレージ度が１１／１２であり、ノードＳの子と孫のノードシーケンスが「ｂ＿ｐ，ｂ＿ｐ，ｐ＿ｔｅｘｔ，ｐ＿ｔｅｘｔ，ｐ＿ｔｅｘｔ，ｂ＿ｐ，ｐ＿ｔｅｘｔ，ｐ＿ｔｅｘｔ，ｐ＿ｔｅｘｔ，ｂ＿ｐ，ｐ＿ｔｅｘｔ，ｐ＿ｔｅｘｔ，」であるものと判断する。また、二次ＰＡＴ方法を利用することによって、第二の繰り返しパターンが「ｂ＿ｐ，（ｐ＿ｔｅｘｔ，）*」であり、第二の繰り返しパターンのカバレージ度が１１／１２であるものと判断する。そして、第一の繰り返しパターンのカバレージ度と第二の繰り返しパターンのカバレージ度との大きさを比較することによって、第一の繰り返しパターンのカバレージ度が第二の繰り返しパターンのカバレージ度と同じ又はそれ以下であり、第二の繰り返しパターンが最適パターン、すなわち、分割基準であるものと判断する。
【００７８】
このユニット中では、繰り返しパターンを計算する際に二次ＰＡＴ方法を用いると、正確な繰り返しパターンを引き出すことが可能であり、例えば、シーケンス「ｂ，ｂ，ｐ，ｐ，ｐ，ｂ，ｐ，ｐ，ｐ，ｂ，ｐ，ｐ，」の繰り返しパターンの計算において、最初に、シーケンス「ｂ，ｂ，ｐ，ｐ，ｐ，ｂ，ｐ，ｐ，ｐ，ｂ，ｐ，ｐ」の繰り返しパターンが「ｐ」であることを計算して導出し、次に、指定された文字Ｍを用いて上記シーケンスを「ｂ，ｂ，Ｍ，ｂ，Ｍ，ｂ，Ｍ，」に修正し、更に、修正された繰り返しパターンが「ｂ，Ｍ」であることを導出して、修正された繰り返しシーケンス「ｂ，Ｍ，」が「Ｍ」を含むことから、次に繰り返しパターンが「ｂ，（Ｐ）*」であることを導出する。
【００７９】
そして、分割基準生成ユニット３は、この分割基準を用いて分割を実行し、これによって、ルートノードＳの子と孫のノードシーケンス「ｂ＿ｐ，ｂ＿ｐ，ｐ＿ｔｅｘｔ，ｐ＿ｔｅｘｔ，ｐ＿ｔｅｘｔ，ｂ＿ｐ，ｐ＿ｔｅｘｔ，ｐ＿ｔｅｘｔ，ｐ＿ｔｅｘｔ，ｂ＿ｐ，ｐ＿ｔｅｘｔ，ｐ＿ｔｅｘｔ，」が三つのグループ「ｂ＿ｐ，ｂ＿ｐ，ｐ＿ｔｅｘｔ，ｐ＿ｔｅｘｔ，ｐ＿ｔｅｘｔ」、「ｂ＿ｐ，ｐ＿ｔｅｘｔ，ｐ＿ｔｅｘｔ，ｐ＿ｔｅｘｔ」、「ｂ＿ｐ，ｐ＿ｔｅｘｔ，ｐ＿ｔｅｘｔ」とに分割され、各グループがある領域、すなわち、情報ブロックに対応する。このように識別され分割された情報ブロックを図１４に示す。
【００８０】
この実施例３に上述の非特許文献２の方法を採用すると、上記方法は文書構造を考慮していないため、文書シーケンス全体が図１３のツリーグラフの通りがけ順（inorder）のシーケンスとなり、また、この通りがけ順のシーケンス中で繰り返しシーケンスが発見されると、最大の繰り返し度を持つタグシーケンスは「Ｐ」であり、これをＨＴＭＬファイル全体の分割タグとして用いると、正しい分割結果を得ることができないことは明らかである。
【００８１】
このように本発明にかかる分割装置は、構造化文書中の選択性タグに対する処理を可能とし、深いレベルの情報と構造化文書の構造的特徴とを考慮して識別と分割を実行し、たとえ構造化文書の構造と繰り返しパターンとが比較的複雑で、また、情報ブロックが完全には互いに整合していなくても、構造化文書中の情報ブロックに対して正確な識別と分割を実行する。したがって、構造化文書の情報ブロックを正しく自動的に分割することが可能となる。
【００８２】
本発明の具体的な構成及び方法は、実施の形態や各実施例に示したものに限定されず、特許請求の範囲に記載した各発明の技術的思想の範囲内において、任意に改変及び改良することができる。例えば、本発明による分割装置は、図１に示したような四つのユニットを備えるものに限定されず、これら四つのユニットを命令に応じてランダムに組み合わせて、一〜三つのユニットとしたり、又は、五つ以上のユニットに特殊化することもできる。同様に、本発明による方法は、四つの工程には制限されず、これもまた、命令に応じてランダムに組み合わせて二つもしくは三つの工程荷してもよく、あるいは、五つ以上の工程に細分化することができる。加えて、本発明による構造化文書は、ＨＴＭＬファイルに限られず、ＸＭＬ、ＸＨＴＭＬ、及び、構造的特徴を持つ他の文書にも同様に適用できる。
【００８３】
また、上記の説明中、自動的に行われるものとして説明した処理の全部又は任意の一部を手動で行っても良い。また、本装置の各機能ブロックは、実際には、ＣＰＵ及びこのＣＰＵにて読み出され実行されるコンピュータプログラム（特許請求の範囲における構造化文書分割プログラムに対応する）として構成することができ、あるいは、ハードワイヤードロジックにて構成することができる。また、プログラムは、ハードディスク、フレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤなどのコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行することもできる。また、プログラムは、インターネットなどのネットワークを介して配布することができる。この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【００８４】
（付記１）構造化文書に含まれる情報ブロックを分割する分割装置であって、
前記構造化文書を受け取って、当該構造化文書の文書構造情報を当該構造化文書に基づいて生成する文書構造情報生成手段と、
前記文書構造情報生成手段によって生成された前記文書構造情報に基づいて、前記情報ブロックの範囲を判定する情報ブロック範囲判定手段と、
前記文書構造情報生成手段によって生成された前記文書構造情報と、前記情報ブロック範囲判定手段によって判定された前記範囲とに基づいて、分割基準を生成する分割基準生成手段と、
前記分割基準生成手段によって生成された前記分割基準に基づいて、前記構造化文書を分割してその結果を出力する分割手段と、
を備えることを特徴とする構造化文書の分割装置。
【００８５】
（付記２）文書構造情報生成手段によって生成された前記文書構造情報は文書構造ツリーであり、
幅優先アルゴリズムを用いて前記文書構造ツリーを探索することにより、最大の有効子ノードを有し、かつ、有効テキスト量と文書全体の有効テキスト量との比率が所定の閾値より大きいノードを発見し、
前記ノードが対応する範囲が、全ての情報ブロックを含む最小の範囲であり、前記ノードをルートとするサブツリーが、全ての情報ブロックを含む最小のサブツリーであること、
を特徴とする付記１に記載の構造化文書の分割装置。
【００８６】
（付記３）前記文書構造情報生成手段によって生成された前記文書構造情報は文書構造ツリーであり、
前記分割基準生成手段は、前記情報ブロックが置かれているサブツリーのルートノードの子ノードと孫ノードとのタグシーケンスを利用して、最適繰り返しパターンを計算すること、
を特徴とする付記１又は２に記載の構造化文書の分割装置。
【００８７】
（付記４）前記分割基準生成手段は、最初に、前記ルートノードの子ノードのシーケンスへの第一の繰り返しパターンを計算し、次に、ルートノードの子ノードと孫ノードとのシーケンスへの第二の繰り返しパターンを計算し、最後に、最適繰り返しパターンを前記第一の繰り返しパターンと前記第二の繰り返しパターンとから選択することにより、最適繰り返しパターンを計算すること、
を特徴とする付記３に記載の構造化文書の分割装置。
【００８８】
（付記５）前記分割基準生成手段は、
オリジナルのタグシーケンスの第一の繰り返しシーケンスを計算し、
前記第一の繰り返しシーケンスに基づいて、当該第一の繰り返しシーケンスの指定された記号をタグシーケンスに代入して、オリジナルのタグシーケンスの修正済みシーケンスを取得し、
前記修正済みシーケンスの第二の繰り返しシーケンスを計算し、さらに、
前記第二の繰り返しシーケンスが前記第一の繰り返しシーケンスを含むかどうかに基づいて、最終的な繰り返しパターンを判定することにより、
前記第一の繰り返しパターンと前記第二の繰り返しパターンとから少なくともひとつの前記分割基準を計算すること、
を特徴とする付記４に記載の構造化文書の分割装置。
【００８９】
（付記６）前記分割基準生成手段は、カバレージ度を用いることにより、繰り返しパターンを計算し、最適繰り返しパターンを選択すること、
を特徴とする付記３に記載の構造化文書の分割装置。
【００９０】
（付記７）前記構造化文書がＨＴＭＬ、ＸＭＬ、又は、ＸＨＴＭＬであること、
を特徴とする付記１から６のいずれか一項に記載の構造化文書の分割装置。
【００９１】
（付記８）構造化文書に含まれる情報ブロックを分割する分割方法であって、
前記構造化文書を受け取って、当該構造化文書の文書構造情報を当該構造化文書に基づいて生成する文書構造情報生成工程と、
前記文書構造情報生成工程において生成された前記文書構造情報に基づいて、前記情報ブロックの範囲を判定する情報ブロック範囲判定工程と、
前記文書構造情報生成工程において生成された前記文書構造情報と、前記情報ブロック範囲判定工程において判定された前記範囲とに基づいて、分割基準を生成する分割基準生成工程と、
前記分割基準生成工程において生成された前記分割基準に基づいて、前記構造化文書を分割してその結果を出力する分割工程と、
を含むことを特徴とする構造化文書の分割方法。
【００９２】
（付記９）文書構造情報生成工程において生成された前記文書構造情報は文書構造ツリーであり、
幅優先アルゴリズムを用いて前記文書構造ツリーを探索することにより、最大の有効子ノードを有し、かつ、有効テキスト量と文書全体の有効テキスト量との比率が所定の閾値より大きいノードを発見し、
前記ノードが対応する範囲が、全ての前記情報ブロックを含む最小の範囲であり、前記ノードをルートとするサブツリーが、全ての前記情報ブロックを含む最小のサブツリーであること、
を特徴とする付記８に記載の構造化文書の分割方法。
【００９３】
（付記１０）前記文書構造情報生成工程において生成された前記文書構造情報は文書構造ツリーであり、
前記分割基準生成工程において、前記情報ブロックが置かれているサブツリーのルートノードの子ノードと孫ノードとのタグシーケンスを利用して最適繰り返しパターンを計算すること、
を特徴とする付記８又は９に記載の構造化文書の分割方法。
【００９４】
（付記１１）前記分割基準生成工程において、最初に、前記ルートノードの子ノードのシーケンスへの第一の繰り返しパターンを計算し、次に、ルートノードの子ノードと孫ノードとのシーケンスへの第二の繰り返しパターンを計算し、最後に、最適繰り返しパターンを前記第一の繰り返しパターンと前記第二の繰り返しパターンとから選択することにより、最適繰り返しパターンを計算すること、
を特徴とする付記１０に記載の構造化文書の分割方法。
【００９５】
（付記１２）前記分割基準生成工程において、
オリジナルのタグシーケンスの第一の繰り返しシーケンスを計算し、
前記第一の繰り返しシーケンスに基づいて、当該第一の繰り返しシーケンスの指定された記号をタグシーケンスに代入して、オリジナルのタグシーケンスの修正済みシーケンスを取得し、
前記修正済みシーケンスの第二の繰り返しシーケンスを計算し、さらに、
前記第二の繰り返しシーケンスが前記第一の繰り返しシーケンスを含むかどうかに基づいて、最終的な繰り返しパターンを判定することにより、
前記第一の繰り返しパターンと前記第二の繰り返しパターンとから少なくともひとつの前記分割基準を計算すること、
を特徴とする付記１１に記載の構造化文書の分割方法。
【００９６】
（付記１３）前記分割基準生成工程において、カバレージ度を用いることにより、繰り返しパターンを計算し、最適繰り返しパターンを選択すること、
を特徴とする付記１０に記載の構造化文書の分割方法。
【００９７】
（付記１４）前記構造化文書がＨＴＭＬ、ＸＭＬ、又は、ＸＨＴＭＬであること、
を特徴とする付記８から１３のいずれか一項に記載の構造化文書の分割方法。
【００９８】
（付記１５）コンピュータを、
前記構造化文書を受け取って、当該構造化文書の文書構造情報を当該構造化文書に基づいて生成する文書構造情報生成手段と、
前記文書構造情報生成手段によって生成された前記文書構造情報に基づいて、前記情報ブロックの範囲を判定する情報ブロック範囲判定手段と、
前記文書構造情報生成手段によって生成された前記文書構造情報と、前記情報ブロック範囲判定手段によって判定された前記範囲とに基づいて、分割基準を生成する分割基準生成手段と、
前記分割基準生成手段によって生成された前記分割基準に基づいて、前記構造化文書を分割してその結果を出力する分割手段と、
として機能させるための構造化文書分割プログラム。
【００９９】
（付記１６）前記コンピュータを、前記文書構造情報生成手段として機能させた際に生成された前記文書構造情報は文書構造ツリーであり、
幅優先アルゴリズムを用いて前記文書構造ツリーを探索することにより、最大の有効子ノードを有し、かつ、有効テキスト量と文書全体の有効テキスト量との比率が所定の閾値より大きいノードを発見し、
前記ノードが対応する範囲が、全ての情報ブロックを含む最小の範囲であり、前記ノードをルートとするサブツリーが、全ての情報ブロックを含む最小のサブツリーであること、
を特徴とする付記１５に記載の構造化文書分割プログラム。
【０１００】
（付記１７）前記コンピュータを、前記文書構造情報生成手段として機能させた際に生成された前記文書構造情報は文書構造ツリーであり、
前記分割基準生成手段は、前記情報ブロックが置かれているサブツリーのルートノードの子ノードと孫ノードとのタグシーケンスを利用して、最適繰り返しパターンを計算すること、
を特徴とする付記１５又は付記１６に記載の構造化文書分割プログラム。
【０１０１】
（付記１８）前記分割基準生成手段は、最初に、前記ルートノードの子ノードのシーケンスへの第一の繰り返しパターンを計算し、次に、ルートノードの子ノードと孫ノードとのシーケンスへの第二の繰り返しパターンを計算し、最後に、最適繰り返しパターンを前記第一の繰り返しパターンと前記第二の繰り返しパターンとから選択することにより、最適繰り返しパターンを計算すること、
を特徴とする付記１７に記載の構造化文書分割プログラム。
【産業上の利用可能性】
【０１０２】
以上のように、本発明にかかる構造化文章の分割プログラム、分割装置及び分割方法は、構造的に記述された文章における情報ブロックを自動的に分割することに有用であり、特に、構造と繰り返しパターンとが比較的複雑で、また、情報ブロックが完全には互いに整合していない構造化文書の情報ブロックを分割することに適用できる。
【図面の簡単な説明】
【０１０３】
【図１】本実施の形態にかかる分割装置の構成を概念的に例示する図である。
【図２】実施例１で分割対象とするＨＴＭＬファイルを示す図である。
【図３】実施例１のＨＴＭＬファイルのソースファイルを示す図である。
【図４】実施例１のＨＴＭＬファイルの構造情報を示す図である。
【図５】実施例１のＨＴＭＬファイルの分割結果を示す図である。
【図６】実施例２で分割対象とするＨＴＭＬファイルを示す図である。
【図７】実施例２のＨＴＭＬファイルのソースファイルを示す図である。
【図８】実施例２のＨＴＭＬファイルの構造情報を示す図である。
【図９】従来技術によるＨＴＭＬファイルの分割結果を示す図である。
【図１０】実施例２のＨＴＭＬファイルの分割結果を示す図である。
【図１１】実施例３で分割対象とするＨＴＭＬファイルを示す図である。
【図１２】実施例３のＨＴＭＬファイルのソースファイルを示す図である。
【図１３】実施例３のＨＴＭＬファイルの構造情報を示す図である。
【図１４】実施例３のＨＴＭＬファイルの分割結果を示す図である。
【符号の説明】
【０１０４】
１  文書構造情報生成ユニット
２  情報ブロック範囲判定ユニット
３  分割基準生成ユニット
４  分割ユニット
【図１】
2005025763.tif 000004
【図２】
2005025763.tif 000005
【図３】
2005025763.tif 000006
【図４】
2005025763.tif 000007
【図５】
2005025763.tif 000008
【図６】
2005025763.tif 000009
【図７】
2005025763.tif 000010
【図８】
2005025763.tif 000011
【図９】
2005025763.tif 000012
【図１０】
2005025763.tif 000013
【図１１】
2005025763.tif 000014
【図１２】
2005025763.tif 000015
【図１３】
2005025763.tif 000016
【図１４】
2005025763.tif 000017