[go: up one dir, main page]

JP2007226813A - 構造化された文書を圧縮／伸長する方法 - Google Patents

構造化された文書を圧縮／伸長する方法 Download PDF

Info

Publication number
JP2007226813A
JP2007226813A JP2007054875A JP2007054875A JP2007226813A JP 2007226813 A JP2007226813 A JP 2007226813A JP 2007054875 A JP2007054875 A JP 2007054875A JP 2007054875 A JP2007054875 A JP 2007054875A JP 2007226813 A JP2007226813 A JP 2007226813A
Authority
JP
Japan
Prior art keywords
document
component
instruction
group
code
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
JP2007054875A
Other languages
English (en)
Inventor
Claude Seyrat
セラ，クロード
Cedric Thienot
ティエノ，セドリック
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Expway SA
Original Assignee
Expway SA
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Expway SA filed Critical Expway SA
Publication of JP2007226813A publication Critical patent/JP2007226813A/ja
Pending legal-status Critical Current

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N21/00—Selective content distribution, e.g. interactive television or video on demand [VOD]
    • H04N21/20—Servers specifically adapted for the distribution of content, e.g. VOD servers; Operations thereof
    • H04N21/23—Processing of content or additional data; Elementary server operations; Server middleware
    • H04N21/235—Processing of additional data, e.g. scrambling of additional data or processing content descriptors
    • H04N21/2353—Processing of additional data, e.g. scrambling of additional data or processing content descriptors specifically adapted to content descriptors, e.g. coding, compressing or processing of metadata
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
    • H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Library & Information Science (AREA)
  • Multimedia (AREA)
  • Signal Processing (AREA)
  • Document Processing Apparatus (AREA)
  • Compression, Expansion, Code Conversion, And Decoders (AREA)
  • Jellies, Jams, And Syrups (AREA)
  • Press Drives And Press Lines (AREA)
  • Input From Keyboards Or The Like (AREA)
  • Auxiliary Devices For And Details Of Packaging Control (AREA)

Abstract

【課題】構造化された文書を効率的に圧縮する。
【解決手段】文書は、文書の構造を定義し、情報要素を表す、互いの中にネストされた複数の構造成分からなる少なくとも一つの構造スキーマ（１）と関連付けられている。さらに、本発明は、上記文書の構造スキーマ（１）を解析（１１）してコンパイル（１３）し、上記スキーマの各成分について実行可能な命令（５）のシーケンスを得ること、および、ビット・ストリーム形式の伸長する文書（１０）を伸長（１４’）することからなる。命令（５）のシーケンスは、制御コードおよび要素のコードまたは成分命令の呼び出しを挿入する命令と、制御コード値に基づいて上記シーケンスの実行の進捗を制御する命令とからなる。なお、上記ステップは命令（５）のシーケンスを上記ビット・ストリームに対して実行して、元の文書を復元することを含む。
【選択図】図１

Description

発明の詳細な説明
本発明は、構造化された文書（英：structured document;仏（原語）：documents structure`s）の圧縮及び伸長に関するものである。なお、本明細書では、原語（フランス語）を併記する際、アクサン・テギュおよびアクサン・グラーブを、字母の後に付した'および`で代用表記している。
本発明は、特に、画像や動画や音声のデータなどの文書をデジタルデータ通信網を通じて転送する際や、こういった文書や文書を表すデータを記録する際に利用できるが、これに限ったものではない。
構造化された文書というのは、型と属性とに関連付けた情報要素（英：information elemtent ；仏：d'e'le'ments d'informations）を複数個集めたものであり、ここで情報要素同士は、主に階層関係にある。こういった文書は、SGML、HTML、XMLなどの構造化言語を用いており、当該構造化言語は、特に、文書を構成している、異なるサブ（二次；英：sub ；仏：sous-）情報要素を区別する。一方で、線形文書（英：linear document；仏：document dit line'aire）と呼ばれる文書では、文書の内容を定義する情報が、見栄え（プレゼンテーション；英：presentation ；仏：pre'sntation）の情報およびタイプセット（英：typeset；仏：typage）情報と混合されている。
構造化された文書は、文書中の異なる複数の情報要素を分離する目印（マーカ；英：markers 仏：repe`res）を含んでいる。SGML、XML、またはHTML形式の場合であれば、この目印は、「タグ」と呼ばれ、<XXXX>及び</XXXX>といった形をしている。また、一つ目のタグは、情報要素<XXXX>の始点を示し、二つ目のタグが該情報要素の終点を示している。各情報要素は、それより低い階層の情報要素の複数から構成されていてもよい。このように、構造化された文書は、階層状あるいはツリー状（樹状；英：tree-like；仏：arborescente）の構造スキーマを有していて、各ノードは、情報要素を表していて、上の階層のノード、すなわち、下の階層の情報要素を複数個含んだ情報要素を表す上の階層のノードに繋がっている。このツリー状構造の枝の端に配されたノードは、サブ情報要素に分割不可能な、予め定義した種類のデータを含んでいる。
このように、構造化された文書には、テキストデータまたはバイナリ（二進（の）；２値（の）；英：binary；仏：binaires）データ形式で表した分離タグが含まれていて、このタグは、情報要素またはサブ情報要素がどこからどこまでなのかを定義している。また、情報要素またはサブ情報要素は、範囲がタグで定義されたサブ情報要素を、さらに含んでいてもよい。
また、構造化された文書は、いわゆる構造スキーマ（英：structure schema；仏：sche'ma de structure）に関連していて、当該構造スキーマは、文書中の各情報要素における情報の構造と型（英：type；仏：type）とを、規則という形で定義する。スキーマは、ネスト（入れ子に；英：nested；仏：imbrique's）された成分の複数のグループからなっている。これらのグループは、順序付けされたシーケンス（ひと続き；英：sequence；仏：se'quences ）でもよいし、順序付けされた選択成分のグループでも、あるいは、順序付けしていない選択成分のグループでもよいし、または、必要な成分のグループであってもよい。
現在、複数のデジタル文書圧縮アルゴリズムがある。その中には、データの型を考慮せずに文書バイナリデータを直接処理するように設計した圧縮アルゴリズムもある。この種のアルゴリズムには、どんな種類の文書でも処理できるという長所があるが、大きな文書（音声文書や画像文書がその典型）を扱うには処理能力があまりよくない（つまり圧縮率が低い）。
画像や音声などのデータ型に特化した、効率の高い圧縮アルゴリズムも知られている。この種の圧縮アルゴリズムは、ある型のデータを対象に設計されていて、それ以外のデータを含んだ文書に対して使用すると、使えないか、もしくは効率が悪い。したがって、ある特定の型のデータに対して使用することを目的として設計した圧縮アルゴリズムでは、異なる型のデータを含んだ構造化された文書を扱うには効率があまりよくなく、また、そういった文書処理に対してうまく適応させることができない。
ＸＭＬ形式の文書の圧縮に適応化した圧縮アルゴリズムの開発については、「ＸＭＩＬＬ、ＸＭＬデータの高効率圧縮（XMILL: An Efficient Compressor for XML Data）」、エイチ・ライフク他（H. Liefke et al.）著、Sigmond Record、コンピュータ機器協会、アメリカ・ニューヨーク、No. 2、２０００年６月、１５３〜１６４頁、および「ミリアウ：ウエッブにおける、ＸＭＬの高効率表示と送信を実現する符号化方式（Millau: An Encoding Format for Efficient Representation and Exchange of XML over the Web）」、エム・ジラルドット他（M. Girardot et al.）著、Computer Networks and ISDN Systems、North Holland Publising, アムステルダム、NL、Vol. 33、No. 1-6、２０００年６月に記載がある。
本発明の目的は、上記の短所を解消することである。この目的は、構造化された文書を圧縮する、以下のような方法を提供することで達成できる。つまり、この構造化された文書は、互いの中にネストされた複数の情報要素からなり、情報要素は、各々ある情報の型と関連付けられている。さらに、この構造化された文書には、互いの中にネストされた複数の構造成分からなり、文書のツリー状構造を定義する少なくとも一つの構造スキーマと関連付けられている。文書情報（英：document information；仏：d'indormation du document）の型は、それぞれ、該スキーマ中のある成分によって定義されている。
本発明によれば、この方法は、上記文書構造スキーマを解析して上記構造スキーマの各成分について実行可能な命令のシーケンス（連続；英：sequence；仏：se'quence）を得るステップからなり、
該命令のシーケンスは、制御コードおよび情報要素の圧縮値または成分の命令シーケンスの呼び出しコードを挿入する命令と、制御コードの値の関数として、上記シーケンスの実行を制御する命令とからなり、
上記構造化された文書に対する上記命令シーケンスの実行は、上記構造化された文書を文書中の情報要素の圧縮値を含んだビット・ストリーム（流れ；英；stream 仏：flux binaire）に圧縮する。
この方法が、構造化された文書に対して命令シーケンスを実行するステップをさらに含んでいればより有利な効果がある。
本発明のある特殊な態様では、上記文書がサブ要素に分解できない基底要素からなり、少なくとも一つの型の基底要素情報が、前もってその情報の型にあわせた圧縮アルゴリズムと関連付けられ、該方法が、上記命令シーケンスの実行中に、そのアルゴリズムと関連付けられた型の各情報要素の値に対して、上記圧縮アルゴリズムを適用することを含んでいる。
本発明の別の特殊な態様では、上記方法が、上記構造スキーマの各成分について得られた命令シーケンスをコンパイルして、上記構造スキーマ専用、かつ、コンピュータによって直接実行可能もしくは解釈可能で、上記構造スキーマを有する文書を圧縮するためのバイナリ符号化プログラムを得るステップを含んでいる。
本発明の別の特殊な態様では、上記方法が、文書構造スキーマを前もって正規化して、上記スキーマの成分の、予め定義された一つの順序を得るステップを含んでいる。
本発明の別の特殊な態様では、上記方法が、構造成分におけるネストのレベルの個数を減らすことからなり、上記文書構造スキーマを前もって最適化し簡素化するステップを含んでいる。
上記文書中の少なくとも一つの情報要素は、上記生成されたビット・ストリーム中の情報要素コードと対応付けられており、当該情報要素コードは、上記ビット・ストリーム中で、その要素に先行する情報要素を伸長しなくても、当該ビット・ストリーム中のある特定の圧縮した情報要素に直接アクセスできるようにマークされていれば、より有利な効果がある。
本発明のさらに別の特殊な態様では、上記生成された圧縮文書が、上記構造化された文書の各情報要素について、情報要素に関連付けられている情報の型と該情報要素のバイナリ値とを決定するために用いるコードを含んでいる。
本発明のさらに別の特殊な態様では、上記文書構造スキーマが少なくとも一つの型の情報のサブタイプの定義を含み、
n個のサブタイプを有する型の成分のために生成した上記命令シーケンスが、
上記文書の成分に対応する要素に適用するサブタイプを表すサブタイプコードを挿入し、ビット数で表した、このコードのサイズに関連した命令と、
上記サブタイプコードの値をテストする命令とを順に含み、
各テスト命令が、サブタイプコードのテスト済みの値と対応する要素のサブタイプへの参照と、上記サブタイプと関連付けられた要素の圧縮のために生成された命令シーケンスとに関連付けられている。
上記文書中の少なくとも一つの情報要素からなる要素群が複数回出現することに対応した成分について生成した上記ビット・ストリームが、予め定義したエンド・コードを含んでいれば好ましい。
本発明のさらに別の特殊な態様では、上記構造スキーマの各成分が、少なくとも一つの情報要素からなる上記文書中の要素群に対応し、また、出現する可能性のある回数の組（セット；英：set ；仏：ensemble）と関連付けられていて、この組は、この成分に対応する要素群がそれの属するレベルのすぐ上のレベルの情報要素中に現われえる回数を示している。
本発明のさらに別の特殊な態様では、出現回数が０か１に等しい成分のために生成した上記命令シーケンスが、
上記成分に対応する要素群が上記文書中に存在するかしないかを示す１ビットによる存在コードを挿入する命令と、
上記存在コードの値をテストする命令と、
上記テスト命令に関連して、上記文書中に該要素群が存在することを存在コードの値が示している場合、関連する出現回数とは無関係に、上記成分のために生成された命令シーケンスと、を順に含んでいる。
本発明のさらに別の特殊な態様では、出現回数がｎとｍとの間の成分のために生成した上記命令シーケンスが、
上記圧縮文書中で上記成分に対応する要素群が連続して出現する回数から最低出現回数を引いたものを示す出現回数コードを挿入し、ビット数で表した、このコードのサイズに関連した命令と、
上記出現回数コードの値に対応した反復回数を定義するループ命令と、
上記ループ命令に関連して、関連する出現回数とは無関係に、上記成分のために生成された命令シーケンスとを順に含んでいる。
本発明のさらに別の特殊な態様では、出現回数が０とｍとの間の成分のために生成した上記命令シーケンスが、さらに、
上記文書中で上記成分に対応する要素群が少なくとも一回出現するかしないかを示す存在コードを挿入する命令と、
少なくとも一つの要素群が存在することを存在コードの値が示している場合、出現回数が１とｍとの間の成分のために生成した命令シーケンスに関連する存在コードの値をテストする命令とを含んでいる。
本発明のさらに別の特殊な態様では、出現回数がｎとｍとの間の成分のために生成した上記命令シーケンスが、
上記文書中の上記成分に対応する要素群の出現を報知する１ビットの存在コードを挿入し、ビット数で表した、このコードのサイズに関連した命令と、
挿入する上記存在コードが上記要素群の新たな出現を示している限り実行するループ命令と、
上記ループ命令と関連して、上記成分のために生成した命令シーケンスと、上記文書中で上記要素群が新たに出現することを報知する１ビットの存在コードを新たに挿入する命令とを順に含んでいる。
本発明のさらに別の特殊な態様では、上記構造スキーマ中の各成分が、少なくとも一つの情報要素からなる要素群に対応し、
上記構造化された文書（２）の構造スキーマ（１）は、順序付けした成分からなる、少なくとも一つのシーケンス型（順序型；英：sequence type；仏：de type se'quence）成分を含んでおり、当該シーケンス中で現われる順序は、上記シーケンス型グループの成分に対応する要素群が文書中で現われる順序を定義し、また、
n個の成分からなるシーケンスのために生成した上記命令シーケンスが、該シーケンス中の各成分のために生成した命令シーケンスを連続して含んでいる。
本発明のさらに別の特殊な態様では、上記構造スキーマの各成分が、少なくとも一つの情報要素からなる要素群に対応し、圧縮する上記文書の構造スキーマが選択成分グループ型の成分を少なくとも一つ含み、各選択成分が情報要素群に対応し、上記選択成分グループ型の成分が、上記文書中の選択成分に対応する情報群の一つに対応し、
対応するn個の要素群を定義するn個の成分からなる選択成分のグループのために生成した上記命令シーケンスが、
n個の要素群のうちでどの要素群が文書中で現われるかを示す要素群番号コードを挿入し、ビット数で表した、このコードのサイズに関連した命令と、
上記要素群番号コードの値をテストする、複数の命令とを順に含み、各テスト命令は、それぞれ要素群番号コードのテスト済みの値に対応する要素群（Xi）に対応する成分のために生成された命令シーケンスに関連付けられている。
本発明のさらに別の特殊な態様では、上記構造スキーマの各成分が、少なくとも一つの情報要素からなる要素群に対応し、
圧縮する上記文書の構造スキーマが、少なくとも一つの順序付けしていない成分の型のグループを含み、順序付けしていないグループ中の各成分が要素群に対応し、順序付けしていないグループ型のグループが、上記文書において、上記順序付けしていない型のグループの成分に対応する全ての要素群を任意の順序で含んだグループに対応し、
文書中のn個の要素群に対応するn個の成分からなる順序付けしていない型のグループのために生成した上記命令シーケンスが、
上記文書中で次に現われる要素群を示す要素群の番号コードを挿入し、ビット数で表した、このコードのサイズに関連した命令と、
上記要素群番号コードの値をテストする命令とを順に含み、各テスト命令は、それぞれ、要素群番号コードのテスト済みの値に対応する要素群に対応する成分のために生成された命令シーケンスと、当該要素群に対応する成分を除いた、順序付けしていないグループの全ての成分からなる順序付けしていない型のグループのために生成された命令シーケンスと関連付けられている。
また、本発明は、互いの中にネストされて、それぞれが情報の型と関連付けられている複数の情報要素からなる構造化された文書を伸長する方法に関し、上記構造化された文書は、文書のツリー状構造を定義し、互いの中にネストされた複数の構造成分からなる少なくとも一つの構造スキーマと関連付けられていて、文書情報の型はそれぞれ上記スキーマの成分によって定義されている。
本発明によると、この方法は、上記文書構造スキーマを解析して上記構造スキーマの各成分について実行可能な命令のシーケンスを得るステップからなり、
このシーケンスは、
制御コードと、情報要素の圧縮値、または成分命令シーケンスを呼び出す呼び出しコードとを読み取る命令と、
上記圧縮文書を形成するビット・ストリームにおいて、上記制御コード値の関数として上記シーケンスの実行を制御する命令とを含み、
命令シーケンスを上記圧縮文書に対して実行すれば、元の文書と同じ形式かつ少なくとも同等の構造に文書が復元できる。
この方法が、伸長する文書を構成するビット・ストリームに対して命令シーケンスを実行するステップをさらに含んでいればより有利な効果がある。
本発明の特殊な態様では、上記構造化された文書がサブ要素に分解できない基底要素からなり、少なくとも一つの型の基底要素情報が、その情報の型にあわせた伸長アルゴリズムと関連付けられ、該方法が、上記圧縮文書を形成するビット・ストリーム中の命令シーケンスの実行中にビット・ストリーム中の上記情報型に対応する情報要素バイナリコードを検出し、このバイナリコードに対して上記伸長アルゴリズムを適用する。
本発明の別の特殊な態様では、上記方法が、上記構造スキーマの各成分について得られた命令シーケンスをコンパイルして、上記構造スキーマ専用、かつ、コンピュータによって直接実行可能もしくは解釈可能で、この構造スキーマを有する文書を伸長するためのバイナリ復号化プログラムを得るステップを含んでいる。
本発明のさらに別の特殊な態様では、上記方法が、文書構造スキーマを前もって正規化して、上記スキーマの成分の、予め定義された一つの順序を得るステップを含んでいる。
本発明のさらに別の特殊な態様では、上記方法が、構造成分グループの階層の個数を選らすことからなり、上記文書構造スキーマを前もって最適化し簡素化するステップを含んでいる。
ビット・ストリーム中で、その要素に先行する情報要素を伸長しなくても、この情報要素に直接アクセスできるように、少なくとも一つの情報要素コードを上記圧縮文書のビット・ストリーム中で識別すれば、より有利な効果がある。
本発明のさらに別の特殊な態様では、上記情報要素と圧縮した情報要素のバイナリの値とに関連付けられた情報型を決定するために、上記圧縮文書が元の文書における各情報要素のコードを含んでいる。
本発明のさらに別の特殊な態様では、伸長する上記文書の構造スキーマが少なくとも一つの情報型のサブタイプの定義を含み、
n個のサブタイプを有する型の成分のために生成した命令シーケンスが、
文書中の成分に対応した要素に適用するサブタイプの番号を表すサブタイプコードを読み取り、ビット数で表した、このコードのサイズに関連した命令と、
当該サブタイプコードの値をテストする命令とを順に含み、上記各テスト命令は、それぞれ、サブタイプコードのテスト済みの値と対応する要素のサブタイプへの参照と、サブタイプと関連付けられた要素の伸長のために生成された命令シーケンスとに関連付けられている。
上記スキーマの成分に対応する少なくとも一つの情報要素からなる要素群が複数回出現するグループの末尾は、上記圧縮文書のビット・ストリームにおいて所定のバイナリコードでマークされていれば好ましい。
本発明のさらに別の特殊な態様では、上記構造スキーマの各成分が、少なくとも一つの情報要素からなる文書のビット・ストリームの要素群に対応し、また、出現する可能性のある回数の組と関連付けられていて、この組は、この構造成分に対応する要素群が、それの属するレベルのすぐ上のレベルの情報要素中に現われえる回数を示している。
本発明のさらに別の特殊な態様では、出現回数が０か１に等しい成分のために生成した上記命令シーケンスが、
上記成分に対応する要素群が上記圧縮文書中に存在するかしないかを示す１ビットの存在コードを読み取る命令と、
上記存在コードの値をテストする命令と、
上記テスト命令に関連して、上記圧縮文書中に該要素群が存在することを存在コード値が示している場合、関連する出現回数とは無関係に、上記成分のために生成された命令シーケンスと、を順に含んでいる。
本発明のさらに別の特殊な態様では、出現回数がｎとｍとの間の成分のために生成した上記命令シーケンスが、
上記圧縮文書中で上記成分に対応する要素群が連続して出現する回数から最低出現回数を引いたものを示す出現回数コードを読み取り、ビット数で表したこのコードのサイズに関連した命令と、
出現回数コードの値に対応する反復回数を定義するループ命令と、
上記ループ命令に関連して、関連する出現回数とは無関係に、上記成分のために生成された命令シーケンスと、を順に含んでいる。
本発明のさらに別の特殊な態様では、出現回数が０とｍとの間の成分のために生成した上記命令シーケンスが、さらに、
上記圧縮文書中で上記成分に対応する要素群が少なくとも一回出現するかしないかを示す１ビットの存在コードを読み取る命令と、
少なくとも一つの要素群が存在することを存在コードの値が示している場合、出現回数が１とｎとの間の成分のために生成した命令シーケンスに関連する存在コードの値をテストする命令とを含んでいる。
本発明のさらに別の特殊な態様では、出現回数がｎとｍとの間の成分について生成した上記命令シーケンスが、
上記圧縮文書中の上記成分に対応する要素群の出現が出現するかしないかを示す１ビットの存在コードを読み取り、ビット数で表した、このコードのサイズに関連した命令と、
上記圧縮文書のビット・ストリームから読み取った上記存在コードが上記要素群の新たな出現を示している限り実行するループ命令と、
上記ループ命令と関連して、上記成分について生成した命令シーケンスと、上記圧縮文書中で上記要素群が新たに出現するかしないかを示す１ビットの存在コードを新たに挿入する命令とを連続して含んでいる。
本発明のさらに別の特殊な態様では、上記構造スキーマの各成分が少なくとも一つの情報要素からなる要素群に対応し、
上記圧縮文書の構造スキーマが、順序付けした成分からなる、少なくとも一つのシーケンス型成分を含んでおり、上記シーケンス中で現われる順序が上記シーケンス型グループの成分に対応する要素群が文書中で現われる順序を定義し、また、
n個の成分からなるシーケンスのために生成した上記命令シーケンスが、該シーケンス中の各成分のために生成した命令シーケンスを連続して含んでいる。
本発明のさらに別の特殊な態様では、上記構造スキーマの各成分が、少なくとも一つの情報要素からなる要素群に対応し、
伸長する上記文書の構造スキーマが選択成分グループ型の成分を少なくとも一つ含んでいて、各選択成分が情報要素群に対応し、上記選択成分グループ型の成分が、上記文書中で選択成分に対応する情報群の一つに対応し、
選択成分のグループのために生成した上記命令シーケンスが、n個の要素（X1, X2, ..., Xn）群をそれぞれ定義するn個の成分からなり、
n個の要素群のうちで上記文書中に現われる要素群を示す要素群番号コードを読み取り、ビット数で表した、このコードのサイズに関連した命令と、
上記要素群番号コードの値をテストする複数の命令とを順に含み、各テスト命令は、それぞれ要素群番号コードのテスト済みの値に対応する要素群に対応する成分のために生成された命令シーケンスに関連付けられている。
本発明のさらに別の特殊な態様では、上記構造スキーマの各成分が、少なくとも一つの情報要素からなる要素群に対応し、
圧縮する上記文書の構造スキーマが、少なくとも一つの、順序付けしていない成分の型のグループからなり、順序付けしていないグループ中の各成分が要素群に対応し、順序付けしていないグループ型のグループが、上記文書において、上記順序付けしていない型のグループの成分に対応する全ての要素群を任意の順序で含んだグループに対応し、
文書中のn個の要素群に対応するn個の成分からなる順序付けしていない型のグループについて生成した上記命令シーケンスが、
上記文書中で次に現われる要素群を示す要素群の番号コードを読み取り、ビット数で表した、このコードのサイズに関連した命令と、
上記要素群番号コードの値をテストする命令とを順に含み、各テスト命令は、それぞれ、要素群番号コードのテスト済みの値に対応する要素群に対応する成分のために生成された命令シーケンスと、当該要素群に対応する成分を除いた、順序付けしていないグループの全ての成分からなる順序付けしていない型のグループのために生成した命令シーケンスとに関連付けられている。
次に、添付の図面を参照しながら、本発明の好適な実施の形態を例にとって説明するが、本発明はこの例に限定されるものではない。
図１は、本発明の方法における異なるステップを示すブロック図である。
図２ａ、２ｂ、２ｃは、ツリー状構造スキーマを描いた図である。
図３は、本発明の低減方法を図２の構造スキーマに適用して得られた構造スキーマを示す図である。
図４ａ、４ｂ、４ｃは、本発明の別の低減方法を図２の構造スキーマに適用して得られた構造スキーマを示す図である。
図１は、本発明の方法における、異なるステップ間のつながりを示している。
この方法は、文書構造を定義する構造スキーマ１と該文書の構造化された情報２とからなる、構造化された文書を扱うために設計されている。
次に示すのは、構造スキーマの形式を、XMLスキーマ言語を使って示した一例である。
<element name= "C">
<complexType>
<Choice>
<element name="A" type="TA" minOccurs=1 maxOccurs=1/>
<element name="B" type="TB" minOccurs=1 maxOccurs=1/>
</Choice>
<attribute name="a2" required=false type="boolean"/>
<attribute name="a1" required=true type="integer"/>
</complexType>
</element>
このスキーマは、「c」という構造成分（コンポーネント；英：component；仏：composant ）が、第一の省略可能なブーリアン（論理；英：boolean；仏：boole'en）型の属性a2と、構造中に常に存在する第二の整数型の属性a1と、型がそれぞれ「TA」、「TB」と表される選択成分A、Bのグループとからなる複雑構造を有していることを示している。なお、選択成分A、Bは、いずれか一つが一回だけ構造中に現われる。
型TAとTBとは、文書構造スキーマにおいて、類似の（アナログの；英：analogue；仏：analogue）形成方法で定義される。
文書構造を定義するには、成分グループと呼ばれる特定の成分を複数個用いるのが一般的である。
これらの成分グループは、例えば次のような型が考えられる。
・順序付けされた成分のリストを定義するSEQ。文書中の対応する要素全ては、該リストにおいて指定された順序で掲載されていなければならない。
・選択成分のグループを定義するCHO。グループの成分に対応する一つの要素が、文書中に含まれていなければならない。
・複数成分からなるグループを定義するAND。この成分に対応する要素は、全て任意の順序で文書中に含まれていなければならず、この順序は、変更してはならない。XMLスキーマの規格（基準；標準；英：standard ；仏：norme）では、このグループは、「all（全て）」のグループに相当する。
・複数成分からなるグループを定義するANDNO。この成分に対応する要素は、全て任意の順序で文書中に含まれていなければならず、この順序は、重要ではない。このグループを使って、XMLの規格では順序が重要でない属性を符号化してもよい。
・文書中で見つかる可能性のある要素を全て含んだANY。
本発明では、この形成方法を本方法のステップ１１で解析・変形し、各構造成分について一つの構文ツリー（シンタックス・ツリー；英：syntactic tree；仏：arbres syntaxiques）４を得る。構造TCを有する成分に対応する構文ツリーを次式で表す。
TC→SEQ[1,1]( ANDNO[1,1](a1int[1,1],a2bool[0,1]),CHO[1,1](ATA[1,1],BTB[1,1]))
ここで、A[x,y]は、成分Aが文書中でX回からY回までの間で繰り返し現われる要素に相当することを示し、この繰り返し回数を不定値を表す記号「*」で表すこともできる。
この数式を、図２ｃのようにツリーで表すこともできる。この場合、ツリーは、ルート成分（根；英：root component；仏：composant racine）TC４３を含み、当該ルート成分TC４３では、シーケンス型成分４４からなるグループが一回現われる。このグループでは、AND型成分４５からなる、順序付けしていないグループが一回と、選択成分４６からなるグループが一回現われる。グループ４５では、整数a1とブーリアンa2とが一回ずつ現われる。さらに、グループ４６は、一回出現する、型がTAで名前がAの要素と、一回出現する、型がTBで名前がBの要素とを含んでいる。ステップ１１で得られた型TAとTBとは、次の公式
TA→SEQ[1,1](AND[1,1](a3int[1,1],a4int[0,1]),SEQ[1,1](XTC[1,1],YTC[1,1]))
TB→SEQ[1,1](a1bool[1,1],a5bool[1,1])
によって求めてもよく、このとき、それぞれ図２ａと図２ｂに示すツリーで表される。
型TA３１は、シーケンス型グループ３２が一つからなり、このグループ３２は、一つのAND型グループ３３と一つのシーケンス型グループ３４との二グループからなる。グループ３３では、整数型が二回（つまり、a3、a4）現われる。グループ３４では、TC型が二回（つまり、XとY）現われる。
型TB３９は、シーケンス型グループ４０一つからなり、このシーケンス型グループ４０は、二つのブーリアンa1、a5からなる。上記では、要素名とその型とを区別してきたが、本発明の方法は、この区別をしない構造化言語に対しても適用できる。
さらに、XMLスキーマ言語のように、「ポリモフィズム（多態性；英：polymorphism；仏：polymorphisme）」と呼ばれるもの、あるいは、サブタイプ（二次型；英：sub types；仏：sous-types）の使用を可能にする言語もある。
このサブタイプは、以下のように定義する。
<complexType name="TA1">
<restriction base="TA">
</restriction>
</complexType>

<complexType type="TA2">
<extension base="TA">
</extension>
</complexType>
<element name="X" type="TA" />
この構文は、制限または拡張によって、型TA1とTA2が型TAのサブタイプであると定義する。また、型TAの情報成分Xを定義する。
この構造スキーマを有する文書には、型TA1の要素Xを含ませることができるが、該要素Xは、
<X xsi:type="TA1">
を使って追加すればよい。
さらに、このようにサブタイプを有する型の中には、アブストラクト（抽象（的）；英：abstract；仏：abstraits）であると宣言してもよいものがある。こう宣言するということは、つまり、あるアブストラクト型の定義を含んだ構造スキーマを有する文書中の情報要素が、アブストラクト型の情報要素を必ずしも含んでいるわけではないということを意味している。アブストラクト要素は、階層またはタイプクラス（型クラス；英：type classes；仏：des classes de types）の生成にしか使わない。XMLスキーマ言語では、アブストラクト型を次のように定義する。
<complexType name="a" type="TA" abstraet="true">
</complexType>
また、構造成分は、決定論的（決定性；英：deterministic；仏：de'terministes）でないといけない。つまり、文書の要素は、一通りにしか解釈できないものでないといけない。例えば、CHO(a,SEQ(a,b))スキーマでは、aが文書中に現われた場合には、その後、bが現われるはずなのかどうかが分からない。こういった目的を持ったアルゴリズムがあり、本発明の方法に対して該アルゴリズムを適用すれば、非決定論的スキーマを決定論的スキーマに変えられる。参考文献としては、例えば、「正規表現から有限オートマタへ（Regular expressions into finite automata）」、ブルッグマン−クレイン、アン（Bruggemann-Klein, Anne）著、Extended Abstract in I. Simon. Hrsg., LATIN 1992, S. 97-98. Springer-Verlag, Berlin 1992（全稿は、Theoretical Computer Science 120; 197-213, 1993に掲載）が挙げられる。このように、上記スキーマをSEQ(a,b[0,1])で置き換えることができる。
本発明の方法の次のステップ１２では、構文ツリーに変形した構造スキーマの成分に対して処理を行い、構文ツリーを縮小または簡素化する。
この縮小処理は、例えば、図３のように、全てのツリー３１、３９、４３から構文ツリー５１を一つ生成する、全体的に平坦化（英：flattening；仏：aplatissement）する方法からなっていればよい。
実際には、このツリーは、文書中で出会う可能性のある要素型すべてを挙げた辞書を示し、要素は、文書中で少なくとも一回[1,*]は現われる選択型グループ５２にまとめてある。このツリーでは、複合（英：complex；仏：complexe）型成分A、B、X、YがANY型と関連付けられている。また、異なる型で二回（成分TBとTCにおいて）現われる成分a1が、XML言語に従って、デフォルトである"pcdata"型と関連付けられているか、あるいは初期文書中の要素型（例えばテキスト）と関連付けられている。同じ情報要素を実際には違う方法で表していてもよい。例えば、バイナリシーケンスも文字列または整数であると考えてもよい。
変形例を挙げると、この縮小処理は、構文ツリーを局部的に平坦化して、図４ａ〜４ｃで３１’、３９’、４３’で表したツリーを得ることからなっていてもよい。
これら各図では、グループ３２〜３４（図２ａ）、４０（図２ｂ）、４４〜４６（図２ｅ）が、少なくとも一回[1,*]は現われる選択型グループ５３、５４、５５とそれぞれ置き換えられている。
ツリーTA、TB、TCをさらに処理して、上記構造スキーマに現われる曖昧さを排除してもよい。
生成するバイナリコードをよりコンパクトなものにしつつ、構文ツリーを壊さずに簡素化してもよい場合もある。
この種類の簡素化は、最低出現回数nxが０か１に等しい成分Xを一つ含む成分のグループの場合には、以下の形式で実行してもよい。
GROUP[nG, mG](X[nx, mx])
ここで、グループは、SEQ、CHO、またはAND型のグループである。任意のグループを次の成分で置き換えてもよい。
X[nG.nx,mG.mx]
ツリーを壊さずに簡素化ができる他の場合として、選択成分CHOのグループが、最低出現回数が０に等しい、少なくとも一つの成分からなる場合が挙げられる。このように、グループ CHO[nc,mc](X1[ nx1,mx1],X2[0,mx2],X3[ nx3,mx3])を、CHO[0,mc](X1[nx1,mx1],X2[1,mx2],X3[nx3,mx3])に置き換えることができる。
同様に、CHO型が一回出現する、特に、CHO型の出現を一回含むグループCHO[1,1](..., CHO[1,1](...), ...)は、これを、上記両CHO型グループの成分を全て含んだCHO型のCHO[1,1](...)グループ一つと置き換えることで簡略化できる。
ステップ１２では、ツリーTA、TB、TCにも正規化処理を行う。この正規化処理は、スキーマ中の成分の順序を一つ得るために、スキーマを再度順序付けすることからなる。次に、この処理は、先の処理で得られた構文ツリーの異なるノードに二進数を割り当てる。この二進数は、対応する情報要素を圧縮する際に使われる。
特に、正規化処理は、先に順序付けをしておいたグループ内の全ての成分の署名とグループ名を連結することによって生成され、各グループに割り当てることからなる。このようにして、図４のグループ５３は、CHO.a3.a4.X.Yという署名と関連づけられている。
この処理では、順序付けしたグループ（SEQ）は既に正規化されているとみなされる。したがって、正規化するグループは、選択型グループ（CHO）、AND型グループ、それにANDNO型グループである。この処理は、サブグループgiと、文書中で対応する要素を定義する成分eiとからなる各グループG毎に、以下のステップからなる。
・グループGが正規化される前にグループG内にサブグループgiがあれば、これを正規化するステップ。この正規化アルゴリズムは、再帰的である。
・さらに、サブグループgiの前にグループG中に成分eiがあれば、これを記録するステップ、
・予め定義した順に成分eiを記録するステップ、
・予め定義した順にサブグループgiを記録するステップ、および、
・上記ステップで生成した順にグループGの成分（およびサブグループ）の全ての署名を連結することによって、グループGの署名を決定するステップ。
上記のように、グループ成分は、予め定義した順に記録するのであるが、この順序は、対応する署名のアルファベット順であってもよい。あるいは、最低出現回数が多い順であってもよい。後者の場合、最低出現回数が同じ成分はアルファベット順に記録する。
なお、この正規化処理は、本発明の方法では必須ではない。スキーマ中で成分が現われる順序は、維持することができる。
該方法における次のステップ１３は、ビット・ストリームを表す「バイナリ構文」とも呼ばれる命令シーケンス５を生成することからなる。この処理は、構造スキーマ内の各構文ツリーまたは複合型毎に、命令シーケンスを生成することからなる。該命令シーケンスの生成は、文書ツリー状構造スキーマ中の構文ツリーにおける最下層レベルでのノードまたは成分から始める。最下層レベルのノードについて、このようにして生成したバイナリ構文に対する呼び出し命令は、次に、その下層レベル成分が現われる、より上層レベルのノード用のバイナリ構文に挿入される。この結果、文書構造スキーマ全体について、バイナリ構文が一つ得られ、これが、ソフトウェアを形成する主プログラムがサブプログラムを呼び出し、サブプログラムがさらに別のサブプログラムを呼び出すといったのと同様に、より下層のレベル成分用のバイナリ構文を呼び出す。
型がTXである要素Xを表す成分のバイナリ構文は以下のような形式である。
Figure 2007226813
ここで、「X」は、要素Xの値を挿入するか読み取る、あるいは、要素Xに対応する命令シーケンスを呼び出す命令を表している。また、「TX」は、要素Xの型への参照を表している。
型TXがサブタイプを一つあるいは複数個有するのであれば、ポリモフィズムと呼ばれる状態であることを表している。この場合、次に記すバイナリ構文と関連付けられている。
Figure 2007226813
型TXがサブタイプS1、S2、．．．Snからなるのであれば、デフォルトの型TXがアブストラクトであるか否かによって、二つの異なる場合を考えなければならない。
上記デフォルト型TXがアブストラクトであれば、TX_polyバイナリ構文は、以下のものを順番に含む。つまり、
・要素Xに適用するサブタイプの番号（英：number；仏：nume'ro）を表すサブタイプのコードflagPolyを挿入または読み取り、ビット数として、このコードのサイズと関連付けられた一つの命令。および、
・サブタイプコードの値をテストする複数の命令。当該各テスト命令は、
それぞれ、要素Xの値を挿入するまたは読み取る命令、あるいは、要素Xに対応した命令シーケンスを呼び出す命令と関連付けられており、当該テスト命令は、サブタイプコードのテスト値に対応する要素Xのサブタイプへの参照と関連付けられている。
この操作の前に、サブタイプＳ１、．．．Ｓｎは署名の順に並べる。
このバイナリ構文の型は、例えば、次の形式であればよい。
Figure 2007226813
ここで、E()は、次に大きな整数に繰り上げる関数を示している。また、"flagPoly"は要素Xに適用するサブタイプの番号コードを含む。また、Xは、要素Xのコードを挿入しないといけない位置を示している。
2E(log2(n))＞nであれば、バイナリシーケンスの最後に次の一行を加えて、誤作動を検出することができる。なお、上記式および以降の式において、上付きのＥ（log2(n)）は、上付きのＥ（log2(n)）を意味している。
Figure 2007226813
ここで、SpecificProcessとは、flagPoly値がTXのサブタイプに対応しないときに、処理エラーを知らせるよう設計した手順のことである。
上記デフォルト型TXがアブストラクトでなければ、以下のものが連続して含まれているバイナリ構文に、先のバイナリ構文を挿入することで、TX1Polyのバイナリ構文が得られる。つまり、
・要素型が上記デフォルト型であるのか、あるいは、このデフォルト型のサブタイプであるのかを示す１ビットのサブタイピング存在コードtypInfoFlagを挿入するまたは読み取る命令。
・サブタイピング存在コードの値をテストする命令、および、
・このテスト命令と関連して、要素型がサブタイプであることをサブタイピング存在コードの値が示している場合、表１に示すようなポリモフィズムを定義する命令シーケンス、他の場合には、要素Xのデフォルト型への参照と関連付けて要素Xの値を挿入するまたは読み取る命令。
このバイナリ構文の型は、例えば、次の形式であればよい。
Figure 2007226813
ここで、typeInfoFlagは、Xの型がTXであるのか、あるいはTXのサブタイプの一つであるのかを示すコードである。
次のステップでは、バイナリ構文が決定した要素あるいは要素群X各々の出現回数[n,m]のバイナリ構文を決定する。以下では、要素群を要素と記述することもある。
この目的のために、三つの場合を区別する。第一の場合では、mもnも１に等しい。つまり、成分Xは、出現回数[1,1]と関連している。このとき生成されるバイナリ構文は、成分X用に生成されたバイナリ構文に対応する。
第二の場合には、n＝0、m＝1で、生成されるバイナリ構文は、次のものを連続して含む。つまり、
・要素Xが圧縮された文書（圧縮文書）中に存在するかしないかを示す、１ビットの存在コード"flagX"を挿入あるいは読み取り、ビット数として、このコードのサイズと関連付けられた命令。
・存在コードの値をテストする命令。および、
・このテスト命令と関連して、要素Xが文書中に存在することを上記存在コードの値が示しているときに、該要素Xの値を挿入するまたは読み取る命令、あるいは、要素Xに対応する命令シーケンスを呼び出す命令。
このバイナリ構文の型は、例えば、次の形式であればよい。
Figure 2007226813
ここで、flagXは、文書中にXが存在するかしないかを示す１ビットのコードである。このバイナリ構文は、インジケータflagXの値が「真」に等しければXを挿入するという命令をプログラミングするシーケンスに類似している。
第３の場合には、m−nが所定の閾値定数、例えば216（＝65536）より小さく、これは出現回数が１６ビットの符号なし整数の形で符号化されていることを意味している。この場合、上記要素X[n,m]のバイナリ構文は、以下のものを連続して含んでいる。つまり、
・要素Xが現われる最低回数nを圧縮文書で要素Xが連続して現われる回数から引いた数を表す出現回数コードloopflagXを、挿入または読み取り、ビット数で表した、このコードのサイズに関連付けられた命令。
・出現回数コードの値に対応する繰り返し回数を定義するループ命令。および、
・上記ループ命令に関連して、要素Xの値を挿入するまたは読み取る、あるいは、要素Xに対応する命令シーケンスを呼び出す命令。
このバイナリ構文の型は、例えば、次の形式であればよい。
Figure 2007226813
ここでloopflagXは、文書中にXが連続して現われる回数からXの最低出現回数を引いた数を示すコードであり、E()は次に大きな整数に繰り上げる関数である。
この構文は、loopflagXがE(log2(m-n+1))ビットで符号化してあること、それに、Xを、(loopflagX+n)回挿入しなければならないことを示している。
第４の場合には、mの値に制限がない、もしくは、m−nが所定の閾値定数より大きい。生成されるバイナリ構文は、第３の場合のバイナリ構文に類似しているが、loopflagXをE(log2(m-n+1))ビットで符号化するのではなく、整数であればなんでも符号化することができる別の形式で符号化している。
こういった形式には、例えば、UlNT＿VLC形式がある。UlNT＿VLC形式は、所定ビット数（例えば５ビット）の組み合わせからなっていて、この組み合わせが整数のコードにおける最後の組み合わせなのかどうかを、各組み合わせの第１のビットが示し、続く４ビットが整数をコード化するのに使われる。
第３の場合と第４の場合、最低出現回数nが0であれば、次のものを含んだバイナリ構文を加えるのが好ましい。つまり、
・１ビットの存在コードshuntflagXを挿入するまたは読み取る命令。当該存在コードshuntflagXは、圧縮文書中に要素Xが一つ以上存在するかしないかを示している。および、
・要素Xが少なくとも一つ存在することをこの存在コード値が示しているとき、1とmの間の要素Xの出現回数と同じ回数生成した命令シーケンスに関連して、該存在コード値をテストする命令。
このバイナリ構文の型は、例えば、次の形式であればよい。
Figure 2007226813
ここで、shuntFlagは、出現回数が0であるかどうかを表す１ビットのコードを示す。また、「binary syntax of X[n,m]」とある一行は、第３の場合あるいは第４の場合に対応する出現回数Xのバイナリ構文である。
変形例を挙げると、構造スキーマの要素の出現回数を入力しなくてもよい場合には、上記のものとは異なる種類の符号化を選んでもよい。この種の符号化では、次のものを連続して含むバイナリ構文を使う。つまり、
・文書中に要素Xが現われるかどうかを示す、１ビットのflagX存在コードを挿入または読み取り、ビット数で表した、このコードのサイズに関連付けられた命令。
・挿入した読み取った上記存在コードが要素Xの新たな出現の存在を示している限り実行されるループ命令。
・上記ループ命令に関連して、要素Xの値を挿入するまたは読み取る、あるいは要素Xに対応する命令シーケンスを呼び出す命令。および、
・文書中で要素Xが新たに現われるかどうかを示す、新たな１ビットflagX存在コードを挿入するまたは読み取る命令。
このバイナリ構文の型は、例えば、次の形式であればよい。
Figure 2007226813
この解決方法の長所は、構造中で各要素が現われる回数の最小値と最大値とを決定するのに、文書の構造スキーマ全体を解析する必要がないことである。
シーケンシャル型のグループSEQ(X1, X2, ..., Xn)のバイナリ構文は、シーケンシャル型のグループ成分のための、連続して生成された命令のシーケンス、または、これらの命令シーケンスの呼び出しからなる。
このバイナリ構文の型は、例えば、次の形式であればよい。
Figure 2007226813
選択グループCHO(X1, X2, ..., Xn)のバイナリ構文は、次のものを連続して含んでいる。つまり、
・圧縮文書中において、成分番号Xi（i=1 ... n）を示し、このグループ中で次に挿入するまたは読み取る要素を表す成分番号コードflagChoXを、挿入または読み取り、ビット数で表した、このコードのサイズに関連付けられた命令。および、
・該要素番号コードの値をテストする命令。このテスト命令は、それぞれ、要素Xiの値を挿入するまたは読み取る命令、もしくは成分コードのテスト済みの値に対応する要素Xiに対応する命令シーケンスを呼び出す命令と関連付けられている。
このバイナリ構文の型は、例えば、次の形式であればよい。
Figure 2007226813
ここで、nは、該グループ中の成分の番号であり、flagChoは、CHOグループ中から選択すべき成分コードである。
上記のように、2E(log2(n))＞nであれば、該バイナリ構文の末尾に次の一行を加えて、誤作動を検知することができる。
Figure 2007226813
インジケータ（標識；英：indicator；仏：l'indicateur）flagChoの値が、CHOグループ中にあると思われる成分のうちの一つと対応していない場合、この命令がエラー報知手順を呼び出す。
出現回数が符号化されていなければ、flagChoの未使用の値を使用して（2E(log2(n))＞nの場合）、グループCHOの最後の出現をマークしてもよい。
Figure 2007226813
上記ANDグループのバイナリ構文は、再帰的な手順によって生成される。この手順は、どの要素が表現中に存在するのかを決定するCHO型グループを、複数個ネストすることからなる。
詳しく述べると、この型のバイナリ構文は、二つの場合を区別することによって生成される。二つの場合とは、グループが一つの成分だけを含んでいる第１の場合と、複数の成分を含んでいる第２の場合とである。
グループが一つの成分だけを含んでいる場合、このグループのバイナリ構文は、成分が一つのシーケンス型グループのバイナリ構文と同じである。
グループが成分をn個含んでいる場合には、AND(X1, X2, ・・・, Xn)の形で書いてもよい。このグループのバイナリ構文は、次のものを連続して含んでいる。つまり、
・圧縮文書中において、該グループの成分番号Xiを示し、このグループ中で次に挿入するまたは読み取る要素Xiを表す成分番号コードflagChoXを、挿入または読み取り、ビット数で表した、このコードのサイズに関連付けられた命令。および、
・該成分番号コードの値をテストする命令。各テスト命令は、それぞれ、要素Xiの値を挿入するまたは読み取る命令、もしくは、成分コードのテスト済みの値に対応する要素Xiに対応する命令シーケンスを呼び出す命令と、成分Xiを除いた、該グループ中の全ての成分X1, ..., Xnからなる「順序付けしていないグループ」の型のグループについて生成される命令シーケンスとに関連付けられている。
このバイナリ構文の型は、例えば、次の形式であればよい。
Figure 2007226813
このバイナリ構文を得る際には、成分Xkを除いた後の、グループAND(X1, ... Xk+1, ..., Xn)のバイナリ構文を該グループ各成分Xkのバイナリ構文に続いて加えた、CHO(X1, X2, ..., Xn)グループのバイナリ構文がまず初めに得られる。ここで、kは、1とnとの間の数値をとる。したがって、このバイナリ構文は、再帰的である。
ANDNO型グループのバイナリ構文は、SEQグループのバイナリ構文と同じであり、該バイナリ構文において、グループの成分の順序を適当なものにすることで符号化を最適化することもできる。
次のステップ１４は、文書２を読み取ることからなり、バイナリ構文を実行することによって、文書に含まれるデータを圧縮する。当該バイナリ構文は、文書の各要素または基底情報要素（英：basic information element；仏：e'le'ment d'informations de base）を圧縮した値が配置されたバイナリコードのシーケンスを含んでいるビット・ストリームを得るために、文書構造に基づいて生成される。
さらに詳細に述べると、その目的は、文書の内容（コンテンツ；英：contents；仏：contenu）から始めて、typelnfoFlag、flagX、loopflagXなどの異なるコードの値を決めることである。このコードの値は、バイナリシーケンスで定義され、ビット・ストリームに挿入される。
第１の符号化型によると、このビット・ストリームは、各要素eについて(K.N.V1..Vn)e の形式である。ここで、Nは、要素eの出現回数、または、要素eに対応する連続した情報要素の個数であり、Kは、該要素eを決定するのに使用するコードである。また、V1からVnは、要素eの出現回数Nの対応する値であり、圧縮されていてもよい。eが複数の要素からなるグループであれば、その中には複数の要素が含まれるのであるから、その値Vは、数多くのバイナリシーケンス(K.N.V)に分けられる。ただし、Nを省略してよい場合もある。具体的には、この数字が固定されるときには、Nが省略可能である。同じことがKについても成り立ち、シーケンス型グループの場合がその一例である。
比較をする意味で、ＩＳＯ８６０１規格で定義されている拡張期間表現形式（英：extended duration representation format；仏：le format e'tendu de repre'sentation des dure'es）、
「sPnYnMnDTnHnMnS」
を考えてみる。ここで、sは、＋または−符号である。また、nYは、年の数字（整数値であり、限定はない）を、nMは、月の数字（整数値であり、限定はない）を、nDは、日の数字（整数値であり、限定はない）をそれぞれ表す。Tは、日付と時間との間を区切る文字である。nHは、時間の数字（整数値であり、限定はない）を、nMは、分の数字（整数値であり、限定はない）を、nSは、秒の数字（十進；小数；英：decimal；仏：de'cimal）をそれぞれ表している。この要素はどれも省略が可能である。
この形式は、次のように表現できる（他の表現方法も可能）構造スキーマに対応する。
(＼+|＼-)p(＼d+Y)?(＼d+M)?(＼d+D)?(T(＼d+H)?(＼d+M)?(＼d+(＼,＼d+)?S)?)?
ここで、"＼+"はプラス（＋）の文字を挿入することを示し、(x|y)は、要素xまたはyを挿入することを示す。また、?は、先の要素の挿入が省略可能なであることを、"＼d+"は任意のビット数の二進数を示す。
この種のバイナリ構文の構造の一例を次に示す。
Figure 2007226813
ここでSignの値は、0であれば＋記号を示し、1であれば−記号を表す。
このようにして、期間+Pl347Yは、次のように符号化される
Figure 2007226813
従来の符号化システムでは、４８ビット必要であったが、この符号化システムでは、２２ビット必要である。期間-P1Y2MT2Hは次のように符号化される。
Figure 2007226813
つまり、従来の符号化であれば、７２ビット必要だったところが、２２で済む。
これをする前に、圧縮文書のために、文書描写に役立つ符号化されたパラメータをいくつか含んだ一般的なヘッダを生成できる。このように、この種のヘッダは、一つもしくは複数の使用された構造スキーマの署名と、使用された符号化を定義するパラメータの組とを含んでいてもよい。次にそのパラメータ組の一例を示す。つまり、
各要素の長さの符号化が必須か、省略可能か、あるいは、該文書中には存在しないのかを示すパラメータと、
要素がサブタイプに対応付けられているか、つまり、その要素の基底型より明確な（細かい；英：precise；仏：pre'cis）型に関連付けられているかどうかを示すパラメータと、
出現回数について使用した符号化の種類を示すパラメータとである。
文書中の各情報要素は、さらに、ヘッダと関連付けることができる。ヘッダがあることと、その性質とは、文書ヘッダで明記されている。
また、文書を伸長している間に、文書中で先にある要素を全て伸長しなくても特定の要素へアクセスできるようにするために、要素ヘッダには、要素の符号化した長さを含んでいてもよい。要素ヘッダは、文書中、例えば、要素の値を符号化する直前に挿入される。
一般に、文書の伸長は、バイナリ構文を実行することによって、圧縮文書を順に読み取ることからなっており、当該バイナリ構文は、圧縮文書を順に読み取ることによって得られるビット・ストリームについてのスキーマから生成される。この処理によっても、圧縮文書の構造が、バイナリ構文でコンパイルされたスキーマに対応していることを検証できるようになる。
構造スキーマ中の要素の出現回数が符号化されていないとき、要素符号化は、KVという単純な形を取り、同じ型の各要素群の符号化は、0に等しいKescビットで終わる。
この種の符号化は、複雑な形式の符号化や、最大出現回数がないか、もしくは最低出現回数が0かの要素に対してだけ役に立つ。特に、pが整数であるとして、含んでいる要素の数が2Pに等しくない選択型グループを符号化するのには理想的である。
この種の符号化を先に述べた種類のものとあわせて使ってもよい。
この場合、圧縮文書のヘッダに含めてしまい、複数回現われる符号化位置に対してビットを割り当てるだけでよい。
本発明によると、少なくとも一つの基底型の文書の情報要素が、外部の圧縮モジュール１６と関連付けられる。このようにして、出会った情報要素の対応する型が、文書の読み取り時に解析される。また、情報の型（英：information type；仏：type d'information）が外部の圧縮モジュール１６と関連付けられているときには、それは、その情報要素の内容に適用されて、圧縮の結果が、対応する情報要素の値として、圧縮文書中に挿入される。
例えば、複数の外部の圧縮モジュールが、音声情報にはｍｐ３規格、画像にはｊｐｅｇ、動画データ類にはＭＰＥＧ１かＭＰＥＧ２、実数型の値にはＩＥＥＥ７５４、文字列にはＵＴＦ８を用いてもよい。
圧縮モジュールのどれもが情報の型と関連付けられていない場合には、デフォルト圧縮モジュールを使ってもよく、また、この型の情報要素を、初期文書中で現われるのと同じように取り込んでもよい。
例えば、CHO[0,*](a1, a2, a3)構造を符号化すれば、次のバイナリ構文が生成される。
Figure 2007226813
ここで、「a2 a3 a1 a1 a3」を、この構造で符号化したければ、出現回数を符号化した場合、符号化の結果は次のようになる。
00101 01 Va2 10 Va3 00 Va1 00 Va1 10 Va3
ここで、00101は、出現回数を二進数で表した値を示し、UlNT＿VLC形式では、５に等しい。また、Va1、Va2、Va3は、それぞれ、a1、a2、a3の出現回数の値である。
出現回数が符号化されていなければ、符号化は次のようになる。
01 Va2 10 Va3 00 Va1 00 Va1 10 Va311
11が出現回数のエンド・コードであり、この場合、CHOグループの選択コードに組み込まれている。
第１の場合には、要素値が１５ビット以下で符号化され、第２の場合には、１２ビットで符号化され、サイズが比較的小さい。
「b2b1 a1」が出現する符号化処理の構造は以下のようになり、
SEQ[0,*](a1[0,*],CHO[0,*](b1,b2))
次のバイナリ構文が得られる。
Figure 2007226813
このバイナリ構文を得る符号化は、次のようになる。
1 ０に等しくないシーケンスの出現回数
00010 上記シーケンスの出現回数（この場合二回）
0 a = 0の出現回数
l 0に等しくないCHOの出現回数
00010 CHOの出現回数（二回）
1 b2の選択コード
Vb2 b2の符号化値
0 b1の選択コード
Vb1 b1の符号化値
1 a = 0 の出現回数
00001 a1の出現回数（一回）
Va1 a1の符号化値
0 CHO = 0 の出現回数。
ＸＭＬ言語のように、属性の順番が役に立たないものであれば、要素の属性を、必要に応じて、アルファベットと数字との順番などの、所定の順番に再度並べ替える符号化をしてもよい。こうすることで、圧縮した記述（英：description；仏：description）のサイズが見合った分だけ減少する。
長さの符号化が省略可能あるいは必須だということを示す情報を、文書ヘッダが含んでいる場合、 要素は、要素の値の長さをビット数として含んだ、圧縮文書中のヘッダと関連付けられている。この特徴によって、検索対象になっている要素に到るまでの、これら要素の対応する長さだけを読み取るバイナリ構文を用いて、先行する要素を伸長せずに、圧縮文書中の要素に直接アクセスすることができる。
要素の長さは次のように符号化してもよい。
要素の長さの符号化が必須だということを示す情報を、文書ヘッダが含んでいる場合、ビット数で表した要素の長さLは、次の公式を使って計算できる。
L = 8*p + h ... （１）
ここで、pは、要素長さを符号化するのに用いるバイト数（ANSIエンコーディング、または、各バイトの高位ビットを使って、この数値を符号化するのに用いるバイト数）を表す。hは、この長さで残ったビット数である（h＜8）。
ただし、要素値を符号化するために呼び出す外部の圧縮モジュール１６がこの長さを返してもよい。
要素の長さの符号化が必須でなければ、次のビットが要素の長さを表しているかどうかを、要素値に対応する第１ビットの値が示す。
このように圧縮した文書の伸長は、文書構造スキーマに対してステップ１１から１４を実行することで文書構造スキーマの構造成分のバイナリ構文を得て、さらに、ステップ１４’を実行して文書の復号または伸長することで行われる。ステップ１４’は、ステップ１１から１４で得られたバイナリ構文を実行しながら、圧縮文書をブラウズ（拾い読み；英：browsing ；仏：parcourir）することからなり、こうすることで文書中にある圧縮した情報要素の型と名前とを決定できる。外部の圧縮モジュール１６を使って得た要素値は、対応する伸長モジュール１６’を使って伸長する。
ただし、同じ構造スキーマの複数の文書を処理（圧縮または伸長）しないとならない場合には、ステップ１１から１３を一回だけ実行し、処理する各文書に対して、ステップ１４と１６だけ（あるいは１４’と１６’だけ）を適用する。
さらに、従来のプログラミング言語に似た構造スキーマのバイナリ構文は、適当な変換処理を行って、コンピュータのプロセッサで直接実行または解釈可能な圧縮あるいは伸長プログラム６、６’用のバイナリコードを生成するように、コンパイルしてもよい１７，１７’。したがって、本発明の方法によれば、任意の構造スキーマ専用の、実行可能な、したがって、非常に高速な圧縮あるいは伸長プログラムを自動的に生成できる。
また、本発明の圧縮方法は、文書（２）の上記構造スキーマ（１）が少なくとも一つの型の情報のサブタイプの定義を含んでおり、n個のサブタイプ（S1, S2, ..., Sn）を有する型（TX）の成分のために上記命令シーケンス生成手段が生成した命令シーケンス（５）は、上記文書符号化手段が上記文書の成分に対応する要素（X）に適用されるサブタイプを表すサブタイプコード（flagPoly）を、ビット数で表したこのコードのサイズと共に挿入する命令と、上記文書符号化手段が上記サブタイプコードの値をテストする命令とを順に含み、各テスト命令は、サブタイプコードのテスト済みの値と対応する要素（X）のサブタイプ（Sl, S2, ..., Sn）への参照と、上記サブタイプと関連付けられた要素（X）の圧縮のために上記命令シーケンス生成手段により生成された命令シーケンスとに関連付けられていてもよい。
また、本発明の伸長方法は、上記文書復号化手段が伸長（１０）する上記文書の構造スキーマ（１）が少なくとも一つの情報型（TX）のサブタイプの定義を含んでいること、および、n個のサブタイプ（Sl, S2, ・・・, Sn）を有する型（TX）の成分のために上記命令シーケンス生成手段が生成した命令シーケンス（５）は、上記文書復号化手段が文書中の成分に対応した要素（X）に適用されるサブタイプの番号を表すサブタイプコード（flagPoly）を、ビット数で表したこのコードのサイズと共に読み取る命令と、上記文書復号化手段が当該サブタイプコードの値をテストする命令とを順に含み、各テスト命令は、それぞれ、サブタイプコードのテスト済みの値と対応する要素（X）のサブタイプ（Sl, S2, ・・・, Sn）への参照と、サブタイプに関連付けられた要素（X）の伸長のために上記命令シーケンス生成手段により生成された命令シーケンスとに関連付けられていてもよい。
本発明の方法における異なるステップを示すブロック図である。 図２ａは、ツリー状構造スキーマを描いた図である。 図２ｂは、ツリー状構造スキーマを描いた図である。 図２ｃは、ツリー状構造スキーマを描いた図である。 図３は、本発明の低減方法を図２の構造スキーマに適用して得られた構造スキーマを示す図である。 図４ａは、本発明の別の低減方法を図２の構造スキーマに適用して得られた構造スキーマを示す図である。 図４ｂは、本発明の別の低減方法を図２の構造スキーマに適用して得られた構造スキーマを示す図である。 図４ｃは、本発明の別の低減方法を図２の構造スキーマに適用して得られた構造スキーマを示す図である。

Claims (32)

  1. ネストされて、それぞれが情報の型と関連付けられている複数の情報要素からなる構造化された文書を、デジタルデータ通信網を通じて転送するかまたは記録するために圧縮する方法であり、上記構造化された文書（２）は、文書のツリー状構造を定義し、ネストされた複数の構造成分（a3, a4, X, Y, a1, a5, a1, a2, A, B, 32, 33, 34, 40, 44, 45, 46）からなる少なくとも一つの構造スキーマ（１；３１、３９、４３）と関連付けられていて、文書情報の型は、それぞれ上記スキーマの中の成分によって定義されている方法において、
    上記方法は、
    制御コードと、情報要素を圧縮した値または成分の命令シーケンスの呼び出しコードとを、コンピュータの文書符号化手段がビット・ストリームに挿入する命令と、
    制御コードの値の関数として、上記命令シーケンスの実行を上記文書符号化手段が制御する命令と
    からなるシーケンスであり、上記構造スキーマの各成分に対して、実行可能な命令シーケンス（５）を得るために上記文書構造スキーマ（１）を解析する（１１、１３）、コンピュータの構文分析手段による処理ステップと、
    上記構造スキーマ各成分に対する命令シーケンスを生成する、コンピュータの命令シーケンス生成手段による処理ステップと、
    上記構造化された文書（２）を、当該文書中の情報要素を圧縮した値を含んだビット・ストリーム（１０）へ圧縮する（１４）ために、上記構造化された文書（２）に対して上記命令シーケンスを実行する、上記文書符号化手段による処理ステップと
    を含んだことを特徴とする方法。
  2. 上記文書がサブ要素に分解できない基底要素からなり、
    少なくとも一つの型の基底要素情報が、前もって、その情報の型にあわせた圧縮アルゴリズム（１６）と関連付けられ、
    上記方法では、上記文書符号化手段が、上記命令シーケンス（５）の実行中に、そのアルゴリズムと関連付けられた型の各情報要素の値に対して、上記圧縮アルゴリズム（１６）を適用することを含んでいることを特徴とする請求項１に記載の圧縮方法。
  3. 上記方法では、コンピュータの専用符号化プログラム生成手段が、上記構造スキーマの各成分について得られた命令シーケンス（５）をコンパイルして、上記構造スキーマ専用、かつ、コンピュータによって直接実行可能もしくは解釈可能で、上記構造スキーマ（１）を有する文書（２）を圧縮するためのバイナリ符号化プログラム（６）を得るステップ（１７）を含んでいることを特徴とする請求項１または２に記載の圧縮方法。
  4. 上記方法では、コンピュータの変換正規化手段が、文書構造スキーマ（５）を前もって正規化して、上記スキーマの成分の、予め定義された一つの順序を得るステップ（１２）を含んでいることを特徴とする請求項１ないし３のいずれか一つに記載の圧縮方法。
  5. 上記方法では、コンピュータの変換正規化手段が、構造成分におけるネストのレベルの個数を減らすことからなり、上記文書構造スキーマを前もって最適化し簡素化するステップ（１２）を含んでいることを特徴とする請求項１ないし４のいずれか一つに記載の圧縮方法。
  6. 上記文書（２）中の少なくとも一つの情報要素は、上記文書符号化手段により生成されたビット・ストリーム中の情報要素コードと対応付けられており、
    当該情報要素コードは、上記ビット・ストリーム中で、その要素に先行する情報要素をコンピュータの文書復号化手段が伸長しなくても、当該ビット・ストリーム（１０）中のある特定の圧縮された情報要素に上記文書復号化手段が直接アクセスできるように上記文書符号化手段によりマークされていることを特徴とする請求項１ないし５のいずれか一つに記載の圧縮方法。
  7. 上記文書符号化手段により生成された圧縮文書（１０）は、上記構造化された文書（２）の各情報要素について、情報要素に関連付けられている情報の型と該情報要素のバイナリ値とを上記文書符号化手段が決定するために用いるコードを含んでいることを特徴とする請求項１ないし６のいずれか一つに記載の圧縮方法。
  8. 上記文書（２）中の少なくとも一つの情報要素からなる要素群が複数回出現することに対応した成分について上記文書符号化手段が生成した上記ビット・ストリームは、予め定義したエンド・コードを含んでいることを特徴とする請求項１ないし７のいずれか一つに記載の圧縮方法。
  9. 上記構造スキーマ（１）の各成分は、少なくとも一つの情報要素からなる上記文書（２）中の要素群に対応し、また、出現する可能性のある回数の組と関連付けられていて、この組は、この成分に対応する要素群が、それの属するレベルのすぐ上のレベルの情報要素中に現われえる回数を示していることを特徴とする請求項１ないし８のいずれか一つに記載の圧縮方法。
  10. 出現回数が０か１に等しい成分のために上記命令シーケンス生成手段が生成した上記命令シーケンスは、
    上記成分に対応する要素（X）群が上記文書（２）中に存在するかしないかを示す、１ビットによる存在コード（flagX）を上記文書符号化手段が挿入する命令と、
    上記存在コードの値を上記文書符号化手段がテストする命令と、
    上記テスト命令に関連して、上記文書中に該要素群（X）が存在することを存在コードの値が示している場合、関連する出現回数とは無関係に、上記成分のために上記命令シーケンス生成手段により生成された命令シーケンスと、を順に含んでいることを特徴とする請求項９に記載の圧縮方法。
  11. 出現回数がｎとｍとの間の成分のために上記命令シーケンス生成手段が生成した上記命令シーケンスは、
    上記圧縮文書中で上記成分に対応する要素群（X）が連続して出現する回数から最低出現回数を引いたものを示す出現回数コード（loopflagX）を、ビット数で表したこのコードのサイズと共に上記文書符号化手段が挿入する命令と、
    上記出現回数コードの値に対応した反復回数を定義するループ命令と、
    上記ループ命令に関連して、関連する出現回数とは無関係に、上記成分のために上記命令シーケンス生成手段により生成された命令シーケンスとを順に含んでいることを特徴とする請求項９または１０のいずれかに記載の圧縮方法。
  12. 出現回数が０とｍとの間の成分のために上記命令シーケンス生成手段が生成した上記命令シーケンスは、さらに、
    上記文書中で上記成分に対応する要素群（X）が少なくとも一回出現するかしないかを示す存在コード（shuntflagX）を上記文書符号化手段が挿入する命令と、
    少なくとも一つの要素群が存在することを存在コードの値が示している場合、出現回数が１とｍとの間の成分のために上記命令シーケンス生成手段が生成した命令シーケンスに関連する存在コードの値を上記文書符号化手段がテストする命令とを含んでいることを特徴とする請求項１１に記載の圧縮方法。
  13. 出現回数がｎとｍとの間の成分のために上記命令シーケンス生成手段が生成した上記命令シーケンスは、
    上記文書（２）中の上記成分に対応する要素群（X）の出現を報知する１ビットの存在コード（flagX）を、ビット数で表したこのコードのサイズと共に上記文書符号化手段が挿入する命令と、
    上記文書符号化手段が挿入する上記存在コードが上記要素（X）群の新たな出現を示している限り上記文書符号化手段により実行されるループ命令と、
    上記ループ命令と関連して、上記成分のために上記命令シーケンス生成手段が生成した命令シーケンスと、上記文書中で上記要素群（X）が新たに出現することを報知する１ビットの存在コード（flagX）を、上記文書符号化手段が新たに挿入する命令とを順に含んでいることを特徴とする請求項９に記載の圧縮方法。
  14. 上記構造スキーマ（１）中の各成分が、少なくとも一つの情報要素からなる要素群に対応すること、
    上記構造化された文書（２）の構造スキーマ（１）は、順序付けした成分からなる、少なくとも一つのシーケンス型成分を含んでおり、当該シーケンス中で現われる順序は、上記シーケンス型グループの成分に対応する要素群が文書中で現われる順序を定義すること、および、
    n個の成分（X1, X2, ..., Xn）からなるシーケンスのために上記命令シーケンス生成手段が生成した上記命令シーケンスは、該シーケンス中の各成分のために上記命令シーケンス生成手段が生成した命令シーケンスを連続して含んでいることを特徴とする請求項１ないし１３のいずれか一つに記載の圧縮方法。
  15. 上記構造スキーマ（１）の各成分が、少なくとも一つの情報要素からなる要素群に対応し、上記文書符号化手段が圧縮する上記文書の構造スキーマ（１）が選択成分グループ型の成分を少なくとも一つ含み、各選択成分が情報要素群に対応し、上記選択成分グループ型の成分が、上記文書中の選択成分に対応する情報群の一つに対応することと、
    対応するn個の要素群（X1, X2, ..., Xn）を定義するn個の成分からなる選択成分のグループのために上記命令シーケンス生成手段が生成した上記命令シーケンスが、
    n個の要素群（X1, X2, ..., Xn）のうちでどの要素群が文書（２）中で現われるかを示す要素群番号コード（flagChoX）を、ビット数で表したこのコードのサイズと共に上記文書符号化手段が挿入する命令と、
    上記要素群番号コードの値を上記文書符号化手段がテストする複数の命令とを順に含み、
    各テスト命令は、それぞれ要素群番号コードのテスト済みの値に対応する要素群（Xi）に対応する成分のために上記命令シーケンス生成手段により生成された命令シーケンスに関連付けられていることとを特徴とする請求項１ないし１４のいずれか一つに記載の圧縮方法。
  16. 上記構造スキーマ（１）の各成分が、少なくとも一つの情報要素からなる要素群に対応していること、
    上記文書符号化手段が圧縮する上記文書の構造スキーマ（１）が、少なくとも一つの、順序付けしていない成分グループ型を含み、当該順序付けしていないグループ中の各成分が要素群に対応し、当該順序付けしていないグループ型のグループが、上記文書において、上記順序付けしていない型のグループの成分に対応する全ての要素群を任意の順序で含んだグループに対応すること、および、
    上記文書中のn個の要素群（X1, X2, ..., Xn）に対応するn個の成分からなる順序付けしていない型のグループのために上記命令シーケンス生成手段が生成した上記命令シーケンスが、
    文書（２）中で次に現われる要素群を示す要素群（Xi）の番号コード（flagChoX）を、ビット数で表したこのコードのサイズと共に挿入する命令と、
    上記要素群番号コードの値を上記文書符号化手段がテストする命令とを順に含み、
    各テスト命令は、それぞれ、要素群番号コードのテスト済みの値に対応する要素群（Xi）に対応する成分のために上記命令シーケンス生成手段により生成された命令シーケンスと、当該要素群（Xi）に対応する成分を除いた、順序付けしていないグループの全ての成分（X1, ..., Xn）からなる順序付けしていない型のグループのために上記命令シーケンス生成手段により生成された命令シーケンスとに関連付けられていることを特徴とする請求項１ないし１５のいずれか一つに記載の圧縮方法。
  17. ネストされて、それぞれが情報の型と関連付けられている複数の情報要素からなる、デジタルデータ通信網を通じて転送されたかまたは記録された、構造化された文書を伸長する方法であり、上記構造化された文書（２）は、文書のツリー状構造を定義し、ネストされた複数の構造成分（a3, a4, X, Y, a1, a5, a1, a2, A, B, 32, 33, 34, 40, 44, 45, 46）からなる少なくとも一つの構造スキーマ（１; ３１、３９、４３）と関連付けられていて、文書情報の型はそれぞれ上記スキーマの成分によって定義されている方法において、
    上記方法は、
    コンピュータの文書符号化手段により圧縮された上記文書（１０）を形成するビット・ストリーム中の制御コードを、情報要素の圧縮された値または成分の命令シーケンスの呼び出しコードと共にコンピュータの文書復号化手段が読み取る命令と、
    上記制御コードの値の関数として、上記シーケンスの実行を上記文書復号化手段が制御する命令と
    からなるシーケンスであり、上記構造スキーマの各成分に対して、実行可能な命令シーケンス（５）を得るために上記文書構造スキーマ（１）を解析する（１１、１３）、コンピュータの構文分析手段よる処理ステップと、
    上記構造スキーマ各成分に対する命令シーケンスを生成する、コンピュータの命令シーケンス生成手段による処理ステップと、
    元の文書（２）と同じ形式でありかつ少なくとも同等の構造を持つ文書（２’）を復元するために、圧縮された上記文書（１０）に対して命令シーケンスを実行する、上記文書復号化手段による処理ステップと
    を含んだことを特徴とする方法。
  18. 上記構造化された文書（２）がサブ要素に分解できない基底要素からなり、
    少なくとも一つの型の基底要素情報が、その情報の型にあわせた伸長アルゴリズム（１６’）と関連付けられ、
    該方法では、上記文書復号化手段が、上記圧縮文書（１０）を形成するビット・ストリーム中の命令シーケンス（５）の実行中にビット・ストリーム中の上記情報型に対応する情報要素バイナリコードを検出するステップと、
    上記文書復号化手段がこのバイナリコードに対して上記伸長アルゴリズムを適用するステップとを含んでいることを特徴とする請求項１７に記載の伸長方法。
  19. 上記方法では、コンピュータの専用復号化プログラム生成手段が、上記構造スキーマ（１）の各成分について得られた命令シーケンス（５）をコンパイルして、上記構造スキーマ専用、かつ、コンピュータによって直接実行可能もしくは解釈可能で、この構造スキーマを有する文書（１０）を伸長するためのバイナリ復号化プログラム（６）を得るステップ（１７）を含んでいること特徴とする請求項１７または１８に記載の伸長方法。
  20. 上記方法では、コンピュータの変換正規化手段が、文書構造スキーマ（５）を前もって正規化して、上記スキーマの成分の、予め定義された一つの順序を得るステップ（１２）を含んでいることを特徴とする請求項１７ないし１９のいずれか一つに記載の伸長方法。
  21. 上記方法では、コンピュータの変換正規化手段が、構造成分グループの階層の個数を減らすことからなり、上記文書構造スキーマを前もって最適化し簡素化するステップ（１２）を含んでいることを特徴とする請求項１７ないし２０のいずれか一つに記載の伸長方法。
  22. ビット・ストリーム中で、その要素に先行する情報要素を上記文書復号化手段が伸長しなくても、この情報要素に上記文書復号化手段が直接アクセスできるように、少なくとも一つの情報要素コードを上記圧縮文書（１０）のビット・ストリーム中で上記文書復号化手段が識別することを特徴とする請求項１７ないし２１のいずれか一つに記載の伸長方法。
  23. 上記圧縮文書（１０）は、上記情報要素と上記文書符号化手段により圧縮された情報要素のバイナリの値とに関連付けられた情報型を決定するために、元の文書における各情報要素のコードを含んでいることを特徴とする請求項１７ないし２２のいずれか一つに記載の伸長方法。
  24. 上記スキーマ（１）の成分に対応する少なくとも一つの情報要素からなる要素群が複数回出現するグループの末尾は、上記圧縮文書（１０）のビット・ストリームでは、上記文書符号化手段により決定されたバイナリコードによりマークされていることを特徴とする請求項１７ないし２３のいずれか一つに記載の伸長方法。
  25. 上記構造スキーマ（１）の各成分は、少なくとも一つの情報要素からなる文書（１０）のビット・ストリームの要素群に対応し、また、出現する可能性のある回数の組と関連付けられていて、この組は、この構造成分に対応する要素群が、それの属するレベルのすぐ上のレベルの情報要素中に現われえる回数を示していることを特徴とする請求項１７ないし２４のいずれか一つに記載の伸長方法。
  26. 出現回数が０か１に等しい成分のために上記命令シーケンス生成手段が生成した上記命令シーケンスは、
    上記成分に対応する要素群（X）が上記圧縮文書中に存在するかしないかを示す１ビットの存在コード（flagX）を上記文書復号化手段が読み取る命令と、
    上記存在コードの値を上記文書復号化手段がテストする命令と、
    上記テスト命令に関連して、上記圧縮文書中に該要素群（X）が存在することを存在コードの値が示している場合、関連する出現回数とは無関係に、上記成分のために上記命令シーケンス生成手段により生成された命令シーケンスと、を順に含んでいることを特徴とする請求項２５に記載の伸長方法。
  27. 出現回数がｎとｍとの間の成分のために上記命令シーケンス生成手段が生成した上記命令シーケンスは、
    上記圧縮文書中で上記成分に対応する要素群（X）が連続して出現する回数から最低出現回数を引いたものを示す出現回数コード（loopflagX）を、ビット数で表したこのコードのサイズと共に上記文書復号化手段が読み取る命令と、
    上記出現回数コードの値に対応する反復回数を定義するループ命令と、
    上記ループ命令に関連して、関連する出現回数とは無関係に、上記成分のために上記命令シーケンス生成手段により生成された命令シーケンスと、を順に含んでいることを特徴とする請求項２５または２６のいずれかに記載の伸長方法。
  28. 出現回数が０とｍとの間の成分のために上記命令シーケンス生成手段が生成した上記命令シーケンスは、さらに、
    上記圧縮文書中で上記成分に対応する要素群（X）が少なくとも一回出現するかしないかを示す１ビットの存在コード（shuntflagX）を上記文書復号化手段が読み取る命令と、
    少なくとも一つの要素群が存在することを存在コードの値が示している場合、出現回数が１とｎとの間の成分のために上記命令シーケンス生成手段が生成した命令シーケンスに関連する存在コードの値を上記文書復号化手段がテストする命令とを含んでいることを特徴とする請求項２７に記載の伸長方法。
  29. 出現回数がｎとｍとの間の成分について上記命令シーケンス生成手段が生成した上記命令シーケンスは、
    上記圧縮文書（１０）中の上記成分に対応する要素群（X）が出現するかしないかを示す１ビットの存在コード（flagX）を、ビット数で表したこのコードのサイズと共に上記文書復号化手段が読み取る命令と、
    上記圧縮文書のビット・ストリームから上記文書復号化手段が読み取った上記存在コードが上記要素群（X）の新たな出現を示している限り上記文書復号化手段により実行されるループ命令と、
    上記ループ命令と関連して、上記成分について上記命令シーケンス生成手段が生成した命令シーケンスと、上記圧縮文書（１０）中で上記要素群（X）が新たに出現するかしないかを示す１ビットの存在コード（flagX）を上記文書符号化手段が新たに挿入する命令とを連続して含んでいることを特徴とする請求項２５に記載の伸長方法。
  30. 上記構造スキーマの各成分（１）が少なくとも一つの情報要素からなる要素群に対応すること、
    上記圧縮文書（１０）の構造スキーマ（１）が、順序付けした成分からなる、少なくとも一つのシーケンス型成分を含んでおり、当該シーケンス中で現われる順序は、上記シーケンス型グループの成分に対応する要素群が文書中で現われる順序を定義すること、および、
    n個の成分（X1, X2, ..., Xn）からなるシーケンスのために上記命令シーケンス生成手段が生成した上記命令シーケンスは、該シーケンス中の各成分のために上記命令シーケンス生成手段が生成した命令シーケンスを連続して含んでいることを特徴とする請求項１７ないし２９のいずれか一つに記載の伸長方法。
  31. 上記構造スキーマ（１）の各成分が、少なくとも一つの情報要素からなる要素群に対応すること、
    上記文書復号化手段が伸長する上記文書の構造スキーマ（１）が選択成分グループ型の成分を少なくとも一つ含んでいて、各選択成分が情報要素群に対応し、上記選択成分グループ型の成分が、上記文書中で選択成分に対応する情報群の一つに対応すること、および、
    選択成分のグループのために上記命令シーケンス生成手段が生成した上記命令シーケンスが、n個の要素群をそれぞれ定義するn個の成分（X1, X2, ..., Xn）からなり、
    n個の要素群（X1, X2, ... Xn）のうちで上記文書中に現われる要素群を示す要素群番号コード（flagChoX）を、ビット数で表したこのコードのサイズと共に上記文書復号化手段が読み取る命令と、
    上記要素群番号コードの値を上記文書復号化手段がテストする、複数の命令とを順に含み、
    各テスト命令は、それぞれ要素群番号コードのテスト済みの値に対応する要素群（Xi）に対応する成分のために上記命令シーケンス生成手段により生成された命令シーケンスに関連付けられていることとを特徴とする請求項１７ないし３０のいずれか一つに記載の伸長方法。
  32. 上記構造スキーマ（１）の各成分が、少なくとも一つの情報要素からなる要素群に対応していること、
    上記文書復号化手段が伸長する上記文書の構造スキーマ（１）が、少なくとも一つの、順序付けしていない成分の型のグループからなり、順序付けしていないグループ中の各成分が要素群に対応し、順序付けしていないグループ型のグループが、上記文書において、上記順序付けしていない型のグループの成分に対応する全ての要素群を任意の順序で含んだグループに対応すること、および、
    文書中のn個の要素群（X1, X2, .... Xn）に対応するn個の成分からなる順序付けしていない型のグループについて上記命令シーケンス生成手段が生成した上記命令シーケンスが、
    上記文書（１０）中で次に現われる要素群を示す要素群（Xi）の番号コードを、ビット数で表したこのコードのサイズと共に上記文書復号化手段が読み取る命令と、
    上記要素群番号コードの値を上記文書復号化手段がテストする命令とを順に含み、
    各テスト命令は、それぞれ、要素群番号コードのテスト済みの値に対応する要素群（Xi）に対応する成分のために上記命令シーケンス生成手段が生成した命令シーケンスと、当該要素群（Xi）に対応する成分を除いた、順序付けしていないグループの全ての成分（X1, ..., Xn）からなる順序付けしていない型のグループのために上記命令シーケンス生成手段が生成した命令シーケンスとに関連付けられていることを特徴とする請求項１７ないし３１のいずれか一つに記載の伸長方法。
JP2007054875A 2001-02-02 2007-03-05 構造化された文書を圧縮／伸長する方法 Pending JP2007226813A (ja)

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
FR0101447A FR2820563B1 (fr) 2001-02-02 2001-02-02 Procede de compression/decompression d'un document structure

Related Parent Applications (1)

Application Number Title Priority Date Filing Date
JP2002563607A Division JP3973557B2 (ja) 2001-02-02 2002-02-01 構造化された文書を圧縮／伸長する方法

Publications (1)

Publication Number Publication Date
JP2007226813A true JP2007226813A (ja) 2007-09-06

Family

ID=8859571

Family Applications (2)

Application Number Title Priority Date Filing Date
JP2002563607A Expired - Fee Related JP3973557B2 (ja) 2001-02-02 2002-02-01 構造化された文書を圧縮／伸長する方法
JP2007054875A Pending JP2007226813A (ja) 2001-02-02 2007-03-05 構造化された文書を圧縮／伸長する方法

Family Applications Before (1)

Application Number Title Priority Date Filing Date
JP2002563607A Expired - Fee Related JP3973557B2 (ja) 2001-02-02 2002-02-01 構造化された文書を圧縮／伸長する方法

Country Status (12)

Country Link
US (1) US20040054692A1 (ja)
EP (1) EP1356595B1 (ja)
JP (2) JP3973557B2 (ja)
KR (1) KR100614677B1 (ja)
CN (1) CN1309173C (ja)
AT (1) ATE336108T1 (ja)
AU (1) AU2002234715B2 (ja)
CA (1) CA2445300C (ja)
DE (1) DE60213760T2 (ja)
ES (1) ES2272666T3 (ja)
FR (1) FR2820563B1 (ja)
WO (1) WO2002063776A2 (ja)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US9075737B2 (en) 2012-10-26 2015-07-07 Kabushiki Kaisha Toshiba Verification device, verification method and computer program product

Families Citing this family (47)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
FR2813743B1 (fr) * 2000-09-06 2003-01-03 Claude Seyrat Procede de compression/decompression de documents structures
EP1388211A2 (en) * 2001-02-05 2004-02-11 Expway Method and system for compressing structured documents
US7080318B2 (en) * 2001-02-28 2006-07-18 Koninklijke Philips Electronics N.V. Schema, syntactic analysis method and method of generating a bit stream based on a schema
US7028286B2 (en) * 2001-04-13 2006-04-11 Pts Corporation Methods and apparatus for automated generation of abbreviated instruction set and configurable processor architecture
ES2272429T3 (es) * 2001-07-13 2007-05-01 France Telecom Metodo para comprimir un arbol jerarquico, señal correspondiente y metodo para descodificar una señal.
US20030188265A1 (en) * 2002-04-02 2003-10-02 Murata Kikai Kabushiki Kaisha Structured document processing device and recording medium recording structured document processing program
US20050021502A1 (en) * 2003-05-23 2005-01-27 Benjamin Chen Data federation methods and system
KR20060123197A (ko) 2003-11-07 2006-12-01 이엑스피웨이 구조적 문서의 압축 및 압축 해제 방법
US8037102B2 (en) 2004-02-09 2011-10-11 Robert T. and Virginia T. Jenkins Manipulating sets of hierarchical data
US7603654B2 (en) * 2004-03-01 2009-10-13 Microsoft Corporation Determining XML schema type equivalence
CN1697327A (zh) * 2004-05-13 2005-11-16 皇家飞利浦电子股份有限公司 一种顺序压缩/解压缩数据的方法及装置
US9646107B2 (en) 2004-05-28 2017-05-09 Robert T. and Virginia T. Jenkins as Trustee of the Jenkins Family Trust Method and/or system for simplifying tree expressions such as for query reduction
US7620632B2 (en) 2004-06-30 2009-11-17 Skyler Technology, Inc. Method and/or system for performing tree matching
US7801923B2 (en) 2004-10-29 2010-09-21 Robert T. and Virginia T. Jenkins as Trustees of the Jenkins Family Trust Method and/or system for tagging trees
US7627591B2 (en) 2004-10-29 2009-12-01 Skyler Technology, Inc. Method and/or system for manipulating tree expressions
US7636727B2 (en) 2004-12-06 2009-12-22 Skyler Technology, Inc. Enumeration of trees from finite number of nodes
US7630995B2 (en) 2004-11-30 2009-12-08 Skyler Technology, Inc. Method and/or system for transmitting and/or receiving data
US8316059B1 (en) 2004-12-30 2012-11-20 Robert T. and Virginia T. Jenkins Enumeration of rooted partial subtrees
US7634502B2 (en) * 2005-01-24 2009-12-15 Paul Colton System and method for improved content delivery
US8615530B1 (en) 2005-01-31 2013-12-24 Robert T. and Virginia T. Jenkins as Trustees for the Jenkins Family Trust Method and/or system for tree transformation
US7681177B2 (en) 2005-02-28 2010-03-16 Skyler Technology, Inc. Method and/or system for transforming between trees and strings
KR100714539B1 (ko) * 2005-03-09 2007-05-07 엘지전자 주식회사 냉장고용 정수장치
US8111694B2 (en) 2005-03-23 2012-02-07 Nokia Corporation Implicit signaling for split-toi for service guide
US8356040B2 (en) 2005-03-31 2013-01-15 Robert T. and Virginia T. Jenkins Method and/or system for transforming between trees and arrays
US20060234681A1 (en) * 2005-04-18 2006-10-19 Research In Motion Limited System and method for data and message optimization in wireless communications
US7899821B1 (en) 2005-04-29 2011-03-01 Karl Schiffmann Manipulation and/or analysis of hierarchical data
US20060288028A1 (en) * 2005-05-26 2006-12-21 International Business Machines Corporation Decompressing electronic documents
US20070143664A1 (en) * 2005-12-21 2007-06-21 Motorola, Inc. A compressed schema representation object and method for metadata processing
JP4429329B2 (ja) * 2007-02-16 2010-03-10 キヤノン株式会社 符号化装置及びその制御方法、復号装置及びその制御方法、プログラム、記憶媒体
US7747558B2 (en) 2007-06-07 2010-06-29 Motorola, Inc. Method and apparatus to bind media with metadata using standard metadata headers
US8694893B2 (en) * 2008-08-08 2014-04-08 Oracle International Corporation Interactive product configurator with persistent component association
US20100049727A1 (en) * 2008-08-20 2010-02-25 International Business Machines Corporation Compressing xml documents using statistical trees generated from those documents
FR2936623B1 (fr) * 2008-09-30 2011-03-04 Canon Kk Procede de codage d'un document structure et de decodage, dispositifs correspondants
JP5570202B2 (ja) * 2009-12-16 2014-08-13 キヤノン株式会社 構造化文書解析装置、構造化文書解析方法、及びコンピュータプログラム
WO2011079796A1 (zh) * 2009-12-30 2011-07-07 北京飞天诚信科技有限公司 .net文件压缩方法
US8963959B2 (en) 2011-01-18 2015-02-24 Apple Inc. Adaptive graphic objects
US8442998B2 (en) 2011-01-18 2013-05-14 Apple Inc. Storage of a document using multiple representations
CN103019895B (zh) * 2012-12-28 2015-01-28 华为技术有限公司 文件存储方法及装置
US9498819B2 (en) 2013-03-14 2016-11-22 Hitchiner Manufacturing Co., Inc. Refractory mold and method of making
US9481029B2 (en) 2013-03-14 2016-11-01 Hitchiner Manufacturing Co., Inc. Method of making a radial pattern assembly
US9486852B2 (en) 2013-03-14 2016-11-08 Hitchiner Manufacturing Co., Inc. Radial pattern assembly
CN104868922B (zh) * 2014-02-24 2018-05-29 华为技术有限公司 数据压缩方法及装置
US10333696B2 (en) 2015-01-12 2019-06-25 X-Prime, Inc. Systems and methods for implementing an efficient, scalable homomorphic transformation of encrypted data with minimal data expansion and improved processing efficiency
KR101702767B1 (ko) * 2015-08-18 2017-02-03 라인 가부시키가이샤 비트를 이용하여 문서에 대한 접근 권한과 타입에 따라 문서를 검색하는 시스템 및 방법
US20200042735A1 (en) * 2016-10-11 2020-02-06 Genomsys Sa Method and system for selective access of stored or transmitted bioinformatics data
US11553210B2 (en) * 2018-12-07 2023-01-10 Interdigital Vc Holdings, Inc. Managing coding tools combinations and restrictions
CN114266018B (zh) * 2021-11-17 2025-01-21 成都安恒信息技术有限公司 一种将任意字节转化为执行逻辑的方法及系统

Family Cites Families (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5778375A (en) * 1996-06-27 1998-07-07 Microsoft Corporation Database normalizing system
US6580834B2 (en) * 1997-05-30 2003-06-17 Competitive Technologies Of Pa, Inc. Method and apparatus for encoding and decoding signals
EP0928070A3 (en) * 1997-12-29 2000-11-08 Phone.Com Inc. Compression of documents with markup language that preserves syntactical structure
US6272252B1 (en) * 1998-12-18 2001-08-07 Xerox Corporation Segmenting image data into blocks and deleting some prior to compression
GB9911099D0 (en) * 1999-05-13 1999-07-14 Euronet Uk Ltd Compression/decompression method
US6883137B1 (en) * 2000-04-17 2005-04-19 International Business Machines Corporation System and method for schema-driven compression of extensible mark-up language (XML) documents
US6865664B2 (en) * 2000-12-13 2005-03-08 Conexant Systems, Inc. Methods, systems, and computer program products for compressing a computer program based on a compression criterion and executing the compressed program

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US9075737B2 (en) 2012-10-26 2015-07-07 Kabushiki Kaisha Toshiba Verification device, verification method and computer program product

Also Published As

Publication number Publication date
CA2445300A1 (en) 2002-08-15
JP3973557B2 (ja) 2007-09-12
DE60213760D1 (de) 2006-09-21
JP2004530188A (ja) 2004-09-30
KR100614677B1 (ko) 2006-08-21
ATE336108T1 (de) 2006-09-15
FR2820563A1 (fr) 2002-08-09
WO2002063776A3 (fr) 2002-11-28
WO2002063776A2 (fr) 2002-08-15
US20040054692A1 (en) 2004-03-18
EP1356595A2 (fr) 2003-10-29
CN1309173C (zh) 2007-04-04
CN1494767A (zh) 2004-05-05
KR20040007442A (ko) 2004-01-24
EP1356595B1 (fr) 2006-08-09
CA2445300C (en) 2007-04-24
FR2820563B1 (fr) 2003-05-16
ES2272666T3 (es) 2007-05-01
DE60213760T2 (de) 2007-08-09
AU2002234715B2 (en) 2005-10-06

Similar Documents

Publication Publication Date Title
JP3973557B2 (ja) 構造化された文書を圧縮／伸長する方法
CA2437123C (en) Method and system for compressing structured descriptions of documents
JP4997777B2 (ja) デリミタを減少させる方法及びシステム
JP2004508647A (ja) 構造化文書の圧縮／解凍方法
JP5044942B2 (ja) 文書分析において受付状態を決定するシステム及び方法
AU2002253002A1 (en) Method and system for compressing structured descriptions of documents
JP5377818B2 (ja) コンパイル済みスキーマに順次アクセスする方法とシステム
WO2007024378A2 (en) Encoding of markup-language data
JP5044943B2 (ja) データ文書の高速符号化方法及びシステム
EP1990737A1 (en) Document transformation system
US6883087B1 (en) Processing of binary data for compression
JP5789236B2 (ja) 構造化文書分析方法、構造化文書分析プログラム、および構造化文書分析システム
US7571152B2 (en) Method for compressing and decompressing structured documents
JP4776389B2 (ja) 符号化文書復号方法及びシステム
JP2006221655A (ja) スキーマをコンパイルする方法とシステム
CN102119384B (zh) 用于编码元素的方法和设备
JP2004342029A (ja) 構造化文書圧縮方法及び装置

Legal Events

Date Code Title Description
A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A821

Effective date: 20070510

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20090113

A601 Written request for extension of time

Free format text: JAPANESE INTERMEDIATE CODE: A601

Effective date: 20090401

A602 Written permission of extension of time

Free format text: JAPANESE INTERMEDIATE CODE: A602

Effective date: 20090406

A02 Decision of refusal

Free format text: JAPANESE INTERMEDIATE CODE: A02

Effective date: 20091006