JP2004508647A

JP2004508647A - 構造化文書の圧縮／解凍方法

Info

Publication number: JP2004508647A
Application number: JP2002526128A
Authority: JP
Inventors: ティエノ　セドリ; セーラ　クロード
Original assignee: エクスプウェイ
Priority date: 2000-09-06
Filing date: 2001-08-31
Publication date: 2004-03-18
Anticipated expiration: 2021-08-31
Also published as: FR2813743A1; DE60107964D1; DK1316220T3; ES2234878T3; ATE285656T1; FR2813743B1; US20110283183A1; AU2001287796A1; US20040013307A1; JP4653381B2; US8015218B2; EP1316220B1; PT1316220E; DE60107964T2; EP1316220A1; WO2002021848A1

Abstract

本発明は、情報のタイプと関連付けられ、データ・セットを表すネストになった構造要素を含み、文書構造を定義する少なくとも１つのツリー図構造（１、３１、３９、４３）と関連付けられた構造化文書を圧縮および解凍する方法に関し、この方法は、構造図の構文解析（１１）を行い、構造図を標準化（１２）して図の要素の単一の所定の順番を得るステップと、標準化した図をコンパイル（１３）して有限オートマトン（５）を得、各オートマトンは、それぞれが構造の要素を表す遷移（ｍ１、ｍ２．．ｍｎ）によって相互に連結された状態（０、１、ｎ）を含むステップと、文書を圧縮（１５）し、文書（２）中である情報タイプのデータ・セットに遭遇した際は、前記情報タイプと関連付けられた少なくとも１つの圧縮アルゴリズム（１６）を実行するステップとを含む。

Description

【０００１】
本発明は、構造化文書を圧縮／解凍する方法に関する。
【０００２】
本発明は、これに限定する訳ではないが、特にデジタル伝送ネットワークを介した画像または画像シーケンス、ビデオまたは音声データなどの文書の伝送、およびそのような文書の記憶に適用される。
【０００３】
現在、いくつかのデジタル文書の圧縮アルゴリズムが存在する。圧縮アルゴリズムには、データ・タイプを考慮せずに文書のバイナリ・データを直接処理するものがある。こうしたアルゴリズムには、どの文書でも処理できるという利点があるが、一般的には、音声または画像タイプである大容量文書の処理には効果的ではない（圧縮率が低い）。
【０００４】
さらに、他の圧縮アルゴリズムとして、より効率的なものとして、例えば画像や音声など、あるデータ・タイプに特別に適合させたものが知られるが、対象とするデータだけを含むのではない文書に適用すると、使用することができないか、あるいは効果的でないという結果になる。
【０００５】
しかし、利用され、データ伝送ネットワークでやり取りされる文書は、１つの構造にまとめられたいくつかの情報タイプを含むようになりつつある。
【０００６】
構造化文書とは、それぞれがタイプと関連付けられ、主に階層的な関係に従って、ともに配列されたデータ・セットの集合である。こうした文書にはＳＧＭＬ、ＨＴＭＬ、ＸＭＬなどの構造化言語が使用され、特に、文書を構成する異なるデータ・セットを区別することが可能になる。これに対し、いわゆる線形文書では、文書の内容情報はプレゼンテーションおよびタイピングの情報と混在している。
【０００７】
このため、構造化文書は、文書の異なるデータ・セットを区分するロケータまたはマーカを含む。ＳＧＭＬ、ＸＭＬ、またはＨＴＭＬフォーマットの場合、「タグ」と称されるこうしたロケータは「＜ＸＸＸＸ＞」と「＜／ＸＸＸＸ＞」の形をとり、最初のマーカはデータ・セット「ＸＸＸＸ」の始まりを意味し、２番目のマーカはこのセットの終わりを意味する。データ・セットは、いくつかのより低いレベルのデータ・セットからなることができる。このように、構造化文書は階層的あるいは木構造のスキーマを有し、各ノードはデータ・セットを表し、より低いレベルのデータ・セットを含むデータ・セットを表す、より高い階層レベルのノードに連結される。この木構造の枝の最後に位置するノードは、所定タイプのデータを含むデータ・セットを表し、このデータ・セットは、データのサブセットに分解することができない。
【０００８】
一般に、構造化文書は、文書の各データ・セットの情報の構造およびタイプを規則の形で示す、いわゆる構造スキーマと関連付けられる。スキーマは、ネストになったデータ・セット構造のグループによって構築され、これらのグループは、例えば順序付けされたシーケンス、順番付けされた、あるいは、順番付けされていない二者択一の要素グループまたは必須の要素グループなどである。
【０００９】
構造化文書はこのように構造スキーマと関連付けられ、テキスト・データまたはバイナリ・データの形で表される区分マーカを含み、このマーカは、マーカによって画定される他のデータ・セットを、それ自体が含むことのできるデータ・セットを画定する。この結果、このように構造化された文書は、テキスト・データだけでなく、任意の他タイプの情報（例えば音声データ、画像など）も含むことができる。したがって、ある特定のデータ・タイプに固有の圧縮アルゴリズムは、このタイプの文書の処理には効果的でなく、適さない。
【００１０】
本発明の目的は、これらの欠点を取り除くことである。このために、本発明は、文書の構造を定義し、データ・セットを表すネストになった構造要素を含む、少なくとも１つの木構造スキーマと関連付けられた構造化文書を圧縮および解凍する方法を提案し、この構造要素は３つのカテゴリ、すなわち、構造化された、あるいは、構造化されない要素グループに分解される構造化されたルート要素、および構造中の最下位レベルの要素に対応する基本要素、に分類され、各基本要素とルート要素は、情報タイプと関連付けられる。
【００１１】
本発明によれば、初めに、基本要素の少なくとも１つの情報タイプを、適合する圧縮アルゴリズムと関連付け、この方法は次のステップを含む。
−文書の構造スキーマの構文解析を行い、構造スキーマを正規化してスキーマの構造要素の単一の所定の順番を得るステップ、
−正規化した構造スキーマをコンパイルして、ルート要素１つにつき１つの有限オートマトンを得るステップであって、各オートマトンは、それぞれが、構造要素を表す遷移によって相互に連結された状態を含むステップ、および
−文書に有限オートマトンを実行することを含めて構造化文書を圧縮し、圧縮する文書中で前記アルゴリズムと関連付けられた情報タイプのデータ・セットに遭遇すると、前記圧縮アルゴリズムを実行するステップ。
【００１２】
構造スキーマをコンパイルすることにより文書の構造が非常に簡潔に表され、基本構造要素に対応する各データ・セットをある情報タイプと関連付けるとすると、そのタイプに最も合った圧縮アルゴリズムによってデータ・セットを処理することができる。このように、文書が、例えばテキスト・データ、画像、音声データを含む場合、そのデータは構造化文書内に完全に位置し、低レベルの構造要素とあるタイプとに関連付けられる。オートマトンを実行すると、ある圧縮アルゴリズムと関連付けられた基本タイプのデータ・セットの存在を検出し、そのデータに対応するアルゴリズムを順次呼び出して対応するバイナリの情報シーケンスを得、このシーケンスは、出現すると同時に、その圧縮で得られるバイナリ文書に挿入される。
【００１３】
さらにデータ伝送の場合では、伝送される文書が常に同じ構造スキーマを有する場合は、文書を伝送するたびにその構造スキーマを伝送する必要はなく、本発明による方法を用いて得られる圧縮率の点で、さらに利得が生じる。そのスキーマがすでに文書の受け取り側に知られている場合には、スキーマの伝送はさらに無意味になる。例えばＨＴＭＬ文書の場合には、一番最初でさえ、文書スキーマを符号化する必要がない。
【００１４】
有限オートマトンとは状態のセットと理解されたく、各状態は、入力事象のセットと、入力事象ごとにオートマトンのアクティブな状態のセットを定義する遷移関数とに関連付けられる。この定義によると、例えばコード変換テーブルに関して、入力事象ごとに次の状態に対応するテーブル、または再度対応テーブルを示す１つの状態につき１つのテーブルに基づいて、また、オートマトンに含まれる状態と同じだけの多くの行および列を有し、テーブルの各ボックスが２つの対応する状態間の遷移の記述を含む、１つのオートマトンにつき１つのテーブルに基づいて、複数の表現を考えることができる。
【００１５】
解凍する際は、圧縮と同じ方法で構造スキーマを処理して、圧縮に用いられたオートマトンを判定し、全く同一でなくとも少なくとも、同等の構造を有する元のフォーマットに文書を再構築するために圧縮された文書の内容を分析し、圧縮の際に使用された圧縮アルゴリズムに対応する解凍アルゴリズムを実行して、圧縮された文書内に位置するバイナリの情報シーケンスから、元のデータ・セットを復元する。
【００１６】
文書とともに構造スキーマを伝送する場合、本発明による方法は、好ましくは、本来の構造スキーマ、あるいは、変換と正規化の後に得られる構造スキーマ、あるいは、コンパイル後に得られる構造スキーマを伝送するステップを含む。
【００１７】
本発明の実施例の１つによれば、圧縮された文書中に各データ・セットを配置することにより、文書全体、または解凍するセットより前のデータ・セットを解凍する必要なしに、特定の情報要素に直接アクセスすることが可能になる。
【００１８】
本発明の別の実施例によれば、各構造スキーマ要素を、さらに可能な出現回数のセットと関連付け、その構造要素を有するデータ・セットが、それが属する１つ上の階層レベルのデータ・セット中に現れることができる回数を示す。
【００１９】
本発明によるプロセスは、構造要素のグループの階層レベル数を減らすことにより、文書の構造スキーマを最適化するステップを含むことができる。この最適化により、構造スキーマを単純化することができるが、圧縮プロセスの効率はより低くなる。
【００２０】
以下に、添付の図面を参照して、本発明による方法を実施する好ましいモードの１つを非制限的な意味で説明する。
【００２１】
図１は、本発明による方法の様々なステップ間の結びつきを示す。
【００２２】
この方法は、文書の構造を定義する構造スキーマ１と、文書の構造化データとによって構築された構造化文書２を処理するものである。
【００２３】
ＸＭＬスキーマ言語では、構造スキーマは、例えば次のような形である。

【００２４】
このスキーマは、「Ｃ」という名の要素は、任意選択のブール・タイプの第１の要素「ａ２」と、常にこの構造中に存在する整数タイプの第２の要素「ａ１」と、それぞれタイプ「ＴＡ」と「ＴＢ」である二者択一の要素「Ａ」および「Ｂ」からなるグループとによって構築された複雑な構造を持ち、要素「Ａ」および「Ｂ」の１回の機会に１つが構造中に現れることを示している。
【００２５】
タイプ「ＴＡ」と「ＴＢ」は、同様の定式化によってこの文書の構造スキーマに定義される。
【００２６】
一般には次の要素グループが文書構造の定義に使用される。
−ＳＥＱ：そのすべてが、指示される順番で文書中に現れなければならない順番付けられた要素のリストを定義する。
−ＣＨＯ：二者択一要素のセットを定義し、グループのうち１要素が現れなければならない。
−ＥＴ：変更されることのない何らかの順序で、そのすべてが文書中に現れなければならない要素のセットを定義する。
−ＥＴ_ＮＯ：すべてが何らかの順序で文書中になければならない要素のセットを定義する。順序は重要でない。
−ＡＮＹ：文書中に現れることが可能なすべての可能な要素のうち、いずれかの要素を含む。
【００２７】
本発明によれば、この定式化をこの方法のステップ１１で分析および変換して、１つの構造要素につき１つのツリーの対応で構文木４を得る。構造要素ＴＣに対応する構文木は、次の式（１）によって表される。
【数１】

の式で、
「→」は、ＴＣがこの記号の後に定義される構造に与えられる名前であることを示し、
「（　）」は、その要素グループを読む優先度を示し、
「，」は、シーケンス・タイプ（ＳＥＱ）の要素グループに対応し、
「｜」は、二者択一要素グループ（ＣＨＯ）を表し、
「＆」は、ＥＴタイプの要素グループを表し、
「＆_ＮＯ」は、順番付けられていないＥＴタイプの要素グループを表し、
「｛｝」は、要素を構造要素名または基本タイプ（例えば整数やブール）と関連付け、
「Ａ^ｘ．．ｙ」は、文書中で要素Ａをｘからｙの回数繰り返すことを示し、ｙは中間値を表す「^＊」に等しくなることができる。
【００２８】
この定式化では、任意の要素（ＡＮＹ）を表す記号「＄」も使用する。
【００２９】
式（１）は図２ｃに示すツリーで表すことができ、このツリーは、シーケンス・タイプ・グループ４４の１回の出現によって構築されるルート要素「ＴＣ」４３を含む。このグループは、順番付けられていない「ＥＴ」タイプ・グループ４５の１回の出現と、二者択一グループ４６の１回の出現を含む。
【００３０】
グループ４５は、整数「ａ１」とブール「ａ２」の１回の出現によって構築され、グループ４６は、「ＴＡ」タイプの要素「Ａ」と「ＴＢ」タイプの要素「Ｂ」の１回の出現を含む。
【００３１】
ステップ１１で得られるタイプ「ＴＡ」および「ＴＢ」は、例えば次の式によって得られ、
【数２】

それぞれ図２ａと２ｂに示すツリーによって表される。
【００３２】
タイプ「ＴＡ」３１は、それぞれＥＴタイプとＳＥＱタイプである２つの単一のグループ３３、３４によって構築される単一のシーケンス・タイプ・グループ３２を含む。グループ３３は、それぞれ「ａ３」と「ａ４」という２つの整数タイプの１回の出現を含む。グループ３４は、それぞれ「Ｘ」と「Ｙ」という２つのタイプ「ＴＣ」の１回の出現を含む。
【００３３】
タイプ「ＴＢ」３９は単一のシーケンス・タイプ・グループ４０によって構築され、このグループはそれぞれ「ａ１」と「ａ５」という２つのブールを含む。
【００３４】
以上の説明では、各要素の名前とそのタイプを区別したが、本発明による方法は、このような区別をしない構造化言語にも適用することができる。
【００３５】
さらに、構造要素は決定性でなければならない。換言すると、要素はいくつかの異なる形で解釈することが可能であってはならない。例えば、スキーマ「（ａ｜（ａ，ｂ））」では、「ａ」が現れる場合に「ｂ」がａの後に現れなければならないかどうかが分からない。この目的のために、非決定性のスキーマを決定性スキーマに変換するために、本発明による方法で適用できるアルゴリズムがある。これについては、例えば「Ｒｅｇｕｌａｒ　ｅｘｐｒｅｓｓｉｏｎｓ　ｉｎｔｏ　ｆｉｎｉｔｅ　ａｕｔｏｍａｔａ」（Ｂｒｕｇｇｅｍａｎｎ−Ｋｌｅｉｎ，Ａｎｎｅ、Ｅｘｔｅｎｄｅｄ　Ａｂｓｔｒａｃｔ　ｉｎ　Ｉ．Ｓｉｍｏｎ，Ｈｒｓｇ，ＬＡＴＩＮ　１９９２、ｓ．９７−９８、Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ、ベルリン　１９９２。完全版はＴｈｅｏｒｅｔｉｃａｌ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　１２０、１９７〜２１３、１９９３）を参照されたい。したがって、先に挙げたスキーマは、例えば「（ａ，ｂ^０．．１）」と置き替えることができる。
【００３６】
本発明による方法の次のステップ１２では、構文木に変換した構造スキーマの要素に、初めに簡約化または単純化のプロセスを行うことができる。
【００３７】
この簡約化プロセスは、図３に示すように、すべてのツリー３１、３９、および４３から単一の構文木５１を生成することにより、大まかな平坦化を行うものである。
【００３８】
このツリーは事実上、文書中で遭遇する可能性の高いすべての要素タイプのディクショナリを表し、これらの要素は、少なくとも１回（１．．＊）文書中に現れる二者択一タイプのグループ５２に合わせてまとめられる。このツリーでは、複雑なタイプの要素「Ａ」、「Ｂ」、「Ｘ」、および「Ｙ」は「ＡＮＹ」タイプと関連づけられ、異なる要素タイプで（要素「ＴＢ」および「ＴＣ」に）２度現れている要素「ａ１」は、ＸＭＬ言語によるデフォルトの「ｐｃｄａｔａ」タイプか、または、例えば「ｔｅｘｔ」など、最初の文書中にある要素タイプと関連付けられる。これと同じデータ・セットはいくつかの方式で表すことができ、例えば、バイナリ・シーケンスを文字列または整数と考えることもできる。
【００３９】
あるいは、この簡約化プロセスは、構文木をローカルに平坦化して、図４ａから４ｃに３１’、３９’、および４３’で示すツリーを得るものであってもよい。
【００４０】
これら各図では、グループ３２〜３４（図２ａ）、４０（図２ｂ）、および４４〜４６（図２ｃ）をそれぞれ二者択一タイプ・グループ５３、５４、５５に置き換えており、これらのグループは少なくとも１回現れる（１．．＊）。
【００４１】
ツリー「ＴＡ」、「ＴＢ」、および「ＴＣ」には、さらに追加的なプロセスを施して、構造スキーマに生じるあいまい性を除去することができる。
【００４２】
ステップ１２で、ツリー「ＴＡ」、「ＴＢ」、および「ＴＣ」に、スキーマの要素の単一の順番が得られるような方式で、スキーマを再度順番付けすることからなる正規化プロセスも行う。このプロセスでは、前のプロセスで得られた構文木の異なるノードに、２進数を割り当てる。この数は、関連する要素を圧縮する際に用いられる。
【００４３】
この正規化プロセスは、各グループに、そのグループの名前と、すでに順番付けられているそのグループのすべての要素と、下位グループの署名の連接によって構築される署名を割り当てるものである。したがって、図４のグループ５３は、署名「ＣＨＯ．ａ３．ａ４．Ｘ．Ｙ」（または「｜ａ３．ａ４．Ｘ．Ｙ」）と関連付けられる。
【００４４】
この正規化プロセスで、順番付けられたグループ（ＳＥＱ）がすでに正規化されていると考える。したがって正規化するグループは、二者択一タイプ（「ＣＨＯ」）と、「ＥＴ」および「ＥＴ_ＮＯ」グループになる。このプロセスは、下位グループｇ_ｉおよび要素ｅ_ｉからなる各グループＧについて、次のステップを含む。
−グループＧを正規化する前にグループＧの下位グループｇ_ｉを正規化し、正規化アルゴリズムは再帰アルゴリズムであるステップ、
−下位グループｇ_ｉの前にグループＧの任意の要素ｅ_ｉを配列するステップ、
−所定の順序で要素ｅ_ｉを配列するステップ、
−所定の順序で下位グループｇ_ｉを配列するステップ、および
−以上のステップの結果確立される順序に従って、その構成要素（要素および下位グループ）のすべての署名の連接により得られるグループＧの署名を判定するステップ。
【００４５】
グループの構成要素を配列する所定の順序は、構成要素個々の署名の英数字順でも、あるいは、各自の最小出現回数の降順にして、同じ最小出現回数を有する構成要素を英数字順に配列してもよい。
【００４６】
この正規化プロセスは、本発明による方法では必要でないことに留意されたい。スキーマ中に構成要素が現れる順序は、実際には保存してもよい。
【００４７】
この方法の次のステップ１３は、有限オートマトン５の生成である。このプロセスでは、１つの構文木グループにつき１つのオートマトンの対応で、各構文木に基本オートマトンのセットを生成し、次いで、その基本オートマトンを組み合わせる。
【００４８】
図５ａで、１つ下の階層レベルの署名ｍ１、ｍ２〜ｍｎのｎ個の要素からなるシーケンシャル・グループ（ＳＥＱ）のオートマトンは、図に円で表す０からｎ＋１の番号を付けたｎ＋２個の状態を含み、各ノードは、グループ要素に対応する円弧で表す、要素の署名を名前とした遷移によってその次のノードに連結され、最後の遷移Ｆ（状態ｎ＋１に向かう）は、このグループの終わりをマークしている。
【００４９】
図５ｂでは、１つ下の階層レベルの署名ｍ１、ｍ２〜ｍｎのｎ個の要素からなる二者択一タイプ・グループ（ＣＨＯ）のオートマトンは、番号「０」の初期状態と、番号１〜ｎのｎ個の最終状態を含み、状態０は、それぞれｎ個のグループ要素に対応するｎ個の遷移によって最終状態１〜ｎに連結されている。
【００５０】
図５ｃでは、１つ下の階層レベルの署名ｍ１、ｍ２〜ｍｎのｎ個の要素からなるＥＴグループのオートマトンは、ｎ個の要素のすべての可能な組み合わせを表す１＋ｎ＋ｎ（ｎ−１）＋ｎ（ｎ−１）（ｎ−２）＋．．．＋ｎ！個の状態を含む。
【００５１】
この種のオートマトンは、以下のような単純なアルゴリズムによって生成することができる。
Ｅをグループのすべての可能な構成要素のセットとする。
Ｆｕｎｃｔｉｏｎ＿１を実行する（Ｅ，初期状態）
Ｆｕｎｃｔｉｏｎ＿１（Ｅ、状態ｅ）：
Ｒｅｐｅａｔ　Ｅが空でない間は、
Ｅから要素ｍｉを選択し、それをＥから除外する
状態ｅ’と、ｅとｅ’を結ぶ円弧を作成する
表示されるｍｉ
ＥをＥ’として複製する
Ｆｕｎｃｔｉｏｎ＿１を実行する（Ｅ’、状態ｅ’）
Ｅｎｄ　ｒｅｐｅａｔ
【００５２】
１つ下の階層レベルの署名ｍ１、ｍ２〜ｍｎのｎ個の要素からなるグループＥＴ_ＮＯのオートマトンは、グループ中の要素の出現順序に関する情報が失われても許容できるか、順序が固定されているのであれば、ＳＥＱのオートマトンでよい。
【００５３】
これらのオートマトン（タイプＣＨＯ、ＥＴおよびＥＴ_ＮＯのグループの場合）は、任意選択の要素、すなわち、可能な出現の総数が（０．．ｋ）の形である要素の回避プロセスを適用することにより最適化することができる。
【００５４】
この規則は、最小の出現回数ゼロと関連付けられた各要素は、必ずしも符号化されないという事実を反映している。
【００５５】
図６に示すように、このプロセスでは、任意選択の要素「２」の１つ上流に位置する状態「１」と、要素「２」の１つ下流に位置するすべての状態「３」との間に遷移を追加し、この新しい遷移はそれが終了する状態に対応する要素の署名「ｍ３」と関連付ける。
【００５６】
１つ下流に位置する状態の１つも任意選択要素と関連付ける場合には、その状態の１つ上流に位置するすべての状態にも遷移を提供しなければならない。
【００５７】
このプロセスは以下のアルゴリズムを使用して行うことができる。
関連付けられた要素が最小の０回の出現を有するオートマトンのノードのサブセットをＺとする。
Ｒｅｐｅａｔ（このオートマトンが次の手順によって修正される間は）：
Ｆｏｒ　Ｚの要素Ｘごとに：
Ｆｏｒ　Ｘの入ってくる遷移ＴＥｘごとに：
Ｆｏｒ　Ｘの出て行く遷移ＴＳｘごとに：
１．遷移ＴＥｘのソース・ノードと遷移ＴＳｘの宛先ノードを結ぶ新しい遷移Ｎを作成する。この遷移は、円弧ＴＳｘの値によってマークする。
２．グラフ中に同じ遷移がまだ存在しなければ、それをグラフに追加する。
Ｅｎｄ　ｆｏｒ
Ｅｎｄ　ｆｏｒ
Ｅｎｄ　ｆｏｒ
Ｅｎｄ　ｒｅｐｅａｔ
【００５８】
このように１つの構造スキーマに対して生成されたオートマトンは、相互にネストになっていることに留意されたい。実際、図２に示すスキーマ例に対応するオートマトンでは、タイプＴＡ３１に対応するオートマトンでタイプＴＣ（要素ＸおよびＹ）に遭遇すると、タイプＴＣ４３に対応するオートマトンを完全に実行してから、タイプＴＡに対応するオートマトンの実行を続ける。
【００５９】
本発明による方法の次のステップ１４では、先に得たオートマトンを簡約化し、変換する。
【００６０】
したがって、図７ａおよび７ｂを参照して説明する方法で、同じ構文木のオートマトン（互いを呼び出す異なるツリーのオートマトンは除く）を併合することができる。
【００６１】
図７ａおよび７ｂは、本発明による方法により、構造要素（ａ_１ ^０．．＊、（ｂ_１｜ｂ_２）^０．．＊）から生成されたオートマトンを示している。最初のオートマトン（図７ａ）はグループＳＥＱ（「，」）に対応し、２番目のオートマトン（図７ｂ）は、二者択一グループ（「｜」）に対応する。
【００６２】
これらのオートマトンを実行すると、第１のオートマトンで状態２に達すると第２のオートマトンの実行が起動され、第２のオートマトンで最終状態１または２に達すると、続いて第１のオートマトン、言い換えると第１のオートマトンの状態２と最終状態３の間の遷移Ｆの実行に移る。
【００６３】
２つのオートマトンを併合するプロセスにより図８に示すオートマトンを得ることができ、この図では、ＣＨＯグループの各選択肢を、選択された選択肢の中に現れるグループ要素の署名「ｂ１」、「ｂ２」と連接したこのグループの署名「ｃｈｏ．ｂ１．ｂ２」と関連付けた遷移によって示している。
【００６４】
このステップ１４では、例えばＨｏｐｏｒｏｆｔのアルゴリズムを適用することにより、状態の数を最小にするプロセスをオートマトンに施し、次いで、正規化プロセスを施して、正規化されたオートマトン６を得てもよい。
【００６５】
このプロセスに次いで、各ノードからの遷移に０〜ｎの番号を付ける。
【００６６】
次のステップ１５では、文書の各要素または基本データ・セットの圧縮された値を見つけるバイナリ・シーケンスの連続を得るために、文書２を再度読み、文書の構造にオートマトンを実行することにより、文書に含まれるデータを圧縮する。第１のタイプの符号化によると、このバイナリ・シーケンスは（Ｋ．Ｎ．Ｖ_１．．Ｖ_Ｎ）ｅの形であり、各要素または要素のグループｅに対して、Ｎは要素ｅの出現回数または要素ｅに対応する連続したデータ・セットの数であり、Ｋは要素ｅに到達することを可能にした遷移の回数であり、Ｖ_１．．Ｖ_Ｎは、要素ｅのＮ回の出現の、可能性としては圧縮された個々の値である。ｅが要素のグループである場合、その値Ｖはｅが含む要素の数と同じだけの多数のバイナリ・シーケンス（Ｋ．Ｎ．Ｖ）に分解される。ただし、ある場合には、特にＮの数が固定されている場合には、Ｎを省略することができる。これと同じことは、例えばシーケンス・タイプのグループで、ある状態から１つの円弧しか出ていない場合には、Ｋにも当てはまる。
【００６７】
いくつかの符号化されたパラメータをまとめる圧縮文書の概略的な見出しを初めに作成することができ、これは文書を記述するのに有用である。この見出しは、使用される１つまたは複数の構造スキーマの署名と、例えば以下のような使用された符号化を記述するパラメータのセットを含むことができる。
−各要素の長さの符号化が必須か、任意選択か、あるいは文書中に存在しないかを示すパラメータ
−要素をサブタイプ（ｓｕｂ−ｔｙｐｅ）する、すなわち、その基本タイプよりも厳密なタイプと関連付けることが可能か不可能かを示すパラメータ
−出現回数に使用する符号化タイプを示すパラメータ
【００６８】
文書の各情報要素も見出しと関連付けることができ、要素の存在と性質はその文書見出しに示される。
【００６９】
したがって、要素の見出しは、文書を解凍する際に文書中のそれより前の要素をすべて解凍することなく特定の要素にアクセスできるようにする形で、符号化されたその要素の長さを含むことができる。要素の見出しは、例えば要素の値を符号化する直前に文書に挿入する。
【００７０】
一般的には、文書の圧縮は、文書を順次読み、スキーマのオートマトンを実行することからなり、これにより、さらに、その文書の構造がコンパイルされたスキーマに対応していることを確認できるようになる。
【００７１】
このプロセス中に、各要素が文書中に現れる出現回数を符号化する。このために、次の規則を適用する。
【００７２】
要素ｅの出現回数を（ｉ．．ｊ）によって定義する場合、次の事例を区別することができる。
【００７３】
ｊが「＊」と異なり、ｉが０と異なる場合には、符号化を２部分、すなわち（ｉ．．ｉ）と（０．．ｊ−ｉ）に分解し、この定式化はｉ回の出現が必須であることを指定するので、第１の部分は符号化しない。第２の部分は｜ｌｏｇ_２（ｊ−ｉ＋１）｜ビットで符号化する。
【００７４】
ｊが「＊」と異なり、ｉが０に等しい場合は、この符号化が必須である場合には、文書中に少なくとも１つの要素ｅがあることになるので、出現回数は１からｊの間、すなわち｜ｌｏｇ_２（ｊ）｜ビットで符号化される。
【００７５】
ｊが「＊」に等しい場合はＡＳＮ１などの符号化技術を使用し、その符号化に従って最初のバイトがコーディング・バイトの数を表し、続くバイトが出現回数の値を含む。各バイトの高位ビットを使用してそのビットが出現回数の最後のコーディング・バイトであるか否かを示し、各バイトの次の７ビットを使用して出現回数を符号化することも可能である。
【００７６】
あるいは、構造スキーマの要素の出現回数を取り込む必要がない別の符号化タイプを選択してもよい。この符号化タイプによると、オートマトンの最終状態を表す「ｅｓｃａｐｅ」または「ｅｓｃ」と呼ばれるタイプを導入する。したがって、初めに以前に得たオートマトンへの変換を適用することが必要となる。
【００７７】
この変換は、オートマトンの各状態に１つ前の状態への戻り遷移を追加し、最終状態に「ｅｓｃ」遷移を追加して、オートマトンの実行の終了をマークすることからなる。これにより要素の符号化はわずか（ＫＶ）の形になり、すなわち遷移「ｅｓｃ」の回数Ｋ_ｅｓｃで終了するオートマトンの符号化となる。
【００７８】
実際この符号化タイプは、複雑な形態の符号化と、最大の出現回数を持たない要素にのみ有用である。この符号化タイプは、特に、ｐが整数である場合に２^Ｐと異なる複数の要素を含む二者択一タイプのグループを符号化するのに適している。
【００７９】
この符号化タイプは、上述のタイプと組み合わせることができる。これは、圧縮した文書の見出しと、複数回の出現がある符号化中の位置に割り当てられたビットにのみ示せばよい。
【００８０】
本発明によれば、文書のデータ・セットの少なくとも１つの基本タイプを外部圧縮モジュール１６と関連付ける。このように、文書を読み取る際には遭遇するデータ・セットの個々のタイプを分析し、データ・セットのタイプを外部圧縮モジュール１６に関連付けるときには、そのタイプをそのデータ・セットの内容に適用し、圧縮の結果を、対応するデータ・セットの値として圧縮した文書に挿入する。
【００８１】
外部圧縮モジュールは、例えば音声情報には「ｍｐ３」規格を、画像には「ｊｐｅｇ」規格を、ビデオ・タイプ・データには「ＭＰＥＧ１」または「ＭＥＰＧ２」を適用することができる。
【００８２】
データ・セットのタイプに圧縮モジュールを関連付けない場合は、デフォルトの圧縮モジュールを使用するか、そのタイプのデータ・セットが最初の文書に現れたときに回復することができる。
【００８３】
長さの符号化が任意選択または必須であることが文書の見出しに示される場合、要素は、その要素の値の複数ビットとして長さを含む圧縮文書内の見出しと関連付けられている。これにより、特に、ある要素を求める限りはオートマトンを用いてそれら要素の個々の長さだけを読み取ることにより、文書中でその要素より前に位置する要素を解凍しなくとも、圧縮された文書のその要素に直接アクセスすることが可能になる。
【００８４】
要素の長さは以下のように符号化することができる。
【００８５】
文書の見出し中で要素の長さの符号化が必須であると示される場合は、次の式を使用して要素の長さＬを複数ビットとして計算する。
Ｌ＝８ｐ＋ｈ
ｐは要素の長さを符号化するのに用いられるバイト数を表し（ＡＳＮ１符号化、またはこの数を符号化するのに使用される各バイトの高位ビットを使用して）、ｈはこの長さの残りのビット数を表す（ｈ＜８）。
【００８６】
要素の値を符号化するために呼び出される外部圧縮モジュール１６は、この長さを提供することができることに留意されたい。
【００８７】
要素の長さの符号化が必須でない場合は、要素の値に対応する最初のビットの値が、続くビットが要素の長さを表すか、表さないかを示す。
【００８８】
要素をサブタイプすることができる場合（文書の見出しに示される）は、圧縮された文書中で要素の値の直前に位置する要素の見出しに任意の新しいタイプを挿入する。最初のビットが、その要素タイプが予想されるタイプと異なるか、異ならないかを示す。第１の事例では、要素の見出し中の続くビットが新しいタイプのコードを含み、このコードは、要素の基本タイプのすべての可能な下位タイプに番号を付けることによって判断し、この番号付けは文書の構造を符号化することによって与えられる。
【００８９】
より正確には、文書は３つの主要なステップで符号化する。
【００９０】
第１のステップでは、各ノードから出る円弧に番号を付ける。ノードから出る円弧が１つだけの場合はこのステップは任意選択である。ｎ個の円弧が出る場合は、その円弧それぞれを、正規化の際に割り当てられる円弧の順序で与えられる番号と関連付ける（ステップ１４）。この番号はｎ’ビットで符号化し、ｎ’は、２^ｎ’―１＜ｎ≦２^ｎ’である。
【００９１】
したがって、状態Ｅからｎ回の遷移が生じる場合、各遷移は｜ｌｏｇ_２（ｎ−１）｜＋１ビットで符号化されることになる。
【００９２】
第２のステップでは、各下位オートマトンの出現回数を上述のように符号化する。
【００９３】
第３のステップでは下位オートマトンを符号化する。このプロセスは次のアルゴリズムで表すことができる。
オートマトンの開始位置に入り、
Ｗｈｉｌｅ　アクティブな状態が最終状態でない間は、
必要ならば交差する円弧を符号化する
必要ならば出現回数ｎを符号化する
到達したノードに対応する下位オートマトン中を移動する
その下位オートマトンをｎ回符号化する
最初のオートマトンに戻る
Ｅｎｄ　Ｗｈｉｌｅ
【００９４】
例えば、オートマトン（ａ_１｜ａ_２｜ａ_３）^{（０．．＊）}の出現「ａ_２　ａ_３　ａ_２　ａ_１　ａ_３」を符号化するには、出て行く円弧が３つある。したがってこの円弧は２ビットで番号を付ける。したがって、出現回数を符号化する場合、符号化の結果は以下のようになる。
００００　０１０１　０１　Ｖ_ａ２　１０　Ｖ_ａ３　００　Ｘ_ａ１　００　Ｖ_ａ１　１０　Ｖ_ａ３
「００００　０１０１」は出現回数、すなわち、５の２進値を表し、Ｖ_ａ１、Ｖ_ａ２、およびＶ_ａ３はそれぞれａ１、ａ２、およびａ３の出現の値である。
【００９５】
出現回数を符号化しない場合は
０１　Ｖ_ａ２　１０　Ｖ_ａ３　００　Ｖ_ａ１　００　Ｖ_ａ１　１０　Ｖ_ａ３　１１
となり、１１は、出て行く遷移「ｅｓｃ」の数に対応する。
【００９６】
図７ａ、７ｂの例では、オートマトン（ａ_１ ^０．．＊、ｂ_１｜ｂ_２）^０．．＊）の出現「ｂ_３　ｂ_１　ａ_１」の符号化により、次の結果が得られる（状態を併合しない場合）。
００００　００１０　シーケンスの出現回数（ここでは倍）
１　　　　　　　　　円弧「ｃｈｏ．ｂ_１．ｂ_２」の符号化
００００　００１０　グループ「ｃｈｏ．ｂ_１．ｂ_２」の出現回数（ここでは倍）
１　　　　　　　　　グループ「ｃｈｏ．ｂ_１．ｂ_２」中の円弧ｂ_２の符号化
Ｖ_ｂ２　　　　　　　値ｂ_２の符号化
０　　　　　　　　　グループ「ｃｈｏ．ｂ_１．ｂ_２」の円弧ｂ_１の符号化
Ｖ_ｂ１　　　　　　　値ｂ_１の符号化
０　　　　　　　　　円弧ａ_１の符号化
００００　０００１　ａ_１の出現回数
Ｖ_ａ１　　　　　　　ａ_１の値の符号化
１　　　　　　　　　出て行く円弧Ｆの符号化
【００９７】
状態を併合した場合（図８）は、
００００　００１０　シーケンスの出現回数
１０　　　　　　　　円弧「ｃｈｏ．ｂ_１．ｂ_２−ｂ_２」の符号化
００００　００１０　グループ「ｃｈｏ．ｂ_１．ｂ_２」の出現回数
Ｖ_ｂ２　　　　　　　　値ｂ_２の符号化
０　　　　　　　　　グループ「ｃｈｏ．ｂ_１．ｂ_２」の円弧ｂ_１の符号化
Ｖ_ｂ１　　　　　　　　値ｂ_１の符号化
００　　　　　　　　円弧ａ_１の符号化
００００　０００１　ａ_１の出現回数
Ｖ_ａ１　　　　　　　　ａ_１の値の符号化
１０　　　　　　　　出て行く円弧Ｆの符号化
【００９８】
特にグループＥＴ_ＮＯの場合に符号化を最適化するような形でスキーマが解釈され、再度順序付けされている場合には、このオートマトンを再配列することが必要となる場合がある。
【００９９】
属性の順番が有用でない場合（ＸＭＬ言語など）は、例えば英数字順など所定の順番で、そしてそれらの属性が必須か否かに従って、要素の属性を再度順序付けをするように符号化を行うことが可能である。この配列により、圧縮後の記述のサイズをその分だけ小さくすることができる。
【０１００】
文書の構造スキーマにステップ１１から１５を実行してオートマトンを得、次いでステップ１５’で文書の復号と解凍を行うことにより、このように得た文書を解凍するプロセスを行う。ステップ１５’では、文書中で遭遇する圧縮された情報要素のタイプと名前を判定できるような方式で、圧縮された文書中を移動して、ステップ１１から１４の結果得られたオートマトンを実行する。外部圧縮モジュール１６を用いて得た要素の値は、対応する解凍モジュール１６’を用いて解凍する。
【０１０１】
同じ構造スキーマを有するいくつかの文書を処理する（圧縮または解凍）場合は、ステップ１１から１５を一度だけ実行し、ステップ１５および１６（または１５’および１６’）だけを、処理する各文書に適用すればよいことに留意されたい。
【図面の簡単な説明】
【図１】
本発明による方法の様々なステップ間の結びつきを表すブロック図である。
【図２ａ、２ｂおよび２ｃ】
ツリーの形で構造スキーマを示す略図である。
【図３】
本発明による簡約化方法を図２の構造スキーマに適用することにより得られる構造スキーマの図である。
【図４ａ、４ｂ、および４ｃ】
本発明による別の簡約化方法を図２の構造スキーマに適用することにより得られる構造スキーマの図である。
【図５ａ〜５ｃ】
本発明による方法で得られ、使用される３つの有限オートマトンをそれぞれ示す図である。
【図６】
本発明による方法で使用される最適化法を表す別のオートマトンの図である。
【図７ａおよび７ｂ】
本発明によるプロセスを使用して特定の構造スキーマから得られる２つのオートマトンの図である。
【図８】
図７ａおよび７ｂに示すオートマトンに簡約化法を適用する図である。

Claims

文書の構造を定義し、文書のデータ・セットを表すネストになった構造要素（３２、３３、３４、４０、４４、４５、４６、ａ３、ａ４、Ｘ、Ｙ、ａ１、ａ５、ａ１、ａ２、Ａ、Ｂ）を含む少なくとも１つの木構造スキーマ（１；３１、３９、４３）と関連付けられた構造化文書を圧縮および解凍する方法であって、構造要素は、３つのカテゴリ、すなわち、構造化されたルート要素（３１、３９、４３）、要素のグループ（３２、３３、３４、４０、４４、４５、４６）、および、構造中の最下位レベルの要素に対応する構造化された（Ｘ、Ｙ、Ａ、Ｂ）または非構造化（ａ３、ａ４、ａ１、ａ５、ａ１、ａ２）基本要素、に分類され、各基本要素は情報タイプと関連付けられ、基本要素の少なくとも１つの情報タイプを初めに適合された圧縮アルゴリズム（１６）と関連付け、
−文書の構造スキーマの構文解析（１１）を行うステップ、
−正規化した構造スキーマをコンパイル（１３）して、１つのルート要素につき１つの有限オートマトン（５）を得、各オートマトンは、それぞれが構造要素を表す遷移（「ｍ１」、「ｍ２」、〜「ｍｎ」）によって相互に連結された状態（「０」、「１」、〜「ｎ」）を含むステップ、および
−文書に有限オートマトン（５）を実行することを含めて圧縮のために構造化文書（２）を圧縮（１５）し、前記アルゴリズムと関連づけられた情報タイプのデータ・セットに構造化文書（２）中で遭遇すると前記圧縮アルゴリズム（１６）を実行するステップ
を含むことを特徴とする方法。
圧縮された文書（１０）を解凍するために、ステップ（１１、１２、１３）を実行して、圧縮に使用されたオートマトン（５）を構造スキーマ（１）から判断することと、圧縮された文書（１０）にオートマトン（５）を実行（１５’）して文書の内容を分析することと、少なくとも同等の構造を有する元の形式に文書を再構築するために、圧縮（１５）の際に用いられた圧縮アルゴリズム（１６）に対応する解凍アルゴリズム（１６’）を実行して、オートマトンを実行しながら、圧縮された文書中に位置するバイナリ情報シーケンスから元の構造化文書（２）のデータ・セットを復元することとを含むことを特徴とする請求項１に記載の方法。
構造スキーマ（１）を文書とともに伝送する場合において、構造スキーマ（５）を伝送するステップを含むことを特徴とする請求項１または２に記載の方法。
文書の構造スキーマ（５）を正規化（１２）して、スキーマの要素の単一の所定の順番を得るステップを含むことを特徴とする請求項１から３のいずれか一項に記載の方法。
各データ・セットを圧縮された文書中に配置することにより、解凍するセットより前のデータ・セットを解凍する必要なしに、特定のデータ・セットに直接アクセスすることを可能にすることを特徴とする請求項１から４のいずれか一項に記載の方法。
各構造スキーマ要素をさらに可能な出現回数のセットと関連付け、その構造要素を有するデータ・セットが、それが属する１つ上の階層レベルのデータ・セット中に現れることができる回数を示すことを特徴とする請求項１から５のいずれか一項に記載の方法。
構造要素のグループの階層レベル数を減らすことにより文書の構造スキーマを最適化するステップを含むことを特徴とする請求項１から６のいずれか一項に記載の方法。
圧縮された文書（１０）が、元の文書のデータ・セットごとに、そのデータ・セットと関連付けられた構造要素に対応する遷移数と、圧縮されたデータ・セットの２進値とを含むことを特徴とする請求項１から７のいずれか一項に記載の方法。
圧縮された文書（１０）中で、構造スキーマの構造要素の少なくとも一部の各構造要素が、文書中におけるデータ・セットの複数回の出現と関連付けられることを特徴とする請求項８に記載の方法。
圧縮された文書（１０）中で、同じタイプのデータ・セットの数回の出現のグループの終わりが、最終状態番号への遷移を表すバイナリ・シーケンスによって見つけられることを特徴とする請求項８または９に記載の方法。