(57)【特許請求の範囲】
【請求項１】
ＸＭＬタイプの構造化文書の復元のためのバイナリ文書の復号化方法であって、
ａ．前記構造化文書は、
１）前記構造化文書の構造を定義する少なくとも１つの木構造スキーマと関連付けられ、また、
２）前記構造化文書のデータ・セットを表すネストになった構造要素を含み、
ｂ．前記バイナリ文書は、それを簡潔に表すために前記木構造スキーマを用いて符号化され、
ｃ．前記復号化は、前記構造化文書を復元するために前記木構造スキーマを用いるステップを含む
ことを特徴とする方法。
【請求項２】
前記復号化は、前記木構造スキーマの知識を用いる復号化プロセスをモデル化するステップと、前記構造化文書の復元のために、前記構造化文書の異なるデータ・セットに適用された異なる解凍アルゴリズムを選択することにより、前記木構造スキーマを用いての復号化を開始させるステップとを含む、請求項１に記載の方法。
【請求項３】
前記構造スキーマを正規化して、前記構造スキーマの構造要素の単一の所定の順番を得るステップを含む、請求項１又は２に記載の方法。
【請求項４】
前記符号化文書と共に前記構造スキーマを伝送するステップを更に含む、請求項１又は２に記載の方法。
【請求項５】
符号化したデータ・セットにそれぞれ前記符号化文書中においてタグを付すことにより、特定の符号化データ・セットに対し、前記符号化文書中において前記特定の符号化データ・セットより前のデータ・セットを復号化することなく、直接アクセスすることを可能にした、請求項１又は２に記載の方法。
【請求項６】
構造要素のグループの階層レベル数を減らすことにより前記構造スキーマを最適化するステップを更に含む、請求項１又は２に記載の方法。
【請求項７】
更に各構造要素を前記構造スキーマ中において、可能な出現回数のセットと関連付け、前記可能な出現回数は、前記構造要素を有する前記符号化文書の符号化したデータ・セットが、１つ上の階層レベルのデータ・セット中に現れることができる回数を示す、請求項１又は２に記載の方法。
【請求項８】
前記符号化文書が、元の構造化文書の各データ・セットごとに、前記データ・セットの構造を定義する構造要素に対応する遷移数と、前記データ・セットの２進値とを含む、請求項１又は２に記載の方法。
【請求項９】
前記構造スキーマの構造要素の少なくとも一部の構造要素がそれぞれ、前記符号化文書中において、前記構造要素によって定義される構造を有するデータ・セットの、１つ上の階層レベルのデータ・セット中における出現回数と関連付けられる、請求項１又は２に記載の方法。
【請求項１０】
同じタイプの符号化データ・セットの数回の出現のグループの終わりに、最終状態番号への遷移を表すバイナリ・シーケンスによって、前記符号化文書中においてタグが付される、請求項１又は２に記載の方法。
【請求項１１】
前記構造要素は、構造化された、あるいは、構造化されない要素グループに分解される構造化されたルート要素、および、構造中の最下位レベル要素に対応する基本要素のカテゴリーに分類され、前記基本要素はそれぞれ情報タイプに関連付けられ、前記基本要素の少なくとも１つの情報タイプは、適用される復号化アルゴリズムに関連付けられる、請求項１又は２に記載の方法。
【請求項１２】
符号化文書中において、前記復号化アルゴリズムに関連付けられた情報タイプを有する符号化データ・セットに遭遇したときに、前記復号化アルゴリズムを実行するステップを含む、請求項１１に記載の方法。
【請求項１３】
前記構造スキーマの構文解析を実行するステップを含む、請求項１又は２に記載の方法。
【請求項１４】
符号化工程中に、少なくとも１つの有限オートマトンを発生させるために構造スキーマをコンパイルすることと、復号化工程中に、前記有限オートマトンを前記符号化文書の符号化データ・セットに実行することとを含み、前記有限オートマトンは、それぞれが前記構造要素を表す遷移によって相互に連結された状態を含む、請求項１又は２に記載の方法。
【発明の詳細な説明】
【０００１】
本発明は、構造化文書を圧縮／解凍する方法に関する。
【０００２】
本発明は、これに限定する訳ではないが、特にデジタル伝送ネットワークを介した画像または画像シーケンス、ビデオまたは音声データなどの文書の伝送、およびそのような文書の記憶に適用される。
【０００３】
現在、いくつかのデジタル文書の圧縮アルゴリズムが存在する。圧縮アルゴリズムには、データ・タイプを考慮せずに文書のバイナリ・データを直接処理するものがある。こうしたアルゴリズムには、どの文書でも処理できるという利点があるが、一般的には、音声または画像タイプである大容量文書の処理には効果的ではない（圧縮率が低い）。
【０００４】
さらに、他の圧縮アルゴリズムとして、より効率的なものとして、例えば画像や音声など、あるデータ・タイプに特別に適合させたものが知られるが、対象とするデータだけを含むのではない文書に適用すると、使用することができないか、あるいは効果的でないという結果になる。
【０００５】
しかし、利用され、データ伝送ネットワークでやり取りされる文書は、１つの構造にまとめられたいくつかの情報タイプを含むようになりつつある。
【０００６】
構造化文書とは、それぞれがタイプと関連付けられ、主に階層的な関係に従って、ともに配列されたデータ・セットの集合である。こうした文書にはＳＧＭＬ、ＨＴＭＬ、ＸＭＬなどの構造化言語が使用され、特に、文書を構成する異なるデータ・セットを区別することが可能になる。これに対し、いわゆる線形文書では、文書の内容情報はプレゼンテーションおよびタイピングの情報と混在している。
【０００７】
このため、構造化文書は、文書の異なるデータ・セットを区分するロケータまたはマーカを含む。ＳＧＭＬ、ＸＭＬ、またはＨＴＭＬフォーマットの場合、「タグ」と称されるこうしたロケータは「＜ＸＸＸＸ＞」と「＜／ＸＸＸＸ＞」の形をとり、最初のマーカはデータ・セット「ＸＸＸＸ」の始まりを意味し、２番目のマーカはこのセットの終わりを意味する。データ・セットは、いくつかのより低いレベルのデータ・セットからなることができる。このように、構造化文書は階層的あるいは木構造のスキーマを有し、各ノードはデータ・セットを表し、より低いレベルのデータ・セットを含むデータ・セットを表す、より高い階層レベルのノードに連結される。この木構造の枝の最後に位置するノードは、所定タイプのデータを含むデータ・セットを表し、このデータ・セットは、データのサブセットに分解することができない。
【０００８】
一般に、構造化文書は、文書の各データ・セットの情報の構造およびタイプを規則の形で示す、いわゆる構造スキーマと関連付けられる。スキーマは、ネストになったデータ・セット構造のグループによって構築され、これらのグループは、例えば順序付けされたシーケンス、順番付けされた、あるいは、順番付けされていない二者択一の要素グループまたは必須の要素グループなどである。
【０００９】
構造化文書はこのように構造スキーマと関連付けられ、テキスト・データまたはバイナリ・データの形で表される区分マーカを含み、このマーカは、マーカによって画定される他のデータ・セットを、それ自体が含むことのできるデータ・セットを画定する。この結果、このように構造化された文書は、テキスト・データだけでなく、任意の他タイプの情報（例えば音声データ、画像など）も含むことができる。したがって、ある特定のデータ・タイプに固有の圧縮アルゴリズムは、このタイプの文書の処理には効果的でなく、適さない。
【００１０】
本発明の目的は、これらの欠点を取り除くことである。このために、本発明は、文書の構造を定義し、データ・セットを表すネストになった構造要素を含む、少なくとも１つの木構造スキーマと関連付けられた構造化文書を圧縮および解凍する方法を提案し、この構造要素は３つのカテゴリ、すなわち、構造化された、あるいは、構造化されない要素グループに分解される構造化されたルート要素、および構造中の最下位レベルの要素に対応する基本要素、に分類され、各基本要素とルート要素は、情報タイプと関連付けられる。
【００１１】
本発明によれば、初めに、基本要素の少なくとも１つの情報タイプを、適合する圧縮アルゴリズムと関連付け、この方法は次のステップを含む。
−文書の構造スキーマの構文解析を行い、構造スキーマを正規化してスキーマの構造要素の単一の所定の順番を得るステップ、
−正規化した構造スキーマをコンパイルして、ルート要素１つにつき１つの有限オートマトンを得るステップであって、各オートマトンは、それぞれが、構造要素を表す遷移によって相互に連結された状態を含むステップ、および
−文書に有限オートマトンを実行することを含めて構造化文書を圧縮し、圧縮する文書中で前記アルゴリズムと関連付けられた情報タイプのデータ・セットに遭遇すると、前記圧縮アルゴリズムを実行するステップ。
【００１２】
構造スキーマをコンパイルすることにより文書の構造が非常に簡潔に表され、基本構造要素に対応する各データ・セットをある情報タイプと関連付けるとすると、そのタイプに最も合った圧縮アルゴリズムによってデータ・セットを処理することができる。このように、文書が、例えばテキスト・データ、画像、音声データを含む場合、そのデータは構造化文書内に完全に位置し、低レベルの構造要素とあるタイプとに関連付けられる。オートマトンを実行すると、ある圧縮アルゴリズムと関連付けられた基本タイプのデータ・セットの存在を検出し、そのデータに対応するアルゴリズムを順次呼び出して対応するバイナリの情報シーケンスを得、このシーケンスは、出現すると同時に、その圧縮で得られるバイナリ文書に挿入される。
【００１３】
さらにデータ伝送の場合では、伝送される文書が常に同じ構造スキーマを有する場合は、文書を伝送するたびにその構造スキーマを伝送する必要はなく、本発明による方法を用いて得られる圧縮率の点で、さらに利得が生じる。そのスキーマがすでに文書の受け取り側に知られている場合には、スキーマの伝送はさらに無意味になる。例えばＨＴＭＬ文書の場合には、一番最初でさえ、文書スキーマを符号化する必要がない。
【００１４】
有限オートマトンとは状態のセットと理解されたく、各状態は、入力事象のセットと、入力事象ごとにオートマトンのアクティブな状態のセットを定義する遷移関数とに関連付けられる。この定義によると、例えばコード変換テーブルに関して、入力事象ごとに次の状態に対応するテーブル、または再度対応テーブルを示す１つの状態につき１つのテーブルに基づいて、また、オートマトンに含まれる状態と同じだけの多くの行および列を有し、テーブルの各ボックスが２つの対応する状態間の遷移の記述を含む、１つのオートマトンにつき１つのテーブルに基づいて、複数の表現を考えることができる。
【００１５】
解凍する際は、圧縮と同じ方法で構造スキーマを処理して、圧縮に用いられたオートマトンを判定し、全く同一でなくとも少なくとも、同等の構造を有する元のフォーマットに文書を再構築するために圧縮された文書の内容を分析し、圧縮の際に使用された圧縮アルゴリズムに対応する解凍アルゴリズムを実行して、圧縮された文書内に位置するバイナリの情報シーケンスから、元のデータ・セットを復元する。
【００１６】
文書とともに構造スキーマを伝送する場合、本発明による方法は、好ましくは、本来の構造スキーマ、あるいは、変換と正規化の後に得られる構造スキーマ、あるいは、コンパイル後に得られる構造スキーマを伝送するステップを含む。
【００１７】
本発明の実施例の１つによれば、圧縮された文書中に各データ・セットを配置することにより、文書全体、または解凍するセットより前のデータ・セットを解凍する必要なしに、特定の情報要素に直接アクセスすることが可能になる。
【００１８】
本発明の別の実施例によれば、各構造スキーマ要素を、さらに可能な出現回数のセットと関連付け、その構造要素を有するデータ・セットが、それが属する１つ上の階層レベルのデータ・セット中に現れることができる回数を示す。
【００１９】
本発明によるプロセスは、構造要素のグループの階層レベル数を減らすことにより、文書の構造スキーマを最適化するステップを含むことができる。この最適化により、構造スキーマを単純化することができるが、圧縮プロセスの効率はより低くなる。
【００２０】
以下に、添付の図面を参照して、本発明による方法を実施する好ましいモードの１つを非制限的な意味で説明する。
【００２１】
図１は、本発明による方法の様々なステップ間の結びつきを示す。
【００２２】
この方法は、文書の構造を定義する構造スキーマ１と、文書の構造化データとによって構築された構造化文書２を処理するものである。
【００２３】
ＸＭＬスキーマ言語では、構造スキーマは、例えば次のような形である。
0004653381.tif 000002
【００２４】
このスキーマは、「Ｃ」という名の要素は、任意選択のブール・タイプの第１の要素「ａ２」と、常にこの構造中に存在する整数タイプの第２の要素「ａ１」と、それぞれタイプ「ＴＡ」と「ＴＢ」である二者択一の要素「Ａ」および「Ｂ」からなるグループとによって構築された複雑な構造を持ち、要素「Ａ」および「Ｂ」の１回の機会に１つが構造中に現れることを示している。
【００２５】
タイプ「ＴＡ」と「ＴＢ」は、同様の定式化によってこの文書の構造スキーマに定義される。
【００２６】
一般には次の要素グループが文書構造の定義に使用される。
−ＳＥＱ：そのすべてが、指示される順番で文書中に現れなければならない順番付けられた要素のリストを定義する。
−ＣＨＯ：二者択一要素のセットを定義し、グループのうち１要素が現れなければならない。
−ＥＴ：変更されることのない何らかの順序で、そのすべてが文書中に現れなければならない要素のセットを定義する。
−ＥＴＮＯ：すべてが何らかの順序で文書中になければならない要素のセットを定義する。順序は重要でない。
−ＡＮＹ：文書中に現れることが可能なすべての可能な要素のうち、いずれかの要素を含む。
【００２７】
本発明によれば、この定式化をこの方法のステップ１１で分析および変換して、１つの構造要素につき１つのツリーの対応で構文木４を得る。構造要素ＴＣに対応する構文木は、次の式（１）によって表される。
【数１】
0004653381.tif 000003
の式で、
「→」は、ＴＣがこの記号の後に定義される構造に与えられる名前であることを示し、
「（  ）」は、その要素グループを読む優先度を示し、
「，」は、シーケンス・タイプ（ＳＥＱ）の要素グループに対応し、
「｜」は、二者択一要素グループ（ＣＨＯ）を表し、
「＆」は、ＥＴタイプの要素グループを表し、
「＆ＮＯ」は、順番付けられていないＥＴタイプの要素グループを表し、
「｛｝」は、要素を構造要素名または基本タイプ（例えば整数やブール）と関連付け、
「Ａｘ．．ｙ」は、文書中で要素Ａをｘからｙの回数繰り返すことを示し、ｙは中間値を表す「＊」に等しくなることができる。
【００２８】
この定式化では、任意の要素（ＡＮＹ）を表す記号「＄」も使用する。
【００２９】
式（１）は図２ｃに示すツリーで表すことができ、このツリーは、シーケンス・タイプ・グループ４４の１回の出現によって構築されるルート要素「ＴＣ」４３を含む。このグループは、順番付けられていない「ＥＴ」タイプ・グループ４５の１回の出現と、二者択一グループ４６の１回の出現を含む。
【００３０】
グループ４５は、整数「ａ１」とブール「ａ２」の１回の出現によって構築され、グループ４６は、「ＴＡ」タイプの要素「Ａ」と「ＴＢ」タイプの要素「Ｂ」の１回の出現を含む。
【００３１】
ステップ１１で得られるタイプ「ＴＡ」および「ＴＢ」は、例えば次の式によって得られ、
【数２】
0004653381.tif 000004
0004653381.tif 000005
それぞれ図２ａと２ｂに示すツリーによって表される。
【００３２】
タイプ「ＴＡ」３１は、それぞれＥＴタイプとＳＥＱタイプである２つの単一のグループ３３、３４によって構築される単一のシーケンス・タイプ・グループ３２を含む。グループ３３は、それぞれ「ａ３」と「ａ４」という２つの整数タイプの１回の出現を含む。グループ３４は、それぞれ「Ｘ」と「Ｙ」という２つのタイプ「ＴＣ」の１回の出現を含む。
【００３３】
タイプ「ＴＢ」３９は単一のシーケンス・タイプ・グループ４０によって構築され、このグループはそれぞれ「ａ１」と「ａ５」という２つのブールを含む。
【００３４】
以上の説明では、各要素の名前とそのタイプを区別したが、本発明による方法は、このような区別をしない構造化言語にも適用することができる。
【００３５】
さらに、構造要素は決定性でなければならない。換言すると、要素はいくつかの異なる形で解釈することが可能であってはならない。例えば、スキーマ「（ａ｜（ａ，ｂ））」では、「ａ」が現れる場合に「ｂ」がａの後に現れなければならないかどうかが分からない。この目的のために、非決定性のスキーマを決定性スキーマに変換するために、本発明による方法で適用できるアルゴリズムがある。これについては、例えば「Ｒｅｇｕｌａｒ  ｅｘｐｒｅｓｓｉｏｎｓ  ｉｎｔｏ  ｆｉｎｉｔｅ  ａｕｔｏｍａｔａ」（Ｂｒｕｇｇｅｍａｎｎ−Ｋｌｅｉｎ，Ａｎｎｅ、Ｅｘｔｅｎｄｅｄ  Ａｂｓｔｒａｃｔ  ｉｎ  Ｉ．Ｓｉｍｏｎ，Ｈｒｓｇ，ＬＡＴＩＮ  １９９２、ｓ．９７−９８、Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ、ベルリン  １９９２。完全版はＴｈｅｏｒｅｔｉｃａｌ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  １２０、１９７〜２１３、１９９３）を参照されたい。したがって、先に挙げたスキーマは、例えば「（ａ，ｂ０．．１）」と置き替えることができる。
【００３６】
本発明による方法の次のステップ１２では、構文木に変換した構造スキーマの要素に、初めに簡約化または単純化のプロセスを行うことができる。
【００３７】
この簡約化プロセスは、図３に示すように、すべてのツリー３１、３９、および４３から単一の構文木５１を生成することにより、大まかな平坦化を行うものである。
【００３８】
このツリーは事実上、文書中で遭遇する可能性の高いすべての要素タイプのディクショナリを表し、これらの要素は、少なくとも１回（１．．＊）文書中に現れる二者択一タイプのグループ５２に合わせてまとめられる。このツリーでは、複雑なタイプの要素「Ａ」、「Ｂ」、「Ｘ」、および「Ｙ」は「ＡＮＹ」タイプと関連づけられ、異なる要素タイプで（要素「ＴＢ」および「ＴＣ」に）２度現れている要素「ａ１」は、ＸＭＬ言語によるデフォルトの「ｐｃｄａｔａ」タイプか、または、例えば「ｔｅｘｔ」など、最初の文書中にある要素タイプと関連付けられる。これと同じデータ・セットはいくつかの方式で表すことができ、例えば、バイナリ・シーケンスを文字列または整数と考えることもできる。
【００３９】
あるいは、この簡約化プロセスは、構文木をローカルに平坦化して、図４ａから４ｃに３１’、３９’、および４３’で示すツリーを得るものであってもよい。
【００４０】
これら各図では、グループ３２〜３４（図２ａ）、４０（図２ｂ）、および４４〜４６（図２ｃ）をそれぞれ二者択一タイプ・グループ５３、５４、５５に置き換えており、これらのグループは少なくとも１回現れる（１．．＊）。
【００４１】
ツリー「ＴＡ」、「ＴＢ」、および「ＴＣ」には、さらに追加的なプロセスを施して、構造スキーマに生じるあいまい性を除去することができる。
【００４２】
ステップ１２で、ツリー「ＴＡ」、「ＴＢ」、および「ＴＣ」に、スキーマの要素の単一の順番が得られるような方式で、スキーマを再度順番付けすることからなる正規化プロセスも行う。このプロセスでは、前のプロセスで得られた構文木の異なるノードに、２進数を割り当てる。この数は、関連する要素を圧縮する際に用いられる。
【００４３】
この正規化プロセスは、各グループに、そのグループの名前と、すでに順番付けられているそのグループのすべての要素と、下位グループの署名の連接によって構築される署名を割り当てるものである。したがって、図４のグループ５３は、署名「ＣＨＯ．ａ３．ａ４．Ｘ．Ｙ」（または「｜ａ３．ａ４．Ｘ．Ｙ」）と関連付けられる。
【００４４】
この正規化プロセスで、順番付けられたグループ（ＳＥＱ）がすでに正規化されていると考える。したがって正規化するグループは、二者択一タイプ（「ＣＨＯ」）と、「ＥＴ」および「ＥＴＮＯ」グループになる。このプロセスは、下位グループｇｉおよび要素ｅｉからなる各グループＧについて、次のステップを含む。
−グループＧを正規化する前にグループＧの下位グループｇｉを正規化し、正規化アルゴリズムは再帰アルゴリズムであるステップ、
−下位グループｇｉの前にグループＧの任意の要素ｅｉを配列するステップ、
−所定の順序で要素ｅｉを配列するステップ、
−所定の順序で下位グループｇｉを配列するステップ、および
−以上のステップの結果確立される順序に従って、その構成要素（要素および下位グループ）のすべての署名の連接により得られるグループＧの署名を判定するステップ。
【００４５】
グループの構成要素を配列する所定の順序は、構成要素個々の署名の英数字順でも、あるいは、各自の最小出現回数の降順にして、同じ最小出現回数を有する構成要素を英数字順に配列してもよい。
【００４６】
この正規化プロセスは、本発明による方法では必要でないことに留意されたい。スキーマ中に構成要素が現れる順序は、実際には保存してもよい。
【００４７】
この方法の次のステップ１３は、有限オートマトン５の生成である。このプロセスでは、１つの構文木グループにつき１つのオートマトンの対応で、各構文木に基本オートマトンのセットを生成し、次いで、その基本オートマトンを組み合わせる。
【００４８】
図５ａで、１つ下の階層レベルの署名ｍ１、ｍ２〜ｍｎのｎ個の要素からなるシーケンシャル・グループ（ＳＥＱ）のオートマトンは、図に円で表す０からｎ＋１の番号を付けたｎ＋２個の状態を含み、各ノードは、グループ要素に対応する円弧で表す、要素の署名を名前とした遷移によってその次のノードに連結され、最後の遷移Ｆ（状態ｎ＋１に向かう）は、このグループの終わりをマークしている。
【００４９】
図５ｂでは、１つ下の階層レベルの署名ｍ１、ｍ２〜ｍｎのｎ個の要素からなる二者択一タイプ・グループ（ＣＨＯ）のオートマトンは、番号「０」の初期状態と、番号１〜ｎのｎ個の最終状態を含み、状態０は、それぞれｎ個のグループ要素に対応するｎ個の遷移によって最終状態１〜ｎに連結されている。
【００５０】
図５ｃでは、１つ下の階層レベルの署名ｍ１、ｍ２〜ｍｎのｎ個の要素からなるＥＴグループのオートマトンは、ｎ個の要素のすべての可能な組み合わせを表す１＋ｎ＋ｎ（ｎ−１）＋ｎ（ｎ−１）（ｎ−２）＋．．．＋ｎ！個の状態を含む。
【００５１】
この種のオートマトンは、以下のような単純なアルゴリズムによって生成することができる。
0004653381.tif 000006
【００５２】
１つ下の階層レベルの署名ｍ１、ｍ２〜ｍｎのｎ個の要素からなるグループＥＴＮＯのオートマトンは、グループ中の要素の出現順序に関する情報が失われても許容できるか、順序が固定されているのであれば、ＳＥＱのオートマトンでよい。
【００５３】
これらのオートマトン（タイプＣＨＯ、ＥＴおよびＥＴＮＯのグループの場合）は、任意選択の要素、すなわち、可能な出現の総数が（０．．ｋ）の形である要素の回避プロセスを適用することにより最適化することができる。
【００５４】
この規則は、最小の出現回数ゼロと関連付けられた各要素は、必ずしも符号化されないという事実を反映している。
【００５５】
図６に示すように、このプロセスでは、任意選択の要素「２」の１つ上流に位置する状態「１」と、要素「２」の１つ下流に位置するすべての状態「３」との間に遷移を追加し、この新しい遷移はそれが終了する状態に対応する要素の署名「ｍ３」と関連付ける。
【００５６】
１つ下流に位置する状態の１つも任意選択要素と関連付ける場合には、その状態の１つ上流に位置するすべての状態にも遷移を提供しなければならない。
【００５７】
このプロセスは以下のアルゴリズムを使用して行うことができる。
関連付けられた要素が最小の０回の出現を有するオートマトンのノードのサブセットをＺとする。
0004653381.tif 000007
【００５８】
このように１つの構造スキーマに対して生成されたオートマトンは、相互にネストになっていることに留意されたい。実際、図２に示すスキーマ例に対応するオートマトンでは、タイプＴＡ３１に対応するオートマトンでタイプＴＣ（要素ＸおよびＹ）に遭遇すると、タイプＴＣ４３に対応するオートマトンを完全に実行してから、タイプＴＡに対応するオートマトンの実行を続ける。
【００５９】
本発明による方法の次のステップ１４では、先に得たオートマトンを簡約化し、変換する。
【００６０】
したがって、図７ａおよび７ｂを参照して説明する方法で、同じ構文木のオートマトン（互いを呼び出す異なるツリーのオートマトンは除く）を併合することができる。
【００６１】
図７ａおよび７ｂは、本発明による方法により、構造要素（ａ１０．．＊、（ｂ１｜ｂ２）０．．＊）から生成されたオートマトンを示している。最初のオートマトン（図７ａ）はグループＳＥＱ（「，」）に対応し、２番目のオートマトン（図７ｂ）は、二者択一グループ（「｜」）に対応する。
【００６２】
これらのオートマトンを実行すると、第１のオートマトンで状態２に達すると第２のオートマトンの実行が起動され、第２のオートマトンで最終状態１または２に達すると、続いて第１のオートマトン、言い換えると第１のオートマトンの状態２と最終状態３の間の遷移Ｆの実行に移る。
【００６３】
２つのオートマトンを併合するプロセスにより図８に示すオートマトンを得ることができ、この図では、ＣＨＯグループの各選択肢を、選択された選択肢の中に現れるグループ要素の署名「ｂ１」、「ｂ２」と連接したこのグループの署名「ｃｈｏ．ｂ１．ｂ２」と関連付けた遷移によって示している。
【００６４】
このステップ１４では、例えばＨｏｐｏｒｏｆｔのアルゴリズムを適用することにより、状態の数を最小にするプロセスをオートマトンに施し、次いで、正規化プロセスを施して、正規化されたオートマトン６を得てもよい。
【００６５】
このプロセスに次いで、各ノードからの遷移に０〜ｎの番号を付ける。
【００６６】
次のステップ１５では、文書の各要素または基本データ・セットの圧縮された値を見つけるバイナリ・シーケンスの連続を得るために、文書２を再度読み、文書の構造にオートマトンを実行することにより、文書に含まれるデータを圧縮する。第１のタイプの符号化によると、このバイナリ・シーケンスは（Ｋ．Ｎ．Ｖ１．．ＶＮ）ｅの形であり、各要素または要素のグループｅに対して、Ｎは要素ｅの出現回数または要素ｅに対応する連続したデータ・セットの数であり、Ｋは要素ｅに到達することを可能にした遷移の回数であり、Ｖ１．．ＶＮは、要素ｅのＮ回の出現の、可能性としては圧縮された個々の値である。ｅが要素のグループである場合、その値Ｖはｅが含む要素の数と同じだけの多数のバイナリ・シーケンス（Ｋ．Ｎ．Ｖ）に分解される。ただし、ある場合には、特にＮの数が固定されている場合には、Ｎを省略することができる。これと同じことは、例えばシーケンス・タイプのグループで、ある状態から１つの円弧しか出ていない場合には、Ｋにも当てはまる。
【００６７】
いくつかの符号化されたパラメータをまとめる圧縮文書の概略的な見出しを初めに作成することができ、これは文書を記述するのに有用である。この見出しは、使用される１つまたは複数の構造スキーマの署名と、例えば以下のような使用された符号化を記述するパラメータのセットを含むことができる。
−各要素の長さの符号化が必須か、任意選択か、あるいは文書中に存在しないかを示すパラメータ
−要素をサブタイプ（ｓｕｂ−ｔｙｐｅ）する、すなわち、その基本タイプよりも厳密なタイプと関連付けることが可能か不可能かを示すパラメータ
−出現回数に使用する符号化タイプを示すパラメータ
【００６８】
文書の各情報要素も見出しと関連付けることができ、要素の存在と性質はその文書見出しに示される。
【００６９】
したがって、要素の見出しは、文書を解凍する際に文書中のそれより前の要素をすべて解凍することなく特定の要素にアクセスできるようにする形で、符号化されたその要素の長さを含むことができる。要素の見出しは、例えば要素の値を符号化する直前に文書に挿入する。
【００７０】
一般的には、文書の圧縮は、文書を順次読み、スキーマのオートマトンを実行することからなり、これにより、さらに、その文書の構造がコンパイルされたスキーマに対応していることを確認できるようになる。
【００７１】
このプロセス中に、各要素が文書中に現れる出現回数を符号化する。このために、次の規則を適用する。
【００７２】
要素ｅの出現回数を（ｉ．．ｊ）によって定義する場合、次の事例を区別することができる。
【００７３】
ｊが「＊」と異なり、ｉが０と異なる場合には、符号化を２部分、すなわち（ｉ．．ｉ）と（０．．ｊ−ｉ）に分解し、この定式化はｉ回の出現が必須であることを指定するので、第１の部分は符号化しない。第２の部分は｜ｌｏｇ２（ｊ−ｉ＋１）｜ビットで符号化する。
【００７４】
ｊが「＊」と異なり、ｉが０に等しい場合は、この符号化が必須である場合には、文書中に少なくとも１つの要素ｅがあることになるので、出現回数は１からｊの間、すなわち｜ｌｏｇ２（ｊ）｜ビットで符号化される。
【００７５】
ｊが「＊」に等しい場合はＡＳＮ１などの符号化技術を使用し、その符号化に従って最初のバイトがコーディング・バイトの数を表し、続くバイトが出現回数の値を含む。各バイトの高位ビットを使用してそのビットが出現回数の最後のコーディング・バイトであるか否かを示し、各バイトの次の７ビットを使用して出現回数を符号化することも可能である。
【００７６】
あるいは、構造スキーマの要素の出現回数を取り込む必要がない別の符号化タイプを選択してもよい。この符号化タイプによると、オートマトンの最終状態を表す「ｅｓｃａｐｅ」または「ｅｓｃ」と呼ばれるタイプを導入する。したがって、初めに以前に得たオートマトンへの変換を適用することが必要となる。
【００７７】
この変換は、オートマトンの各状態に１つ前の状態への戻り遷移を追加し、最終状態に「ｅｓｃ」遷移を追加して、オートマトンの実行の終了をマークすることからなる。これにより要素の符号化はわずか（ＫＶ）の形になり、すなわち遷移「ｅｓｃ」の回数Ｋｅｓｃで終了するオートマトンの符号化となる。
【００７８】
実際この符号化タイプは、複雑な形態の符号化と、最大の出現回数を持たない要素にのみ有用である。この符号化タイプは、特に、ｐが整数である場合に２Ｐと異なる複数の要素を含む二者択一タイプのグループを符号化するのに適している。
【００７９】
この符号化タイプは、上述のタイプと組み合わせることができる。これは、圧縮した文書の見出しと、複数回の出現がある符号化中の位置に割り当てられたビットにのみ示せばよい。
【００８０】
本発明によれば、文書のデータ・セットの少なくとも１つの基本タイプを外部圧縮モジュール１６と関連付ける。このように、文書を読み取る際には遭遇するデータ・セットの個々のタイプを分析し、データ・セットのタイプを外部圧縮モジュール１６に関連付けるときには、そのタイプをそのデータ・セットの内容に適用し、圧縮の結果を、対応するデータ・セットの値として圧縮した文書に挿入する。
【００８１】
外部圧縮モジュールは、例えば音声情報には「ｍｐ３」規格を、画像には「ｊｐｅｇ」規格を、ビデオ・タイプ・データには「ＭＰＥＧ１」または「ＭＥＰＧ２」を適用することができる。
【００８２】
データ・セットのタイプに圧縮モジュールを関連付けない場合は、デフォルトの圧縮モジュールを使用するか、そのタイプのデータ・セットが最初の文書に現れたときに回復することができる。
【００８３】
長さの符号化が任意選択または必須であることが文書の見出しに示される場合、要素は、その要素の値の複数ビットとして長さを含む圧縮文書内の見出しと関連付けられている。これにより、特に、ある要素を求める限りはオートマトンを用いてそれら要素の個々の長さだけを読み取ることにより、文書中でその要素より前に位置する要素を解凍しなくとも、圧縮された文書のその要素に直接アクセスすることが可能になる。
【００８４】
要素の長さは以下のように符号化することができる。
【００８５】
文書の見出し中で要素の長さの符号化が必須であると示される場合は、次の式を使用して要素の長さＬを複数ビットとして計算する。
Ｌ＝８ｐ＋ｈ
ｐは要素の長さを符号化するのに用いられるバイト数を表し（ＡＳＮ１符号化、またはこの数を符号化するのに使用される各バイトの高位ビットを使用して）、ｈはこの長さの残りのビット数を表す（ｈ＜８）。
【００８６】
要素の値を符号化するために呼び出される外部圧縮モジュール１６は、この長さを提供することができることに留意されたい。
【００８７】
要素の長さの符号化が必須でない場合は、要素の値に対応する最初のビットの値が、続くビットが要素の長さを表すか、表さないかを示す。
【００８８】
要素をサブタイプすることができる場合（文書の見出しに示される）は、圧縮された文書中で要素の値の直前に位置する要素の見出しに任意の新しいタイプを挿入する。最初のビットが、その要素タイプが予想されるタイプと異なるか、異ならないかを示す。第１の事例では、要素の見出し中の続くビットが新しいタイプのコードを含み、このコードは、要素の基本タイプのすべての可能な下位タイプに番号を付けることによって判断し、この番号付けは文書の構造を符号化することによって与えられる。
【００８９】
より正確には、文書は３つの主要なステップで符号化する。
【００９０】
第１のステップでは、各ノードから出る円弧に番号を付ける。ノードから出る円弧が１つだけの場合はこのステップは任意選択である。ｎ個の円弧が出る場合は、その円弧それぞれを、正規化の際に割り当てられる円弧の順序で与えられる番号と関連付ける（ステップ１４）。この番号はｎ’ビットで符号化し、ｎ’は、２ｎ’―１＜ｎ≦２ｎ’である。
【００９１】
したがって、状態Ｅからｎ回の遷移が生じる場合、各遷移は｜ｌｏｇ２（ｎ−１）｜＋１ビットで符号化されることになる。
【００９２】
第２のステップでは、各下位オートマトンの出現回数を上述のように符号化する。
【００９３】
第３のステップでは下位オートマトンを符号化する。このプロセスは次のアルゴリズムで表すことができる。
0004653381.tif 000008
【００９４】
例えば、オートマトン（ａ１｜ａ２｜ａ３）（０．．＊）の出現「ａ２  ａ３  ａ２  ａ１  ａ３」を符号化するには、出て行く円弧が３つある。したがってこの円弧は２ビットで番号を付ける。したがって、出現回数を符号化する場合、符号化の結果は以下のようになる。
００００  ０１０１  ０１  Ｖａ２  １０  Ｖａ３  ００  Ｘａ１  ００  Ｖａ１  １０  Ｖａ３
「００００  ０１０１」は出現回数、すなわち、５の２進値を表し、Ｖａ１、Ｖａ２、およびＶａ３はそれぞれａ１、ａ２、およびａ３の出現の値である。
【００９５】
出現回数を符号化しない場合は
０１  Ｖａ２  １０  Ｖａ３  ００  Ｖａ１  ００  Ｖａ１  １０  Ｖａ３  １１
となり、１１は、出て行く遷移「ｅｓｃ」の数に対応する。
【００９６】
図７ａ、７ｂの例では、オートマトン（ａ１０．．＊、ｂ１｜ｂ２）０．．＊）の出現「ｂ３  ｂ１  ａ１」の符号化により、次の結果が得られる（状態を併合しない場合）。
００００  ００１０  シーケンスの出現回数（ここでは倍）
１                  円弧「ｃｈｏ．ｂ１．ｂ２」の符号化
００００  ００１０  グループ「ｃｈｏ．ｂ１．ｂ２」の出現回数（ここでは倍）
１                  グループ「ｃｈｏ．ｂ１．ｂ２」中の円弧ｂ２の符号化
Ｖｂ２              値ｂ２の符号化
０                  グループ「ｃｈｏ．ｂ１．ｂ２」の円弧ｂ１の符号化
Ｖｂ１              値ｂ１の符号化
０                  円弧ａ１の符号化
００００  ０００１  ａ１の出現回数
Ｖａ１              ａ１の値の符号化
１                  出て行く円弧Ｆの符号化
【００９７】
状態を併合した場合（図８）は、
００００  ００１０  シーケンスの出現回数
１０                円弧「ｃｈｏ．ｂ１．ｂ２−ｂ２」の符号化
００００  ００１０  グループ「ｃｈｏ．ｂ１．ｂ２」の出現回数
Ｖｂ２                値ｂ２の符号化
０                  グループ「ｃｈｏ．ｂ１．ｂ２」の円弧ｂ１の符号化
Ｖｂ１                値ｂ１の符号化
００                円弧ａ１の符号化
００００  ０００１  ａ１の出現回数
Ｖａ１                ａ１の値の符号化
１０                出て行く円弧Ｆの符号化
【００９８】
特にグループＥＴＮＯの場合に符号化を最適化するような形でスキーマが解釈され、再度順序付けされている場合には、このオートマトンを再配列することが必要となる場合がある。
【００９９】
属性の順番が有用でない場合（ＸＭＬ言語など）は、例えば英数字順など所定の順番で、そしてそれらの属性が必須か否かに従って、要素の属性を再度順序付けをするように符号化を行うことが可能である。この配列により、圧縮後の記述のサイズをその分だけ小さくすることができる。
【０１００】
文書の構造スキーマにステップ１１から１５を実行してオートマトンを得、次いでステップ１５’で文書の復号と解凍を行うことにより、このように得た文書を解凍するプロセスを行う。ステップ１５’では、文書中で遭遇する圧縮された情報要素のタイプと名前を判定できるような方式で、圧縮された文書中を移動して、ステップ１１から１４の結果得られたオートマトンを実行する。外部圧縮モジュール１６を用いて得た要素の値は、対応する解凍モジュール１６’を用いて解凍する。
【０１０１】
同じ構造スキーマを有するいくつかの文書を処理する（圧縮または解凍）場合は、ステップ１１から１５を一度だけ実行し、ステップ１５および１６（または１５’および１６’）だけを、処理する各文書に適用すればよいことに留意されたい。
【図面の簡単な説明】
【図１】  本発明による方法の様々なステップ間の結びつきを表すブロック図である。
【図２ａ、２ｂおよび２ｃ】  ツリーの形で構造スキーマを示す略図である。
【図３】  本発明による簡約化方法を図２の構造スキーマに適用することにより得られる構造スキーマの図である。
【図４ａ、４ｂ、および４ｃ】  本発明による別の簡約化方法を図２の構造スキーマに適用することにより得られる構造スキーマの図である。
【図５ａ〜５ｃ】  本発明による方法で得られ、使用される３つの有限オートマトンをそれぞれ示す図である。
【図６】  本発明による方法で使用される最適化法を表す別のオートマトンの図である。
【図７ａおよび７ｂ】  本発明によるプロセスを使用して特定の構造スキーマから得られる２つのオートマトンの図である。
【図８】  図７ａおよび７ｂに示すオートマトンに簡約化法を適用する図である。
【図１】
0004653381.tif 000009
【図３】
0004653381.tif 000010
【図２ａ】
0004653381.tif 000011
【図２ｂ】
0004653381.tif 000012
【図２ｃ】
0004653381.tif 000013
【図４ａ】
0004653381.tif 000014
【図４ｂ】
0004653381.tif 000015
【図４ｃ】
0004653381.tif 000016
【図５ａ】
0004653381.tif 000017
【図５ｂ】
0004653381.tif 000018
【図５ｃ】
0004653381.tif 000019
【図６】
0004653381.tif 000020
【図７ａ】
0004653381.tif 000021
【図７ｂ】
0004653381.tif 000022
【図８】
0004653381.tif 000023