階層化ツリーを圧縮する方法及び圧縮されたマルチメディア信号をデコーディングする方法
【課題】マルチメディア信号を記述する階層化ツリーを圧縮する方法を提供する。
【解決手段】ツリーは、少なくとも２つの明確なタイプのコンテキストに関連付けることができるノード及びリーフを含み、それぞれがコンテントタイプの少なくとも１つに選択的に関連付けられる少なくとも２つの圧縮コード化技術によって、リーフの少なくとも幾つかに対してコンテント圧縮を実行する。
【解決手段】ツリーは、少なくとも２つの明確なタイプのコンテキストに関連付けることができるノード及びリーフを含み、それぞれがコンテントタイプの少なくとも１つに選択的に関連付けられる少なくとも２つの圧縮コード化技術によって、リーフの少なくとも幾つかに対してコンテント圧縮を実行する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の技術分野は、データを圧縮する分野である。より正確には、本発明はＸＭＬベースの文書（「拡張マークアップ言語規約（eXtended Markup Language）」）に関する。
【背景技術】
【０００２】
本発明には、特に下記の分野のアプリケーションがあるが、それらに限定されない。
−マルチメディア用アプリケーション
−インデクセーションツール（indexation tool）
−メタデータ（meta-data）取扱いツール
−ＭＰＥＧ−７規格
−ＳＭＩＬ
−常設ＴＶ（TV Anytime）
−第三世代の無線通信（３ＧＰＰ）
【０００３】
ＸＭＬに対する従来の圧縮技術には、幾つかの欠点がある。特に、それらの技術はデータへの高速アクセス、高い圧縮率及び文書のプログレッシブ構造に同時に対応していない。言い換えると、大抵の場合、上記の特徴の１つに対応すると、他の全ての特徴が失われてしまう。
【０００４】
従来の圧縮技術の１つは、ＢｉＭ（２進ＭＰＥＧ）として周知である。そのような技術は、文書の構造、すなわちＸＭＬ文書に関連したツリー構造のノードを２進化することによって、ＸＭＬ文書を圧縮する方法を提供する。このため、ＢｉＭ技術はデータへの高速アクセス、文書のプログレッシブ構造及びスキップ能力を可能にするが、ＢｉＭ技術を実行することによって得られる圧縮率は極めて小さい。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
本発明の目的は、従来技術の欠点を補償することである。より正確には、本発明は、ＸＭＬベースの文書に対する効率的な圧縮技術を提供することを目的とする。本発明は、文書のスキップ能力、高い圧縮率、及びプログレッシブ構造を提供する、ＸＭＬ文書に対する圧縮技術を提供することも目的とする。本発明は、ＭＰＥＧ−７記述子を効率的に圧縮することも目的とする。本発明の別の目的はＸＭＬ文書を圧縮するための方法を実現することであり、この方法は、ＢｉＭ形の技術によって与えられた圧縮率を大いに向上させるが、ＢｉＭにより与えられる機能性と同じ機能性を提供する。
【課題を解決するための手段】
【０００６】
後に出てくる本発明の別の目的と同様に本発明の上記の目的は、本発明に基づいて、マルチメディア信号を記述する階層化ツリーを圧縮する方法によって実現される。このツリーは、少なくとも２つの明確なタイプの内容に結び付けることができるノード及びリーフを含むものである。この場合には、この方法は、それぞれが少なくとも１つのコンテントタイプに選択的に関連付けられた少なくとも２つの圧縮コード化技術によって、少なくとも幾つかのリーフに対してコンテント圧縮（content compression）を実現する。
【０００７】
本発明の好ましい実施形態によれば、そのような方法は少なくとも１つのサブツリー（sub-tree）を識別するステップと、圧縮コード化技術の１つをこのサブツリーに割り当てるステップとを含む。
【０００８】
有利には、そのような方法は、サブツリーのリーフのコンテンツ（又は、内容）が圧縮コード化技術に関連したタイプであり、サブツリーの他のリーフがいかなる圧縮コード化処理も受けないようなサブツリーのみに割り当てられた圧縮コード化技術を実行するステップを含む。
【０００９】
本発明の好ましい特徴によれば、そのような方法は、圧縮コード化技術のパラメータ記述を実行する。
そのような方法は、このツリーの構造を選択的に圧縮するステップも含む。
有利には、このツリーは、ＭＰＥＧ７規格によるＢｉＭ（２進ＭＰＥＧ）形である。
この圧縮コード化技術の１つは、線形の量子化を選択的に実行する。
有利には、この圧縮コード化技術の１つは統計的な圧縮アルゴリズムを実行する。
選択的には、このアルゴリズムはＧＺｉｐ形である。
有利には、このアルゴリズムは、少なくとも２つのリーフの内容に対応するデータの集合に対して同時に実行される。
このツリーは、ＸＭＬ（Extended markup language：拡張マークアップ言語規約）形の文書の構造を選択的に示す。
本発明は、階層化ツリーを圧縮するための上記の方法に基づいて圧縮されたマルチメディア信号をデコードする方法にも関係する。
【００１０】
有利には、そのような方法は、信号によって伝達されたコンテキスト情報（context information）のコード化に基づいて、現在のデコーディングコンテキスト（decoding context）をリフレッシュするステップを実行する。
この現在のコンテキストは、少なくとも１つのコンテントタイプを選択的に定義し、この方法は、リーフがこのコンテントタイプの内容を有するようなこのコンテントタイプに関連した圧縮デコーディング技術を実行するステップを含む。
【００１１】
本発明は、階層化ツリーを圧縮する前述した方法が発生する信号にも関係する。
【００１２】
本発明の他の特徴及び利点は、下記の説明及び以下の図面に照らしてより明確になるであろう。下記の説明は、単に説明するために示すものであり、実施例に限定するものではない。
【００１３】
本発明を実行する方法を詳細に説明する前に、ＢｉＭ技術としてよく知られた従来の圧縮技術の主な特徴を最初に思い出してみる。
【００１４】
文書を容易に理解するために、幾つかの引例をＡｎｎｅｘ９（表１６）の中に集めて、本明細書全体にわたって参照する。本明細書に含まれる全てのＡｎｎｅｘ（補遺）は、本発明の説明の一部をなすものである。
【００１５】
１．従来技術
（はじめに）
図１に示したコーディングコンテキストは、ビットストリームをデコーディングする間に必要なデコーディング情報の集合である。コーディングコンテキストは、定義されるノードのサブツリー全体に適用できる。ツリーの全てのノードにおいて、コーディングコンテキストを修正して、新しいコーディングコンテキストを作成し、対応するサブツリーに適用するようにできる。
【００１６】
コンテキストは、命令が関係するサブツリーに適用できることを特徴とする幾つかの情報を保持できる。現在のところ、ＢｉＭのサブツリーのコーディングフォーマット［１］では、これらの特徴は、（後方及び前方の互換性の特徴を提供するため、）サブツリーまたはコンテキストのスキップ能力及びサブツリーまたはコンテキストに対する複数のスキーマ（schema）のコード化である。最後に、このコンテキスト方法は、帯域幅をセーブするために全てのサブツリー内で無効にすることができる。これはコンテキスト凍結モードである。
【００１７】
このコーディングコンテキスト方法は、文書ツリーの全てのサブツリーの中で最大の柔軟性を提供し、ＢｉＭのコード化方法にプラグ接続されるという拡張可能な特徴を可能にする。
【００１８】
発明者らは、次に、ＢｉＭ内で使用されるコンテキスト方法を説明する。
【００１９】
[現在のコーディングコンテキスト方法]
（定義）
（コーディングコンテキスト（codingContext））
「コーディングコンテキスト」とは、デコーダがビットストリームをデコードするために必要とする情報の集合、すなわちコンテキスト情報である。コーディングコンテキストは、それが定義されているノード及びこのノードに対応するサブツリー全体に適用できる。
現在のコーディングコンテキスト（つまり、ある記述の指定されたノードにおいて適用可能なコンテキスト）は、文書内で修正することができる（換言すれば、その下にある情報の集合の修正）。コーディングコンテキストが修正されるたびに、修正された情報の集合を保持する新しいコーディングコンテキストが作成される。全てのコーディングコンテキストは、デコーダがコンテキストに対応するサブツリーのデコーディングを終了したとき、それらを元に戻すためにスタックされるべきものである。
【００２０】
（デコーダ）
ＢｉＭのデコーダは、下記の２つのデコーダからなる、すなわち、
−コンテキストデコーダ（context decoder）。このデコーダは、コンテキスト情報のデコーディング専用である。前述したように、コンテキスト情報は記述の一部ではない。これは幾つかの外部形状、後方及び前方の互換性、高速スキッピング（fast skipping）などを保持する情報の集合である。
−要素デコーダ（element decoder）。このデコーダはＢｉＭ正規デコーダ［１］（BiM regular one）であり、要素情報のデコーディング専用である。
【００２１】
（チャンク）
記述の各要素は、図２に示した３つの部分にコード化される。この場合、ヘッダ部は大きさをゼロにできる２つのチャンクから構成される。
−ＭＣはメタコンテキストのチャンク（metacontext chunk）である。
−Ｃはコンテキストチャンクである。
−エレメント（Element）は要素チャンクであり、これは正規の要素コーディングチャンクである（［１］を参照のこと）
このＭＣメタコンテキストチャンクは、デコーダが次のＣコンテキストチャンクをデコードするために必要とする情報を含む。すなわち、ＭＣチャンクは、Ｃコンテキストチャンクのコンテキストチャンクである。
このＣコンテキストチャンクは、デコーダが次の要素チャンクをデコードするために必要な、現在のコーディングコンテキストの情報の集合を変更できる情報を含む。言い換えると、このＣチャンクは、要素チャンクのコンテキストチャンクである。
【００２２】
（情報の集合）
現在のＢｉＭコーディングコンテキストは、情報の集合、すなわち、次の２つの主な部類に分割できるコンテキスト情報を保持する。
−（この節に含まれた情報がコンテキストデコーディング工程のみに影響する場合の）メタコンテキスト部。
−（この節に含まれた情報が要素デコーディング工程のみに影響する場合の）コンテキスト部。
【００２３】
現在の情報の集合は、下記の変数の集合である。
【表１】
定義されたクラスは、（ＭＣメタコンテキストチャンク及びＣコンテキストチャンク等の）前述したチャンクを正確にコーディングする。
【００２４】
[メタコンテキストチャンク]
（定義）
ＭＣメタコンテキストチャンクは、その大きさをゼロにすることができ、デコーダが以下の節で説明されるような次のＣコンテキストチャンクを読み取る必要があるかどうかを知るための情報を含む。
【００２５】
（関係する変数）
【表２】
【００２６】
（デフォルト値）
freezing_stateのデフォルト値は偽である。すなわち、デフォルトでは、根本的なコンテキストを動的に変更できるようになっている。
【００２７】
（伝搬規則）
新しいコンテキストが作成されるときには、
−freezing_state値は、その父親のコンテキスト（father's context）のfreezing_state値に設定される。
【００２８】
（動的修正規則）
新しいコンテキストを作成するために、記述の各ノードにおいて、
−freezing_state値を偽の値から真の値に切り換えることができる。
【００２９】
（デコーディング規則）
freezing_state値が真の場合には、ＭＣメタコンテキストチャンク（及び次のＣコンテキストチャンク）はビットストリームにコード化されない。真でない場合には、ヘッダ部分のＭＣメタコンテキストチャンクは下記のようにコード化される。
【表３】
context_chunkは偽で初期化されたローカル変数である。
【００３０】
【表４】
前の節で述べたように、現在のコンテキストの変数の修正は、新しいコンテキストの作成を意味する。
【００３１】
（コンテキストデコーディング工程に対する影響）
context_chunk値が真の場合には、デコーダは次のＣコンテキストチャンクを読み込む必要がある。
【００３２】
コンテキストチャンク
（定義）
Ｃコンテキストチャンクは、大きさをゼロにすることができ、現在のコンテキスト変数を動的に変更できる情報の集合を含む。これらの変数は、ＢｉＭ要素のデコーディング工程に影響を与えるため、コーディング特性（codingProperties）と呼ばれる。
（関係するコーディング特性）
【表５】
【００３３】
（デフォルト値）
allows_skip変数は、ＦＤＣシステム文書［１］の中で定義されているように、特別な４ビットのビットフィールド（bitfield）の最初の２ビットによって、ビットストリームの始めで初期化される。
allows_partial_instantiation変数は、特別な４ビットのビットフィールドの第３の２ビットによって、ビットストリームの始めで初期化される。
allows_subtyping変数は、特別な４ビットのビットフィールドの第４の２ビットによって、ビットストリームの始めで初期化される。
schema_modeのデフォルト値は、モノラル（mono）である。すなわち、デフォルトでは、ルートのサブツリー／コンテキストは１つのスキーマを用いてコード化される。
【００３４】
（伝搬規則）
新しいコンテキストの作成時に、
−allows_skip値は、その父親のコンテキストのallows_skip値に設定される。
−allows_partial_instantiation値は、その父親のコンテキストの値に設定される。
−allows_subtyping値は、その父親のコンテキストの値に設定される。
−schema_mode値は、そのデフォルト値に設定される。
【００３５】
（動的修正規則）
新しいコンテキストを作成するために、記述の各ノードにおいて、
−allows_skipは動的に修正できる。
−allows_partial_instantiationは動的に修正できない。
−allows_subtypingは動的に修正できない。
−schema_modeは動的に修正できる。
【００３６】
（デコーディング規則）
Ｃコンテキストチャンクは、ＭＣメタコンテキストチャンクが既に存在し、その以前のローカル変数context_chunkが真の場合にのみ存在する。
現在のコンテキストの動的な修正は、ＢｉＭの正規のコード化方式を用いてコード化されるＸＭＬ要素を用いて記述される。ＢｉＭスキーマからの汎用要素modifyContextが使用される。http://www.mpeg7.org/2001/BiMCodingのコーディングスキーマは、補遺１に記載されている。
Ｃコンテキストチャンクは、上記のスキーマによるＢｉＭの正規の方式を用いて記述する必要がある。
前述したように、コンテキスト内の現在のコーディング特性の修正は、新しいコンテキストの作成を意味する。このため、Ｃコンテキストチャンクが存在することは、修正されたコーディング特性を保持する新しいコンテキストが作られたことを意味する。
allowsSkip要素がmodifyContext要素の中で例示される場合には、allows_skipの値は新しいコンテキストの中で更新される。
schema_mode要素がmodifyContext要素の中で例示される場合には、schema_modeの値は新しいコンテキストの中で更新される。
【００３７】
（要素デコーディング工程に対する影響）
allows_skip値及びschema_mode値は、スキッピング特性を処理する場合に要素デコーディング工程に影響を与える。この動作は［１］に記載されている。
schema_mode値は、要素が１つのスキーマだけにより又は幾つかのスキーマによりコード化されるのかどうかを知るために要素デコーディング工程に影響する。この仕組みは［１］に記載されている。
allows_partial_instantiation値は、１つの特殊なタイプのpartiallylnstantiatedタイプを要素の可能なサブタイプに加えることによって、要素デコーディング工程に影響を与える。［１］を参照のこと。
allows_subtyping値は、要素デコーディング工程に影響し、要素が多形性（polymorphism）（xsi:typeの属性を有する）又はユニオンの場合には、要素又は属性が異なる可能なタイプを持つことができるようにする。［１］を参照のこと。
【発明を実施するための最良の形態】
【００３８】
２．本発明の説明
２．１ リーフを圧縮するためのフレームワークを提供するコンテキスト方法の拡張
本発明は、新規で興味ある特徴、すなわち、結果として生ずるビットストリームの大きさを減らすために、ある文書のリーフを圧縮する局部圧縮機（local compressor）を使用して、現在のＢｉＭコンテキスト方法を拡張することを提案する。
【００３９】
この節では、局部圧縮機を使用できるように現在のＢｉＭコンテキスト方法を拡張する方法を説明する。これは、典型的な例では、特定の意味論規則、伝搬規則及びコーディング規則とリンクした新しい変数の集合のcodingPropertiesである。従って、この新たなcodingPropertiesの集合によって、現在のコンテキストチャンクが拡張される。
【００４０】
（はじめに）
サブツリーでは、１つ又は数個の指定された単純なタイプのインスタンスがあると、それらは全て１つ又は数個の指定された圧縮機を用いて圧縮することができる。これは基本的には、圧縮機と１つ又は数個の単純なタイプとの間のマッピングを定義する。
さらに、
−場合によっては、圧縮機は幾つかの外部パラメータを必要とすることができる。
−幾つかのサブツリー内で圧縮機を使用し、別のサブツリーでは使用しないようにするために、マッピングを起動又は停止することができる。
最後に、起動または停止するために、マッピングは参照可能でなければならず、このためコンテキストの中で固有の識別子を持つ必要がある。
その結果、各コンテキストは、ゼロ、１つ又は数個のcodecTypeMapperを保持できる。ここで、codecTypeMapperは、識別子、１つ又は数個の単純なタイプ、コーデック、選択可能な外部のコーデックパラメータ及び活性化状態から成る４プレット（4-plet）である。
【００４１】
（定義）
（CodecTypeMapper）
codecTypeMapperは、４プレットであり、
−サブツリーまたはコンテキストの中で固有の参照キーとして使用される識別子と、
−マッピングが適用できる１つ又は数個の単純なタイプと、
−コーデックと、
−任意選択的な外部コーデックパラメータ（コーデックに依存する）と、
−活性化状態と
を備えている。
【００４２】
（識別子）
識別子は、固有の番号であり、明白な方法でコンテキスト内のマッピングを識別する。ＢｉＭのコーディングスキーマは、コンテキスト内のcodecTypeMappersの最大数を３２に制限する。
【００４３】
（単純なタイプ）
あるスキーマにおいて定義された全ての単純なタイプ（simple type）は、全てのコーデックによって先験的に（a priori）コード化することができるが、各コーデックはこの選択を制限できる。例えば、以後文書の中で定義するような線形の量子化器（linear quantizer）は、数値的な単純なタイプと共にのみ使用できる。
【００４４】
単純なタイプは、その名前及びそれが属するスキーマのＵＲＬによって識別される。正しいスキーマを指し示すために、ＸＭＬスキーマのプレフィックス（prefix）を用いるべきである。ＢｉＭコーディングスキーマは、この対をコード化するためにある特殊なタイプを定義する、すなわち、このタイプは整数の対としてコード化されなければならない、第１の整数はわかっているスキーマの現在の数に制限され（この情報の部分は、DecoderConfig部［１］の中でフェッチすることができる）、第２の整数は対応するスキーマの中に存在するグローバルな単純なタイプの数に制限される。
【００４５】
（コーデック）
圧縮機または解凍機（compressor/decompressor）の役目をするコーデック（codec）は、入力ビットを取り入れて出力ビットを書き込むモジュールである。それは幾つかの選択可能な外部パラメータを必要とすることがある。
コーデックは、ＢｉＭのコーディングスキーマの中で定義された非抽象的なコーデックの名前の中の名前によって識別される。上記の節の中で定義された現在のＢｉＭのコーディングスキーマは、どの非抽象的なコーデックも定義しないが、本明細書の２．２節（段落番号[００６１]以下）では定義している。
【００４６】
（活性化状態）
活性化状態はブーリアンフラグである。
【００４７】
（意味論規則）
（CodecTypeMapper）
各コンテキストは、
−ゼロ、１つ又は数個のcodecTypeMapperを保持できる。
−１つ又は数個のcodecTypeMapperを定義できる。
−１つ又は数個の現行のcodecTypeMapperを起動又は停止できる。
あるcodecTypeMapperがコンテキストの中で定義されると、それは全てのそのサブコンテキストの中に残る。
コンテキスト内に存在するcodecTypeMapperを削除又は修正することはできない（活性化状態は除く）。
【００４８】
（識別子）
マッピングの識別子は、コンテキストの全てのcodecTypeMapperの中で一意的でなければならない。
【００４９】
（単純なタイプ）
codecTypeMapperを１つ又は数個の単純なタイプ及びコーデックと結び付ける場合、このコーデックは単純なタイプ自体及びそれらから生じた全ての単純なタイプをコード化／デコードする。
コンテキストには、コーデックの場合とは異なり、たかだか１つの単純なタイプが存在する必要がある。
【００５０】
（コーデック）
２種類のコーデック、すなわち、メモリ無しのコーデックとコンテキスト式コーデックとがある。
メモリ無しのコーデックは、常に同じ入力バイトを同じバイト出力にコード化するモジュールであり、コーデックの履歴に無関係である。典型的なメモリ無しのコーデックは、線形の限定子である。ＢｉＭのリーフ圧縮（本明細書の２．２節を参照のこと）は、そのようなコーデックを説明している。
コンテキスト式コーデックは、送られた以前のバイトを使用する（このため、コーデックのコンテキストは変更される）モジュールである。そのようなコーデックは、受け取った同じ入力バイトに対して同じ出力バイトを発生しない。典型的なコンテキスト式コーデックは、Ｚｉｐのようなローカルコーデックであり、本明細書の２．２節に説明されている。
メモリ無しのコーデックは、現在のコンテキストのアーキテクチャでは何ら問題を引き起こさないが、コンテキスト式コーデックはスキップ可能なサブツリーの場合には問題を発生する。そのような場合には、この前者がサブツリーをスキップした場合にデコーダを混乱させないように、コンテキスト式コーデックはリセットされる。
【００５１】
（活性化状態）
全てのサブツリー又はコンテキストにおいて、codecTypeMapperを起動又は停止することができる。
この仕組みにより、codecTypeMapperを文書ツリーのより高いレベルで定義し、使用されているサブツリーの中でのみcodecTypeMapperを再定義せずに起動することができる。
【００５２】
（新しいcodingProperty：codecTypeMapper）
この部分では、新しいcodingPropertyを、前述したコンテキスト部の以前の変数の集合に加える。この新しいcodingPropertyはcodecTypeMapperと名付けられ、前の節の中で説明された以前のcodecTypeMapperのリストである。
【００５３】
（関係する新しいcodingProperty）
コンテキストはcodecTypeMapperのリストを保持する。
【００５４】
【表６】
【００５５】
（新しいデフォルト値）
デフォルトにより、サブツリー又はコンテキスト内にはcodecTypeMapperはない。
codecTypeMapperをコンテキスト内で定義する場合には、その識別子、コーデック及びsimple_type値を定義する必要がある。指定されない場合は、新しく定義されたcodecTypeMapperの活性化状態はデフォルトにより真に設定される。すなわち、新しく定義されたcodecTypeMapperはデフォルトにより起動される。
【００５６】
（新しい伝搬規則）
（規則１）
新しいコンテキストの作成時には、codecTypeMapperのリストはその父親のコンテキストのコピーである。
−識別子の値がコピーされる。
−simple_typeの値がコピーされる。
−コーデックの値が規則２に従ってコピーされる。
−codec_parameterの値がコピーされる。
−activation_stateの値がコピーされる。
（規則２）
コーデックの値がコピーされ、下記が成立する場合、つまり、
−父親のコーデックのcodingProperty[i].codecがコンテキスト式コーデックであり、
−現在のコンテキストがスキップ可能である場合には、
デコーダは、父親のコーデックの事例（その値だけでなく）をコピーし、それをリセットすることによって、コーデックの新しい事例を作成することが期待される。
例えば、ZLibコーデックがコピーされ、スキップ可能なノードに入るときに再度初期化される。
【００５７】
（新しい動的な修正規則）
codecTypeMapperのリストを記述の中で下記のように動的に修正できる。
−新しいcodecTypeMapperを定義できる。
−現在の（次に参照可能な）activation_stateのcodecTypeMapperを動的に修正できる。
（そのactivation_stateを除き、）現在のcodecTypeMapperを削除することはできず、そのメンバを動的に修正することもできない。
【００５８】
（新しいデコーディング規則）
同じ前の規則はＣコンテキストチャンクのデコーディングに適用するが、補遺２で説明される新しいスキーマが、新しいcodecTypeMapperの動的な修正機能を加えるために使用される。
【００５９】
（情報提供部）
（実施例）
補遺３に示した実施例は、記述する場合の１つの活性化された線形の限定子（本明細書の２．２節を参照のこと）の定義を示す。
【００６０】
補遺４に示した実施例は、記述する場合の１つの非活性化された線形の限定子（本明細書の２．２節を参照のこと）の定義を示す。
【００６１】
２．２ ＢｉＭのリーフ圧縮
異なるコーデックを用いてデータをコード化するために、本発明によって実現された仕組みをここで示す。より正確に言うと、ここで２つの実施例を示す、すなわち、１つは線形の量子化コーデックを使用して例えば浮動小数点の値を圧縮する実施例、及びもう１つはgzipのコーデックを使用して例えばストリング値を圧縮する実施例である。
【００６２】
そのような仕組みはコーディングコンテキストに密接に関連しており、幾つかの他の種類のコーデックを使用できるようにする。さらに、この仕組みは、例えば、ストリップ可能なサブツリーなどのコーディングコンテキストの機能を適切に処理できる。最後に、この仕組みは、別のコーディングコンテキスト内のコーデックを再度使用することができる。
【００６３】
（はじめに）
ＢｉＭのサブツリーのコーディング［１］は、記述のデータリーフを圧縮しない。現在は、リーフ値は、（ＩＥＥＥ７５４のフロート及びダブル（floats and doubles）、ＵＴＦストリングなどの）その種類に関連してコード化される。
【００６４】
多くの場合には、ＢｉＭの圧縮比をその主な機能を失わずに向上させるために、（流線型の構文解析（streamline parsing）、高速スキッピング機能、タイプドデコーディング（typed decoding）などの）線形の量子化又は統計的な圧縮のような幾つかの伝統的な圧縮技術を使用することが有用である。
【００６５】
次に、より優れた圧縮比を実現するために、２．１節で説明されたコンテキストコーディングの方法の中で、ある文書のデータリーフの圧縮を行うことができる方法を示す。
【００６６】
２．２．１ 線形量子化
（定義）
線形量子化は、情報源が既知であり、このため損失を制御できる場合に、ビットストリーム内のコード化された数の大きさを減らすための通常の損失の多い方法である。
一例として、サンプリングされたオーディオ信号の包絡線は正確なビットサイズの量子化を有するとして良く知られており、この技術は、ＭＰＥＧ−７のオーディオ記述をコーディングするために効果的に使用することができる。
νが実数の場合には、νはnbitsビットのνqにより下記のようにコード化することができる。
【数１】
ここで、
−νqは、νの量子化及びコード化された値である。
−nbitsは、ビットに必要な精度である。
−νminは、νが到達できる最小の包含的値である。
−νmaxは、νが到達できる最大の包含的値である。
【００６７】
νからのデコード値は、
【数２】
であり、次式で与えられる。
【数３】
ここで、
【数４】
は、νのデコードされた近似値である。
【００６８】
（コンテキスト方法との統合：LinearQuantizerCodec）
線形の量子化は、本明細書の２．１節の中で説明されたコーディングコンテキスト方法で定義されたように、コーデックとして使用できる。この方法を用いて、線形の量子化を記述のどのようなサブツリーの中でも、望ましい単純なタイプの数値データのリーフに対して適用できる。
【００６９】
このように使用することにより、線形の量子化コーデックに関連するコーディングコンテキスト方法は、ＭＰＥＧ−４のＢＩＦＳ［３］の中で使用されるQuantizationParameterノードとして動作する。
【００７０】
（適用可能な単純なタイプに対する制約）
本明細書の２．１節のコーデックに対する定義によれば、このコーデックはメモリ無しのコーデックであり、これは全ての極小の数値及び極小でない数値の単純なタイプに適用できる。そのＸＭＬスキーマの基本タイプは、フロート、ダブル又はデシマルである。
【００７１】
（コーデックの外部パラメータ）
線形量子化器のコーデックは、下記の３つの必須のパラメータである
−上記のnbits変数であるbitSizeと、
−上記のνmin変数であるminInclusiveと、
−上記のνmax変数であるmaxInclusiveと
を必要とする。
【００７２】
（コーデックのスキーマの定義）
線形量子化のコーデックは、抽象的なCodecTypeタイプ（２．１節を参照のこと）に基づいて、コーディングコンテキストのnamespaceのＵＲＬ xmlns:cc=http://www.mpeg7.org/2001/BiMCodingにおける補遺５の中で与えられたスキーマで定義されたタイプLinearQuantizerCodecTypeの新しいコーデックである。
【００７３】
（コード化（情報提供））
値νの数値データのリーフは、nbitsビットの符号のない整数νqにより下記の式のよう
にコード化される。
【数５】
【００７４】
（デコーディング）
nbitsビットでコード化された符号のない整数νqは、下記の式のように、
【数６】
としてデコードされるべきである。
【数７】
【００７５】
（実施例（情報提供））
補遺６で示された実施例は、記述における線形量子化器の定義を示す。
【００７６】
２．２．２ 統計的な圧縮
伝統的な損失のない統計的な圧縮アルゴリズムは、コーディングコンテキスト方法（２．１節を参照）の中で定義されたようなコーデックとして使用できる。この方法を用いて、どの記述のサブツリーの中でも、望ましい単純なタイプのデータリーフを効率的に圧縮できる。
このコーデックは、特に記述が多くの反復的な又は同様のストリングを含む場合には、ビットストリームの大きさを著しく減少させるために有用である。
【００７７】
（定義）
（Zip又はGZipなどの）伝統的な損失のない統計的な圧縮アルゴリズムをＢｉＭの中で用いて、記述の任意のリーフを圧縮することができる。
しかし、大抵の場合、データリーフが１０文字よりも少ない短いストリングの場合には、通常の統計的な圧縮アルゴリズムは大きなルックアヘッドバッファ（lookahead buffer）を必要とするため、このアルゴリズムの性能は良くない。
最適な圧縮比を実現するために、文書のリーフは圧縮する前に、小さいバッファにバッファする必要がある。次の節は、根本的な損失のない統計的な圧縮アルゴリズムに依存するそのようなバッファ付き統計的コーダ（a buffered statistical coder）を定義する。
【００７８】
（バッファ付き統計的コーダの定義）
バッファ付き統計的コーダは、一般的な下記の基本的な方法である、
−ストリームの圧縮又は解凍動作を初期化するinitialize_stream()と、
−コーダの現在の統計的なモデルをリセットするreset_model()と、
−入力の解凍されたバイトを取り、圧縮ストリームの中に入れるfeed_input_bytes()と、
−既に処理された入力バイトを圧縮し、対応する圧縮された出力バイトを出すことによって、圧縮ストリームをフラッシュするflush_output_bytes()と、
−指定された量の圧縮された入力バイトを取り、対応する解凍された出力バイトを出すことによってそれらをデコードするdecompress_input_bytes()と
を必ず含む根本的な統計的コーダに依存する。
バッファ付きコーデックは、bufferSizeのバイト長、すなわちバイトアレイバッファ（byte array buffer）のＦＩＦＯ構造を有する。
エンコーダ側から見ると、bufferSize値はフラッシングの前にエンコーダがどの位の入力バイトを処理できるかを示す。デコーダ側からすると、これは根本的な統計的コーダのＡＰＩを通してビットストリームをデコードするために必要な最小のバッファ寸法である。
このバッファはfillingLevel変数も有する。この変数は、バッファのバイトにおける実際の充填レベルを含む。
【００７９】
（統計的なコーダとしてのZLib ＡＰＩの使用）
GZip圧縮方式の中で使用されるZLibの公開ライブラリのＡＰＩ［４］は、文書リーフに対して統計的圧縮を行うための効率的で有用なＡＰＩを提供する。
【００８０】
ZLib ＡＰＩは、下記のマッピングを用いて前の一般的な方法を実行する。
−initialize_stream()は、Z_DEFAULT_COMPRESSIONの効率値のパラメータを用いて、ZLibのinflateInit()又はdeflateInit()機能によってマッピングすることができる。
−reset_model()は、ZLibのinflateEnd()又はdeflateEnd()コール及び次のinitialize_stream()コールを用いてマッピングすることができる。
−feed_input_bytes()は、Z_NO_FLUSHパラメータを用いてZLibのdeflate()方法によりマッピングすることができる。
−flush_output_bytes()は、Z_SYNC_FLUSHパラメータを用いてZLibのdeflate()方法によりマッピングすることができる。
−decompress_input_bytes()は、ZLibのdeflate()方法によりマッピングすることができる。
【００８１】
ZLibのバッファ付きコーデックは、［４］で定義されたように、Z_DEFAULT_COMPRESSIONの効率値を用いて初期化されるべきである。このことは、メモリのフットプリント（footprint）についての要求事項と圧縮効率との間の良いトレードオフになる。
【００８２】
（コンテキスト方法との統合：ZlibCodec）
この節では、コーディングコンテキスト方法の中で定義された、ZLib ＡＰＩに依存する、上記のバッファ付き統計的コーダの統合について説明する。
【００８３】
（適用可能な単純なタイプに対する制約）
２．１節のコーデックに対する定義によれば、このコーデックはコンテキスト式コーデックであり、これは全ての極小のストリングタイプ及び極小でないストリングタイプに適用できる。ZLibCodecは、［１］の中で説明したように、文書のリーフの根本をなす基本的なコード化に依存している。例えば、intリーフは３２ビットの符号のない整数によりコード化され、stringリーフはＵＴＦ−８のコード化により、float及びdoubleリーフはＩＥＥＥ７５４形式でコード化される。このため、ZLibCodecは、コード化されたリーフを圧縮できる。
【００８４】
（コーデックの外部パラメータ）
バッファ付きのZLibコーデックは、根本的なZLibの効率がZ_DEFAULT_COMPRESSIONに設定され、bufferSizeパラメータがデコーダ側からは必要とはされないため、どのような外部のパラメータも必要としない。
【００８５】
（コーデックのスキーマの定義）
このZLibコーデックは、抽象的なCodecTypeタイプ（２．１節を参照のこと）に基づいて、補遺７のコーディングコンテキストのnamespaceの中で説明されたスキーマによって定義されたZLibCodecTypeタイプの新しいコーデックである。
【００８６】
（コード化（情報提供））
コーデックの活性化又はインスタンシエーションにおいては、
−ＦＩＦＯのバッファ構造はクリアであると想定され、そのfillingLevelは０に設定される。
−グローバル変数referencable_chunkは０に初期化される。
このreferencable_chunkは、エンコーダが保持しなければならない参照可能なビットのチャンクを含むべきである。その理由は、その値がコード化工程の間に後で知られるからである。通信関数signal_reference_chunk_known()は、このチャンクが知られた場合には呼び出すことができる。
全てのゼロでないチャンクのバイトの大きさは、［１］で定義されたように、標準的な符号無しの無限の整数４＋１コーディング（infinite integer 4+1 coding）を用いて、flush_output_bytes()呼出しの間にチャンク自身の前に書き込まれるべきである。
入力リーフ（input leaf）は、その基本のタイプに関連したテキストのリーフのコード化された値である。このリーフのバイトの長さは、フィールドleaf.lengthによって与えられる。一例［１］を挙げれば、stringリーフは、ストリングのバイトの大きさが前に来る（無限整数のコーディング［１］を用いてコード化された）ＵＴＦ−８のコードであり、doubleリーフは、対応するＩＥＥＥ７５４規格の６４ビット値である。
【００８７】
下記のencode_leaf関数は、出力バイトのチャンク内のリーフをコード化することができる。
chunk encode_leaf(chunk leaf) [
while (leaf is not empty) [
if (fillingLevel + leaf.length < bufferSize) [
feed_input_bytes(leaf,leaf.length)
fillingLevel = fillingLevel + leaf.length
if (referencable_chunk is null) [
referencable_chunk = new chunk
return referencable_chunk
] else [
return nil_size_chunk
]
] else [
remaining_bytes = bufferSize - fillingLevel - leaf.length
feed_input_bytes(leaf,remaining_bytes)
referencable_chunk = flush_output_bytes()
signal_reference_chunk_known()
fillingLevel = 0
leaf = leaf.remove_beginning_bytes(remaining_bytes)
referencable_chunk = null
]
]
]
【００８８】
（デコーディング）
string_fifoをストリングＦＩＦＯとする。
下記の方法get()及びput()は、それぞれ、ＦＩＦＯから要素を取り出し、ＦＩＦＯに要素を置く。
ＦＩＦＯが空かどうかを知る方法はEmpty()信号である。
subをサブストリングを取り出す関数とする。
concatを連結関数とする。
getData()を、リーフからのde-gzipデータを保持するchar[]を戻す関数とする。
split(char[] , char sep, Fifo, char[] remainder)を各セパレータ「sep」において文字のアレイを分割し、この分割されたストリング要素をＦＩＦＯに保管し残りを戻す方法とする。
[
if (data==null) return;
int BEGIN=0;
for (int I=0;I<data.length;I++)
[
if (data[I]==sep)
[
char[] str= concat(remainder, sub(data,BEGIN,I));
put(string_fifo, str);
BEGIN=I+1;
]
]
if(BEGIN!=data.length)
[
//there's a remainder.
remainder = sub(data,BEGIN,data.length);
]
]
String decode()
[
if (isEmpty(string_fifo)
[
data = getData();
split(data,0x00,string_fifo,remainder);
]
return get(string_fifo);
]
初期化されたとき、string_fifoは空である。
コーデックの活性化又はインスタンシエーションにおいては、
−ＦＩＦＯの構造はクリアであると想定され、そのnumberOfLeavesは０に設定される。
−変数first_chunkは真に設定される。
セパレータのバイトを0x00とする。
下記のdecode_leaf関数は、ビットストリームからの圧縮されたリーフをデコードすることができる。
string decode_leaf() [
if (numberOfLeaves == 0) [
read_and_decompressed_byte()
numberOfLeaves = count_number_of_leave_in_buffer()
] else [
]
]
【００８９】
デコーディングは、下記により定義される。
１．ＦＩＦＯが空の場合には、
ａ．コード化データをデコードする。
ｂ．0x00により分離された全ての要素をＦＩＦＯの中にスタックする。
ｃ．最後の文字が0x00でない場合は、未完成のストリングを一時的に保管する。
ｄ．「last_element」が空でない場合は、それをＦＩＦＯ内の第１の要素の先頭に挿入する。
ｅ．このラウンドの未完成のストリングをlast_elementの中に入れる。
ｆ．第１の要素を取り除き戻す。
【００９０】
２．ＦＩＦＯが空でない場合には、第１の要素を取り除き戻す。
これは、「ＦＩＦＯは空ではない」及び「現在のリーフにはコード化されたデータはない」と言うのに等しい。
【００９１】
（実施例（情報提供））
補遺８で与えられた説明は、string及びanyURIタイプでマッピングされたZLibCodecTypeのコーデックを使用する場合の例である。
【００９２】
（結果（情報提供））
下記の図面は、記述（string及びanyURIのＸＭＬスキーマの基本のタイプから得られた記述）のテキストのリーフを圧縮するためにZLibCodecを使用する場合の性能を示す。bufferSize＝２５６バイトのバッファは、コード化工程の間に使用された。使用されたファイルは、ＭＰＥＧ−７のＭＤＳサブグループにより提供された。
【表７】
階層化ツリーのリーフの内容を圧縮するために、本発明に基づいて実行されたステップを、ここで手早く説明する。
【００９３】
ステップ１は、圧縮コード化技術をあるコンテントタイプに対応付ける工程から成る。例えば、線形の量子化を、浮動小数点の値に対応付けることができる。
【００９４】
ステップ２では、あるサブツリーが検討されたＸＭＬ文書の構造に対応する階層化ツリーの中で識別される。
【００９５】
ステップ３は、圧縮コード化技術を識別されたサブツリーに割り当てる工程から成る。
【００９６】
そして、ステップ４は、圧縮コード化技術を実行しているコーデックが起動されているかどうかを検査する工程から成る。起動されていない場合には、サブツリーのリーフの圧縮（ステップ５）は行われない。
【００９７】
起動されている場合には、本発明は、その内容が（ステップ１において）圧縮コード化技術に対応付けられたコンテントタイプであるような、サブツリーのリーフの内容の圧縮を実行する（ステップ６）。
【００９８】
［補遺１］
【表８】
【００９９】
［補遺２］
【表９Ａ】
【表９Ｂ】
【０１００】
［補遺３］
【表１０】
【０１０１】
［補遺４］
【表１１Ａ】
【表１１Ｂ】
【０１０２】
［補遺５］
【表１２】
【０１０３】
［補遺６］
【表１３】
【０１０４】
［補遺７］
【表１４】
【０１０５】
［補遺８］
【表１５Ａ】
【表１５Ｂ】
【０１０６】
［補遺９］
【表１６】
【図面の簡単な説明】
【０１０７】
【図１】コーディングコンテキストの概念を説明する図である。
【図２】ＢｉＭ技術に基づいてコーディングされた要素の構造を説明する図である。
【図３】階層化ツリーのリーフの内容を圧縮するために、本発明に基づいて実行される幾つかのステップを示す図である。
【技術分野】
【０００１】
本発明の技術分野は、データを圧縮する分野である。より正確には、本発明はＸＭＬベースの文書（「拡張マークアップ言語規約（eXtended Markup Language）」）に関する。
【背景技術】
【０００２】
本発明には、特に下記の分野のアプリケーションがあるが、それらに限定されない。
−マルチメディア用アプリケーション
−インデクセーションツール（indexation tool）
−メタデータ（meta-data）取扱いツール
−ＭＰＥＧ−７規格
−ＳＭＩＬ
−常設ＴＶ（TV Anytime）
−第三世代の無線通信（３ＧＰＰ）
【０００３】
ＸＭＬに対する従来の圧縮技術には、幾つかの欠点がある。特に、それらの技術はデータへの高速アクセス、高い圧縮率及び文書のプログレッシブ構造に同時に対応していない。言い換えると、大抵の場合、上記の特徴の１つに対応すると、他の全ての特徴が失われてしまう。
【０００４】
従来の圧縮技術の１つは、ＢｉＭ（２進ＭＰＥＧ）として周知である。そのような技術は、文書の構造、すなわちＸＭＬ文書に関連したツリー構造のノードを２進化することによって、ＸＭＬ文書を圧縮する方法を提供する。このため、ＢｉＭ技術はデータへの高速アクセス、文書のプログレッシブ構造及びスキップ能力を可能にするが、ＢｉＭ技術を実行することによって得られる圧縮率は極めて小さい。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
本発明の目的は、従来技術の欠点を補償することである。より正確には、本発明は、ＸＭＬベースの文書に対する効率的な圧縮技術を提供することを目的とする。本発明は、文書のスキップ能力、高い圧縮率、及びプログレッシブ構造を提供する、ＸＭＬ文書に対する圧縮技術を提供することも目的とする。本発明は、ＭＰＥＧ−７記述子を効率的に圧縮することも目的とする。本発明の別の目的はＸＭＬ文書を圧縮するための方法を実現することであり、この方法は、ＢｉＭ形の技術によって与えられた圧縮率を大いに向上させるが、ＢｉＭにより与えられる機能性と同じ機能性を提供する。
【課題を解決するための手段】
【０００６】
後に出てくる本発明の別の目的と同様に本発明の上記の目的は、本発明に基づいて、マルチメディア信号を記述する階層化ツリーを圧縮する方法によって実現される。このツリーは、少なくとも２つの明確なタイプの内容に結び付けることができるノード及びリーフを含むものである。この場合には、この方法は、それぞれが少なくとも１つのコンテントタイプに選択的に関連付けられた少なくとも２つの圧縮コード化技術によって、少なくとも幾つかのリーフに対してコンテント圧縮（content compression）を実現する。
【０００７】
本発明の好ましい実施形態によれば、そのような方法は少なくとも１つのサブツリー（sub-tree）を識別するステップと、圧縮コード化技術の１つをこのサブツリーに割り当てるステップとを含む。
【０００８】
有利には、そのような方法は、サブツリーのリーフのコンテンツ（又は、内容）が圧縮コード化技術に関連したタイプであり、サブツリーの他のリーフがいかなる圧縮コード化処理も受けないようなサブツリーのみに割り当てられた圧縮コード化技術を実行するステップを含む。
【０００９】
本発明の好ましい特徴によれば、そのような方法は、圧縮コード化技術のパラメータ記述を実行する。
そのような方法は、このツリーの構造を選択的に圧縮するステップも含む。
有利には、このツリーは、ＭＰＥＧ７規格によるＢｉＭ（２進ＭＰＥＧ）形である。
この圧縮コード化技術の１つは、線形の量子化を選択的に実行する。
有利には、この圧縮コード化技術の１つは統計的な圧縮アルゴリズムを実行する。
選択的には、このアルゴリズムはＧＺｉｐ形である。
有利には、このアルゴリズムは、少なくとも２つのリーフの内容に対応するデータの集合に対して同時に実行される。
このツリーは、ＸＭＬ（Extended markup language：拡張マークアップ言語規約）形の文書の構造を選択的に示す。
本発明は、階層化ツリーを圧縮するための上記の方法に基づいて圧縮されたマルチメディア信号をデコードする方法にも関係する。
【００１０】
有利には、そのような方法は、信号によって伝達されたコンテキスト情報（context information）のコード化に基づいて、現在のデコーディングコンテキスト（decoding context）をリフレッシュするステップを実行する。
この現在のコンテキストは、少なくとも１つのコンテントタイプを選択的に定義し、この方法は、リーフがこのコンテントタイプの内容を有するようなこのコンテントタイプに関連した圧縮デコーディング技術を実行するステップを含む。
【００１１】
本発明は、階層化ツリーを圧縮する前述した方法が発生する信号にも関係する。
【００１２】
本発明の他の特徴及び利点は、下記の説明及び以下の図面に照らしてより明確になるであろう。下記の説明は、単に説明するために示すものであり、実施例に限定するものではない。
【００１３】
本発明を実行する方法を詳細に説明する前に、ＢｉＭ技術としてよく知られた従来の圧縮技術の主な特徴を最初に思い出してみる。
【００１４】
文書を容易に理解するために、幾つかの引例をＡｎｎｅｘ９（表１６）の中に集めて、本明細書全体にわたって参照する。本明細書に含まれる全てのＡｎｎｅｘ（補遺）は、本発明の説明の一部をなすものである。
【００１５】
１．従来技術
（はじめに）
図１に示したコーディングコンテキストは、ビットストリームをデコーディングする間に必要なデコーディング情報の集合である。コーディングコンテキストは、定義されるノードのサブツリー全体に適用できる。ツリーの全てのノードにおいて、コーディングコンテキストを修正して、新しいコーディングコンテキストを作成し、対応するサブツリーに適用するようにできる。
【００１６】
コンテキストは、命令が関係するサブツリーに適用できることを特徴とする幾つかの情報を保持できる。現在のところ、ＢｉＭのサブツリーのコーディングフォーマット［１］では、これらの特徴は、（後方及び前方の互換性の特徴を提供するため、）サブツリーまたはコンテキストのスキップ能力及びサブツリーまたはコンテキストに対する複数のスキーマ（schema）のコード化である。最後に、このコンテキスト方法は、帯域幅をセーブするために全てのサブツリー内で無効にすることができる。これはコンテキスト凍結モードである。
【００１７】
このコーディングコンテキスト方法は、文書ツリーの全てのサブツリーの中で最大の柔軟性を提供し、ＢｉＭのコード化方法にプラグ接続されるという拡張可能な特徴を可能にする。
【００１８】
発明者らは、次に、ＢｉＭ内で使用されるコンテキスト方法を説明する。
【００１９】
[現在のコーディングコンテキスト方法]
（定義）
（コーディングコンテキスト（codingContext））
「コーディングコンテキスト」とは、デコーダがビットストリームをデコードするために必要とする情報の集合、すなわちコンテキスト情報である。コーディングコンテキストは、それが定義されているノード及びこのノードに対応するサブツリー全体に適用できる。
現在のコーディングコンテキスト（つまり、ある記述の指定されたノードにおいて適用可能なコンテキスト）は、文書内で修正することができる（換言すれば、その下にある情報の集合の修正）。コーディングコンテキストが修正されるたびに、修正された情報の集合を保持する新しいコーディングコンテキストが作成される。全てのコーディングコンテキストは、デコーダがコンテキストに対応するサブツリーのデコーディングを終了したとき、それらを元に戻すためにスタックされるべきものである。
【００２０】
（デコーダ）
ＢｉＭのデコーダは、下記の２つのデコーダからなる、すなわち、
−コンテキストデコーダ（context decoder）。このデコーダは、コンテキスト情報のデコーディング専用である。前述したように、コンテキスト情報は記述の一部ではない。これは幾つかの外部形状、後方及び前方の互換性、高速スキッピング（fast skipping）などを保持する情報の集合である。
−要素デコーダ（element decoder）。このデコーダはＢｉＭ正規デコーダ［１］（BiM regular one）であり、要素情報のデコーディング専用である。
【００２１】
（チャンク）
記述の各要素は、図２に示した３つの部分にコード化される。この場合、ヘッダ部は大きさをゼロにできる２つのチャンクから構成される。
−ＭＣはメタコンテキストのチャンク（metacontext chunk）である。
−Ｃはコンテキストチャンクである。
−エレメント（Element）は要素チャンクであり、これは正規の要素コーディングチャンクである（［１］を参照のこと）
このＭＣメタコンテキストチャンクは、デコーダが次のＣコンテキストチャンクをデコードするために必要とする情報を含む。すなわち、ＭＣチャンクは、Ｃコンテキストチャンクのコンテキストチャンクである。
このＣコンテキストチャンクは、デコーダが次の要素チャンクをデコードするために必要な、現在のコーディングコンテキストの情報の集合を変更できる情報を含む。言い換えると、このＣチャンクは、要素チャンクのコンテキストチャンクである。
【００２２】
（情報の集合）
現在のＢｉＭコーディングコンテキストは、情報の集合、すなわち、次の２つの主な部類に分割できるコンテキスト情報を保持する。
−（この節に含まれた情報がコンテキストデコーディング工程のみに影響する場合の）メタコンテキスト部。
−（この節に含まれた情報が要素デコーディング工程のみに影響する場合の）コンテキスト部。
【００２３】
現在の情報の集合は、下記の変数の集合である。
【表１】
定義されたクラスは、（ＭＣメタコンテキストチャンク及びＣコンテキストチャンク等の）前述したチャンクを正確にコーディングする。
【００２４】
[メタコンテキストチャンク]
（定義）
ＭＣメタコンテキストチャンクは、その大きさをゼロにすることができ、デコーダが以下の節で説明されるような次のＣコンテキストチャンクを読み取る必要があるかどうかを知るための情報を含む。
【００２５】
（関係する変数）
【表２】
【００２６】
（デフォルト値）
freezing_stateのデフォルト値は偽である。すなわち、デフォルトでは、根本的なコンテキストを動的に変更できるようになっている。
【００２７】
（伝搬規則）
新しいコンテキストが作成されるときには、
−freezing_state値は、その父親のコンテキスト（father's context）のfreezing_state値に設定される。
【００２８】
（動的修正規則）
新しいコンテキストを作成するために、記述の各ノードにおいて、
−freezing_state値を偽の値から真の値に切り換えることができる。
【００２９】
（デコーディング規則）
freezing_state値が真の場合には、ＭＣメタコンテキストチャンク（及び次のＣコンテキストチャンク）はビットストリームにコード化されない。真でない場合には、ヘッダ部分のＭＣメタコンテキストチャンクは下記のようにコード化される。
【表３】
context_chunkは偽で初期化されたローカル変数である。
【００３０】
【表４】
前の節で述べたように、現在のコンテキストの変数の修正は、新しいコンテキストの作成を意味する。
【００３１】
（コンテキストデコーディング工程に対する影響）
context_chunk値が真の場合には、デコーダは次のＣコンテキストチャンクを読み込む必要がある。
【００３２】
コンテキストチャンク
（定義）
Ｃコンテキストチャンクは、大きさをゼロにすることができ、現在のコンテキスト変数を動的に変更できる情報の集合を含む。これらの変数は、ＢｉＭ要素のデコーディング工程に影響を与えるため、コーディング特性（codingProperties）と呼ばれる。
（関係するコーディング特性）
【表５】
【００３３】
（デフォルト値）
allows_skip変数は、ＦＤＣシステム文書［１］の中で定義されているように、特別な４ビットのビットフィールド（bitfield）の最初の２ビットによって、ビットストリームの始めで初期化される。
allows_partial_instantiation変数は、特別な４ビットのビットフィールドの第３の２ビットによって、ビットストリームの始めで初期化される。
allows_subtyping変数は、特別な４ビットのビットフィールドの第４の２ビットによって、ビットストリームの始めで初期化される。
schema_modeのデフォルト値は、モノラル（mono）である。すなわち、デフォルトでは、ルートのサブツリー／コンテキストは１つのスキーマを用いてコード化される。
【００３４】
（伝搬規則）
新しいコンテキストの作成時に、
−allows_skip値は、その父親のコンテキストのallows_skip値に設定される。
−allows_partial_instantiation値は、その父親のコンテキストの値に設定される。
−allows_subtyping値は、その父親のコンテキストの値に設定される。
−schema_mode値は、そのデフォルト値に設定される。
【００３５】
（動的修正規則）
新しいコンテキストを作成するために、記述の各ノードにおいて、
−allows_skipは動的に修正できる。
−allows_partial_instantiationは動的に修正できない。
−allows_subtypingは動的に修正できない。
−schema_modeは動的に修正できる。
【００３６】
（デコーディング規則）
Ｃコンテキストチャンクは、ＭＣメタコンテキストチャンクが既に存在し、その以前のローカル変数context_chunkが真の場合にのみ存在する。
現在のコンテキストの動的な修正は、ＢｉＭの正規のコード化方式を用いてコード化されるＸＭＬ要素を用いて記述される。ＢｉＭスキーマからの汎用要素modifyContextが使用される。http://www.mpeg7.org/2001/BiMCodingのコーディングスキーマは、補遺１に記載されている。
Ｃコンテキストチャンクは、上記のスキーマによるＢｉＭの正規の方式を用いて記述する必要がある。
前述したように、コンテキスト内の現在のコーディング特性の修正は、新しいコンテキストの作成を意味する。このため、Ｃコンテキストチャンクが存在することは、修正されたコーディング特性を保持する新しいコンテキストが作られたことを意味する。
allowsSkip要素がmodifyContext要素の中で例示される場合には、allows_skipの値は新しいコンテキストの中で更新される。
schema_mode要素がmodifyContext要素の中で例示される場合には、schema_modeの値は新しいコンテキストの中で更新される。
【００３７】
（要素デコーディング工程に対する影響）
allows_skip値及びschema_mode値は、スキッピング特性を処理する場合に要素デコーディング工程に影響を与える。この動作は［１］に記載されている。
schema_mode値は、要素が１つのスキーマだけにより又は幾つかのスキーマによりコード化されるのかどうかを知るために要素デコーディング工程に影響する。この仕組みは［１］に記載されている。
allows_partial_instantiation値は、１つの特殊なタイプのpartiallylnstantiatedタイプを要素の可能なサブタイプに加えることによって、要素デコーディング工程に影響を与える。［１］を参照のこと。
allows_subtyping値は、要素デコーディング工程に影響し、要素が多形性（polymorphism）（xsi:typeの属性を有する）又はユニオンの場合には、要素又は属性が異なる可能なタイプを持つことができるようにする。［１］を参照のこと。
【発明を実施するための最良の形態】
【００３８】
２．本発明の説明
２．１ リーフを圧縮するためのフレームワークを提供するコンテキスト方法の拡張
本発明は、新規で興味ある特徴、すなわち、結果として生ずるビットストリームの大きさを減らすために、ある文書のリーフを圧縮する局部圧縮機（local compressor）を使用して、現在のＢｉＭコンテキスト方法を拡張することを提案する。
【００３９】
この節では、局部圧縮機を使用できるように現在のＢｉＭコンテキスト方法を拡張する方法を説明する。これは、典型的な例では、特定の意味論規則、伝搬規則及びコーディング規則とリンクした新しい変数の集合のcodingPropertiesである。従って、この新たなcodingPropertiesの集合によって、現在のコンテキストチャンクが拡張される。
【００４０】
（はじめに）
サブツリーでは、１つ又は数個の指定された単純なタイプのインスタンスがあると、それらは全て１つ又は数個の指定された圧縮機を用いて圧縮することができる。これは基本的には、圧縮機と１つ又は数個の単純なタイプとの間のマッピングを定義する。
さらに、
−場合によっては、圧縮機は幾つかの外部パラメータを必要とすることができる。
−幾つかのサブツリー内で圧縮機を使用し、別のサブツリーでは使用しないようにするために、マッピングを起動又は停止することができる。
最後に、起動または停止するために、マッピングは参照可能でなければならず、このためコンテキストの中で固有の識別子を持つ必要がある。
その結果、各コンテキストは、ゼロ、１つ又は数個のcodecTypeMapperを保持できる。ここで、codecTypeMapperは、識別子、１つ又は数個の単純なタイプ、コーデック、選択可能な外部のコーデックパラメータ及び活性化状態から成る４プレット（4-plet）である。
【００４１】
（定義）
（CodecTypeMapper）
codecTypeMapperは、４プレットであり、
−サブツリーまたはコンテキストの中で固有の参照キーとして使用される識別子と、
−マッピングが適用できる１つ又は数個の単純なタイプと、
−コーデックと、
−任意選択的な外部コーデックパラメータ（コーデックに依存する）と、
−活性化状態と
を備えている。
【００４２】
（識別子）
識別子は、固有の番号であり、明白な方法でコンテキスト内のマッピングを識別する。ＢｉＭのコーディングスキーマは、コンテキスト内のcodecTypeMappersの最大数を３２に制限する。
【００４３】
（単純なタイプ）
あるスキーマにおいて定義された全ての単純なタイプ（simple type）は、全てのコーデックによって先験的に（a priori）コード化することができるが、各コーデックはこの選択を制限できる。例えば、以後文書の中で定義するような線形の量子化器（linear quantizer）は、数値的な単純なタイプと共にのみ使用できる。
【００４４】
単純なタイプは、その名前及びそれが属するスキーマのＵＲＬによって識別される。正しいスキーマを指し示すために、ＸＭＬスキーマのプレフィックス（prefix）を用いるべきである。ＢｉＭコーディングスキーマは、この対をコード化するためにある特殊なタイプを定義する、すなわち、このタイプは整数の対としてコード化されなければならない、第１の整数はわかっているスキーマの現在の数に制限され（この情報の部分は、DecoderConfig部［１］の中でフェッチすることができる）、第２の整数は対応するスキーマの中に存在するグローバルな単純なタイプの数に制限される。
【００４５】
（コーデック）
圧縮機または解凍機（compressor/decompressor）の役目をするコーデック（codec）は、入力ビットを取り入れて出力ビットを書き込むモジュールである。それは幾つかの選択可能な外部パラメータを必要とすることがある。
コーデックは、ＢｉＭのコーディングスキーマの中で定義された非抽象的なコーデックの名前の中の名前によって識別される。上記の節の中で定義された現在のＢｉＭのコーディングスキーマは、どの非抽象的なコーデックも定義しないが、本明細書の２．２節（段落番号[００６１]以下）では定義している。
【００４６】
（活性化状態）
活性化状態はブーリアンフラグである。
【００４７】
（意味論規則）
（CodecTypeMapper）
各コンテキストは、
−ゼロ、１つ又は数個のcodecTypeMapperを保持できる。
−１つ又は数個のcodecTypeMapperを定義できる。
−１つ又は数個の現行のcodecTypeMapperを起動又は停止できる。
あるcodecTypeMapperがコンテキストの中で定義されると、それは全てのそのサブコンテキストの中に残る。
コンテキスト内に存在するcodecTypeMapperを削除又は修正することはできない（活性化状態は除く）。
【００４８】
（識別子）
マッピングの識別子は、コンテキストの全てのcodecTypeMapperの中で一意的でなければならない。
【００４９】
（単純なタイプ）
codecTypeMapperを１つ又は数個の単純なタイプ及びコーデックと結び付ける場合、このコーデックは単純なタイプ自体及びそれらから生じた全ての単純なタイプをコード化／デコードする。
コンテキストには、コーデックの場合とは異なり、たかだか１つの単純なタイプが存在する必要がある。
【００５０】
（コーデック）
２種類のコーデック、すなわち、メモリ無しのコーデックとコンテキスト式コーデックとがある。
メモリ無しのコーデックは、常に同じ入力バイトを同じバイト出力にコード化するモジュールであり、コーデックの履歴に無関係である。典型的なメモリ無しのコーデックは、線形の限定子である。ＢｉＭのリーフ圧縮（本明細書の２．２節を参照のこと）は、そのようなコーデックを説明している。
コンテキスト式コーデックは、送られた以前のバイトを使用する（このため、コーデックのコンテキストは変更される）モジュールである。そのようなコーデックは、受け取った同じ入力バイトに対して同じ出力バイトを発生しない。典型的なコンテキスト式コーデックは、Ｚｉｐのようなローカルコーデックであり、本明細書の２．２節に説明されている。
メモリ無しのコーデックは、現在のコンテキストのアーキテクチャでは何ら問題を引き起こさないが、コンテキスト式コーデックはスキップ可能なサブツリーの場合には問題を発生する。そのような場合には、この前者がサブツリーをスキップした場合にデコーダを混乱させないように、コンテキスト式コーデックはリセットされる。
【００５１】
（活性化状態）
全てのサブツリー又はコンテキストにおいて、codecTypeMapperを起動又は停止することができる。
この仕組みにより、codecTypeMapperを文書ツリーのより高いレベルで定義し、使用されているサブツリーの中でのみcodecTypeMapperを再定義せずに起動することができる。
【００５２】
（新しいcodingProperty：codecTypeMapper）
この部分では、新しいcodingPropertyを、前述したコンテキスト部の以前の変数の集合に加える。この新しいcodingPropertyはcodecTypeMapperと名付けられ、前の節の中で説明された以前のcodecTypeMapperのリストである。
【００５３】
（関係する新しいcodingProperty）
コンテキストはcodecTypeMapperのリストを保持する。
【００５４】
【表６】
【００５５】
（新しいデフォルト値）
デフォルトにより、サブツリー又はコンテキスト内にはcodecTypeMapperはない。
codecTypeMapperをコンテキスト内で定義する場合には、その識別子、コーデック及びsimple_type値を定義する必要がある。指定されない場合は、新しく定義されたcodecTypeMapperの活性化状態はデフォルトにより真に設定される。すなわち、新しく定義されたcodecTypeMapperはデフォルトにより起動される。
【００５６】
（新しい伝搬規則）
（規則１）
新しいコンテキストの作成時には、codecTypeMapperのリストはその父親のコンテキストのコピーである。
−識別子の値がコピーされる。
−simple_typeの値がコピーされる。
−コーデックの値が規則２に従ってコピーされる。
−codec_parameterの値がコピーされる。
−activation_stateの値がコピーされる。
（規則２）
コーデックの値がコピーされ、下記が成立する場合、つまり、
−父親のコーデックのcodingProperty[i].codecがコンテキスト式コーデックであり、
−現在のコンテキストがスキップ可能である場合には、
デコーダは、父親のコーデックの事例（その値だけでなく）をコピーし、それをリセットすることによって、コーデックの新しい事例を作成することが期待される。
例えば、ZLibコーデックがコピーされ、スキップ可能なノードに入るときに再度初期化される。
【００５７】
（新しい動的な修正規則）
codecTypeMapperのリストを記述の中で下記のように動的に修正できる。
−新しいcodecTypeMapperを定義できる。
−現在の（次に参照可能な）activation_stateのcodecTypeMapperを動的に修正できる。
（そのactivation_stateを除き、）現在のcodecTypeMapperを削除することはできず、そのメンバを動的に修正することもできない。
【００５８】
（新しいデコーディング規則）
同じ前の規則はＣコンテキストチャンクのデコーディングに適用するが、補遺２で説明される新しいスキーマが、新しいcodecTypeMapperの動的な修正機能を加えるために使用される。
【００５９】
（情報提供部）
（実施例）
補遺３に示した実施例は、記述する場合の１つの活性化された線形の限定子（本明細書の２．２節を参照のこと）の定義を示す。
【００６０】
補遺４に示した実施例は、記述する場合の１つの非活性化された線形の限定子（本明細書の２．２節を参照のこと）の定義を示す。
【００６１】
２．２ ＢｉＭのリーフ圧縮
異なるコーデックを用いてデータをコード化するために、本発明によって実現された仕組みをここで示す。より正確に言うと、ここで２つの実施例を示す、すなわち、１つは線形の量子化コーデックを使用して例えば浮動小数点の値を圧縮する実施例、及びもう１つはgzipのコーデックを使用して例えばストリング値を圧縮する実施例である。
【００６２】
そのような仕組みはコーディングコンテキストに密接に関連しており、幾つかの他の種類のコーデックを使用できるようにする。さらに、この仕組みは、例えば、ストリップ可能なサブツリーなどのコーディングコンテキストの機能を適切に処理できる。最後に、この仕組みは、別のコーディングコンテキスト内のコーデックを再度使用することができる。
【００６３】
（はじめに）
ＢｉＭのサブツリーのコーディング［１］は、記述のデータリーフを圧縮しない。現在は、リーフ値は、（ＩＥＥＥ７５４のフロート及びダブル（floats and doubles）、ＵＴＦストリングなどの）その種類に関連してコード化される。
【００６４】
多くの場合には、ＢｉＭの圧縮比をその主な機能を失わずに向上させるために、（流線型の構文解析（streamline parsing）、高速スキッピング機能、タイプドデコーディング（typed decoding）などの）線形の量子化又は統計的な圧縮のような幾つかの伝統的な圧縮技術を使用することが有用である。
【００６５】
次に、より優れた圧縮比を実現するために、２．１節で説明されたコンテキストコーディングの方法の中で、ある文書のデータリーフの圧縮を行うことができる方法を示す。
【００６６】
２．２．１ 線形量子化
（定義）
線形量子化は、情報源が既知であり、このため損失を制御できる場合に、ビットストリーム内のコード化された数の大きさを減らすための通常の損失の多い方法である。
一例として、サンプリングされたオーディオ信号の包絡線は正確なビットサイズの量子化を有するとして良く知られており、この技術は、ＭＰＥＧ−７のオーディオ記述をコーディングするために効果的に使用することができる。
νが実数の場合には、νはnbitsビットのνqにより下記のようにコード化することができる。
【数１】
ここで、
−νqは、νの量子化及びコード化された値である。
−nbitsは、ビットに必要な精度である。
−νminは、νが到達できる最小の包含的値である。
−νmaxは、νが到達できる最大の包含的値である。
【００６７】
νからのデコード値は、
【数２】
であり、次式で与えられる。
【数３】
ここで、
【数４】
は、νのデコードされた近似値である。
【００６８】
（コンテキスト方法との統合：LinearQuantizerCodec）
線形の量子化は、本明細書の２．１節の中で説明されたコーディングコンテキスト方法で定義されたように、コーデックとして使用できる。この方法を用いて、線形の量子化を記述のどのようなサブツリーの中でも、望ましい単純なタイプの数値データのリーフに対して適用できる。
【００６９】
このように使用することにより、線形の量子化コーデックに関連するコーディングコンテキスト方法は、ＭＰＥＧ−４のＢＩＦＳ［３］の中で使用されるQuantizationParameterノードとして動作する。
【００７０】
（適用可能な単純なタイプに対する制約）
本明細書の２．１節のコーデックに対する定義によれば、このコーデックはメモリ無しのコーデックであり、これは全ての極小の数値及び極小でない数値の単純なタイプに適用できる。そのＸＭＬスキーマの基本タイプは、フロート、ダブル又はデシマルである。
【００７１】
（コーデックの外部パラメータ）
線形量子化器のコーデックは、下記の３つの必須のパラメータである
−上記のnbits変数であるbitSizeと、
−上記のνmin変数であるminInclusiveと、
−上記のνmax変数であるmaxInclusiveと
を必要とする。
【００７２】
（コーデックのスキーマの定義）
線形量子化のコーデックは、抽象的なCodecTypeタイプ（２．１節を参照のこと）に基づいて、コーディングコンテキストのnamespaceのＵＲＬ xmlns:cc=http://www.mpeg7.org/2001/BiMCodingにおける補遺５の中で与えられたスキーマで定義されたタイプLinearQuantizerCodecTypeの新しいコーデックである。
【００７３】
（コード化（情報提供））
値νの数値データのリーフは、nbitsビットの符号のない整数νqにより下記の式のよう
にコード化される。
【数５】
【００７４】
（デコーディング）
nbitsビットでコード化された符号のない整数νqは、下記の式のように、
【数６】
としてデコードされるべきである。
【数７】
【００７５】
（実施例（情報提供））
補遺６で示された実施例は、記述における線形量子化器の定義を示す。
【００７６】
２．２．２ 統計的な圧縮
伝統的な損失のない統計的な圧縮アルゴリズムは、コーディングコンテキスト方法（２．１節を参照）の中で定義されたようなコーデックとして使用できる。この方法を用いて、どの記述のサブツリーの中でも、望ましい単純なタイプのデータリーフを効率的に圧縮できる。
このコーデックは、特に記述が多くの反復的な又は同様のストリングを含む場合には、ビットストリームの大きさを著しく減少させるために有用である。
【００７７】
（定義）
（Zip又はGZipなどの）伝統的な損失のない統計的な圧縮アルゴリズムをＢｉＭの中で用いて、記述の任意のリーフを圧縮することができる。
しかし、大抵の場合、データリーフが１０文字よりも少ない短いストリングの場合には、通常の統計的な圧縮アルゴリズムは大きなルックアヘッドバッファ（lookahead buffer）を必要とするため、このアルゴリズムの性能は良くない。
最適な圧縮比を実現するために、文書のリーフは圧縮する前に、小さいバッファにバッファする必要がある。次の節は、根本的な損失のない統計的な圧縮アルゴリズムに依存するそのようなバッファ付き統計的コーダ（a buffered statistical coder）を定義する。
【００７８】
（バッファ付き統計的コーダの定義）
バッファ付き統計的コーダは、一般的な下記の基本的な方法である、
−ストリームの圧縮又は解凍動作を初期化するinitialize_stream()と、
−コーダの現在の統計的なモデルをリセットするreset_model()と、
−入力の解凍されたバイトを取り、圧縮ストリームの中に入れるfeed_input_bytes()と、
−既に処理された入力バイトを圧縮し、対応する圧縮された出力バイトを出すことによって、圧縮ストリームをフラッシュするflush_output_bytes()と、
−指定された量の圧縮された入力バイトを取り、対応する解凍された出力バイトを出すことによってそれらをデコードするdecompress_input_bytes()と
を必ず含む根本的な統計的コーダに依存する。
バッファ付きコーデックは、bufferSizeのバイト長、すなわちバイトアレイバッファ（byte array buffer）のＦＩＦＯ構造を有する。
エンコーダ側から見ると、bufferSize値はフラッシングの前にエンコーダがどの位の入力バイトを処理できるかを示す。デコーダ側からすると、これは根本的な統計的コーダのＡＰＩを通してビットストリームをデコードするために必要な最小のバッファ寸法である。
このバッファはfillingLevel変数も有する。この変数は、バッファのバイトにおける実際の充填レベルを含む。
【００７９】
（統計的なコーダとしてのZLib ＡＰＩの使用）
GZip圧縮方式の中で使用されるZLibの公開ライブラリのＡＰＩ［４］は、文書リーフに対して統計的圧縮を行うための効率的で有用なＡＰＩを提供する。
【００８０】
ZLib ＡＰＩは、下記のマッピングを用いて前の一般的な方法を実行する。
−initialize_stream()は、Z_DEFAULT_COMPRESSIONの効率値のパラメータを用いて、ZLibのinflateInit()又はdeflateInit()機能によってマッピングすることができる。
−reset_model()は、ZLibのinflateEnd()又はdeflateEnd()コール及び次のinitialize_stream()コールを用いてマッピングすることができる。
−feed_input_bytes()は、Z_NO_FLUSHパラメータを用いてZLibのdeflate()方法によりマッピングすることができる。
−flush_output_bytes()は、Z_SYNC_FLUSHパラメータを用いてZLibのdeflate()方法によりマッピングすることができる。
−decompress_input_bytes()は、ZLibのdeflate()方法によりマッピングすることができる。
【００８１】
ZLibのバッファ付きコーデックは、［４］で定義されたように、Z_DEFAULT_COMPRESSIONの効率値を用いて初期化されるべきである。このことは、メモリのフットプリント（footprint）についての要求事項と圧縮効率との間の良いトレードオフになる。
【００８２】
（コンテキスト方法との統合：ZlibCodec）
この節では、コーディングコンテキスト方法の中で定義された、ZLib ＡＰＩに依存する、上記のバッファ付き統計的コーダの統合について説明する。
【００８３】
（適用可能な単純なタイプに対する制約）
２．１節のコーデックに対する定義によれば、このコーデックはコンテキスト式コーデックであり、これは全ての極小のストリングタイプ及び極小でないストリングタイプに適用できる。ZLibCodecは、［１］の中で説明したように、文書のリーフの根本をなす基本的なコード化に依存している。例えば、intリーフは３２ビットの符号のない整数によりコード化され、stringリーフはＵＴＦ−８のコード化により、float及びdoubleリーフはＩＥＥＥ７５４形式でコード化される。このため、ZLibCodecは、コード化されたリーフを圧縮できる。
【００８４】
（コーデックの外部パラメータ）
バッファ付きのZLibコーデックは、根本的なZLibの効率がZ_DEFAULT_COMPRESSIONに設定され、bufferSizeパラメータがデコーダ側からは必要とはされないため、どのような外部のパラメータも必要としない。
【００８５】
（コーデックのスキーマの定義）
このZLibコーデックは、抽象的なCodecTypeタイプ（２．１節を参照のこと）に基づいて、補遺７のコーディングコンテキストのnamespaceの中で説明されたスキーマによって定義されたZLibCodecTypeタイプの新しいコーデックである。
【００８６】
（コード化（情報提供））
コーデックの活性化又はインスタンシエーションにおいては、
−ＦＩＦＯのバッファ構造はクリアであると想定され、そのfillingLevelは０に設定される。
−グローバル変数referencable_chunkは０に初期化される。
このreferencable_chunkは、エンコーダが保持しなければならない参照可能なビットのチャンクを含むべきである。その理由は、その値がコード化工程の間に後で知られるからである。通信関数signal_reference_chunk_known()は、このチャンクが知られた場合には呼び出すことができる。
全てのゼロでないチャンクのバイトの大きさは、［１］で定義されたように、標準的な符号無しの無限の整数４＋１コーディング（infinite integer 4+1 coding）を用いて、flush_output_bytes()呼出しの間にチャンク自身の前に書き込まれるべきである。
入力リーフ（input leaf）は、その基本のタイプに関連したテキストのリーフのコード化された値である。このリーフのバイトの長さは、フィールドleaf.lengthによって与えられる。一例［１］を挙げれば、stringリーフは、ストリングのバイトの大きさが前に来る（無限整数のコーディング［１］を用いてコード化された）ＵＴＦ−８のコードであり、doubleリーフは、対応するＩＥＥＥ７５４規格の６４ビット値である。
【００８７】
下記のencode_leaf関数は、出力バイトのチャンク内のリーフをコード化することができる。
chunk encode_leaf(chunk leaf) [
while (leaf is not empty) [
if (fillingLevel + leaf.length < bufferSize) [
feed_input_bytes(leaf,leaf.length)
fillingLevel = fillingLevel + leaf.length
if (referencable_chunk is null) [
referencable_chunk = new chunk
return referencable_chunk
] else [
return nil_size_chunk
]
] else [
remaining_bytes = bufferSize - fillingLevel - leaf.length
feed_input_bytes(leaf,remaining_bytes)
referencable_chunk = flush_output_bytes()
signal_reference_chunk_known()
fillingLevel = 0
leaf = leaf.remove_beginning_bytes(remaining_bytes)
referencable_chunk = null
]
]
]
【００８８】
（デコーディング）
string_fifoをストリングＦＩＦＯとする。
下記の方法get()及びput()は、それぞれ、ＦＩＦＯから要素を取り出し、ＦＩＦＯに要素を置く。
ＦＩＦＯが空かどうかを知る方法はEmpty()信号である。
subをサブストリングを取り出す関数とする。
concatを連結関数とする。
getData()を、リーフからのde-gzipデータを保持するchar[]を戻す関数とする。
split(char[] , char sep, Fifo, char[] remainder)を各セパレータ「sep」において文字のアレイを分割し、この分割されたストリング要素をＦＩＦＯに保管し残りを戻す方法とする。
[
if (data==null) return;
int BEGIN=0;
for (int I=0;I<data.length;I++)
[
if (data[I]==sep)
[
char[] str= concat(remainder, sub(data,BEGIN,I));
put(string_fifo, str);
BEGIN=I+1;
]
]
if(BEGIN!=data.length)
[
//there's a remainder.
remainder = sub(data,BEGIN,data.length);
]
]
String decode()
[
if (isEmpty(string_fifo)
[
data = getData();
split(data,0x00,string_fifo,remainder);
]
return get(string_fifo);
]
初期化されたとき、string_fifoは空である。
コーデックの活性化又はインスタンシエーションにおいては、
−ＦＩＦＯの構造はクリアであると想定され、そのnumberOfLeavesは０に設定される。
−変数first_chunkは真に設定される。
セパレータのバイトを0x00とする。
下記のdecode_leaf関数は、ビットストリームからの圧縮されたリーフをデコードすることができる。
string decode_leaf() [
if (numberOfLeaves == 0) [
read_and_decompressed_byte()
numberOfLeaves = count_number_of_leave_in_buffer()
] else [
]
]
【００８９】
デコーディングは、下記により定義される。
１．ＦＩＦＯが空の場合には、
ａ．コード化データをデコードする。
ｂ．0x00により分離された全ての要素をＦＩＦＯの中にスタックする。
ｃ．最後の文字が0x00でない場合は、未完成のストリングを一時的に保管する。
ｄ．「last_element」が空でない場合は、それをＦＩＦＯ内の第１の要素の先頭に挿入する。
ｅ．このラウンドの未完成のストリングをlast_elementの中に入れる。
ｆ．第１の要素を取り除き戻す。
【００９０】
２．ＦＩＦＯが空でない場合には、第１の要素を取り除き戻す。
これは、「ＦＩＦＯは空ではない」及び「現在のリーフにはコード化されたデータはない」と言うのに等しい。
【００９１】
（実施例（情報提供））
補遺８で与えられた説明は、string及びanyURIタイプでマッピングされたZLibCodecTypeのコーデックを使用する場合の例である。
【００９２】
（結果（情報提供））
下記の図面は、記述（string及びanyURIのＸＭＬスキーマの基本のタイプから得られた記述）のテキストのリーフを圧縮するためにZLibCodecを使用する場合の性能を示す。bufferSize＝２５６バイトのバッファは、コード化工程の間に使用された。使用されたファイルは、ＭＰＥＧ−７のＭＤＳサブグループにより提供された。
【表７】
階層化ツリーのリーフの内容を圧縮するために、本発明に基づいて実行されたステップを、ここで手早く説明する。
【００９３】
ステップ１は、圧縮コード化技術をあるコンテントタイプに対応付ける工程から成る。例えば、線形の量子化を、浮動小数点の値に対応付けることができる。
【００９４】
ステップ２では、あるサブツリーが検討されたＸＭＬ文書の構造に対応する階層化ツリーの中で識別される。
【００９５】
ステップ３は、圧縮コード化技術を識別されたサブツリーに割り当てる工程から成る。
【００９６】
そして、ステップ４は、圧縮コード化技術を実行しているコーデックが起動されているかどうかを検査する工程から成る。起動されていない場合には、サブツリーのリーフの圧縮（ステップ５）は行われない。
【００９７】
起動されている場合には、本発明は、その内容が（ステップ１において）圧縮コード化技術に対応付けられたコンテントタイプであるような、サブツリーのリーフの内容の圧縮を実行する（ステップ６）。
【００９８】
［補遺１］
【表８】
【００９９】
［補遺２］
【表９Ａ】
【表９Ｂ】
【０１００】
［補遺３］
【表１０】
【０１０１】
［補遺４］
【表１１Ａ】
【表１１Ｂ】
【０１０２】
［補遺５］
【表１２】
【０１０３】
［補遺６］
【表１３】
【０１０４】
［補遺７］
【表１４】
【０１０５】
［補遺８］
【表１５Ａ】
【表１５Ｂ】
【０１０６】
［補遺９］
【表１６】
【図面の簡単な説明】
【０１０７】
【図１】コーディングコンテキストの概念を説明する図である。
【図２】ＢｉＭ技術に基づいてコーディングされた要素の構造を説明する図である。
【図３】階層化ツリーのリーフの内容を圧縮するために、本発明に基づいて実行される幾つかのステップを示す図である。
【特許請求の範囲】
【請求項１】
マルチメディア信号を記述する階層化ツリーを圧縮する方法であって、
該ツリーが、データタイプと呼ばれる少なくとも２つの明確な特徴を有するデータに関連付けることができ、ノードとリーフとを含み、
それぞれが前記データタイプの少なくとも１つに選択的に関連付けられる少なくとも２つの圧縮コード化技術によって、前記リーフの少なくとも幾つかに対してデータ圧縮を実行するものである方法。
【請求項２】
少なくとも１つのサブツリーを識別するステップと、該サブツリーに対して前記圧縮コード化技術の１つを割り当てるステップとを含む請求項１に記載の方法。
【請求項３】
前記圧縮コード化技術に関連したタイプのデータをもつ前記サブツリーのリーフに対してのみ、該サブツリーに割り当てられた前記圧縮コード化技術を実行するステップを含み、前記サブツリーの他のリーフはどのような圧縮コード化も受けることはないものである請求項２に記載の方法。
【請求項４】
前記圧縮コード化技術のパラメータ記述を実行する請求項１から請求項３のいずれかに記載の方法。
【請求項５】
前記ツリーの構造を圧縮するステップをさらに含む請求項１から請求項４のいずれかに記載の方法。
【請求項６】
前記ツリーがＭＰＥＧ７規格によるＢｉＭ（２進ＭＰＥＧ）タイプである請求項１から請求項５のいずれかに記載の方法。
【請求項７】
前記圧縮コード化技術の１つが線形の量子化を実行する請求項１から請求項６のいずれかに記載の方法。
【請求項８】
前記圧縮コード化技術の１つが統計的圧縮アルゴリズムを実行する請求項１から請求項７のいずれかに記載の方法。
【請求項９】
前記アルゴリズムがGZipタイプである請求項８に記載の方法。
【請求項１０】
前記アルゴリズムが少なくとも２つのリーフのデータに対応するデータの集合に対して同時に実行されるものである請求項８及び請求項９のいずれかに記載の方法。
【請求項１１】
前記ツリーがＸＭＬ（拡張マークアップ言語）タイプの文書の構造を示すものである請求項１から請求項１０のいずれかに記載の方法。
【請求項１２】
前記階層化ツリーをデコーディングする間に前記サブツリーをスキップできるようにする幾つかの情報を含む少なくとも１つのコーディングコンテキストを前記サブツリーに関連付けるステップをさらに含む請求項１から請求項１１のいずれかに記載の方法。
【請求項１３】
前記幾つかの情報が、
使用された圧縮コード化技術を示す１つの情報、及び／又は、
対応するサブツリーが圧縮されているかどうかを示す１つの情報、及び／又は、
対応するサブツリーがスキップ可能かどうかを示す１つの情報、及び／又は、
使用された圧縮コード化技術の少なくとも１つのパラメータが修正されているかどうかを示す１つの情報
を含むものである請求項１２に記載の方法。
【請求項１４】
請求項１から請求項１３のいずれかの方法に従って圧縮されたマルチメディア信号をデコーディングする方法。
【請求項１５】
前記信号によって送られたコード化コンテキストの情報に基づいて、現在のデコーディングコンテキストをリフレッシュするステップを実行する請求項１４に記載の方法。
【請求項１６】
前記現在のコンテキストが少なくとも１つのデータタイプを定義し、該データタイプのデータを含むリーフに対して該データタイプに関連した圧縮デコーディング技術を実行するステップを含む請求項１５に記載の方法。
【請求項１７】
請求項１から請求項１３のいずれかの方法によって生成された信号。
【請求項１】
マルチメディア信号を記述する階層化ツリーを圧縮する方法であって、
該ツリーが、データタイプと呼ばれる少なくとも２つの明確な特徴を有するデータに関連付けることができ、ノードとリーフとを含み、
それぞれが前記データタイプの少なくとも１つに選択的に関連付けられる少なくとも２つの圧縮コード化技術によって、前記リーフの少なくとも幾つかに対してデータ圧縮を実行するものである方法。
【請求項２】
少なくとも１つのサブツリーを識別するステップと、該サブツリーに対して前記圧縮コード化技術の１つを割り当てるステップとを含む請求項１に記載の方法。
【請求項３】
前記圧縮コード化技術に関連したタイプのデータをもつ前記サブツリーのリーフに対してのみ、該サブツリーに割り当てられた前記圧縮コード化技術を実行するステップを含み、前記サブツリーの他のリーフはどのような圧縮コード化も受けることはないものである請求項２に記載の方法。
【請求項４】
前記圧縮コード化技術のパラメータ記述を実行する請求項１から請求項３のいずれかに記載の方法。
【請求項５】
前記ツリーの構造を圧縮するステップをさらに含む請求項１から請求項４のいずれかに記載の方法。
【請求項６】
前記ツリーがＭＰＥＧ７規格によるＢｉＭ（２進ＭＰＥＧ）タイプである請求項１から請求項５のいずれかに記載の方法。
【請求項７】
前記圧縮コード化技術の１つが線形の量子化を実行する請求項１から請求項６のいずれかに記載の方法。
【請求項８】
前記圧縮コード化技術の１つが統計的圧縮アルゴリズムを実行する請求項１から請求項７のいずれかに記載の方法。
【請求項９】
前記アルゴリズムがGZipタイプである請求項８に記載の方法。
【請求項１０】
前記アルゴリズムが少なくとも２つのリーフのデータに対応するデータの集合に対して同時に実行されるものである請求項８及び請求項９のいずれかに記載の方法。
【請求項１１】
前記ツリーがＸＭＬ（拡張マークアップ言語）タイプの文書の構造を示すものである請求項１から請求項１０のいずれかに記載の方法。
【請求項１２】
前記階層化ツリーをデコーディングする間に前記サブツリーをスキップできるようにする幾つかの情報を含む少なくとも１つのコーディングコンテキストを前記サブツリーに関連付けるステップをさらに含む請求項１から請求項１１のいずれかに記載の方法。
【請求項１３】
前記幾つかの情報が、
使用された圧縮コード化技術を示す１つの情報、及び／又は、
対応するサブツリーが圧縮されているかどうかを示す１つの情報、及び／又は、
対応するサブツリーがスキップ可能かどうかを示す１つの情報、及び／又は、
使用された圧縮コード化技術の少なくとも１つのパラメータが修正されているかどうかを示す１つの情報
を含むものである請求項１２に記載の方法。
【請求項１４】
請求項１から請求項１３のいずれかの方法に従って圧縮されたマルチメディア信号をデコーディングする方法。
【請求項１５】
前記信号によって送られたコード化コンテキストの情報に基づいて、現在のデコーディングコンテキストをリフレッシュするステップを実行する請求項１４に記載の方法。
【請求項１６】
前記現在のコンテキストが少なくとも１つのデータタイプを定義し、該データタイプのデータを含むリーフに対して該データタイプに関連した圧縮デコーディング技術を実行するステップを含む請求項１５に記載の方法。
【請求項１７】
請求項１から請求項１３のいずれかの方法によって生成された信号。
【図１】
【図２】
【図３】
【図２】
【図３】
【公開番号】特開２００９−４３２６７（Ｐ２００９−４３２６７Ａ）
【公開日】平成２１年２月２６日（２００９．２．２６）
【国際特許分類】
【出願番号】特願２００８−２１５４８０（Ｐ２００８−２１５４８０）
【出願日】平成２０年８月２５日（２００８．８．２５）
【分割の表示】特願２００３−５１３２４８（Ｐ２００３−５１３２４８）の分割
【原出願日】平成１４年７月１２日（２００２．７．１２）
【出願人】（５９１０３４１５４）フランス テレコム (290)
【出願人】（５０４０１５２６３）
【出願人】（５０４０１４６９１）
【Ｆターム（参考）】
【公開日】平成２１年２月２６日（２００９．２．２６）
【国際特許分類】
【出願日】平成２０年８月２５日（２００８．８．２５）
【分割の表示】特願２００３−５１３２４８（Ｐ２００３−５１３２４８）の分割
【原出願日】平成１４年７月１２日（２００２．７．１２）
【出願人】（５９１０３４１５４）フランス テレコム (290)
【出願人】（５０４０１５２６３）
【出願人】（５０４０１４６９１）
【Ｆターム（参考）】
[ Back to top ]