(57)【要約】構造化フラグメントグループに対する符号化方法において、構造スキーマのコンポーネントに対して実行可能であり、フラグメント構造及び情報エレメントの値を表わす制御コードをストリームに挿入する指示を含む指示シーケンスを取得するための、構造スキーマ分析ステップと、制御コード値及び情報エレメント値を有するバイナリ符号化コンテナが得られるよう、フラグメントに対し指示シーケンスを実行するステップと、構造ブロック５３への制御コード挿入ステップと、情報エレメントの値をタイプ毎にデータブロック５４に分配するステップと、制御コード及び情報エレメント値の、構造ブロック及びデータブロックにおける位置をポインタテーブル５２に蓄積するステップと、内容に適した圧縮アルゴリズムをデータブロックに適用するステップと、バイナリ符号化コンテナになるようポインタテーブル及びデータブロックの内容を連結するステップとを備える。【選択図】図４
2007516514.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも２つの構造化フラグメントを備え、
各々の前記フラグメントは、互いに入れ子になっており情報タイプあるいは情報サブタイプに関連付けられた複数の情報エレメントを有しており、かつ文書のツリー型構造を定義し入れ子になった複数の構造コンポーネントを有する少なくとも１つの構造スキーマと関連付けられており、
前記フラグメントにおける情報エレメントのタイプあるいはサブタイプが、前記構造スキーマのコンポーネントによって定義されるグループ（５）に対する符号化方法において、
前記構造スキーマの各々のコンポーネントに対して実行可能であり、前記フラグメントの構造および情報エレメントの値あるいはコンポーネントインストラクションシーケンスコールコードを表わすコントロールコードをビットストリームに挿入するインストラクションと、コントロールコードに応じてシーケンスの実行を制御するインストラクションと、を含むインストラクションシーケンス（２）を取得するために、構造スキーマ（１）を分析するステップと、
コントロールコード値およびフラグメントの情報エレメント値を有するバイナリ符号化コンテナ（６）が得られるよう、グループ（５）の構造化された前記フラグメントに対して前記インストラクションシーケンスを実行するステップと、を備え、前記符号化方法は、さらに、
フラグメントのコントロールコードを構造ブロック（５３）に挿入するステップと、
予め定められた情報エレメントタイプあるいはサブタイプを有するフラグメントの情報エレメントの値を、情報エレメントのエレメントタイプに応じて、各エレメントタイプあるいはサブタイプごとに、少なくとも１つのデータブロック（５４ｉ）に分配するステップと、
フラグメントのコントロールコードおよび情報エレメント値の、構造ブロックおよびデータブロックにおける位置を、各々のフラグメントに対してポインタテーブル（５２）に蓄積するステップと、
前記データブロックに、前記データブロックの内容に適した圧縮アルゴリズムを適用するステップと、
前記ポインタテーブル、前記構造ブロックおよび前記データブロックの内容を、バイナリ符号化コンテナストリームになるよう連結するステップとを備えることを特徴とする符号化方法。
【請求項２】
前記ポインタテーブル（５２）および前記構造ブロック（５３）の内容が、前記バイナリ符号化コンテナストリーム（６）に挿入される前に、適切な圧縮アルゴリズム（１２）によってそれぞれ圧縮されることを特徴とする請求項１に記載の符号化方法。
【請求項３】
前記ポインタテーブル（５２）、前記構造ブロック（５３）および前記データブロック（５４ｉ）を有する少なくとも２つのエレメントが、前記バイナリ符号化コンテナストリーム（６）に挿入される前に、合わせて圧縮されることを特徴とする請求項１又は２に記載の符号化方法。
【請求項４】
前記データブロック（５４ｉ）の１つが、前記グループ（５）のフラグメントに含まれかつ予め定義されたストリングサブタイプに属するサブタイプを含むすべてのストリングデータを有するストリングデータブロック（５４ｉ）により構成されており、
前記ストリングデータブロック（５４ｉ）は、バイナリ符号化コンテナストリーム（６）に挿入される前に、前記ポインタテーブル（５２）および前記構造ブロック（５３）とともに圧縮されることを特徴とする請求項１又は３に記載の符号化方法。
【請求項５】
前記グループ（５）に対応する前記ポインタテーブル（５２）、前記構造ブロック（５３）および前記ストリングデータブロック（５４ｉ）の内容に適用される前記圧縮アルゴリズムが、ＺＬＩＢであることを特徴とする請求項４に記載の符号化方法。
【請求項６】
グループ（５）のフラグメントにおけるデータブロック（５４ｉ）内の連続する飛び越し可能なエレメント（８２）のオフセット値（８１、８１’）が、構造ブロック（５３）内に挿入されており、前記飛び越し可能なエレメント（８２）の最後を追っていることを特徴とする請求項１乃至５に記載の符号化方法。
【請求項７】
少なくとも２つの構造化フラグメントがグループ化されており、各々の前記フラグメントが、互いに入れ子になっており情報タイプあるいは情報サブタイプと関連付けられた情報エレメントをそれぞれ有しているバイナリ符号化コンテナ（６）を復号化する方法であり、
各々の前記フラグメントは、文書のツリー型構造を定義し入れ子になった複数の構造コンポーネントを有する少なくとも１つの構造スキーマと関連付けられており、
フラグメントにおける情報エレメントのタイプあるいはサブタイプが、前記構造スキーマのコンポーネントによって定義される復号化方法において、
前記構造スキーマの各々のコンポーネントに対して実行可能であり、バイナリ符号化コンテナのコントロールコード、情報エレメントの値、あるいはコールコードを読込むためのインストラクションと、コントロールコードに応じてシーケンスの実行を制御するためのインストラクションと、を含むインストラクションシーケンス（２）を取得するために、構造スキーマを分析するステップと、
少なくとも元のフラグメント（５）のグループと同等の構造を有するグループ（５’）のフラグメントを復元するために、前記バイナリ符号化コンテナ（６）に対して前記インストラクションシーケンスを実行するステップと、を備え、バイナリ符号化コンテナ（６）が、
すべての前記フラグメントのコントロールコードを含む構造ブロック（５３）と、
すべてのフラグメントに対する情報エレメントの値を含み、かつ該エレメントが予め定義されたタイプあるいはサブタイプのセットに属している、少なくとも１つのデータブロック（５４ｉ）と、
フラグメントのコントロールコードおよび情報エレメント値の、構造ブロックおよびデータブロックにおける位置を、各々のフラグメントに対して示すポインタテーブル（５２）と、を備えることを特徴とし、前記復号化方法が、さらに、
前記ポインタテーブル、前記構造ブロックおよび前記データブロックを読込み、復元されたフラグメントのグループ（５’）からなるフラグメントを形成するよう、ポインタテーブルを用いて、構造ブロックおよびデータブロック内のデータを組み立てるステップを備えることを特徴とする復号化方法。
【請求項８】
前記ポインタテーブル（５２）、前記構造ブロック（５３）または、いずれか１つのデータブロック（５４ｉ）のうちの少なくとも１つに適切な解凍アルゴリズムを適用することを特徴とする請求項７に記載の復号化方法。
【請求項９】
いずれか１つのデータブロック（５４ｉ）が、バイナリ符号化コンテナ（６）のフラグメント内にありかつ予め定義されたストリングサブタイプのセットに属するストリングサブタイプを有するすべてのストリングデータを含んでおり、
前記ポインタテーブル（５２）が読込まれる前に、ストリングデータブロックが、ポインタテーブル（５２）および構造ブロック（５３）とともに解凍されることを特徴とする請求項７又は８に記載の復号化方法。
【請求項１０】
前記ポインタテーブル（５２）、前記構造ブロック（５３）および前記バイナリ符号化コンテナ（６）のすべてのストリングデータを含む前記データブロック（５４ｉ）の内容に適用される解凍アルゴリズムが、ＺＬＩＢであることを特徴とする請求項９に記載の復号化方法。
【請求項１１】
構造ブロック（５３）が、バイナリ符号化コンテナ（６）のフラグメント内の連続する飛び越し可能なエレメント（８２）の、データブロック（５４ｉ）におけるオフセット値（８１、８１’）を備え、オフセット値（８１、８１’）は、前記構造ブロック内の前記飛び越し可能なエレメントの後ろを追っており、
前記復号化方法が、さらに、前記オフセットを読込み、データブロック（５４ｉ）の適切な位置を読込むよう再同期をするために用いるステップを備えることを特徴とする請求項７乃至１０に記載の復号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピューターシステムに関するものである。より詳しくは、ＳＧＭＬ（Ｓｔａｎｄａｒｄ  Ｇｅｎｅｒａｌｉｚｅｄ  Ｍａｒｋｕｐ  Ｌａｎｇｕａｇｅ）やＸＭＬ（Ｅｘｔｅｎｓｉｂｌｅ  Ｍａｒｋｕｐ  Ｌａｎｇｕａｇｅ）などの汎用のマークアップ言語に適合する文書記述を用いた構造化文書を圧縮する方法およびシステムに関するものである。
【０００２】
本発明は、より詳しくは、デジタルビデオプログラムを記載するメタデータおよびモバイルサービスに適用されるものである。
【背景技術】
【０００３】
近年、コンピュータネットワークは、主要な通信媒体となった。コンピュータは、共有のネットワークに接続され、オペレーティングシステムは、アプリケーションソフトに、メッセージの交換を容易に行わせ、インターネット基盤は、コンピュータ同士が対話者を検索するようにし、アプリケーションソフトは、コンピュータ同士が同期するよう複雑なアルゴリズムを利用するようになっている。
【０００４】
このような相互運用の状況において、汎用のマークアップ言語は、文書処理を行うための解決策となる。ここで、文書構造は、文書の取り扱いに重要な役割を果たす。文書の書式設定、印刷あるいは索引付けは、この文書構造に従って行われる。
【０００５】
ＳＧＭＬは、ドキュメントプレゼンテーションを、文書構造と内容とを容易に分離することを目的として開発された。ＸＭＬは、構造を符号化できるので、文書への適用とは異なる目的を有する分野からも注目されている。ＸＭＬの利用者は、文書処理以外には、電子商取引、データベースおよび知識表現の分野などに広がっている。
【０００６】
ＸＭＬや、より汎用的なマークアップ言語は、文書（メタデータ）を記述し構造化するために広く用いられている。構造化された文書は、ツリーのような構造によって互いに入れ子になった複数の情報エレメントを備えている。情報エレメントは、タグによって互いに識別され分離されており、タグは、情報エレメントのエレメントタイプを識別するようになっている。
【０００７】
構造化文書は、一般に、文書全体を代表する第１の情報エレメントあるいはベースエレメントを備えており、文書の最初と最後に記されたタグによって識別される。この第１のエレメントは、文書パラグラフなどの複数の情報サブエレメントを備えており、各々の情報サブエレメントは、このエレメントの最初と最後に記されたタグによって識別される。タグは、情報エレメントの少なくとも１つ以上の特性を明記したタグ属性と関連付けられていてもよい。
【０００８】
タグ内容は、ディスプレーに表示されたり、利用者により操作されるようになっている。タグ内容は、タグの種類によりオプションあるいは必須であり、追加的な入れ子の情報サブエレメントを有していてもよい。この情報サブエレメントは、タグによって区切られており、内容や属性を有している。
【０００９】
構造化文書は、スキーマと関連付けられていてもよく、スキーマは、構造化文書が“有効”であると認識されるために確認するためのルールを示すようになっている。スキーマは、さらにデフォルト値の情報を含んでおり、エレメントおよび属性のタイプと、タイプの階層を定義するようになっている。受信した文書は、スキーマに適合しておりその結果意図された意味を有していることを有効性により保証される。
【００１０】
スキーマは、さらに各々の記述アイテム（情報エレメントあるいは属性）の種類、すなわちタイプを定義するようになっている。
【００１１】
ＸＭＬ標準は、ＸＭＬスキーマ言語を有しており、類似の構造を有するＸＭＬ文書のクラスに対する文法を特定するようになっている。各々のエレメントタイプおよび属性は、ＸＭＬネームスペースに属するネームを有している。
【００１２】
しかしながら、ＸＭＬは冗長な言語であるため、処理をする際に非効率であり、送信するためにコストがかかる。このため、ＩＳＯ／ＩＥＣ１５９３８−１、より詳しくはＭＰＥＧ−７（Ｍｏｖｉｎｇ  Ｐｉｃｔｕｒｅ  Ｅｘｐｅｒｔ  Ｇｒｏｕｐ）が、構造化文書に対する符号化（圧縮）および復号化の方法およびバイナリフォーマットを提案している。この標準化は、より具体的には、マルチメディアにおけるメタデータなど、より構造化されたデータを扱うようになっている。
【００１３】
本出願人により出願された米国特許出願公開第２００４／００１３３０７号明細書および米国特許出願公開第２００４／００５４６９２号明細書において開示されているように、この方法は、スキーマ分析段階を有することによって、圧縮効率を高めるようになっている。
【００１４】
この段階において、内部テーブルは、バイナリコードを各々のＸＭＬエレメント、タイプおよび属性と結びつけるよう計算する。この方法においては、符号器と、この符号器に対応する復号器が、同一のスキーマを完全に認識することを必要とする。
【００１５】
ディジタルビデオ送信などいくつかのアプリケーションでは、メタデータは、コンテナの形状でビデオストリームによって送信される。コンテナは、小さいサイズを有するデータフラグメントをグループ化したものである。
【００１６】
この場合、ストリングデータ上では特に冗長が限られるため、ＺＬＩＢなどストリングの冗長を利用するストリング圧縮アルゴリズムは、時としては期待される程効率的ではない。
【発明の開示】
【発明が解決しようとする課題】
【００１７】
本発明は、フラグメント形態の文書がコンテナにグループ化されたときの圧縮効率を改善することを目的とする。
【課題を解決するための手段】
【００１８】
上記の問題を解決するために、本発明に係る符号化方法は、少なくとも２つの構造化フラグメントを備え、各々の前記フラグメントは、互いに入れ子になっており情報タイプあるいは情報サブタイプに関連付けられた複数の情報エレメントを有しており、かつ文書のツリー型構造を定義し入れ子になった複数の構造コンポーネントを有する少なくとも１つの構造スキーマと関連付けられており、前記フラグメントにおける情報エレメントのタイプあるいはサブタイプが、前記構造スキーマのコンポーネントによって定義されるグループに対する符号化方法において、前記構造スキーマの各々のコンポーネントに対して実行可能であり、前記フラグメントの構造および情報エレメントの値あるいはコンポーネントインストラクションシーケンスコールコードを表わすコントロールコードをビットストリームに挿入するインストラクションと、コントロールコードに応じてシーケンスの実行を制御するインストラクションと、を含むインストラクションシーケンスを取得するために、構造スキーマを分析するステップと、コントロールコード値およびフラグメントの情報エレメント値を有するバイナリ符号化コンテナが得られるよう、グループの構造化された前記フラグメントに対して前記インストラクションシーケンスを実行するステップと、を備えている。
【００１９】
本発明に係る符号化方法は、さらに、フラグメントのコントロールコードを構造ブロックに挿入するステップと、予め定められた情報エレメントタイプあるいはサブタイプを有するフラグメントの情報エレメントの値を、情報エレメントのエレメントタイプに応じて、各エレメントタイプあるいはサブタイプごとに、少なくとも１つのデータブロックに分配するステップと、フラグメントのコントロールコードおよび情報エレメント値の、構造ブロックおよびデータブロックにおける位置を、各々のフラグメントに対してポインタテーブルに蓄積するステップと、データブロックに、前記データブロックの内容に適した圧縮アルゴリズムを適用するステップと、前記ポインタテーブル、前記構造ブロックおよび前記データブロックの内容を、バイナリ符号化コンテナストリームになるよう連結するステップとを備えることを特徴とする。
【００２０】
本発明に係る符号化方法は、さらに、前記ポインタテーブルおよび前記構造ブロックの内容が、前記バイナリ符号化コンテナストリームに挿入される前に、適切な圧縮アルゴリズムによってそれぞれ圧縮されることを特徴とする。
【００２１】
本発明に係る符号化方法は、さらに、前記ポインタテーブル、前記構造ブロックおよび前記データブロックを有する少なくとも２つのエレメントが、前記バイナリ符号化コンテナストリームに挿入される前に、合わせて圧縮されることを特徴とする。
【００２２】
本発明に係る符号化方法は、さらに、前記データブロックの１つが、前記グループのフラグメントに含まれかつ予め定義されたストリングサブタイプに属するサブタイプを含むすべてのストリングデータを有するストリングデータブロック（５４ｉ）により構成されており、前記ストリングデータブロックは、バイナリ符号化コンテナストリームに挿入される前に、前記ポインタテーブルおよび前記構造ブロックとともに圧縮されることを特徴とする。
【００２３】
本発明に係る符号化方法は、さらに、前記グループに対応する前記ポインタテーブル、前記構造ブロックおよび前記ストリングデータブロックの内容に適用される前記圧縮アルゴリズムが、ＺＬＩＢであることを特徴とする。
【００２４】
本発明に係る符号化方法は、さらに、グループのフラグメントにおけるデータブロック内の連続する飛び越し可能なエレメントのオフセット値が、構造ブロック内に挿入されており、前記飛び越し可能なエレメントの最後を追っていることを特徴とする。
【００２５】
本発明に係る復号化方法は、少なくとも２つの構造化フラグメントがグループ化されており、各々の前記フラグメントが、互いに入れ子になっており情報タイプあるいは情報サブタイプと関連付けられた情報エレメントをそれぞれ有しているバイナリ符号化コンテナ（６）を復号化する方法であり、各々の前記フラグメントは、文書のツリー型構造を定義し入れ子になった複数の構造コンポーネントを有する少なくとも１つの構造スキーマと関連付けられており、フラグメントにおける情報エレメントのタイプあるいはサブタイプが、前記構造スキーマのコンポーネントによって定義される復号化方法において、前記構造スキーマの各々のコンポーネントに対して実行可能であり、バイナリ符号化コンテナのコントロールコード、情報エレメントの値、あるいはコールコードを読込むためのインストラクションと、コントロールコードに応じてシーケンスの実行を制御するためのインストラクションと、を含むインストラクションシーケンスを取得するために、構造スキーマを分析するステップと、少なくとも元のフラグメントのグループと同等の構造を有するグループのフラグメントを復元するために、前記バイナリ符号化コンテナに対して前記インストラクションシーケンスを実行するステップと、を備えることを特徴とする。
【００２６】
本発明に係る復号化方法は、さらに、バイナリ符号化コンテナが、すべての前記フラグメントのコントロールコードを含む構造ブロックと、すべてのフラグメントに対する情報エレメントの値を含み、かつ該エレメントが予め定義されたタイプあるいはサブタイプのセットに属している、少なくとも１つのデータブロックと、フラグメントのコントロールコードおよび情報エレメント値の、構造ブロックおよびデータブロックにおける位置を、各々のフラグメントに対して示すポインタテーブルと、を備えることを特徴とし、前記復号化方法が、さらに、前記ポインタテーブル、前記構造ブロックおよび前記データブロックを読込み、復元されたフラグメントのグループからなるフラグメントを形成するよう、ポインタテーブルを用いて、構造ブロックおよびデータブロック内のデータを組み立てるステップを備えることを特徴とする。
【００２７】
本発明に係る復号化方法は、さらに、前記ポインタテーブル、前記構造ブロックまたは、いずれか１つのデータブロックのうちの少なくとも１つに適切な解凍アルゴリズムを適用することを特徴とする。
【００２８】
本発明に係る復号化方法は、さらに、いずれか１つのデータブロックが、バイナリ符号化コンテナのフラグメント内にありかつ予め定義されたストリングサブタイプのセットに属するストリングサブタイプを有するすべてのストリングデータを含んでおり、前記ポインタテーブルが読込まれる前に、ストリングデータブロックが、ポインタテーブルおよび構造ブロックとともに解凍されることを特徴とする。
【００２９】
本発明に係る復号化方法は、さらに、前記ポインタテーブル、前記構造ブロックおよび前記バイナリ符号化コンテナのすべてのストリングデータを含む前記データブロックの内容に適用される解凍アルゴリズムが、ＺＬＩＢであることを特徴とする。
【００３０】
本発明に係る復号化方法は、さらに、構造ブロックが、バイナリ符号化コンテナのフラグメント内の連続する飛び越し可能なエレメントの、データブロックにおけるオフセット値を備え、オフセット値は、前記構造ブロック内の前記飛び越し可能なエレメントの後ろを追っており、前記復号化方法が、さらに、前記オフセットを読込み、データブロックの適切な位置を読込むよう再同期をするために用いるステップを備えることを特徴とする。
【００３１】
本発明に係る符号化（圧縮）方法および復号化（解凍）方法を、図面を参照しながら以下詳細に説明する。
【発明を実施するための最良の形態】
【００３２】
以下、本発明に係る圧縮方法および解凍方法について説明する。
【００３３】
本発明に係る圧縮方法は、図１に示すように、複数の構造化された文書あるいはフラグメントにより構成されたグループ５を取り扱うようになっており、各々のフラグメントは、フラグメントの構造を定義するための構造スキーマ１と関連付けられている。このようなフラグメントは、例えば、構造化されたビデオプログラムのメタデータにより構成されており、ビデオストリームに埋め込まれるようになっている。
【００３４】
本実施の形態の圧縮方法に係るコンピレーション１０の段階において、複数のフラグメントにより構成されるグループ内のフラグメントに対するスキーマは、米国特許出願公開第２００４／００５４６９２号明細書において開示された方法に従ってコンパイルされ、構造スキーマの各々のコンポーネントに対する実行可能なインストラクションシーケンス２が得られる。
【００３５】
構造スキーマの各々のコンポーネントに対するこれらのインストラクションシーケンス２は、情報エレメントのコントロールコードおよび値やコンポーネントインストラクションシーケンスコールコードを挿入するためのインストラクションと、コントロールコード値に応じてシーケンスの実行を制御するためのインストラクションとを備えている。
【００３６】
構造スキーマのコンピレーションは、スキーマ内における単一の予め定められたオーダーのコンポーネントを得るための正規化ステップと、スキーマの構造コンポーネントの入れ子の数を減らすことによる最適化および平易化ステップとを含んでいる。
【００３７】
次の符号化段階１１においては、インストラクションシーケンス２がグループ５内の構造フラグメントに対して実行され、圧縮されたグループ５のフラグメント内の構造情報を含むバイナリストリームが取得されるようになっている。また、バイナリストリームには、基本情報エレメントの値が挿入されている。ここで、基本情報エレメントは、サブエレメントに分解されていない。
【００３８】
基本情報エレメントの値の少なくともいくつかは、バイナリストリームに挿入される前に、圧縮アルゴリズム１２によってそれぞれ処理される。圧縮アルゴリズム１２は、基本情報エレメントの情報タイプに適したものが選ばれる。
【００３９】
符号化段階１１においては、グループ５が、縮小されたバイナリ符号化コンテナ６に変換される。図２は、符号化段階１１を詳細に説明するための模式図である。図２において、バイナリシーケンス（インストラクションシーケンス）２は、まずステップ２１においてグループ５のフラグメントに対して実行され、バイナリストリーム３１が取得される。バイナリストリーム３１は、バイナリデータ形式で文書構造を有しており、グループ５のフラグメントに含まれる基本情報エレメントの値が挿入されている。
【００４０】
次に、ステップ２２において、バイナリストリーム３１が読込まれ、複数のバッファに分配される。複数のバッファは、バイナリ構造シーケンスを取得する第１のバッファ３３と、各々の情報エレメントタイプあるいはサブタイプに応じて基本情報エレメントの値が分配されるいくつかのバッファ３４１、３４２、・・・３４ｉとによって構成されている。
【００４１】
各々のバッファ３４ｉは、情報エレメントタイプを有するデータを取得する。情報エレメントタイプは、グループ５のフラグメントに対する構造スキーマ１内に予め定義されたセットのタイプあるいはサブタイプに属している。
【００４２】
図３は、バイナリ構造データ４１（白のエリア）を含み、ストリングタイプなど他のタイプのデータ４２（ハッチされたエリア）が挿入されたバイナリストリーム３１を示している。
【００４３】
分配の工程において、バイナリ構造データは第１のバッファ３３に挿入され、データ４２は、バッファ３４１に挿入される。この分配の工程において、各々のフラグメントに対するポインタのセットが、ポインタテーブル３２に記憶される。各々のポインタセットは、各々のバッファ３３、３４１、３４２・・・において、フラグメントのデータがメモリ位置のどこから蓄積されたかを参照するポインタを備えている。
【００４４】
各々のポインタは、フラグメントデータの最初のメモリ位置の、バッファの始点に対するゼロベースのバイト数によるオフセットと一致している。
【００４５】
ここで、ステップ２１およびステップ２２は、バイナリストリームを生成せずに同時に行われてもよく、この場合には、インストラクションシーケンスが実行されるにしたがって、データがバッファ３３、３４ｉに分配される。
【００４６】
次に、ステップ２３において、ポインタテーブル３２および各々のバッファ３３、３４ｉの内容に対し、圧縮アルゴリズム１２がそれぞれ適用される。これらの圧縮アルゴリズム１２は、ポインタテーブルやバッファに含まれるデータのタイプに応じて選択される。
【００４７】
ポインタテーブル３２、バイナリデータバッファ（第１のバッファ）３３およびストリングを含むバッファ３４ｉは、ＺＬＩＢアルゴリズムによって一括して圧縮されると好適である。
【００４８】
ステップ２３およびステップ２４は、どちらを先に行ってもよく、また、部分的に数回繰り返してもよい。実行する圧縮モジュールの選択と、圧縮パラメータのうち少なくとも一方は、ステップ２１の工程で抽出されたパラメータに応じて決定してもよい。
【００４９】
ポインタテーブル３２、バイナリデータバッファ３３および各バッファ３４ｉの圧縮された内容は、ステップ２４において符号化バイナリストリームになるよう連結され、符号化バイナリストリームの先頭にコンテナヘッダが付加される。これにより、図４に示すように、バイナリ符号化コンテナ６が生成される。バイナリ符号化コンテナ６は、コンテナヘッダ５１と、圧縮されたポインタテーブル３２の内容を含むカプセル化構造５２と、バイナリデータバッファ３３の圧縮した内容を含む構造データブロック５３と、バッファ３４ｉのそれぞれ圧縮した内容を含む複数のデータブロックとを備えている。
【００５０】
図４に示す例においては、バイナリ符号化コンテナ６は、バッファ３４１の圧縮された内容を含むストリングデータブロック５４１を備えている。
【００５１】
カプセル化構造５２は、第１のフラグメントおよび第２のフラグメントに対するポインタ５５、５６を備えている。ポインタ５５は、構造データブロック５３内における第１のフラグメントの構造データ５７に対するポインタを備え、また、ストリングデータブロック５４１内における第１のフラグメントのストリングデータ５９に対するポインタを備えている。
【００５２】
同様に、ポインタ５６は、構造データブロック５３内における第２のフラグメントの構造データ５８に対するポインタを備え、また、ストリングデータブロック５４１内における第２のフラグメントのストリングデータ６０に対するポインタを備えている。
【００５３】
コンテナヘッダ５１は、バイナリ符号化コンテナ６の主要部に対するポインタを備え、バイナリ符号化コンテナ６内におけるカプセル化構造５２およびデータブロック５３、５４ｉの位置を示すようになっている。
【００５４】
図５は、本発明に係る復号化方法を示したものである。
【００５５】
この復号化方法は、復号化段階１１’を備えており、インストラクションシーケンス２’および解凍アルゴリズム１２’がバイナリ符号化コンテナ６に対して実行され、復号化されたフラグメントのグループ５’が生成される。
【００５６】
インストラクションシーケンス２’は、バイナリ符号化コンテナ６に含まれるフラグメントに対する構造スキーマから取得される。これらのインストラクションシーケンス２は、図１に示す符号化方法に用いられたものに対応しており、挿入インストラクションが読込みインストラクションに置き換わったものである。
【００５７】
図６に詳細を示すように、復号化段階１１’は、ステップ６１を備えており、バイナリ符号化コンテナ６が読込まれる。また、コンテナヘッダ５１内の情報を用いて、カプセル化構造５２、構造データブロック５３およびストリングデータブロック５４が、ポインタテーブル７２、構造バイナリデータバッファ７３、データバッファ７４１、７４２、・・・７４ｉに同じタイプのデータごとにそれぞれ分配される。
【００５８】
次に、ステップ６２において、ポインタテーブル７２およびバッファ７３、７４ｉに含まれるバイナリストリームが、適切な解凍アルゴリズム１２’によって解凍される。
【００５９】
ステップ６１および６２は、同時に行われてもよく、この場合には、符号化コンテナの後半部が読込まれているときに、解凍アルゴリズムがバイナリ符号化コンテナに適用され、ポインタテーブル７２やバッファ７３、７４ｉに分配される。ステップ６１と６２とは、どちらを先に行ってもよく、部分的に繰り返して行ってもよい。
【００６０】
次に、ステップ６３において、ポインタテーブル７２と、バッファ７３、７４ｉとが読込まれ、コンテナの各々のフラグメントを含むバイナリストリーム７５が再び組み立てられる。
【００６１】
次に、バイナリストリーム７５に含まれるバイナリ構造データが、フラグメントに対するスキーマ１から生成されたインストラクションシーケンス２’を用いて復号化される。これにより、復号化されたフラグメント５’のグループが生成される（ステップ６４）。
【００６２】
ステップ６３および６４は、同時に行われてもよい。この場合には、バッファ７４ｉに含まれるデータを含むフラグメントが組み立てられる前に、構造データバッファ７３の内容が復号化される。
【００６３】
このような構成により、本発明の符号化方法は、フラグメント間のデータの冗長に対して統計的な圧縮アルゴリズムを利用できるので、コンテナに対する全般的な圧縮効率を改善することができる。
【００６４】
また、本発明の符号化方法は、圧縮アルゴリズムがフラグメント内に対して適用されるのではないため、圧縮アルゴリズムの実行を簡単化し、互換性を高めることができる。
【００６５】
また、それぞれのフラグメントに含まれる同じタイプのバイトが並ぶため、バイナリストリームの構造部分の圧縮を大幅に改善することができる。さらに、コンテナを復号化することなく、コンテナ内のストリングの検索を容易に行うことができる。
【００６６】
図７および図８は、新しいバージョンの構造スキーマをサポートしない復号器が、バイナリ符号化ストリームにおいて認識しない部分をスキップできるようにし、スキーマ互換性をサポートする方法を示したものである。スキーマ互換性に関するより詳細な情報は、米国特許出願公開第２００４／００６８６９６号明細書に開示されている。
【００６７】
カプセル化構造５２内のポインタテーブルによってアドレスされたブロック５３、５４ｉへデータを分配する場合、バイナリストリームの一部の塊がスキップされた後、ポインタをブロック５３、５４ｉに再一致させる必要がある。
【００６８】
本発明の特徴によると、ブロック５４ｉ内におけるスキップ可能な塊に対するオフセット値８１、８１’（各々のブロック５４ｉの先頭からの値）が構造バイナリデータブロック５３に挿入されており、飛び越し可能なエレメント８２の後ろに続く各データに対しては、ブロック５４ｉ内のどこを読むべきかを示し、構造ブロック５３における飛び越し可能なエレメント８２の直前におかれている。
【００６９】
バイナリストリーム６を復号化するときは、復号器はこれらのオフセットを読込み、バッファ７４ｉ内の適切な位置にポインタが再一致するようオフセットを利用する。
【図面の簡単な説明】
【００７０】
【図１】本発明に係る符号器を模式的に示す図である。
【図２】図１の符号器をより詳細に示す図である。
【図３】符号化されたバイナリストリームの一部およびバイナリストリームが図１に示された符号器によって処理される過程を模式的に示す図である。
【図４】図１に示す符号器によって生成されたバイナリ符号化コンテナを模式的に示す図である。
【図５】本発明に係る復号器を模式的に示す図である。
【図６】図５の復号器をより詳細に示す図である。
【図７】コンテナのデータエレメントが飛び越し可能である場合において、図１に示す符号器によって生成されたバイナリ符号化コンテナの一部を示す図である。
【図８】コンテナのデータエレメントが飛び越し可能である場合において、図１に示す符号器によって生成されたバイナリ符号化コンテナの一部を示す図である。
【図１】
2007516514.tif 000003
【図２】
2007516514.tif 000004
【図３】
2007516514.tif 000005
【図７】
2007516514.tif 000006
【図８】
2007516514.tif 000007
【図４】
2007516514.tif 000008
【図５】
2007516514.tif 000009
【図６】
2007516514.tif 000010
【国際調査報告】
2007516514.tif 000011
2007516514.tif 000012
2007516514.tif 000013