(57)【要約】【課題】  本発明は、文法的に圧縮されたテキスト構造を生成する方法、システム、及び、コンピュータ可読記憶媒体を提供する。【解決手段】    テキストに対して少なくとも１つのテキスト構造を決定し、構文解析文法、生成文法、および、変換規則を決定する。決定されたテキスト構造に基づいてパック構造を決定し、パック構造の変換に基づいて縮小パック構造を決定する。縮小パック構造および曖昧性解消モデルに基づいて候補構造を決定し、生成文法および候補構造に基づいて、文法的に圧縮されたテキスト構造を決定する。【選択図】      図２
2004342104.tif 000002
【特許請求の範囲】
【請求項１】
テキストに対して少なくとも１つのテキスト構造を決定するステップと、
構文解析文法、生成文法、および、変換規則を決定するステップと、
決定された前記テキスト構造に基づいてパック構造を決定するステップと、
前記パック構造の変換に基づいて縮小パック構造を決定するステップと、
前記縮小パック構造および曖昧性解消モデルに基づいて候補構造を決定するステップと、
前記生成文法および前記候補構造に基づいて、文法的に圧縮されたテキスト構造を決定するステップと、
を含むテキストを圧縮する方法。
【請求項２】
前記変換規則は前記パック構造の要素を操作する請求項１に記載の方法。
【請求項３】
前記要素は、言語学的事実(facts)および関連する言語学的文脈である請求項２に記載の方法。
【請求項４】
前記変換規則は、パック構造の前記言語学的事実に直接に適用される請求項３に記載の方法。
【請求項５】
テキストを受信する入力／出力回路と、
メモリと、
テキストのテキスト構造を決定するプロセッサと、
構文解析文法を決定する構文解析文法回路と、
前記構文解析文法に基づいて、テキスト構造ごとのパック構造を決定するパック構造回路と、
少なくとも１つの変換規則に基づいて、パック構造ごとの縮小構造を決定する縮小構造回路と、
縮小構造および曖昧性解消モデルに基づいて候補構造を決定する候補構造回路と、
生成文法を決定する生成文法回路と、
決定された前記生成文法および前記候補構造に基づいて、文法的に圧縮されたテキスト構造を決定する文法的圧縮テキスト構造回路と、
を備えたテキストを圧縮するシステム。
【請求項６】
コンピュータ可読プログラムコードを備えたコンピュータ可読記憶媒体であって、
文法的テキスト圧縮のためにコンピュータをプログラムするのに使用することができる前記コンピュータ可読プログラムコードが、
テキストの少なくとも１つのテキスト構造を決定するステップと、
構文解析文法、生成文法、および、変換規則を決定するステップと、
決定された前記テキスト構造に基づいてパック構造を決定するステップと、
前記パック構造の変換に基づいて縮小パック構造を決定するステップと、
前記縮小パック構造および曖昧性解消モデルに基づいて候補構造を決定するステップと、
前記生成文法および前記候補構造に基づいて、文法的に圧縮されたテキスト構造を決定するステップと、
を備えた、
コンピュータ可読記憶媒体。
【請求項７】
前記テキスト構造は、センテンス、パラグラフ、テキストの選択された部分、および、談話の少なくとも１つである請求項１に記載の方法。
【請求項８】
テキスト構造は、談話文法および統計的モデルの少なくとも１つに基づいて選択される請求項７に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、テキスト構造を圧縮することに関する。
【背景技術】
【０００２】
従来のテキスト圧縮システムは、ｎグラムモデル(n-grams)および単語集合モデル(bag-of-word )に基づいて要約語句を選択および配列することを用いるものである。
【０００３】
従来のテキスト圧縮システムは、言語学的な構文解析および生成に基づくものであり、包含および／または削除のために、センテンスおよびそれに関連する要約に対する構文解析のコーパスから学習された確率モデルに基づいて、テキスト下位構造を選択する。これらの従来のシステムによって生成される要約は、内容を表現してはいるが、それらの要約は、文法性に欠けるために、理解するのが難しい。
【０００４】
なお、本発明に関連する技術として、例えば、特許文献１〜４などがある。
【特許文献１】米国特許第５，７７８，３９７号
【特許文献２】米国特許第５，９１８，２４０号
【特許文献３】米国特許第５，６８９，７１６号
【特許文献４】米国特許第５，７４５，６０２号
【発明の開示】
【発明が解決しようとする課題】
【０００５】
本発明によるシステムおよび方法は、文法的に圧縮されたテキスト構造を生成する。
【課題を解決するための手段】
【０００６】
本発明によるシステムおよび方法は、構文解析文法を用いて、テキスト構造にパック構文解析構造を割り当てる。そして、パック構造を縮小するために、圧縮または簡略化のような変換が、適用される。候補構造が、縮小パック構造の曖昧性解消に基づいて、決定される。さらに、本発明によるシステムおよび方法は、文法的に正しい生成文法に基づいて、候補構造からセンテンスのような文法的に圧縮されたテキスト構造を決定する。
【０００７】
本発明の第１の態様のテキストを圧縮する方法は、テキストに対して少なくとも１つのテキスト構造を決定するステップと、構文解析文法、生成文法、および、変換規則を決定するステップと、決定された前記テキスト構造に基づいてパック構造を決定するステップと、前記パック構造の変換に基づいて縮小パック構造を決定するステップと、前記縮小パック構造および曖昧性解消モデルに基づいて候補構造を決定するステップと、前記生成文法および前記候補構造に基づいて、文法的に圧縮されたテキスト構造を決定するステップと、を含む。
【０００８】
本発明の第２の態様のテキストを圧縮するシステムは、テキストを受信する入力／出力回路と、メモリと、テキストのテキスト構造を決定するプロセッサと、構文解析文法を決定する構文解析文法回路と、前記構文解析文法に基づいて、テキスト構造ごとのパック構造を決定するパック構造回路と、少なくとも１つの変換規則に基づいて、パック構造ごとの縮小構造を決定する縮小構造回路と、縮小構造および曖昧性解消モデルに基づいて候補構造を決定する候補構造回路と、生成文法を決定する生成文法回路と、決定された前記生成文法および前記候補構造に基づいて、文法的に圧縮されたテキスト構造を決定する文法的圧縮テキスト構造回路と、を備えている。
【０００９】
本発明の第３の態様のコンピュータ可読記憶媒体は、コンピュータ可読プログラムコードを備えたコンピュータ可読記憶媒体であって、文法的テキスト圧縮のためにコンピュータをプログラムするのに使用することができる前記コンピュータ可読プログラムコードが、  テキストの少なくとも１つのテキスト構造を決定するステップと、構文解析文法、生成文法、および、変換規則を決定するステップと、決定された前記テキスト構造に基づいてパック構造を決定するステップと、前記パック構造の変換に基づいて縮小パック構造を決定するステップと、前記縮小パック構造および曖昧性解消モデルに基づいて候補構造を決定するステップと、前記生成文法および前記候補構造に基づいて、文法的に圧縮されたテキスト構造を決定するステップと、を備えている。
【発明を実施するための最良の形態】
【００１０】
図１は、本発明による典型的な文法的テキスト圧縮システムの概略図である。文法的テキスト圧縮システム１００、および、テキスト１０００へのアクセスを通信リンク９９を介して提供する情報レポジトリ２００には、ウェブ対応型パーソナルコンピュータ３００、ウェブ対応型タブレットコンピュータ４００、および、電話５００を接続することができる。
【００１１】
情報レポジトリ２００は、ＨＴＭＬ、ＸＭＬ、および／または、ＷＭＬでコード化されたものを提供するウェブサーバ、Ｗｏｒｄ（登録商標）ドキュメントおよび／またはＰＤＦ（登録商標）ドキュメントへのアクセスを提供するディジタルライブラリ、または、テキスト１０００へのアクセスを提供するその他の何らかの良く知られている方法かまたは今後開発されるであろう方法を含む。
【００１２】
第１の実施形態において、ウェブ対応型タブレットコンピュータ４００のユーザは、テキスト１０００の圧縮されたバージョンを要求することを開始する。一実施形態においては、圧縮されたテキストの要求は、文法的テキスト圧縮システム１００によって仲介され、その文法的テキスト圧縮システム１００は、テキスト圧縮バージョンの要求を受信し、その要求を通信リンク９９を介して情報レポジトリ２００へ転送する。
【００１３】
情報レポジトリ２００は、要求されたテキスト１０００をリトリーブし、文法的テキスト圧縮システム１００へ転送し、その文法的テキスト圧縮システム１００は、構文解析文法を使用し、テキスト構造に対応するパック構造を決定する。
【００１４】
変換がパック構造に適用され、縮小されたパック構造が決定される。その縮小パック構造の曖昧性解消モデルに基づいて、候補構造が決定される。例えば、有望な候補構造を表現する確率的曖昧性解消モデルおよび／またはその他の曖昧性解消モデルが決定され、縮小パック構造に適用され、有望な候補構造が選択される。しかしながら、すべての候補構造が、必ずしも、文法的な英語のセンテンスに対応しなければならないわけではない。生成文法が、候補構造に適用され、文法的なセンテンスに対応する候補構造が決定される。生成の後、文法的なセンテンスに対応する候補構造は、順位づけられる。例えば、センテンス長の縮小率が、確率モデルまたは予測モデルから得られた候補の順位と組み合わせられてもよい。その縮小パック構造から得られた総合的に最も高い順位を有するテキスト構造が、選択される。
【００１５】
別の実施形態においては、電話５００のユーザが、情報レポジトリ２００に含まれるテキスト１０００の圧縮されたバージョンを要求する。テキスト１０００の要求は、（図示しない）自動音声認識装置、電話翻音オペレータ(telephone transcription operator)、または、音声要求を認識するその他の何らかの方法によって処理される。認識された音声要求は、通信リンク９９を介して情報レポジトリ２００へ転送され、その情報レポジトリ２００は、テキスト１０００を、通信リンク９９を介して文法的テキスト圧縮システム１００へ転送する。文法的テキスト圧縮システム１００は、テキスト構造を決定する。変換規則がテキスト構造に適用され、縮小パック構造が決定される。その結果として得られた縮小パック構造は、曖昧性解消モデルおよび決定された候補構造を用いて、曖昧性を解消される。異なる実施形態においては、確率的曖昧性解消が、候補構造を決定するのに使用されてもよい。文法的に正しい生成文法が、候補構造に対応する文法的圧縮センテンスを決定する。文法的圧縮センテンスは、通信リンク９９を介して電話５００へ転送され、（図示しない）音声合成器を用いて出力される。
【００１６】
第３の実施形態においては、ウェブ対応型コンピュータ３００のユーザが、情報レポジトリ２００に存在するテキスト１０００の圧縮バージョンを要求することを開始する。この要求は、文法的テキスト圧縮システム１００によって仲介される。例えば、文法的テキスト圧縮システム１００は、プロキシサーバとして使用されてもよく、情報レポジトリ２００へのアクセスを仲介し、かつ、要求されたテキスト１０００の圧縮バージョンを提供する。異なる実施形態においては、文法的テキスト圧縮システム１００は、情報レポジトリ２００またはウェブ対応型コンピュータ３００内に含まれ、あるいは、通信リンク９９を介してアクセスすることのできるいずれかの場所に配置される。
【００１７】
情報レポジトリ２００は、テキスト１０００の圧縮バージョンの要求を受信し、要求されたテキスト１０００をリトリーブし、それを通信リンク９９を介して情報圧縮システム１００へ転送する。テキスト圧縮システム１００は、テキスト１０００のテキスト構造に基づいてパック構造を決定する。縮小パック構造が、パック構造および変換規則に基づいて決定される。曖昧性解消モデルまたは予測モデルが使用され、縮小パック構造に基づいて、候補構造が決定される。文法的に正しい生成文法が候補構造に適用され、テキスト１０００の文法的圧縮センテンスが決定される。要求されたテキスト１０００の圧縮バージョンに対応する文法的圧縮テキストセンテンスが、通信リンク９９を介して転送され、ウェブ対応型パーソナルコンピュータ３００上でユーザに表示される。
【００１８】
図２は、本発明による文法的テキスト圧縮の典型的な方法を示すフローチャートである。処理は、ステップＳ１０から開始し、すぐにステップＳ２０へ進み、そのステップＳ２０において、圧縮されるべきテキストが決定される。テキストは、ファイルから選択されてもよく、ユーザによって入力されてもよく、あるいは、何らかの良く知られているかまたは今後開発されるであろう選択および／または入力する方法を用いて決定されてもよい。そして、制御はステップＳ３０へ進み、そのステップＳ３０において、そのテキストの言語特徴が、決定される。
【００１９】
別の実施形態においては、テキストの言語特徴は、ＸＭＬおよび／またはＨＴＭＬ言語識別タグ、テキストの言語学的解析、または、何らかの良く知られているかまたは今後開発されるであろう言語決定方法を用いて決定される。そして、制御はステップＳ４０へ進む。
【００２０】
ステップＳ４０において、構文解析文法が決定される。構文解析文法は、決定された言語特徴、テキストのジャンル、および／または、何らかの良く知られているかまたは今後開発されるであろうテキスト特徴に基づいて決定される。例えば、「英語」（言語）および「新聞」ジャンル特徴に基づいた第１の構文解析文法が、選択される。「英語」（言語）および「科学関係出版物」ジャンル特徴に基づいた第２の構文解析文法が、英語「生物工学」記事を構文解析するために選択される。このようにして、構文解析文法が選択され、その構文解析文法が、それぞれのテキストに対応する言語構造を認識する。異なる実施形態においては、構文解析文法は、予め決定された汎用文法、テキストに基づいた文法、または、何らかの良く知られているかまたは今後開発されるであろうテキスト特徴を用いて決定された文法である。そして、制御は、ステップＳ５０へ進む。
【００２１】
ステップＳ５０において、生成文法が決定される。生成文法は、生成されるテキスト構造の文法性を保証するものである。生成文法は、構文解析文法と同じものであってもよい。例えば、語彙・機能文法(lexical functional grammar)、主要語句構造文法(head-phrase structure grammar)、語彙化木結合文法(lexicalized tree adjoining grammar)、結合範疇文法(combinatory categorical grammar)、または、テキストを構文解析しパック構造を決定するのに有効な何らかの良く知られているかまたは今後開発されるであろう文法のいずれか１つまたはそれらを組み合わせたものが、本発明において使用されてもよい。本発明の一実施形態においては、言語学的機能文法の文法的に正しいバージョンが、生成文法として使用される。しかしながら、文法的に正しい構造を生成する何らかの良く知られているかまたは今後開発されるであろう文法が、本発明の構文解析部分および生成部分の両方に使用されてもよい。そして、制御は、ステップＳ６０へ進む。
【００２２】
ステップＳ６０において、第１のテキスト構造が決定される。この構造は、限定はしないが、センテンス構造、パラグラフ構造、談話構造、または、何らかの良く知られているかまたは今後開発されるであろう言語学的構造を含んでもよい。例えば、テキストは、センテンスレベルのテキスト構造に分割されてもよい。パラグラフ、談話、および、それらに類似するもののようなより大きなテキスト構造を表現する文法的に圧縮されたセンテンスは、重要なセンテンスを選択する統計学的選択法を用いて、決定されてもよい。
【００２３】
別の実施形態においては、代表的なセンテンスは、米国特許出願第０９／８８３，３４５号および米国特許出願第０９／６８９，７７９号においてＬｉｖｉａ  ＰｏｌａｎｙｉおよびＭａｒｔｉｎ  Ｈｅｎｋ  ｖａｎ  ｄｅｎ  Ｂｅｒｇによって記載される、談話に基づいた技術を用いて選択される。さらに別の実施形態においては、より大きなテキスト構造の代表的なセンテンスは、Ｋｕｐｉｅｃらの米国特許第５，７７８，３９７号（特許文献１）、米国特許第５，９１８，２４０号（特許文献２）、Ｃｈｅｎらの米国特許第５，６８９，７１６号（特許文献３）、米国特許第５，７４５，６０２号（特許文献４）に記載される技術に基づいて選択されてもよい。そして、より大きなテキスト構造に対して選択された代表的なセンテンスは、本発明によるシステムおよび方法を用いて圧縮される。
【００２４】
本発明によるシステムおよび方法は、情報検索業務に従事しているユーザに文脈情報を提供するのに使用されてもよい。例えば、従来の情報検索システムは、検索語を取り囲むテキスト部分をリターンする。これらの非文法的なセンテンス断片は、読むのが難しいので、典型的には、ユーザにとって、認識するのに大きな負担となる。それとは対照的に、本発明は、検索語および文脈情報が文法的センテンス内に提供されので、認識するのに小さな負担しかかけないような形式で文脈情報を提供する。そして、制御は、ステップＳ７０に進む。
【００２５】
ステップＳ７０において、パック構造が、決定されたテキスト構造に基づいて決定される。Ｘｅｒｏｘ  ＸＬＥ環境のパックｆ構造表現が、テキストのパックされた表現として使用されてもよい。しかしながら、本発明を実施する場合、何らかの良く知られているかまたは今後開発されるであろうテキスト表現が、使用されてもよい。上述したように、ＸＬＥパックｆ構造表現は、テキスト構造に対する文脈事実(facts)のリストを決定することによって、自然言語曖昧性を効果的にコード化する。文脈化された事実は、Ｃｉ→Ｆｉの形態を有し、ここで、Ｃｉは、文脈であり、Ｆｉは、言語学的事実である。文脈は、典型的には、テキスト構造またはセンテンスの曖昧性を表現するＡＮＤ−ＯＲフォレストから取り出された一組の選択肢である。Ｘｅｒｏｘ  ＸＬＥ環境のパックｆ構造表現に存在するそれぞれの事実は、それぞれの構造において１回しか発生しない。事実の正規化は、要素を検出および変換するのを容易にする。自然言語曖昧性は、１つのパックｆ構造表現に対して可能性のある複数の意味をもたらすことがある。Ｘｅｒｏｘ  ＸＬＥ環境においては、パックｆ構造は、複数の意味をコード化するが、それぞれの意味の共通要素を重複させなくてもよい。したがって、パックｆ構造に含まれる情報を操作する回数が、減少する。そして、制御は、ステップＳ８０へ進む。
【００２６】
ステップＳ８０において、縮小構造が、パック構造の要素に適用された変換に基づいて決定される。パック構造の要素に適用される変換は、あまり重要でない要素を削除し、より簡潔な要素に置換し、および／または、要素を変更することを含んでもよい。ＸＬＥパックｆ構造表現内にコード化された事実は、変換規則に基づいて変換される。変換規則は、事実を追加、削除、または、変更することによって、パック構造表現内にあまり重要でない情報が発生するのを抑制するアクションおよび手順をコード化する。結果として得られた縮小パック構造は、可能性のあるそれぞれの圧縮テキスト構造を効果的にコード化する。そして、制御は、ステップＳ９０へ進む。
【００２７】
ステップＳ９０において、縮小パック構造ごとの候補構造が、縮小パック構造の確率的または予測的な曖昧性解消モデルに基づいて決定される。候補構造は、曖昧性解消の確率的な方法、語彙的な方法、意味論的な方法、または、何らかの良く知られているかまたは今後開発されるであろう方法を用いて決定される。例えば、一実施形態においては、典型的な縮小構造の統計学的解析が、使用される。最尤曖昧性解消モデルが、一組の縮小パック構造に対して決定される。そして、予測曖昧性解消モデルが使用され、最も有望な縮小構造が、属性、属性の組み合わせ、属性値対、動詞語幹の共起、下位範疇化フレーム、規則追跡情報、および／または、テキスト構造およびそれに対応するパック構造の何らかの良く知られているかまたは今後開発されるであろう特徴のような特性関数に基づいて、パック構造から決定される。例えば、本発明による一実施形態においては、訓練データ
2004342104.tif 000003
、に存在するセンテンスｙごとの可能性のある一組の要約された構造Ｓ（ｙ）が、決定される。次の式、すなわち、
【数１】
2004342104.tif 000004
に基づいて、予測曖昧性解消モデルが与えられたセンテンスごとの要約構造の条件付尤度Ｌ（λ）に基づいて訓練される。ここで、ｆは、特性関数であり、ｙおよびｓは、至適標準要約構造対のための元々のセンテンスである。候補構造が、予測曖昧性解消モデルおよび縮小パック構造に基づいて決定される。そして、制御は、ステップＳ１００へ進む。
【００２８】
ステップＳ１００において、最も有望な候補構造に対応する文法的テキスト構造が、文法的に正しい生成文法を用いて決定され、その結果が出力される。
【００２９】
ステップＳ１１０において、圧縮すべきさらなるテキスト構造が存在するかどうかが判定される。圧縮すべきさらなるテキスト構造が存在すれば、制御は、ステップＳ１２０へ進み、次のテキスト構造が選択され、制御はステップＳ７０へ分岐する。さらなるテキスト構造が存在しなくなるまで、ステップＳ７０〜ステップＳ１１０が反復される。そして、制御は、ステップＳ１３０へ進み、そのステップＳ１３０において、圧縮された文法的テキスト構造が、出力される。
【００３０】
圧縮された文法的テキスト構造は、ファイル、ビデオディスプレイ、または、何らかの良く知られているかまたは今後開発されるであろう表示装置に出力される。そして、制御は、ステップＳ１４０へ進み、処理が終了する。
【００３１】
図３は、本発明による典型的な文法的テキスト圧縮システム１００を示す。文法的テキスト圧縮システム１００は、プロセッサ１５、メモリ２０、言語（決定）回路２５、構文解析文法回路３０、生成文法回路３５、パック構造回路４０、縮小（パック）構造回路４５、候補（テキスト）構造回路５０、および、文法的圧縮テキスト構造回路５５を備え、それらのそれぞれは、入力／出力回路１０を介して通信リンク９９に接続される。
【００３２】
文法的テキスト圧縮システム１００は、通信リンク９９を介して、ウェブ対応型コンピュータ３００、ウェブ対応型タブレットコンピュータ４００、電話５００、および、テキスト１０００を含む情報レポジトリ２００に接続することができる。
【００３３】
異なる実施形態においては、ウェブ対応型コンピュータ３００のユーザが、情報レポジトリ２００に含まれるテキスト１０００の圧縮されたバージョンの要求を開始する。圧縮されたテキストは、テキスト内のキーコンセプトをより素早く識別するのに役立つ。あるいは、テキストの圧縮バージョンは、テキストがユーザの目的とする情報に関係する情報を含むかどうかを判定するのに使用される。テキスト１０００の圧縮バージョンは、重要な情報がほとんど除去されていないので、入念に吟味する必要がない。また、テキスト１０００の圧縮バージョンは、ウェブ対応型携帯電話およびウェブ対応型個人用携帯情報端末のような小画面装置上において有益である。また、文法的圧縮は、音声合成器、動的な点字のような触覚型表示装置、または、何らかの良く知られているかまたは今後開発されるであろう表示装置または出力方法の場合、テキスト１０００の文法的に圧縮されたバージョンを決定するのに使用される。
【００３４】
情報レポジトリ２００に存在するテキスト１０００の圧縮バージョンの要求は、ウェブ対応型コンピュータシステム３００から通信リンク９９を介して文法的テキスト圧縮システム１００の入力／出力回路１０へ転送される。プロセッサ１５は、要求を開始し、通信リンク９９を介して、テキスト１０００を情報レポジトリ２００からリトリーブする。情報レポジトリ２００は、ＨＴＭＬ、ＸＭＬ、および／または、ＷＭＬでコード化されたドキュメントを提供するウェブサーバ、ＰＤＦまたはＷｏｒｄの形式でコード化されたドキュメントを提供するディジタル・ライブラリ、および／または、何らかの良く知られているかまたは今後開発されるであろう情報ソースを含む。
【００３５】
情報レポジトリ２００は、要求されたテキスト１０００を通信リンク９９を介して文法的テキスト圧縮システム１００の入力／出力回路１０へ転送する。そして、要求されたテキスト１０００は、メモリ２０へ転送される。プロセッサ１５は、オプションとして、言語決定回路２５を起動し、テキスト１０００に対応する言語を決定する。言語決定回路２５は、テキスト特徴解析、組み込まれた言語識別タグ、または、テキストの言語を決定する何らかの良く知られている方法を使用してもよい。
【００３６】
そして、プロセッサ１５は、構文解析文法回路３０を起動し、構文解析文法を決定する。構文解析文法は、メモリ２０から予め選択およびリトリーブされてもよく、要求されたテキスト１０００の特徴に基づいて動的に選択されてもよく、あるいは、構文解析文法を決定する何らかの方法を用いて決定されてもよい。構文解析文法は、テキスト言語、テキストジャンル、および／または、テキスト特徴に基づいて選択されてもよい。また、言語学的機能文法のような文法的に正しい生成文法が構文解析文法として使用されてもよい。しかしながら、構文解析文法は文法的に正しいものでなくてもよい。
【００３７】
パック構造回路４０が起動され、要求されたテキスト１０００のためのパック構造が決定される。自然言語テキストに関連する曖昧性を効果的にコード化するために、ＸＬＥパック構造表現が使用されてもよい。しかしながら、テキスト構造を表現するその他の方法もまた使用されてもよい。
【００３８】
プロセッサ１５は縮小パック構造回路４５を起動し、パック構造の要素を減少させる。縮小パック構造回路４５は、メモリ２０、ディスク記憶装置、または、その他の記憶装置から、パック構造および予め記憶された変換規則をリトリーブする。変換規則は、パターン部分およびアクション部分を備えてもよい。変換規則の照合パターン部分が検出されたパック構造の部分が、規則のアクション部分に基づいて変換される。変換規則は、テキストの一部分を削除するようなただ１つのアクション、または、複数のアクションを備えてもよい。しかしながら、本発明を実施するために、要求されたテキストに規則を条件付きで適用する何らかの方法が、使用されてもよい。
【００３９】
パック構造の要素への変換規則の適用は、パック構造内にあまり重要でない情報が発生するのを抑制する。変換規則は、受身化、名詞化、または、あまり重要でない情報を減少させるのに有効な何らかの良く知られているかまたは今後開発されるであろう言語学的変換を含んでもよい。
【００４０】
プロセッサ１５は候補構造（決定）回路５０を起動し、縮小構造の曖昧性を解消する。一実施形態においては、確率的曖昧性解消モデルのような予測曖昧性解消モデルが、候補構造ごとの順位スコアまたは尤度スコアに基づいて候補構造を決定するのに使用される。候補構造の尤度スコアは、テキストコーパスにおけるテキスト構造およびそれに対応する縮小構造の統計的解析に基づいて予め決定されたものであってもよい。そして、候補構造回路５０は、尤度スコアまたは順位スコアに基づいて候補構造を順位づける。
【００４１】
そして、文法的圧縮テキスト構造回路５５が起動され、候補構造およびメモリ２０からリトリーブされた文法的生成文法に基づいて圧縮テキスト構造を決定する。決定された文法的圧縮テキスト構造は、オプションとして、さらなる処理のために表示および／または記憶される。
【００４２】
図４は、本発明による典型的なパック構造を変換する方法のより詳細なフローチャートである。処理は、ステップＳ８０から開始し、ステップＳ８１へ進む。ステップＳ８１において、予め決定されたテキスト構造に対応するパック構造が決定される。例えば、テキストは、テキスト構造に分割され、メモリ、ディスク、または、メモリ・ストレージに記憶されてもよい。異なる実施形態においては、テキスト構造は、メモリ・ストレージからリトリーブされ、および／または、動的に決定される。そして、制御はステップＳ８２へ進み、ステップＳ８２において、変換規則が決定される。
【００４３】
変換規則はユーザによって入力されてもよく、メモリ・ストレージからリトリーブされてもよく、あるいは、何らかの方法を用いて入力されてもよい。変換規則は、ＰＥＲＬ言語および／またはＡＷＫ言語のパターン照合技術、ＰＲＯＬＯＧ言語およびＬＩＳＰ言語に関連するコード化、あるいは、変換規則をコード化する何らかの良く知られているかまたは今後開発されるであろう方法を用いてコード化されてもよい。そして、制御はステップＳ８３へ進み、ステップＳ８３において、変換規則が決定される。
【００４４】
変換規則は、メモリからリトリーブされ、ユーザによって動的に入力され、あるいは、何らかの良く知られているかまたは今後開発されるであろう技術を用いて決定される。変換規則のパターン部分は、パック構造内の単語または句のような特定の要素、品詞タグ、あるいは、何らかの良く知られているかまたは今後開発されるであろう言語学的構造または値に対応づけられる。
【００４５】
したがって、典型的なパターンである「付加詞（Ｘ，Ｙ）」は、テキスト表現Ｘにおける一組の付加詞Ｙを決定する。変換規則のアクション部分は、パック構造に含まれる要素のパターン部分照合に基づいて実行される１つかまたはそれ以上のアクションを含んでもよい。規則のアクション部分は、要素を付加し、要素を削除し、要素を変更し、適用された変換規則を記録し、あるいは、何らかの良く知られているかまたは今後開発されるであろうパック構造要素の変換を実行するアクションを含む。そして、制御は、ステップＳ８４に進む。
【００４６】
ステップＳ８４において、縮小パック構造が、パック構造内に含まれる要素に変換規則を適用することによって、決定される。一実施形態においては、変換規則は、アンパックすることなくＸＬＥパック構造要素に変換を適用するのを可能にするＭａｘｗｅｌｌ  ＩＩＩの同時係属出願である共通に譲渡された米国特許出願第１０／３３８，８４６号に記載される技術を用いて、パック構造に直接に適用される。これらの技術は、曖昧なパック構造を変換することに関連する組み合わせ拡張問題を抑制する。ＸＬＥパック構造は、処理効率を改善するが、テキストをコード化する何らかの方法が、使用されてもよい。そして、制御はステップＳ８５へ進み、処理は図２のステップＳ９０に戻る。
【００４７】
図５は、候補構造を決定する本発明による典型的な方法のより詳細なフローチャートである。制御はステップＳ９０から開始し、ステップＳ９１へ進む。
【００４８】
ステップＳ９１において、縮小構造が決定される。縮小構造は、メモリ、ディスク記憶装置、記憶装置からリトリーブされ、動的に決定され、あるいは、何らかの良く知られているかまたは今後開発されるであろう方法を用いて決定される。縮小構造は、パックｆ構造のようなパック構造に変換規則を適用することによって、決定される。典型的な変換規則は、あまり重要でない要素を除去し、明瞭なものにする要素を追加し、名詞化、受身化、および、その他のアクションをサポートするために要素を変更し、および、それらに類似することをなすことによって、パック構造の要素を圧縮する。そして、制御は、ステップＳ９２へ進み、ステップＳ９２において、順位が縮小構造間で決定される。
【００４９】
例えば、それぞれの縮小構造の統計学的な確率順位が、決定されてもよい。そして、制御は、ステップＳ９４に進み、ステップＳ９４において、最も確かと思われる縮小構造が、順位に基づいて決定される。
【００５０】
最も確かと思われる縮小構造は、曖昧性解消モデルに基づいて最も有望な構造を選択することによって決定される。最も有望な候補構造が選択され、制御はステップＳ９５へ進み、そして、処理は図２のステップＳ１００に戻る。
【００５１】
図６は、候補テキスト構造を決定する本発明による典型的な方法のフローチャートである。処理はステップＳ１００から開始し、ステップＳ１０１へ進む。
【００５２】
ステップＳ１０１において、生成文法が決定される。生成文法は、予め記憶されたパラメータに基づいて、動的にユーザ入力に基づいて、あるいは、その他の何らかの選択方法を用いて、選択される。そして、制御はステップＳ１０２へ進む。
【００５３】
ステップＳ１０２において、候補構造が決定される。候補構造は、メモリ、ディスク記憶装置、および、それらに類似するものからリトリーブされてもよい。そして、制御はステップＳ１０３へ進む。
【００５４】
ステップＳ１０３において、文法的センテンスが、予め決定された生成文法および候補構造に基づいて決定される。生成文法は、生成されるセンテンスが文法的に正しいことを保証する。文法的センテンスは、確率モデルまたは予測モデルから得られた候補の順位に加えて、センテンス長の縮小率によって、順位づけられてもよい。縮小パック構造から得られた総合的に最も高い順位を有するセンテンスが、選択される。そして、生成された文法的センテンスは、圧縮された文法的なテキストセンテンスとして出力される。異なる実施形態においては、圧縮された文法的なテキストセンテンスは、オプションとして、メモリ・ストレージに保存され、表示装置に出力され、あるいは、それらに類似することがなされる。そして、制御はステップＳ１０４へ進み、処理は図２のステップＳ１１０に戻る。
【００５５】
図７は、変換規則を記憶する本発明による典型的なデータ構造を示す。第１の典型的な実施形態においては、変換規則７００を記憶するためのデータ構造は、規則識別子部分７０５、規則部分７１０、および、コメント部分７２０を備える。規則部分７１０は、パターン部分およびアクション部分を備える。
【００５６】
規則識別子部分７０５は、個々のそれぞれの規則に識別子を対応づける。規則識別子は、数字識別子、英数字ストリング、または、その他の何らかの個々の規則識別子であってもよい。変換規則を記憶するための典型的なデータ構造の規則部分７１０は、パック構造の要素を照合しかつ変換を実行するのに使用されるパターンおよびアクションを含む。パック構造内の要素が、規則７１０の規則部分に一致すれば、規則７１０の対応するアクション部分に含まれるアクションが適用され、パック構造を変換する。規則７１０のアクション部分に含まれるアクションは、要素を削除し、要素を追加し、要素を変更し、あるいは、何らかの良く知られているかまたは今後開発されるであろう言語学的変換を実行するのに使用されてもよい。規則７１０のアクション部分は、テキストに適用される１つかまたは複数のアクションを含む。規則のオプションとしてのコメント部分７２０は、実行されるアクションを説明するコメントを含む。
【００５７】
変換規則７００を記憶するデータ構造の第１行目のエントリは、規則識別子部分７０５に「１３」を含み、規則７１０のパターン部分に「＋ｉｎ＿ｓｅｔ（Ｘ，＿Ｙ），ＰＲＥＤ（Ｘ，ｏｆ）」を含み、規則７１０のアクション部分に「ｋｅｅｐ（Ｘ，ｙｅｓ）」を含み、また、コメント部分７２０に「「ｏｆ句」を維持する」を含む。
【００５８】
規則識別子部分７０５は規則を識別し、そして、規則追跡または規則履歴を展開するのに使用される。規則７１０のパターン部分、規則７１０のアクション部分、および、コメント部分７２０は、パック構造を変換するための変換規則を備える。センテンス圧縮に関連する規則は、限定はしないが、パック構造の否定語を除いて、付加詞を削除、追加、または、変更し、等位構造の部分を削除し、簡略化し、また、それらに類似することを実行することを含む。変換規則は、結果として得られる縮小構造の文法性または適格性を維持することを強いられないことに注意されたい。したがって、結果として得られた縮小パック構造には、どの英語センテンスにも対応しないものもある。
【００５９】
変換規則７００を記憶するデータ構造の規則部分７１０のパターン部分は、値「＋ｉｎ＿ｓｅｔ（Ｘ，＿Ｙ），＋ＰＲＥＤ（Ｘ，ｏｆ）」を含む。「＋」は、構造ごとに、パターンが、ＰＲＥＤ（Ｘ，ｏｆ）形式の「ｏｆ句」を決定することを示す。
【００６０】
変換規則７００を記憶するデータ構造の規則部分７１０のアクション部分は、パック構造において対応するパターン部分が識別されたときに実行されるアクションを表現するエントリ「ｋｅｅｐ（Ｘ，ｙｅｓ）」を含む。「ｋｅｅｐ（Ｘ，ｙｅｓ）」修正オペレーションは、語句「＋ｉｎ＿ｓｅｔ（Ｘ，＿Ｙ），＋ＰＲＥＤ（Ｘ，ｏｆ）」を有するパック構造に対して実行される。修正オペレーションアクションは、表現Ｘに関連するそれぞれの「ｏｆ句」を維持する。
【００６１】
第２行は、規則識別子部分７０５に「１６１」を含み、規則７１０のパターン部分に「＋ａｄｊｕｎｃｔ（Ｘ，Ｙ），ＰＲＥＤ（Ｘ，ＨＥＡＤ）」を含み、アクション部分に「ｋｅｅｐ（Ｘ，ｙｅｓ）」を含み、また、コメント部分７２０に「ほかの場所で指定された特定の主要語に対して付加詞を維持する」を含む。
【００６２】
第３行は、規則識別子部分７０５に「１」を含み、規則７１０のパターン部分に「＋ａｄｊｕｎｃｔ（Ｘ，Ｙ），ＰＲＥＤ（Ｘ，Ｐ１），ｉｎ＿ｓｅｔ（Ｚ，Ｙ）」を含み、また、アクション部分に「？＝＞ｄｅｌｅｔｅ＿ｎｏｄｅ（Ｚ，ｒ１）」を含む。オプションとしての修正インジケータ「？＝＞」は、この規則がオプションとして任意の付加詞を削除することを指定する。値「オプションとして任意の付加詞を削除する」であるコメント部分７２０は、規則の機能を説明するものである。
【００６３】
第４行は、規則識別子部分７０５に「２０」を含み、規則７１０のパターン部分に「ｃｏｏｒｄ（Ｘ，’＋＿’），＋ｉｎ＿ｓｅｔ（Ｙ，Ｘ）」を含み、また、アクション部分に「＝＝＞ｅｑｕａｌ（Ｙ，Ｙ）」を含む。規則は、等位構造におけるアイテムの自己等価を主張する。コメント部分７２０の値は、規則の機能を説明するものである。
【００６４】
第５行は、規則識別子部分７０５に「２」を含み、規則７１０のパターン部分に「ｃｏｏｒｄ（Ｘ，ＡＮＤ），＋ｉｎ＿ｓｅｔ（Ｙ，Ｘ），ｐｒｅｄ（Ｙ，Ｐ１）」を含み、また、アクション部分に「＝＝＞ｄｅｌｅｔｅ＿ｎｏｄｅ（Ｙ，ｒ２）」を含む。規則は、オプションとして、等位構造からアイテムＹを削除する。コメント部分７２０のエントリは、規則の機能を説明するものである。
【００６５】
最後の行は、規則識別子部分７０５に「２２」を含み、規則７１０のパターン部分に「ｃｏｏｒｄ＿ｆｏｒｍ（Ｘ，ＡＮＤ），ｉｎ＿ｓｅｔ（Ｚ，Ｘ），ｋｅｅｐ（Ｘ，ｙｅｓ）」を含み、また、アクション部分に「＝＝＞ｄｅｌｅｔｅ＿ｂｅｔｗｅｅｎ（［Ｘ，Ｚ］，ｒ２２）」を含む。規則は、等位構造におけるすべてのアイテムが削除されたならば、等位なものを削除する。コメント部分７２０のエントリは、規則の機能を説明するものである。また、後の処理のために、追跡または蓄積された規則履歴内に規則の適用を記録するために、フラグまたは設定が、セットされてもよい。
【００６６】
図８は、２２個の単語を含む典型的な圧縮されるべきセンテンスを示す。
【００６７】
図９は、本発明に基づいて圧縮されるべき典型的なセンテンスに対応する典型的なアンパック構造８００を示す。構造の最初の２つのレベルにおいて、典型的なアンパック構造８００は、ＣＯＯＲＤ要素８０５、ＰＲＥＤ要素８１０および８４０、ＳＵＢＪ要素８１５および８４５、ＸＣＯＭＰ要素８２０および８５０、ＡＤＪＵＮＣＴ要素８２５、ＴＮＳ−ＡＳＰ要素８３０および８６０、および、ＰＡＳＳＩＶＥ要素８３５および８６５を備える。付加詞下位構造内の第３レベルの構造における副詞的分類マーク８０１は、付加詞を「ＡＤＶ−ＴＹＰＥ  ｖｐａｄｖ，ＰＳＥＭ  ｕｎｓｐｅｃｉｆｉｅｄ，ＰＴＹＰＥ  ｓｅｍ」分類に対応させる。
【００６８】
例示的なパック構造は、構文解析文法を用いて、センテンスのテキスト構造「Ａ  ｐｒｏｔｏｔｙｐｅ  ｉｓ  ｒｅａｄｙ  ｆｏｒ  ｔｅｓｔｉｎｇ，ａｎｄ  Ｌｅａｒｙ  ｈｏｐｅｓ  ｔｏ  ｓｅｔ  ｒｅｑｕｉｒｅｍｅｎｔｓ  ｆｏｒ  ａ  ｆｕｌｌ  ｓｙｓｔｅｍ  ｂｙ  ｔｈｅ  ｅｎｄ  ｏｆ  ｔｈｅ  ｙｅａｒ」のコード化を表現する。例示的なパック構造は、「ａ  ｐｒｏｔｏｔｙｐｅ  ｉｓ  ｒｅａｄｙ  ｆｏｒ  ｔｅｓｔｉｎｇ」である第１の構成素８０２と、「Ｌｅａｒｙ  ｈｏｐｅｓ  ｔｏ  ｓｅｔ  ｒｅｑｕｉｒｅｍｅｎｔｓ  ｆｏｒ  ａ  ｆｕｌｌ  ｓｙｓｔｅｍ  ｂｙ  ｔｈｅ  ｅｎｄ  ｏｆ  ｔｈｅ  ｙｅａｒ」である第２の構成素８０４との等位からなる。
【００６９】
図１０は、本発明による例示的な縮小パック構造を示す。縮小パック構造は、ＰＲＥＤ要素８１０、ＳＵＢＪ要素８１５、および、ＸＣＯＭＰ要素８２０、そして、ＡＤＪＵＮＣＴ要素８２５、ＴＳＮ−ＡＳＰ要素８３０、および、ＰＡＳＳＩＶＥ要素８３５を備える。付加詞下位構造内の第３レベルの構造における副詞的分類マーク８０１は、付加詞に関連する様々な分類をコード化する。
【００７０】
図１１は、本発明による第１の例示的な候補構造１０００を示す。構造の最初の２つのレベルにおいて、第１の例示的な候補構造は、ＰＲＥＤ要素８１０、ＳＵＢＪ要素８１５、ＸＣＯＭＰ要素８２０、ＡＤＪＵＮＣＴ要素８２５、ＴＮＳ−ＡＳＰ要素８３０、および、ＰＡＳＳＩＶＥ要素８３５を備える。付加詞下位構造内の第３レベルの構造における副詞的分類マーク８０１は、付加詞が「ＡＤＶ−ＴＹＰＥ  ｖｐａｄｖ，ＰＳＥＭ  ｕｎｓｐｅｃｉｆｉｅｄ，ＰＴＹＰＥ  ｓｅｍ」分類に対応していることを示す。
【００７１】
第１の例示的な候補構造１０００は、等位において第２の構成素８０４を除去する変換規則の適用を表現している。すなわち、第１の例示的なデータ構造は、第２の構成素８０４に関連する、等位（ＣＯＯＲＤ）要素８０５、そして、ＰＲＥＤ要素８４０、ＳＵＢＪ要素８４５、ＸＣＯＭＰ要素８５０、ＴＮＳ−ＡＳＰ要素８６０、および、ＰＡＳＳＩＶＥ要素８６５を除去されている。最も重要な情報である「ａ  ｐｒｏｔｏｔｙｐｅ  ｉｓ  ｒｅａｄｙ  ｆｏｒ  ｔｅｓｔｉｎｇ」は、維持されている。しかしながら、第２の構成素８０４に関連するあまり重要でない情報である「Ｌｅａｒｙ  ｈｏｐｅｓ  ｔｏ  ｓｅｔ  ｒｅｑｕｉｒｅｍｅｎｔｓ  ｆｏｒ  ａ  ｆｕｌｌ  ｓｙｓｔｅｍ  ｂｙ  ｔｈｅ  ｅｎｄ  ｏｆ  ｔｈｅ  ｙｅａｒ」は、除去されている。
【００７２】
図１２は、本発明による第２の例示的な候補構造１１００を示す。構造の最初の２つのレベルにおいて、候補構造１１００は、ＰＲＥＤ要素８１０、ＳＵＢＪ要素８１５、ＸＣＯＭＰ要素８２０、ＴＮＳ−ＡＳＰ要素８３０、および、ＰＡＳＳＩＶＥ要素８３５を備える。
【００７３】
第２の例示的な候補構造１１００は、第２の構成素８０４を除去するために適用された変換規則およびＡＤＪＵＮＣＴ８２５を除去するためのさらなる規則の適用を表現している。第２の例示的な候補構造は、第１の構成素８０２に関連するＡＤＪＵＮＣＴ構造の除去を表現している。「ａ  ｐｒｏｔｏｔｙｐｅ  ｉｓ  ｒｅａｄｙ」という最も重要な情報は、維持されている。しかしながら、あまり重要ではない付加詞情報「ｆｏｒ  ｔｅｓｔｉｎｇ」は、除去されている。
【００７４】
図１３は、本発明による第３の例示的な候補構造１２００を示す。第３の例示的な候補構造１２００は、構造の第１および第２のレベルにおいて、ＰＲＥＤ要素８１０、ＳＵＢＪ要素８１５、ＸＣＯＭＰ要素８２０、ＡＤＪＵＮＣＴ要素８２５、ＴＮＳ−ＡＳＰ要素８３０、および、ＰＡＳＳＩＶＥ要素８３５を備える。付加詞下位構造内の第３レベルの構造における付加詞分類マーク８０１は、付加詞が「ＡＤＪＵＮＣＴ−ＴＹＰＥ  ｐａｒｅｎｔｈｅｔｉｃａｌ，ＰＳＥＭ  ｕｎｓｐｅｃｉｆｉｅｄ，ＰＴＹＰＥ  ｓｅｍ」分類に対応していることを示す。
【００７５】
第３の例示的な候補構造１２００は、曖昧性解消モデルが縮小パック構造に適用されることを表現している。曖昧性解消モデルは、訓練テキストのコーパスから得られた確率的または予測的な曖昧性解消モデル、言語学的規則、または、何らかの良く知られているかまたは今後開発されるであろう曖昧性解消モデルであってもよい。曖昧性解消モデルは、自然言語テキスト構造またはセンテンス構造に必ずしも対応するとは限らない候補構造を選択する。
【００７６】
そして、文法的に正しい生成文法が、決定された候補構造のそれぞれに適用され、確かと思われる文法的テキスト構造またはセンテンスが、生成される。この例においては、テキスト構造における要素の配列が、付加詞分類マーク８０１の値によって示されるように、変更されている。異なる実施形態においては、文法的テキスト構造は、確率モデルまたは予測モデルから得られた順位に加えて、センテンス長の縮小率によって順位づけられる。縮小パック構造から得られた総合的に最も高い順位を有するテキスト構造が、選択される。生成された文法的テキスト構造が、決定され、そして、文法的に圧縮されたテキストセンテンスとして出力される。異なる実施形態においては、文法的に圧縮されたテキストセンテンスは、オプションとして、メモリ・ストレージに保存され、表示装置に出力され、また、それらに類似することがなされる。
【００７７】
図１４は、本発明による第４の例示的な候補構造１３００を示す。構造の最初の２つのレベルにおいて、第４の例示的な候補構造は、ＰＲＥＤ要素８１０、ＳＵＢＪ要素８１５、ＸＣＯＭＰ要素８２０、ＡＤＪＵＮＣＴ要素８２５、ＴＮＳ−ＡＳＰ要素８３０、および、ＰＡＳＳＩＶＥ要素８３５を備える。付加詞下位構造内の第３レベルの構造における付加詞分類マーク８０１は、付加詞が「ＡＤＶ−ＴＹＰＥ  ｓａｄｖ，ＰＳＥＭ  ｕｎｓｐｅｃｉｆｉｅｄ，ＰＴＹＰＥ  ｓｅｍ」分類に対応していることを示す。
【００７８】
第４の例示的な候補構造１３００は、曖昧性解消モデルが縮小パック構造に適用されることを表現している。上述したように、様々な実施形態において、曖昧性解消モデルは、訓練テキストのコーパスから得られた確率的曖昧性解消モデルまたは予測的曖昧性解消モデル、言語学的な規則、または、何らかの良く知られているかまたは今後開発されるであろう曖昧性解消モデルであってもよい。曖昧性解消モデルは、自然言語テキスト構造またはセンテンス構造に必ずしも対応するとは限らない候補構造を選択する。
【００７９】
文法的に正しい生成文法が、それぞれの候補構造に適用され、確かと思われる文法的テキスト構造またはセンテンスが、生成される。この場合、要素の配列の変更が、付加詞分類マーク８０１の値によって示される。異なる実施形態においては、文法的テキスト構造は、確率モデルまたは予測モデルから得られた順位に加えて、センテンス長の縮小量によって順位づけられる。縮小パック構造から得られた総合的に最も高い順位を有するテキスト構造が、選択される。そして、所望の圧縮特徴を有する生成された文法的テキスト構造が、決定され、文法的に圧縮されたテキストセンテンスとして出力される。異なる実施形態においては、文法的に圧縮されたテキストセンテンスは、オプションとして、メモリ・ストレージに保存され、表示装置に出力され、また、それらに類似することがなされる。
【００８０】
図１５は、例示的な候補テキストデータ構造１４００を示す。候補テキスト構造データ構造１４００は、候補構造ＩＤ部分１４１０、候補テキスト構造部分１４２０、および、順位部分１４３０を備える。候補テキストデータ構造１４００のＩＤ部分１４１０は、候補テキスト構造部分１４２０が生成される候補構造を識別する。順位部分１４３０は、生成された候補テキスト構造の長さ、文法性、および、適合度に基づいた候補テキスト構造の順位を示す。例えば、候補テキストデータ構造１４００の第１行は、候補構造ＩＤ部分１４１０に「Ａ２」を含み、候補テキスト構造部分１４２０に「ａ  ｐｒｏｔｏｔｙｐｅ  ｉｓ  ｒｅａｄｙ」を含み、また、順位部分１４３０に「１」を含む。これは、「Ａ２」候補構造から生成された候補テキスト構造「Ａ  ｐｒｏｔｏｔｙｐｅ  ｉｓ  ｒｅａｄｙ」がテキスト構造を最もよく圧縮していることを示す最も高い順位「１」に対応することを示す。
【００８１】
図１６は、本発明による例示的な規則追跡記憶構造１５００を示す。例示的な規則追跡記憶構造１５００は、規則識別子部分１５０５、規則部分１５１０、および、コメント部分１５２０を備える。
【００８２】
第１行は、規則追跡エントリが規則１３の適用に対応していることを示す規則識別子部分１５０５エントリ「１３」を含む。
【００８３】
規則部分１５１０エントリ「ｋｅｅｐ（ｖａｒ（９８），ｏｆ）」は、規則識別子部分１５０５内に示される規則の適用において実行される個々のアクションの１つである。規則追跡記憶構造１５００のコメント部分１５２０は、値「規則１３によって実行されるアクション」を含む。コメント部分は、それぞれの規則追跡エントリの機能に関する注釈を提供する。
【００８４】
上述した文法的テキスト圧縮システム１００の回路１０〜５５のそれぞれは、ＡＳＩＣ、あるいは、ＦＰＧＡ、ＰＤＬ、ＰＬＡ、または、ＰＡＬを用いて、あるいは、個別論理素子または個別回路素子を用いて、適切にプログラムされた汎用コンピュータの一部分として実施されてもよい。上述した文法的テキスト圧縮システム１００の回路１０〜５５それぞれが有する特定の形態は、設計上の選択に関することであり、この分野に精通する者には、明白なことであり、容易に考え出すことができるものである。
【００８５】
上述した文法的テキスト圧縮システム１００および／またはそれぞれの様々な回路は、それぞれ、プログラムされた汎用コンピュータ、専用コンピュータ、マイクロプロセッサ、または、それらに類似するもので動作するソフトウェアルーチン、マネージャー、または、オブジェクトとして実施されてもよく、また、上述した様々な回路は、通信ネットワークに組み込まれた１つかまたはそれ以上のルーチンとして、サーバに存在する資源として、または、それらに類似するものとして、実施されてもよい。また、上述した文法的テキスト圧縮システム１００および様々な回路は、文法的テキスト圧縮システム１００を、ウェブサーバまたはクライアント装置のハードウェアおよびソフトウェアのようなソフトウェアおよび／またはハードウェアシステムの中に物理的に組み込むことによって、実施されてもよい。
【００８６】
図３に示されるように、メモリ２０は、書き換え可能な、揮発性の、あるいは、不揮発性のメモリ、または、書き換え不能な、または、固定メモリの何らかの適切な組み合わせを用いて、実施されてもよい。
【００８７】
図１および図３に示される通信リンク９９は、それぞれ、何らかの良く知られているかまたは今後開発されるであろう接続システム、または、装置を接続しかつ通信を容易にするのに使用することのできる機構であってもよい。
【００８８】
上述した例示的な実施形態に基づいて、本発明を説明したが、この分野に精通する者は、多くの別法、変更、および、変形を容易に考え出すことができることは明白である。
【図面の簡単な説明】
【００８９】
【図１】本発明による例示的な文法的テキスト圧縮システムの概略図である。
【図２】文法的にテキストを圧縮するための本発明による例示的な方法のフローチャートである。
【図３】本発明による例示的な文法的テキスト圧縮システムを示す図である。
【図４】文法的にテキストを圧縮するための本発明による例示的な方法のより詳細なフローチャートである。
【図５】候補構造を決定するための本発明による例示的な方法のより詳細なフローチャートである。
【図６】候補テキスト構造を決定するための本発明による例示的な方法のフローチャートである。
【図７】変換規則を記憶するための本発明による例示的なデータ構造を示す図である。
【図８】圧縮されるべき例示的なセンテンスである。
【図９Ａ】例示的なアンパック構造を示す図である。
【図９Ｂ】例示的なアンパック構造を示す図である。
【図１０】本発明による例示的なパック構造を示す図である。
【図１１】本発明による第１の例示的な候補構造を示す図である。
【図１２】本発明による第２の例示的な候補構造を示す図である。
【図１３】本発明による第３の例示的な候補構造を示す図である。
【図１４】本発明による第４の例示的な候補構造を示す図である。
【図１５】本発明による例示的な候補テキストデータ構造を示す図である。
【図１６】本発明による例示的な規則追跡記憶構造を示す図である。
【符号の説明】
【００９０】
９９  通信リンク
１００  文法的テキスト圧縮システム
２００  情報レポジトリ
３００  ウェブ対応型パーソナルコンピュータ
４００  ウェブ対応型タブレットコンピュータ
５００  電話
１０００  テキスト
【図１】
2004342104.tif 000005
【図２】
2004342104.tif 000006
【図３】
2004342104.tif 000007
【図４】
2004342104.tif 000008
【図５】
2004342104.tif 000009
【図６】
2004342104.tif 000010
【図７】
2004342104.tif 000011
【図８】
2004342104.tif 000012
【図９Ａ】
2004342104.tif 000013
【図９Ｂ】
2004342104.tif 000014
【図１０】
2004342104.tif 000015
【図１１】
2004342104.tif 000016
【図１２】
2004342104.tif 000017
【図１３】
2004342104.tif 000018
【図１４】
2004342104.tif 000019
【図１５】
2004342104.tif 000020
【図１６】
2004342104.tif 000021