(57)【特許請求の範囲】
【請求項１】
特定フォーマットの構造を有するサンプルファイルのラッパを生成するシステムであって、
複数のストリングトークンを含む特定フォーマットの構造を有する少なくとも１つのサンプルファイルおよびユーザによって選択された属性集合を記憶するメモリと、
前記少なくとも１つのサンプルファイルの帰属可能なトークンを前記属性集合からの属性で注釈付けすることにより、注釈付きサンプル集合を生成するプロセッサと、
を備え、
ラッパの生成が可能であるかどうかを判断するために、前記注釈付きサンプル集合のすべての属性が互いに区別可能であるかどうかを判断し、
ラッパの生成が可能である場合には、前記少なくとも１つのサンプルファイルのラッパを生成し、該ラッパを前記メモリに記憶し、
前記ラッパはファイルに接続されるインタフェースであり、
トークンを前記属性集合の属性に割り当てることができる場合、該トークンは帰属可能なトークンであり、
前記属性の各々はファイルの情報を示す、
ラッパを生成するシステム。
【請求項２】
前記プロセッサが、
前記属性の各々の属性ｔｉに対する逆プレフィックスの集合を生成し、
前記属性集合を、２つの等価クラスが共通の逆プレフィックスを有することのないように、等価クラスｄｉに区分する、
ことを含み、
前記等価クラスが属性に等しい、すなわち、ｄｉ＝ｔｉである場合には、すべての属性ｔｉが区別可能であり、
ｓ＝ｕｒａｖである場合、ストリングｕはａ∈ｓの逆プレフィックスであり、
ｓ∈Sであり、ｓ、ｕ、ｖはストリングを示し、Sはサンプルファイルの集合を示し、ｕｒはｕの逆を示す、
請求項１に記載のシステム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、広く、情報検索及び統合システムに関し、より詳細には、ネットワーク化されたリポジトリ(repositories)に格納されたドキュメントから情報を抽出及び再生するための、ラッパ文法の作成及び生成に関する。
【０００２】
【従来の技術】
ラッパとは、データに接続された一種のインタフェース若しくはコンテナであり、つまり、文法若しくはラッパ文法として知られる一組の規則に従って、遠隔情報源の複雑さを密閉及び隠蔽するものであり、情報ブローカー(broker)に２つの機能を提供する。第１に、ラッパは、クライアントからの問合せを遠隔情報源が理解できるものに翻訳するのに用いられる。ラッパは、特定の情報源と関連付けられる。例えば、ＨＴＴＰラッパはＨＴＴＰサーバ及びＨＴＭＬドキュメントと相互作用し、ＪＤＢＣラッパはＯＤＢＣ仕様データベースと協働し、ＤＭＡラッパはＤＭＡ仕様ドキュメント管理システムと協働する。
【０００３】
第２に、ラッパは、サーチ・エンジンによって、個々のウェブページを表すＨＴＭＬファイルに格納された情報を抽出するのに用いられる。つまり、ラッパは、サーチ・エンジンにより返されたＨＴＭＬファイルを走査し、マークアップ指示を捨て、問合せに関係する情報を抽出する。情報ブローカーが介在する場合には、ラッパは、これらの結果を、情報ブローカーが解釈及びフィルタリングすることのできる形式に構文解析（若しくは処理）する。次に、ラッパは、異なるドキュメントリポジトリから或いは情報ブローカーから探索返答を受け取って、これらをユーザが見ることのできる新しいフォーマットに置き換える。抽出及び構文解析は、応答ファイルのそれぞれの種類に応じた文法若しくは規則に従って行われる。
【０００４】
あいにく、ドキュメントリポジトリ及びプロバイダのＨＴＭＬ応答ファイルは、情報抽出よりも視覚化の都合に合わせて生成される。さらに、異なる情報プロバイダからの応答ファイルは、構造においてもフォーマットにおいても、例えばＨＴＭＬ、ＯＤＢＣ、ＤＭＡというように幅広く多様である。ＨＴＭＬプロバイダ同士の間でさえも、フォーマットは多様であり得る。例えば、ＨＴＭＬタグを生成してドキュメントの各属性（著者、タイトル、掲載誌、及び刊行日）を分離するプロバイダもあれば、著者とタイトルというような属性をつなぎ合わせて、これらをＨＴＭＬタグではなく、コンマやセミコロンのような文法的分離記号によって分離するプロバイダもある。
【０００５】
この結果、応答ファイルの分析、及びほとんどのサーチ・エンジンにおけるラッパ文法の作成には、人間の介入が必要とされる。ウェブプロバイダは時と共に変化（発展）するし、個々のドキュメントも時と共に変化し得るので、人間の介入も、応答構造又はマークアップが変更される度に必要とされる。これにより、ラッパ文法の作成及び保守処理は、極めて時間を要し誤りを起こしやすいものとなる。
【０００６】
２つの主な問題が、自動ラッパ文法生成に影響を及ぼす。第１の問題は、あるウェブベース情報プロバイダによる、応答ページのあいまいなマークアップであり、これは、自動ラッパ文法生成を困難にし、場合によっては不可能にする。例えば、ウェブプロバイダは、各項目が２つのストリング(string)値属性ｔ1及びｔ2（ｔ2は任意）を含む、返答リストを報告する。さらに、プロバイダは、各属性に対して単一のフォーマットを用いることがある。つまり、このウェブプロバイダからの応答ページのＨＴＭＬファイル構造は、(<ｉ>String(t1)<ｉ>(<ｉ>String(t2)</ｉ>))+となる。ラッパ文法が生成されたと仮定すると、このラッパ文法は、このフォーマットを正確に推測し、プロバイダから<ｉ>string1</ｉ><ｉ>string2</ｉ>という応答を受け取る。ラッパ文法は、string1を属性ｔ1に単一に割当てるが、string2はあいまいであると認識する。つまり、ラッパ文法は、string2を属性ｔ1或いは属性ｔ2のいずれかに割当ててしまうことがある（非決定的選択）。明らかに、このような動作は、正確な属性抽出に対して不適切であるので、ラッパ文法生成の際ｔ2は除外するべきである。
【０００７】
自動的に生成されるラッパ文法における第２の主な問題は、過度の汎用化である。例えば、(<HTML>|</HTML>|<body>|</body>|...|String)*のような文法は、いずれのＨＴＭＬファイルも受入れるが、定義されたユーザ属性（タイトル(Title)、著者(Author)など）に、トークン（若しくは特定値）を適切に割当てることができない。過度の汎用化は、サンプル入力ストリングにおいていくつかの共通したフラグメントを検出し、それらを１つの属性に併合することにより汎用化する、文法推定機構から生じる。実際に、過度の汎用化は、併合における不適切な又は欠如した制御に結び付き、これは、正確な属性に対する情報よりも多くの情報を抽出する、汎用文法を生じさせる。
【０００８】
【発明が解決しようとする課題】
本発明の目的は、ネットワーク化されたリポジトリに格納されたドキュメントから情報を抽出するために、特定フォーマット構造を有するファイルに対するラッパ文法を生成する方法を提供することにある。
【０００９】
【課題を解決するための手段】
本発明による、特定フォーマットの構造を有するファイルに対するラッパ文法を生成する方法は、複数のストリングトークンから成る特定フォーマットの、少なくとも１つのサンプルファイルを提供するステップを含む。本発明に関しては、特定の種類のフォーマットファイル（例えば、ＨＴＭＬ、ＪＤＢＣ、ＤＭＡ）のいずれを用いてもよいが、都合上、以下ＨＴＭＬファイルに関してのみ論じる。各サンプルＨＴＭＬファイルは、複数のトークン（データストリング）を含んでおり、これらのトークンは、ドキュメントからの実データ、ＨＴＭＬタグ、又はその他何らかの文法的分離記号であってもよい。
【００１０】
次に、この特定フォーマットのサンプルファイルは、帰属可能トークンを属性集合からの属性で注釈付けして、注釈付きサンプル集合を生成することにより、処理される。トークンは、属性に割当てることができる場合に、帰属可能である。トークンは例えば、著者、タイトルなどのようなユーザが定義した属性を割当てられることにより、注釈付け又はラベル付けされ、これらのトークンのために、このような属性が適切なユーザにより定義されるのである。
【００１１】
次に、この注釈付きサンプル集合は、ラッパ文法生成が可能であるかどうかを判断するために評価され、ラッパ文法生成が可能である場合には、特定フォーマットの構造を有するファイルに対するラッパ文法が生成される。
【００１２】
この注釈付きサンプル集合は、注釈付きサンプル集合における全ての属性が互いに区別可能であるかどうかを判断することにより、評価されるのが好ましい。区別可能性は、各属性ｔiに対する逆プレフィックスの集合を生成して、この属性集合を、２つの等価クラスが共通の逆プレフィックスを有することのない、等価クラスｄiに区分することにより判断され、この等価クラスが属性に等しい、つまりｄi＝ｔiである場合には、全ての属性ｔiが区別可能であり、自動ラッパ文法生成が可能である。
【００１３】
本発明によるラッパ文法を生成する方法は、ラッパ文法生成に関する手動方法の問題を克服して、時間を要し誤りを起こしやすい人間の介入を不必要にする。本発明によるラッパ文法を生成する方法は、文法推定及び機械学習からの技法を用い、上に考察したラッパ文法よりもはるかに大きなクラスのラッパ文法と共に用いることができる。
【００１４】
文法とは規則の集合であり、これら規則全部で、何を「話す」又は表示することができるかを定義する。本発明のコンテキストにおいて、ラッパとは、文法規則を実施するインタフェースプログラムである。例えば、ラッパが、Javaアプリケーションと共に用いるための構文解析ルーチン生成システムである、Javaコンパイラコンパイラでコンパイルされる場合、このJavaコンパイラコンパイラは、ラッパ文法を、応答ページから文法への対応を認識することのできるJavaプログラム（即ち、ラッパ）に変換する。
【００１５】
本発明の方法においては、基本的に、応答ページは正則文法により処理することができると仮定する。より詳細には、応答ページは、ｋ可逆性正則文法（ここで、ｋ≧０）により処理することができると仮定する。可逆性文法のクラスは、正則文法クラスの適切な部分集合であるが、これら２つのクラス間における差は最小限度であるので、これら２つのクラスは、ラッパ文法生成の目的においては同一であるとみなすことができる。さらに、これら２つのクラス（正則文法及びｋ可逆性文法）に対して帰納された属性アクセプタは同じ表現力を有する、ということを証明することができる。従って、本発明の方法を実ウェブ情報プロバイダに適用し、正則文法に基づいてラッパ文法を生成すると、その時間のほぼ１００％において、ラッパ文法は好適に生成される。
【００１６】
この方法は有効である。即ち、必然的完全状態とするのに注釈付きサンプルを必要としない、つまり、応答の全ての構造的要素を表す。この方法は、新しいＨＴＭＬ応答が、前に処理したＨＴＭＬ応答に用いられていない構造的要素を含んでいる度に、ラッパ文法を洗練させることができる。
【００１７】
本発明によるラッパ文法生成方法は、あいまい性及び過度の汎用化という両方の問題を克服する。あいまい性及び過度の汎用化は、サンプルストリングの異なるフラグメント間における適正レベルの共通性を検出することにより、回避される。従って、併合動作の深さは、自動的に生成されたラッパ文法が、サンプル集合におけるストリングと同種のストリングを全て受入れると同時に、ユーザが定義した属性に対応するトークンを認識することができるように、決定される。
【００１８】
さらに、本発明によるラッパ文法生成方法は、一部の場合において、即ち、ユーザが定義した属性のうちのいくつかを自動文法生成により区別することができる場合のみ、ラッパ文法を生成することができる。この場合において、この方法は、部分的解決を行う。つまり、認識することのできない属性を新しく定義した結合属性に併合して、自動文法生成を完成させる。この自動的に生成されたラッパ文法は、もしあれば個別の属性を、或いは、もしあれば結合属性を認識する。例えば、ユーザ属性であるJournal及びVolumeが、自動ラッパ文法生成により区別されない場合、これらの属性は、自動文法生成において用いられるであろうReferenceと呼ばれる結合属性により、置換することができる。ラッパ文法がＨＴＭＬファイルを走査するのに用いられる場合、この特定のファイルがJournal及びVolumeに対して別々のトークンを含んでいれば、これらのトークンは発見される。１つのトークンのみが発見される場合には、属性Referenceとして報告される。
【００１９】
【発明の実施の形態】
図１を参照すると、情報ブローカーが示されており、参照番号１０が付与されている。情報ブローカー１０とは、複数のサーチ・エンジン１２からの探索結果にアクセスし、それらを分類し、その分類した探索結果をユーザ若しくはクライアント１４に提供する、一種のサーチ・エンジンである。ラッパ１６とは、データに接続された一種のインタフェース若しくはコンテナであり、つまり、文法若しくはラッパ文法として知られる一組の規則に従って、遠隔情報源の複雑さを密閉及び隠蔽するものであり、情報ブローカー１０に２つの機能を提供する。第１に、ラッパは、クライアントからの問合せ１８を遠隔情報源１２が理解できるものに翻訳するのに用いられる。ラッパは、特定の情報源と関連付けられる。例えば、ＨＴＴＰラッパはＨＴＴＰサーバ及びＨＴＭＬドキュメントと相互作用し、ＪＤＢＣラッパはＯＤＢＣ仕様データベースと協働し、ＤＭＡラッパはＤＭＡ仕様ドキュメント管理システムと協働する。ラップされた問合せ１５は、共通ゲートウェイインタフェース（ＣＧＩ）を介してさまざまな情報源１２へ送られ、これらの情報源１２は、ＸＭＬ又はＨＴＭＬフォーマットにおける応答１７を生成する。
【００２０】
情報ブローカー１０が情報源１２からの結果を処理するためには、個別のラッパ１６を各情報源１２に対して提供しなければならない。図２を参照すると、情報ブローカー１０がクライアントからの問合せを送ろうとするそれぞれの新しい情報源１２に対して、ラッパ文法を生成し（ステップ２０）、ラッパを作成しなければならない（ステップ２２）。次に、情報ブローカー１０は、このラッパ１６を用いてクライアントからの問合せを処理し（ステップ２４）、情報源１２が理解することのできる形式における問合せ要素（ラップされた問合せ１５）を提供する。
【００２１】
情報源１２が探索結果１７を返すと（ステップ２６）、ラッパ１６が用いられて、これらの結果１７は、情報ブローカー１０が用いることのできる形式に処理される（ステップ２８）。ラッパ１６は、個々のウェブページを表すＨＴＭＬファイルに格納された情報を抽出する。ラッパ１６は、情報源１２により返されたＨＴＭＬファイル１７を走査し、マークアップ指示を捨て、問合せに関係する情報を抽出して、これらの結果を、情報ブローカー１０が解釈及びフィルタリングすることのできる形式に構文解析（若しくは処理）する。処理が終わると、情報ブローカー１０は、これらのラップされた結果１９を、ユーザが見ることのできるフォーマットでクライアントに表示する（ステップ３０）。抽出及び構文解析は、応答ファイルのそれぞれの種類に応じた文法若しくは規則に従って行われる。情報ブローカー１０は、新しい問合せがあるかどうかを確認して（ステップ３２）、なければ処理を終了し（ステップ３４）、あれば戻って新しい問合せを受ける（ステップ２４）。
【００２２】
［基本定義］
本発明の方法及びシステムの理解を助けるために、形式言語及び文法学習の理論からの定義をいくつかここに示す。
【外１】
0004659946.tif 000002
【００２３】
【外２】
0004659946.tif 000003
【００２４】
【外３】
0004659946.tif 000004
Ａにより受入れられたストリングの集合は、Ａの言語と呼ばれ、Ｌ(Ａ)と示される。
【００２５】
【外４】
0004659946.tif 000005
ここで、汎用性による欠如がなければ、２つのタグトークンが１つの「ストリング」トークンを囲むと仮定する（これにより、この「ストリング」トークンを、１つのユーザ属性で又はユーザ属性なしで注釈付けすることができる）。１つのＨＴＭＬ「ストリング」トークンを、１つよりも多くの属性に割当てることができる場合について、以下考察する。
【００２６】
Ｓを言語Ｌの正のサンプル集合とする。
【外５】
0004659946.tif 000006
ＰＴ(Ｓ)は、集合Ｓを正確に受入れる決定的アクセプタである。文法がｋ可逆性（後で定義する）であるかどうかを判断するための推定アルゴリズムは、Ｓに対するプレフィックスツリーアクセプタで始動し、状態を併合することによりこのＳを汎用化する。
【００２７】
先に定義したアクセプタは、入力ストリングを受入れるか或いは拒絶する。ラッパにおいては、単なる受入れ又は拒絶以外に、情報抽出のための動作がさらに必要とされる。属性アクセプタとは、入力ストリングを受入れるか或いは拒絶する以外に、認識した「ストリング」トークンを、ユーザ若しくはアプリケーションが定義したいくつかの属性で注釈付けする、アクセプタである。以下、ユーザが定義した属性はリストＴを作成し、属性アクセプタＡ(Ｔ)はラッパ文法に例えることができる。
【００２８】
【外６】
0004659946.tif 000007
「属性値」は、トークンａ(「ストリング」)とその値（‘ＸＲＣＥ’）とを区別するために用いられる、ということに注意されたい。
【００２９】
属性への割当てなしに遷移を可能にするために、特別属性voidを含むリストＴが、割当ての無い場合毎に用いられる。さらに、ＨＴＭＬアクセプタの実用的ニーズに合わせて、割当て可能な属性は、割当て不可能な属性と区別される。
【外７】
0004659946.tif 000008
【００３０】
逆に、属性アクセプタＡ(Ｔ)に関して、そのプレーン(plain)アクセプタＡは、遷移規則から全ての属性注釈を取り除くことにより、Ａ(Ｔ)から得られるアクセプタである。ストリングｕは、そのプレーンアクセプタＡにより受入れられる場合、またこの場合に限って、Ａ(Ｔ)により受入れられる。
【外８】
0004659946.tif 000009
【００３１】
［実施例１］
【外９】
0004659946.tif 000010
図５は、上のアクセプタＡ(Ｔ)のグラフ表示を示している。
【００３２】
［ｋ可逆性］
本発明の重要な態様は、ＨＴＭＬ応答構造がｋ可逆性であるかどうかを判断することである。
【外１０】
0004659946.tif 000011
これにより、Ａの動作におけるいずれの非決定的選択も、現在のものを通過するｋ記号を予見することにより解決することができる、ということが保証される。
【００３３】
Ａが決定性であり、Ａrがルックアヘッドｋを有する決定性である場合、またこの場合に限って、アクセプタＡはｋ可逆性であると定義される。ｋ可逆性オートマトンＡがあってＬ＝Ｌ(Ａ)である場合、またこの場合に限って、言語Ｌはｋ可逆性であると定義される。属性アクセプタのｋ可逆性も、同様に定義される。Ａが決定性であり、Ａrがルックアヘッドｋを有する決定性である場合、またこの場合に限って、属性アクセプタＡはｋ可逆性であると定義される。ｋ可逆性オートマトンＡがあってＷ＝Ｗ(Ａ)である場合、またこの場合に限って、ＨＴＭＬ応答構造Ｗはｋ可逆性であると定義され、ラッパ文法が生成され得る。
【００３４】
［属性及びプレフィックスの正規化］
所定の情報源からのＨＴＭＬファイルの正のサンプル集合は、自動ラッパ文法推定若しくは生成を可能にするために、必要条件として、以下の条件を満たしていなければならない。
【００３５】
ＳをサンプルＨＴＭＬファイルの集合とし、ＳTを注釈付けしたサンプルファイルの集合とする。サンプルＨＴＭＬファイルは、ユーザにより、若しくはユーザに属性名を対話式に尋ねるルーチンにより、注釈付けすることができる。図３を参照すると、例えば、トークンの集合から成り、ＨＴＭＬタグ及びストリングを含む、サンプルファイルが提供される（ステップ４０）。従って、サンプルＨＴＭＬファイルは、一連の０又は１つ以上の個別ストリングトークンｓから成る。これらのトークンを注釈付けするために、ステップ４２において、各トークンは調べられて、帰属可能であるかどうか（ユーザが定義した又は所定の属性に割当てることができるかどうか）判断される。帰属可能である場合には、そのトークンは、属性の集合における属性のうちの１つに割当てられる（ステップ４４）。帰属可能でない場合には、次のトークンが調べられる。ファイルにおける最後のトークンを調べ終わったとき（ステップ４６）、帰属可能トークンＳTの集合が形成される（ステップ４８）。これらのストリングトークンを属性に注釈付けし終わったとき、各ストリングｓは、属性の集合Ｔからの属性ｔで注釈付けされている。
【外１１】
0004659946.tif 000012
逆に、ストリングｓは、全てのラベルを取り除いたストリングｓ'である。
【００３６】
ｓ'をＳTからのラベル付きストリングとし、ｔiをＴの属性とする。
【外１２】
0004659946.tif 000013
次のステップは、ＳTにおける全ての属性が区別可能であるかどうか、即ち、文法Ｓはｋ可逆性であるかどうかを判断するステップである。
【００３７】
［実施例２］
ユーザ属性リストＴは、２つの属性、著者及びタイトルで表され、注釈付きサンプル集合ＳTは、
0004659946.tif 000014
次に、属性である著者のプレフィックスを、Pr(Author)={<b><HTML>,<b><p>String<b>String<b><HTML>,<b><p>String<b><HTML>}とし、属性であるタイトルのプレフィックスを、Pr(Title)={<b>String<b><HTML>}とする。
【００３８】
ＳTを、上のサンプル集合Ｓに対応する注釈付きサンプル集合とする。
【外１３】
0004659946.tif 000015
【００３９】
［定理１］
Ｔを属性リストとし、ＳTを注釈付きサンプル集合とする。Ｔの属性対がいずれもＳTにおいて区別不可能である場合、またこの場合に限って、集合ＳTに対する決定的属性アクセプタがある。注釈付きサンプル集合ＳTにおける全ての属性が区別可能である場合、文法はｋ可逆性であり、ラッパ文法生成を自動的に行うことができ、全ての属性が適切に認識される、ということが定理１により示される。
【００４０】
或いはまた、２つ以上の属性が区別不可能である場合には、部分ラッパ文法を生成することができない、ということは必ずしも意味しない。多くの実際の状況において、自動的に生成された部分ラッパ文法は、ユーザのニーズを十分満たすことができる。部分ラッパ文法は、（区別不可能な属性のみを除いて）他の全ての区別可能な属性に対して生成される。これは重大な利点である。
【００４１】
部分ラッパ文法の生成を可能にするために、属性集合は正規化される、つまり、区別不可能な属性の各群は１つの結合属性に併合される。（上述したように、ある情報プロバイダ若しくは情報源が、同一のストリングにおいてJournalとVolumeとをつなげると、これらはReferenceと呼ばれる１つの属性に結合される。）
【００４２】
【外１４】
0004659946.tif 000016
【００４３】
以下は、属性正規化のいくつかの重要な場合である。
【００４４】
全ての属性が区別可能である場合、ｄi＝{ｔi}である。これは、ラッパ文法を完全に生成することができる、ということを意味する。
【００４５】
ｄ1＝Ｔである場合、全ての属性は区別不可能であり、部分的構文解析系を自動的に生成することができない。これは、ラッパ文法を全く生成することができない、ということを意味する。
【００４６】
等価クラスｄiが属性ｔi及びｔ0＝voidを含む場合、属性ｔiはvoidにより「使用」され、応答ファイルにおいて認識することができないので、ラッパ文法から取り除かなくてはならない。
【００４７】
属性の正規化は、逆プレフィックス等価に基づいて、Ｔの全てのユーザ属性をクラスに区分する。属性集合Ｔ＝{ｔi}の区分πは、正規化属性集合Ｔ'＝{ｄi}と示される。いくつかの併合した属性があれば、部分ラッパ文法の生成は可能である。
【００４８】
［可逆性指数ｋ］
可逆性指数ｋは、ＨＴＭＬファイルの複雑性の測度である。例えば、そのＨＴＭＬファイルが（実施例１のように）比較的単純である場合、ｋの値は小さい（最小値は１）。より複雑なＨＴＭＬファイルにおいては、ｋの値は、２、３又はそれ以上というように、より大きくなり得る。性能という観点からすれば、文法がより短くなり、処理（構文解析）がより速くなるので、ｋの値は小さい方が好ましい。しかし、ｋの値が大きいほど、ラッパ文法がより複雑で、より多くの情報を抽出することができる、ということを意味する。
【００４９】
属性集合の正規化区分が作成し終わると、Ｔ'における２つのクラス（属性）が共通の逆プレフィックスを有することはない。ｔi及びｔjを、Ｔ'における２つの属性とする。
【外１５】
0004659946.tif 000017
【００５０】
【外１６】
0004659946.tif 000018
【００５１】
［実施例３］
上の実施例２に示された集合の例に関して、属性である著者及びタイトルのプレフィックス、つまり、Pr(Author)={<b><HTML>, <b><p>String<b>String<b><HTML>,<b><p>String<b><HTML>}及びPr(Title) ={<b>String<b><HTML>}を得る。次に、著者とタイトルとの最小結合指数ｋは、k(Author,Title)=2で表される。
【外１７】
0004659946.tif 000019
値ｋ(Ｔ')は、注釈付きサンプル集合ＳTの正規化により得られる属性集合Ｔ'に対応する、正則言語の可逆性指数を示す。
【００５２】
［ラッパ文法生成（帰納）］
前のセクションにおいて得られる可逆性指数ｋが与えられたとすると、上述した定義を適用することにより、ｋ可逆性属性アクセプタを推定することができる。プレフィックスツリーアクセプタＡ0＝ＰＡ(ＳT)から始めて、ｋ可逆性状態を侵害する状態を併合することにより、アクセプタＡ1,Ａ2,...を生成する。これらの状態を侵害するような状態対がなくなったら、その結果が、サンプル集合ＳTに対する最終属性ｋ可逆性アクセプタである。
【００５３】
【外１８】
0004659946.tif 000020
【００５４】
［実施例４］
実施例２に示された注釈付きサンプル集合に関して、図６(ａ)は、初期プレフィックスツリーアクセプタを示している。次に、図６(ｂ)〜図７(ｂ)は、属性アクセプタの２可逆性により行われる併合ステップを示している。各ステップにおける併合状態は、矢印により示されている。図７(ｂ)における最終属性アクセプタは、図１におけるアクセプタと同等である、ということに注意されたい。
【００５５】
図４を参照すると、自動ラッパ文法生成方法を、行うべき一連のステップとして説明することができる。特定フォーマットのサンプルＨＴＭＬファイルの集合、及びユーザが選択した又は所定の属性の集合を提示する（ステップ５０）。属性集合Ｔ＝{ｄ0＝void,ｔ1,ｔ2...}からの属性で帰属可能トークンを注釈付けすることにより、サンプルＨＴＭＬファイルの集合を前処理して、注釈付きサンプル集合を形成する（ステップ５２）。この注釈付きサンプル集合を評価して（ステップ５４）、ラッパ文法生成が可能であるかどうかを判断する。
【外１９】
0004659946.tif 000021
次に、ラッパ文法生成が完全に可能であるかどうかを確認する（ステップ５６）。|Ｔ'|＝|Ｔ|である場合には、完全なラッパを自動的に生成することができ、この完全なラッパは、ラッパ文法を生成し続けることができる（ステップ５８）。次に、部分的文法生成が可能であるかどうかを確認する（ステップ６０）。得られた区分が１つのクラスを含む、つまり|Ｔ'|＝１である場合には、ラッパを自動的に生成することができない（ステップ６２）。１＜|Ｔ'|＜|Ｔ|である場合には、部分ラッパを自動的に生成することができる。属性集合を正規化する（ステップ６４）。１＜|Ｔ'|である場合には、Ｔ'に対する最小可逆性指数ｋを計算する。プレフィックスツリーアクセプタＡ0を構成し、サンプル集合ＳTからｋ可逆性属性アクセプタを帰納する。正規化サンプル集合を生成し（ステップ６６）、ラッパ文法を生成する（ステップ５８）。
【００５６】
いずれかの等価クラスｄiが属性ｔ0＝void及びｔiを含み、ｉ＞０である場合には、属性ｔiは、void属性により使用され、自動ラッパ生成において認識することができない、ということに注意されたい。さらにＨＴＭＬサンプルファイルがある場合には（ステップ６８）、方法はステップ５２へ戻る。ない場合には、ラッパ文法が生成される（ステップ７０）。この方法により生成された属性アクセプタは、情報プロバイダからの応答を受入れて、トークンをユーザ属性に割当てる、正則文法に対応する。
【００５７】
［増分属性アクセプタ］
自動ラッパ文法生成方法は増分である。第１に、初期サンプル集合に現れるのに、情報源からの応答の全ての文法的詳細を必要としない。このような不完全なサンプル集合から生成される属性アクセプタは、同じ（不完全な）構造を有する全ての応答だけでなく、サンプルファイルも受入れる。第２に、情報源からの応答が、前のサンプルに現れていない文法的要素を含んでいる度に、この方法は、初期サンプル集合に対して用いたのと同じ処理に続いて、アクセプタを更新する。この差がいずれの帰属可能トークンも含まない場合、更新はされないままであるか、そうでなければ、デザイナーに、帰属可能トークンを注釈付けして注釈付きサンプル集合を更新するように、依頼する。応答ファイルにおける新しい文法的要素により、いくつかのプレフィックス値を再検討することができるようになるか、或いは、いくつかの区別可能なユーザ属性を区別不可能なものに変換することさえもできるようになる、ということに注意されたい。
【００５８】
ラッパ文法デザイナーによりマーク付けされたサンプルから学習したことを用いる本発明の方法は、（例えば、）他の方法において用いられた固定的手法よりも効率的である、ということがわかる。２１のＨＴＭＬラッパ文法を分析すると、これら全てをｋ可逆性文法が含むことができ、このうち１２が１可逆性文法、８つが２可逆性文法、１つが３可逆性文法である。
【００５９】
さまざまなハードウェアプラットフォームにおいて用いることのできるポータブルソースコードを提供するような、ソフトウェア開発環境を用いるソフトウェアにおいて、本発明は容易に実施することができる、ということは認められるであろう。或いは、ここに開示したシステムは、標準論理回路を用いるハードウェアにおいて、部分的に又は全体的に実施することができる。このシステムを実施するのにソフトウェアを用いるかハードウェアを用いるかは、システムの速度及び効率条件に依って、また、特定の機能及び特定のソフトウェア又はハードウェアシステム、並びに、用いられる特定のマイクロプロセッサ又はマイクロコンピュータシステムに依っても異なる。
【００６０】
本発明を、特定の実施の形態に関して説明してきた。第三者が本明細書を図面と合わせて読んで理解すれば、改造物及び代替物を思いつくであろう。この実施の形態は単なる例であり、当業者は、この教示からさまざまな代替物、改造物、変更物、又は改良物を作成してもよく、これらは、前記特許請求の範囲により含まれることが意図される。
【図面の簡単な説明】
【図１】異なるラッパを用いて複数の異なる情報プロバイダからデータを転記及び抽出する、情報ブローカーシステムを示す、ブロック図である。
【図２】ラッパを生成して用いる全体的方法を示す、フローチャートである。
【図３】本発明による、注釈付きサンプル集合を作成する方法を示す、フローチャートである。
【図４】本発明による、ラッパ文法を生成する方法を示す、フローチャートである。
【図５】実施例１に示したサンプル集合ＳTに対する属性アクセプタＡ(Ｔ)を示す、グラフである。
【図６】  (ａ)及び(ｂ)は、実施例２に示したサンプル集合ＳTに対する属性アクセプタＡ(Ｔ)を示す、グラフである。
【図７】  (ａ)及び(ｂ)は、実施例２に示したサンプル集合ＳTに対する属性アクセプタＡ(Ｔ)を示す、グラフである。
【図１】
0004659946.tif 000022
【図２】
0004659946.tif 000023
【図３】
0004659946.tif 000024
【図４】
0004659946.tif 000025
【図５】
0004659946.tif 000026
【図６】
0004659946.tif 000027
【図７】
0004659946.tif 000028