(57)【特許請求の範囲】
【請求項１】
記述要素の階層的構造を定義するＸＭＬ型スキーマにおけるインスタンスの記述要素を符号化する符号化方法であって、前記階層的構造が階層レベル、親記述要素及び子記述要素を有し、前記符号化されるべき記述要素が内容を有するような符号化方法であって、
−  前記スキーマから導出された少なくとも１つのテーブルを使用するステップであって、該テーブルが或る階層レベルにおける各記述要素のみを識別する識別情報と、何れかの子記述要素を当該子記述要素の親記述要素から取り出すための構造情報とを含むようなステップと、
−  前記インスタンスの階層メモリ表現を親記述要素から子記述要素へと前記符号化されるべき記述要素に到達するまで走査すると共に、走査された各記述要素の前記識別情報を取り出すステップと、
−  前記符号化されるべき記述要素を、前記内容と前記取り出された識別情報の系列とを有する断片として符号化するステップと、
を有している符号化方法において、
或る記述要素が前記スキーマにおいて多重発生を有し得るものとして定義されている場合、前記テーブルは前記記述要素に関して該記述要素がインスタンスにおいて多重発生を有し得ることを示すような発生情報を更に有し、所与のランクを有する発生が前記符号化の間において走査された場合、前記取り出された対応する識別情報が該ランクによりインデックス付けされることを特徴とする符号化方法。
【請求項２】
内容と、識別情報の系列とを有する断片を復号する復号方法であって、
−  ＸＭＬ型スキーマから導出された少なくとも１つのテーブルを使用するステップであって、前記スキーマが階層レベル、親記述要素及び子記述要素を有するような記述要素の階層構造を定義し、前記テーブルが或る階層レベルにおける各記述要素のみを識別する識別情報と、何れかの子記述要素を当該子記述要素の親記述要素から取り出すための構造情報とを含むようなステップと、
−  前記系列を識別情報毎に走査するステップと、
−  各ステップにおいて、現識別情報に関連する記述情報を前記テーブルにおいてサーチすると共に、前記スキーマにおけるインスタンスの階層メモリ表現に未だ含まれていない場合は、該記述要素を該階層メモリ表現に追加するステップと、
前記内容を、前記階層メモリ表現における前記系列の最後の識別情報に関連する記述要素に追加するステップと、
を有している復号方法において、
或る記述要素が前記スキーマにおいて多重発生を有し得るものとして定義されている場合、前記テーブルは前記記述要素に関して該記述要素がインスタンスにおいて多重発生を有し得ることを示すような発生情報を更に有し、前記系列がインデックス付けされた識別情報を有する場合、該インデックスは当該関連する記述要素に関する発生ランクとして解釈され、前記階層メモリ表現に未だ含まれていない場合、低いランク（又は複数のランク）の同一記述要素（又は複数の記述要素）が該階層メモリ表現に加えられることを特徴とする復号方法。
【請求項３】
記述要素の階層的構造を定義するＸＭＬ型スキーマにおけるインスタンスの記述要素を符号化するエンコーダであって、前記階層的構造が階層レベル、親記述要素及び子記述要素を有し、前記符号化されるべき記述要素が内容を有するようなエンコーダであって、
−  前記スキーマから導出された少なくとも１つのテーブルを記憶するメモリであって、該テーブルが或る階層レベルにおける各記述要素のみを識別する識別情報と、何れかの子記述要素を当該子記述要素の親記述要素から取り出すための構造情報とを含むようなメモリと、
−  前記インスタンスを親記述要素から子記述要素へと前記符号化されるべき記述要素に到達するまで走査すると共に、走査された各記述要素の前記識別情報を取り出し、且つ、前記符号化されるべき記述要素を、前記内容と前記取り出された識別情報の系列とを有する断片として符号化する計算手段と、
を有しているエンコーダにおいて、
或る記述要素が前記スキーマにおいて多重発生を有し得るものとして定義されている場合、前記テーブルは前記記述要素に関して該記述要素がインスタンスにおいて多重発生を有し得ることを示すような発生情報を更に有し、所与のランクを有する発生が前記符号化の間において走査された場合、前記取り出された対応する識別情報が該ランクによりインデックス付けされることを特徴とするエンコーダ。
【請求項４】
内容と、識別情報の系列とを有する断片を復号するデコーダであって、
−  ＸＭＬ型スキーマから導出された少なくとも１つのテーブルを記憶するメモリであって、前記スキーマが階層レベル、親記述要素及び子記述要素を有するような記述要素の階層構造を定義し、前記テーブルが或る階層レベルにおける各記述要素のみを識別する識別情報と、何れかの子記述要素を当該子記述要素の親記述要素から取り出すための構造情報とを含むようなメモリと、
−  前記系列を識別情報毎に走査する一方、各ステップにおいて、現識別情報に関連する記述情報を前記テーブルにおいてサーチすると共に前記スキーマにおけるインスタンスの階層メモリ表現に未だ含まれていない場合に該記述要素を該階層メモリ表現に追加し、且つ、前記内容を前記階層メモリ表現における前記系列の最後の識別情報に関連する記述要素に追加する計算手段と、
を有しているデコーダにおいて、
或る記述要素が前記スキーマにおいて多重発生を有し得るものとして定義されている場合、前記テーブルは前記記述要素に関して該記述要素がインスタンスにおいて多重発生を有し得ることを示すような発生情報を更に有し、前記系列がインデックス付けされた識別情報を有する場合、該インデックスは当該関連する記述要素に関する発生ランクとして解釈され、前記階層メモリ表現に未だ含まれていない場合、低いランク（又は複数のランク）の同一記述要素（又は複数の記述要素）が該階層メモリ表現に加えられることを特徴とするデコーダ。
【請求項５】
請求項３に記載のエンコーダを有する伝送システム。
【請求項６】
請求項４に記載のデコーダを有する伝送システム。
【請求項７】
伝送ネットワーク上で伝送する信号を生成する方法であって、該伝送ネットワークはＸＭＬ型スキーマから導出される少なくとも１つのテーブルを記憶するメモリを有するようなエンコーダ及び／又はデコーダを有し、前記ＸＭＬ型スキーマは記述要素の階層的構造を定義し、該階層的構造は階層レベル、親記述要素及び子記述要素を有し、前記テーブルは前記ＸＭＬ型スキーマから導出され、前記テーブルは或る階層レベルにおける各記述要素のみを識別する識別情報と、何れかの子記述要素を当該子記述要素の親記述要素から取り出すための構造情報とを含み、前記信号は符号化記述要素と呼ぶ、記述要素の内容を表す少なくとも１つの断片を具現化し、前記テーブルにおいては識別情報の系列が前記符号化記述要素及び該要素の親記述要素（又は複数の要素）に関連付けられているように前記信号を生成する方法において、
或る記述要素が前記スキーマにおいて多重発生を有し得るものとして定義されている場合、前記テーブルは前記記述要素に関して該記述要素がインスタンスにおいて多重発生を有し得ることを示すような発生情報を更に有し、所与のランクを有する発生が前記符号化の間において走査された場合、前記取り出された対応する識別情報が該ランクによりインデックス付けされることを特徴とする方法。
【請求項８】
エンコーダにおいてＸＭＬ型スキーマにおけるインスタンスの記述要素を符号化するために及び／又はデコーダにおいてＸＭＬ型スキーマにおけるインスタンスの階層メモリ表現を更新するために使用されるテーブルを生成する方法であって、前記ＸＭＬ型スキーマは記述要素の階層的構造を定義し、該階層的構造が階層レベル、親記述要素及び子記述要素を有するような方法であって、該テーブルは、前記ＸＭＬ型スキーマから導出されると共に、或る階層レベルにおける各記述要素のみを識別する識別情報と、何れかの子記述要素を当該子記述要素の親記述要素から取り出すための構造情報とを含んでいる方法において、
或る記述要素が前記スキーマにおいて多重発生を有し得るものとして定義されている場合、前記テーブルは前記記述要素に関して該記述要素がインスタンスにおいて多重発生を有し得ることを示すような発生情報を更に有し、所与のランクを有する発生が前記符号化の間において走査された場合、前記取り出された対応する識別情報が該ランクによりインデックス付けされることを特徴とする方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、記述要素の階層構造を規定するＸＭＬ型スキーマ（schema）におけるインスタンス（instance）の記述要素を符号化する符号化方法に関するもので、上記階層構造は階層レベル、親記述要素及び子記述要素を有し、符号化されるべき上記記述要素は内容（content）を有する。
【０００２】
また、本発明は内容と識別情報の系列とを有する断片（fragment）を復号する復号方法にも関する。
【０００３】
また、本発明は上記符号化方法を実施化することを意図するエンコーダ、上記復号方法を実施化することを意図するデコーダ、及び斯様なエンコーダ及び／又は斯様なデコーダを有する伝送システムにも関する。
【０００４】
更に、本発明は上記のような符号化又は復号方法に使用することを意図するテーブル、及び上記のような符号化方法を用いて発生された符号化された記述要素を伝送する信号にも関する。
【０００５】
本発明は、ＸＭＬ型スキーマのＸＭＬ型インスタンスに適用可能である。特に、本発明はＭＰＥＧ−７文書に適用可能である。
【０００６】
【従来の技術】
ＸＭＬは、Ｗ３Ｃコンソーシアムの勧告である（２０００年１０月６日付け拡張可能マークアップ言語１．０）。また、ＸＭＬスキーマもＷ３Ｃコンソーシアムの勧告である。ＸＭＬスキーマは、記述要素（Ｗ３Ｃ勧告においては、要素又は属性と呼ばれる）の階層構造を定義する。ＸＭＬスキーマのインスタンスは、該ＸＭＬスキーマに定義されるように構造化された記述要素を有している。
【０００７】
【発明が解決しようとする課題】
本発明の目的は、ＸＭＬ型スキーマのインスタンスであるような、ＸＭＬ型文書の１以上の記述要素を伝送及び記憶するための符号化及び復号方法を提案することにある。
【０００８】
【課題を解決するための手段】
本発明によれば、導入部分で述べられたような符号化方法は、
−  前記スキーマから導出された少なくとも１つのテーブルを使用するステップであって、該テーブルが或る階層レベルにおける各記述要素のみを識別する識別情報と、何れかの子記述要素を当該子記述要素の親記述要素から取り出すための構造情報とを含むようなステップと、
−  前記インスタンスの階層メモリ表現を親記述要素から子記述要素へ前記符号化されるべき記述要素に到達するまで走査すると共に、走査された各記述要素の前記識別情報を取り出すステップと、
−  前記符号化されるべき記述要素を、前記内容と前記取り出された識別情報の系列とを有する断片として符号化するステップと、
を有していることを特徴とする。
【０００９】
或る記述要素が前記スキーマにおいて多分多重発生を有するものとして定義されている場合、前記テーブルは前記記述要素に関して該記述要素がインスタンスにおいて多重発生を有し得ることを示すような発生情報を更に有し、所与のランクを有する発生が前記符号化の間において走査された場合、前記取り出された対応する識別情報が該ランクによりインデックス付けされる。
【００１０】
また、本発明によれば、導入部に記載したような復号方法が、
−  ＸＭＬ型スキーマから導出された少なくとも１つのテーブルを使用するステップであって、前記スキーマが階層レベル、親記述要素及び子記述要素を有するような記述要素の階層構造を定義し、前記テーブルが或る階層レベルにおける各記述要素のみを識別する識別情報と、何れかの子記述要素を当該子記述要素の親記述要素から取り出すための構造情報とを含むようなステップと、
−  前記系列を識別情報毎に走査するステップと、
−  各ステップにおいて、現識別情報に関連する記述情報を前記テーブルにおいてサーチすると共に、前記スキーマにおけるインスタンスの階層メモリ表現に未だ含まれていない場合は、該記述要素を該階層メモリ表現に追加するステップと、
前記内容を、前記階層メモリ表現における前記系列の最後の識別情報に関連する記述要素に追加するステップと、
を有していることを特徴とする。
【００１１】
或る記述要素が前記スキーマにおいて多分多重発生を有するものとして定義されている場合、前記テーブルは前記記述要素に関して該記述要素がインスタンスにおいて多重発生を有し得ることを示すような発生情報を更に有し、前記系列がインデックス付けされた識別情報を有する場合、該インデックスは当該関連する記述要素に関する発生ランクとして解釈され、前記階層メモリ表現に未だ含まれていない場合、低いランク（又は複数のランク）の同一記述要素（又は複数の記述要素）が該階層メモリ表現に加えられる。
【００１２】
本発明によれば、各記述要素はストリーム内の独立した断片（フラグメント）により表され、インクリメンタルな伝送に関する限り、要素及び属性に対するランダムなアクセス並びに高度なレベルの柔軟性を保証する。この断片の方法は、所与の記述要素に関連する識別情報の系列を計算するためにスキーマを使用することにより、ＭＰＥＧ−７の基本的な柔軟性及び拡張性がある性質も考慮している。該断片の方法は、提案された二進フォーマットが下記の特性を満たすのを可能にする：
−  インスタンス要素及び属性に対するランダムアクセス、
−  インクリメンタルな非整列及びスケール可能な伝送、
−  コンパクトさ：基本型式の内容を持つ要素及び属性のみが符号化される、
−  インスタンス更新プロトコルとの容易な統合性、
−  二進ＭＰＥＧ―７記述子の容易な解析及び部分的インスタンス生成。
【００１３】
本発明の他の利点は、スキーマの中間表現により得られる。確かに、スキーマから直接的に且つ明確に発生される上記テーブルは、可能性のある有効なインスタンスに関する共通の知識を、サーバとクライアントとの間で、これらのインスタンスの二進符号化及び復号専用の形態で共有することを可能にする。要素及び属性の構造、型式及びタグ名等の情報を集める、この共通知識はクライアントへは伝送する必要はなく、これはインスタンスの効率的なスキーマ認識（schema-aware）符号化に繋がる。このことは、当該二進フォーマットが、ＭＰＥＧ−７の内及び外において定義される将来のスキーマに対する完全な拡張性サポートを達成することも可能にする。
【００１４】
本発明の他の特徴及び利点は、本発明の好ましい実施例を特定し及び示す下記詳細な説明から一層容易に明らかとなるであろう。
【００１５】
【発明の実施の形態】
以下、本発明をＸＭＬスキーマのＸＭＬインスタンスを参照して説明する。該説明は制限するものではない。本発明は、同様の型式のマークアップ言語で書かれた如何なるインスタンス及びスキーマにも適用可能である。
【００１６】
ＸＭＬ型スキーマは、親記述要素及び子記述要素を有する記述要素（ＸＭＬ用語における要素又は属性の何れか）の階層構造を定義する。ＸＭＬ型スキーマのインスタンスは、該ＸＭＬ型スキーマにおいて定義されたように構造化された記述要素を有するＸＭＬ型文書である。インスタンスの記述要素の幾つかは、内容を有する。他のものは、構造的な入れ物（コンテナ）である。
【００１７】
図１に記載したように、本発明による伝送システムは、送信側に配置されたエンコーダBiM-Cと、受信側に配置されたデコーダBiM-Dとを有している。エンコーダBiM-C及びデコーダBiM-Dの両者は、ＸＭＬスキーマXML-Sに対するアクセスを有する（ＸＭＬスキーマはローカルに又はダウンロードされての何れかで利用可能である）。
【００１８】
上記エンコーダ及びデコーダは、ＸＭＬスキーマから直接且つ明確に発生された、要素宣言テーブルと呼ばれる、少なくとも１つのテーブルＥＤＴに対するアクセスも有する。該要素宣言テーブルは、所与のスキーマ定義に関して有効な如何なるインスタンスをも符号化及び復号するのに要する全ての情報を含むことを主に意図するものである。該要素宣言テーブルは１回発生され、関連するスキーマを参照するインスタンスを符号化及び復号するのに利用可能である。該テーブルはクライアントへ伝送する必要はない。
【００１９】
上記エンコーダは、インスタンスXML-Cの階層的メモリ表現DM-C（Ｗ３Ｃ仕様《文書オブジェクトモデル、レベル１仕様、バージョン１．０、１９９８年１０月１日》で定義されたＤＯＭ表現、又は該インスタンスの何れかの他の階層的メモリ表現）を走査すると共に、上記要素宣言テーブルに含まれる情報を使用して、各々が該インスタンスの記述要素に関連するような１以上の二進断片BiM-Fを発生する。
【００２０】
本発明によれば、基本型内容（例えば、組込型、単純型、自身の二進表現を持つ記述子）を有する記述要素は、識別情報（インスタンス構造化キーとも呼ばれる）の系列及び内容値からなる独立した断片として符号化される。当該ＸＭＬ階層内の構造的コンテナに過ぎない記述要素（即ち、内容値を有さない）は送信されず、デコーダ側において上記要素宣言テーブルから推測される。
【００２１】
二進断片BiM-Fは伝送ネットワークＮＥＴ上で送信され、デコーダBiM-Dにより受信される。該デコーダは前記要素宣言テーブルを使用して、
−  全ての親構造的記述要素、
−  記述要素の性質（要素又は属性）、
−  記述要素の名前、
−  内容値を復号するための記述要素型式、
を取り出す。
【００２２】
デコーダBiM-Dは、それに応じて、階層的メモリ表現DM-Dを更新する。次いで、ＸＭＬインスタンスXML-Dが、上記の更新された階層的メモリ表現から発生される。
【００２３】
上記要素宣言テーブルは、要素及び属性宣言構造を展開することにより上記スキーマから固有且つ明確に発生される、可能性のある有効なインスタンスの全数定義（exhaustive definition）として見ることができる。確かに、ＸＭＬスキーマは主に２種類の情報を与える。即ち、一方では、ＸＭＬインスタンス階層内の全ての可能性のある要素及び属性の位置が、複合型の定義（名付けられた又は匿名の何れか）及び要素宣言により特定される。他方、それらの値の型式は、組込データ型式及び単純型定義の使用による与えられる。当該スキーマ内で特定され、且つ、当該インスタンス内で見付けることができる各要素及び属性に関しては、上記要素宣言テーブルが、その名前（例えば、要素のタグ名）、その型式、その性質（要素又は属性）、及びその階層ＸＭＬ構造内での位置を明確に特定するキー（テーブル構造化キーと呼ばれる）を集める。スキーマはインスタンスがバリデーション及び相互運用性の目的でどの様であるべきかを定義するのに対し、上記要素宣言テーブルはインスタンスが符号化の目的での構造的見方からどの様であるかを述べる。
【００２４】
上記要素宣言テーブル及び符号化及び復号処理における該テーブルの使用の基本は、
−  送信される記述要素の型式及び名前、
−  ＸＭＬインスタンス階層における該要素の位置、
を固有に識別することを意図する、テーブル構造化キーにある。
【００２５】
この構造化キーの構文はドット表記であり、ここで、ドットは階層レベルを表す一方、各レベルにおける番号付けが、当該スキーマから全ての要素及び属性宣言を拡張することにより実行される。上記表記の最後の桁は、当該階層レベルにおける記述要素のみを識別する識別情報である。前の桁は、親記述要素から子記述要素を取り出すために使用されるポインティング情報である。
【００２６】
記述要素が当該スキーマ内で多重に発生する又は多分多重に発生するとして定義された場合、ドット表記の最後に発生情報が追加される（以下の説明においては、該発生情報は括弧により表される）。
【００２７】
上記要素宣言テーブルを発生する処理は、当該スキーマにおける全ての要素宣言をブラウズして、所与のスキーマに対応する最大のインスタンス（全ての可能性のある要素及び属性をインスタンス化するもの）の階層メモリ表現に到達することに匹敵する。それにも拘わらず、この“最大の”インスタンスは当該スキーマがＭＰＥＧ−７で通常使用される自己埋込構造を定義するやいなや、無限となる。従って、上記要素宣言テーブルにおける該自己包含（self-containment）を捕捉する必要がある。これは、自己包含記述要素の場合、同じ複合型を有する当該ツリー構造内の該要素の先祖のテーブル構造化キーを特定することにより実行される。このようして、斯様な要素は当該要素宣言テーブルにおいて、それ以上拡張されることはない。上記先祖のテーブル構造化キーは、自己包含キーと呼ばれる。該キーは、子記述要素を該要素の親記述要素から取り出すためにも使用される。
【００２８】
上記ポインティング情報は、上記自己包含キーと共に、全ての子記述要素を当該要素の親記述要素から取り出すために使用される構造的情報である。親記述要素が自己包含記述要素である場合は、該要素の子は、該親記述要素の自己包含キーと同じポインティング情報の記述要素である。親記述要素が自己包含記述要素でない場合は、該要素の子記述要素は該親のテーブル構造化キーと同じポインティング情報の記述要素である。
【００２９】
当該要素宣言テーブルは、当該スキーマの全ての可能性のあるインスタンスの固有且つ明確な番号付けを述べるのを可能にする。以下、スキーマ及び対応する要素宣言テーブルを例示する。
例１
スキーマ１：
<complexType name=”complexType1”>
<sequence>
<element name=”Element1”type=”type1”/>
<element name=”Element2”type=”type2”minOccurs=”0”maxOccurs=”unbounded”/>
<element name=”Element3”>
<complexType>
<sequence>
<element name=”Element4”type=”type4”minOccurs=”0” maxOccurs=”1”/>
<element name=”Element1”type=”type1”/>
</sequence>
</complexType>
</element>
</sequence>
<attribute name=”Attribute1”type=”type4”/>
</complexType>
<element name=”GlobalElement”type=”complexType1”/>
【００３０】
全スキーマ要素宣言の展開と見られる該要素宣言テーブルは、なかでも、以下の要素名を対応するテーブル構造化キーと共に含む：
テーブル１：
名前 テーブル構造化キー        （…）
包括的要素             0
要素1                  0 . 0
要素2                  0 . 1 []
要素3                  0 . 2
要素4                  0 . 2 . 0
要素1                  0 . 2 . 1
属性1                  0 . 3
下線の桁は、識別情報である
【００３１】
例２
スキーマ２：
<complexType name=”complexType1”>
<sequence>
<element name=”Element1” type=”complexType2”/>
<element name=”Element2” type=”type2” minOccurs=”0” maxOccurs=”unbounded”/>
<element name=”Element3” type=”type3”/>
</sequence>
<attribute name=”Attribute1” type=”type4”/>
</complexType>
<complexType name=”complexType2”>
<sequence>
<element name=”Element4” type=”type4”/>
<element name=”Element1” type=”complexType2”/>
</sequence>
</complexType>
<element name=”GlobalElement” type=”complexType1”/>
当該要素宣言テーブルは、各要素の名前及びキー等の他の情報のなかでも、関連する場合は自己包含フィールドを含んでいる。
表２：
0004405146.tif 000002
【００３２】
上記テーブル構造化キーの下線の桁は、識別情報である。該テーブル構造化キーの下線無しの桁及び自己包含キーは、全ての子記述要素を当該要素の親記述要素から取り出すために使用される構造的情報である。
【００３３】
上記要素２のテーブル構造化キーにおける括弧は、多重発生要素の存在を示していることに注意されたい。更に、要素２及び要素４は、任意選択的な要素であっても、番号付けにおいて考慮される。また、要素１は、当該ツリー構造内で異なる位置においてインスタンス化することができるので、該テーブルでは２回現れることにも注意されたい。
例３
スキーマ３：
<?xml version="1.0" encoding="UTF-8"?>
<schema xmlns:xsd="http://www.w3.org/1999/XMLSchema">
<complexType name="MediaTimeType" content="elementOnly">
<sequence>
<element name="Start">
<simpleType base="integer"/>
</element>
<element name="Stop">
<simpleType base="integer"/>
</element>
</sequence>
<attribute name="timeunit" type="string" use="required"/>
</complexType>
<complexType name="VideoSegmentType" content="elementOnly">
<sequence>
<element name="keyFrame" minOccurs="1" maxOccurs="unbounded">
<simpleType base="string"/>
</element>
<element name="Annotation" type="string" minOccurs="0" maxOccurs="1"/>
<element name="MediaTime" type="MediaTimeType" minOccurs="0" maxOccurs="1"/>
<element name="VideoSegment" type="VideoSegmentType" minOccurs="0" maxOccurs="unbounded"/>
</sequence>
<attribute name="id" use="required">
<simpleType base="string"/>
</attribute>
</complexType>
<element name="VideoSegment" type="VideoSegmentType"/>
</schema>
表３：
0004405146.tif 000003
上記テーブル構造化キーの下線の桁は、識別情報である。該テーブル構造化キーの下線無しの桁及び自己包含キーは、全ての子記述要素を当該要素の親記述要素から取り出すために使用される構造的情報である。
【００３４】
スキーマにおけるインスタンスの記述要素を符号化する方法を図２を参照して説明する。図２によれば、スキーマXML-SにおけるインスタンスXML-Cの記述要素ＤＥを符号化するために、該インスタンスXML-Cの階層メモリ表現ＤＭ−Ｃが、符号化されるべき上記記述要素ＤＥに到達するまで親記述要素から子記述要素へと走査される（ステップ２−１）。各階層レベルにおいては、走査された記述要素Ｄｉに関連する識別情報ＩＤｉが、スキーマXML-Sに関連するテーブルＥＤＴから取り出される（ステップ２−２）。記述要素ＤＥのインスタンス構造化キーＫ（ＤＥ）は、取り出された識別情報ＩＤｉの系列として構築される（ステップ２−３）。断片BiM-F(DE)が、最終的に、記述要素ＤＥの内容Ｃ（ＤＥ）を上記取り出された識別情報の系列に付加することにより構築される（ステップ２−４）。該断片は、送信のために二進フォーマットに変換される。
【００３５】
斯様な符号化処理の一例を、前述した例３を参照して説明する。
【００３６】
下記アレイ１は例３に記載したスキーマにおけるインスタンスの一例を示している。左側には、該アレイの対応するラインで定義された要素のインスタンス構造化キーが示される。右側には、該アレイの対応するラインにおいて定義された属性のインスタンス構造化キーが示されている。これらのインスタンス構造化キーは、上述した符号化方法を用いることにより得られたものである。
【００３７】
アレイ１において太字文字で現れている記述要素<Media Time timeunit=”PT1N30F”>の符号化を解説目的でステップ毎に説明する。
【００３８】
ステップ１−１：当該インスタンスの階層メモリ表現が、符号化されるべき記述要素（ここでは、要素“媒体時間（Media Time）”の属性“時間単位（timeUnit）”）に到達するまで親記述要素から子記述要素まで走査される。走査される記述要素は：
ビデオセグメント（Video Segment）
ビデオセグメント（ビデオセグメントの最初に発生する子）
ビデオセグメント（ビデオセグメントの２番目に発生する子）
媒体時間（Media Time）
時間単位（timeUnit）
である。
ステップ１−２：対応する識別情報（もし当てはまるなら、インデックスを含む）がテーブル３から取り出される：
ビデオセグメント………………………………………………………………….0
ビデオセグメント（ビデオセグメントの最初に発生する子）………..3[0]
ビデオセグメント（ビデオセグメントの２番目に発生する子）..3[1]
媒体時間………………….…………………………………………2
時間単位………………………………………………………….2
ステップ２：上記の取り出された識別情報の系列：0.3[0].3[1].2.2.が構築される。この系列は、当該符号化された記述要素に関連するインスタンス構造化キーである。
【００３９】
アレイ１に示される他のインスタンス構造化キーも同様にして導出することができる。
【００４０】
インスタンス構造化キーは、テーブル構造化キーのインスタンス化としても見ることができる。確かに、多重発生要素は実際にインデックス付けされており（0.3[0].0.3[1],…のようなインスタンス構造化キーとなる）、自己包含ループが発生される（当該表には現れないが、該表から計算することが可能な0.3[0].3[1].2.2のようなインスタンス構造化キーとなる）。インスタンス構造化キーは、インスタンス二進断片において記述要素識別子として符号化される。
【００４１】
断片を復号する方法を、図３を参照して説明する。図３によれば、本発明による復号方法は：
−  ステップ３−１：当該テーブルにおいて、前記取り出された識別情報の系列に関連する記述要素を見付ける、
−  ステップ３−２：受信された内容を上記記述要素（該表において見付かった）の基本型式に基づいて復号する、
−  ステップ３−３：上記要素をその内容と一緒に加えることにより階層メモリ表現を更新し；喪失しているなら、その親記述要素を加え；多重発生の場合は、喪失しているなら、低いランクの同一の記述要素を加える、
ことにある。
【００４２】
【表１】
0004405146.tif 000004
【００４３】
実際には、受信された系列が識別情報毎に走査され、当該インスタンスの階層メモリ表現を更新するために下記アルゴリズムが適用される：
アルゴリズム（１）：
−  ステップ４−１：
現トークン＝当該系列の第１識別情報
現ノード＝階層メモリ表現のルート
−  ステップ４−２：
前の記述要素＝現ノードに対応する記述要素
現記述要素＝現トークンを識別情報として持つ前の記述要素の子
−  ステップ４−３：現ノードは現記述要素に対応する子ノードを有するか？
−  ステップ４−４：現ノードが現記述要素に対応する子ノードを有しているなら、ステップ４−８に進む
−  ステップ４−５：現ノードが現記述要素に対応する子ノードを有していないなら、斯様な子ノードを生成する
−  ステップ４−６：多重発生の場合、既存でないなら、低いランクの兄弟ノード（又は複数の兄弟ノード）を生成する
−  ステップ４−７：もし現トークン＝受信された系列の最後の識別情報なら、当該内容をステップ４−５において生成されたノードに加え、ステップ４−８に進む
−  ステップ４−８：
現トークン＝次の識別情報
現ノード＝子ノード
ステップ４−２に進む。
【００４４】
例えば、ステップ４−２において、現記述要素はＣのようなコードにおける下記のアルゴリズムを使用することにより取り出すことができる：
アルゴリズム（２）：
Let instance_key be the sequence of token from the first identification information of the received sequence to the current identification of the received sequence.
Let edt_key be the corresponding table structuring key as found in the table
Let prefix(key) be the largest prefix (n first tokens) of key that actually exists in the table.
Let suffix(key) be the last tokens of key so that key = prefix(key)+suffix(key).
Let self_cont(key) be the self-containment key.
while ( prefix(instance_key) != instance_key )
{
instance_key = self_cont( prefix( instance_key ) ) + suffix( instance_key );
}
edt_key = instance_key ;
アルゴリズム（２）をステップ毎に前述した例２の系列0.0.1.1.0に適用すると：
instance_key = 0.0.1.1.0
prefix(instance_key) = 0.0.1
instance_key = self_cont( prefix(instance_key) ) + suffix( instance_key ) = 0.0 + 1.0 = 0.0.1.0
prefix(instance_key) = 0.0.1
instance_key = self_cont( prefix(instance_key) ) + suffix( instance_key ) = 0.0 + 0 = 0.0.0
が得られる。
【００４５】
これは、最終的に：
edt_key = 0.0.0
となり、現記述要素が要素４であることを意味する。
【００４６】
非自己包含型の階層の場合は、テーブル構造化キーとインスタンス構造化キーとの間のマッピングは素直なものとなる。確かに、対応するテーブル構造化キーを取り出すには、インスタンス構造化キーで見付かったインデックスを単純に削除するだけでよい。前述した例１において、インスタンス構造化キー0.1[5]により表される記述要素は、包括的要素内に存在する５番目の要素２である。
【００４７】
本発明の有利な実施例においては、上記テーブル構造化キー及びインスタンス構造化キーは、以下に説明するように圧縮される。実験によれば、斯様な構造化キーの圧縮はキーのサイズに関して大きな利得に繋がる一方、正確に同一の機能を提供することが分かった。
【００４８】
結果としてのキーは圧縮キー（短くはＣＳＫ）と呼ばれる。単純な（非自己包含の）場合は、ＣＳＫは構造化キー要素宣言テーブルのレコード番号である。
【００４９】
先ず、要素宣言テーブルのレコードを番号付けすることにより、ＥＤＴフィールドの現リストにキーを加える必要がある。前述した例２に適用すると、これは、
テーブル２の２：
0004405146.tif 000005
となる。
【００５０】
通常の場合（自己包含構造を伴う）においてインスタンス構造化キーからＣＳＫを計算するには、アルゴリズム（３）が使用される：
アルゴリズム（３）：
Let instance_key be the instance structuring key of a given description element.
Let cs_key be the corresponding compact structuring key.
Let prefix(key) be the largest prefix (n first tokens) of key that actually exists in the EDT.
Let suffix(key) be the last tokens of key so that key = prefix(key)+suffix(key).
Let self_cont(key) be the self-containment key.
Let compact_form(key) be the corresponding compact form of key in the EDT.
while ( prefix(instance_key) != instance_key )
{
cs_key = cs_key + compact_form( prefix(instance_key) ) ;
instance_key = self_cont( prefix( instance_key ) ) + suffix( instance_key );
}
cs_key = cs_key + compact_form( prefix(instance_key) ) ;
例：キー：0.0.1.1.0に対応するＣＳＫを計算したい。
【００５１】
上述したアルゴリズムをステップ毎に適用すると：
instance_key = 0.0.1.1.0
prefix(instance_key) = 0.0.1
cs_key = 3
instance_key = self_cont( prefix(instance_key) ) + suffix( instance_key ) = 0.0 + 1.0 = 0.0.1.0
prefix(instance_key) = 0.0.1
cs_key = 3.3
instance_key = self_cont( prefix(instance_key) ) + suffix( instance_key ) = 0.0 + 0 = 0.0.0
となり、これは最終的に：
cs_key = 3.3.2
となる。上記例において、当該要素は表現を簡単にするために多重発生要素ではない。それにも拘わらず、インスタンス構造化キー（各々、インスタンスＣＳＫ）の各トークンはインデックス付けされる（各々、幾つかのインデックスを含む）ことに注意すべきである。
【００５２】
上記圧縮キーの唯一の目的は、ストリームの大きさを低減することである。従って、上述した復号フェーズの前に、当該インスタンス圧縮構造化キーはデコーダにより先ず伸張された形態に復号される。下記のアルゴリズム４はインスタンス圧縮キーに対応するインスタンス構造化キーを戻す：
アルゴリズム（４）：
Let resultNCKey be the expanded form of compact_key (result of the algorithm).
Let compact_key be the instance compact structuring key of a given description element.
Let current_key be a token of the instance compact structuring key compact_key.
Let compact_key[i] be the ith token of compact_key.
Let size(compact_key) be the number of tokens of compact_key.
Let diffCode(key1, key2) be the sub-key obtained by removing the common prefix of key1 and key2
Let NCKey(CKey) be the corresponding expanded form of the compact key CKey.
Let self_cont(key) be the self-containment key of key.
All indexes are first removed from compact_key and are put back at the end in the developed form of compact_key:
current_key = compact_key[0]
resultNCKey = NCKey(current_key)
for (i=1; i<size(compact_key); i++)
{
previous_key = current_key ;
current_key = compact_key[i] ;
resultNCKey += "." + diffCode(NCKey(current_key), self_cont(previous_key)) ;
}
例：下記のCSK3.3.2に対応するインスタンス構造化キーを発生したい。
【００５３】
上述したアルゴリズムをステップ毎に適用すると：
compact_key = 3.3.2
current_key = 3
resultNCKey = 0.0.1 (looking at the EDT)
(i=1)
previous_key = 3
current_key = 3
self_cont(previous_key) = 0.0
NCKey(current_key) = 0.0.1
diffCode(0.0.1, 0.0 ) = “1”
resultNCKey = resultNCKey +“.” + “1”
&#222;
resultNCKey = 0.0.1.1
(i=2)
previous_key = 3
current_key = 2
self_cont(previous_key) = 0.0
NCKey(current_key) = 0.0.0
diffCode(0.0.0, 0.0 ) = “0”
resultNCKey = resultNCKey + “.” + “0”
&#222;
resultNCKey = 0.0.1.1.0
end
が得られる。かくして、3.3.2はインスタンス構造化キー0.0.1.1.0の圧縮形態となる。
【００５４】
次に二進構文の例を説明する。断片（フラグメント）はヘッダを有するファイルの一部である。ファイルのヘッダは、当該スキーマの少なくとも一つの識別子（ＭＰＥＧで定義されたＩＤ又はM6142で提案されたＵＲＬの何れか）を有している。
【００５５】
各フラグメントは、図４に示すように、インスタンス圧縮構造化キーK(DEi)（又はインスタンス構造化キー）と、記述要素値C(DEi)（内容とも呼ばれる）とからなっている。インスタンス構造化キーの一般形態は次のようになり：
Key[ind][ind](…)[ind].Key[ind][ind](…)[ind].(…),
ここで、各群Key[ind][ind](…)[ind]はトークンと呼ばれる。インスタンス構造化キーのトークンは最大で１つのインデックスを有する。インスタンス圧縮構造化キーのトークンは数個のインデックスを有することができる。全てのキー及びインデックスは、可変数のバイトを用いて符号化された整数値である。このように、全体の構造化キーは可変組のバイトを用いて符号化され、これらの各々は下記の意味で最上位２ビットにより制御される：
【００５６】
【表２】
0004405146.tif 000006
【００５７】
図４は、記述要素値を符号化するための一般フォーマットも示している。図４によれば、データ値D(DEi)を当該二進ファイル又はストリームに追加する前に、当該データブロックのバイトサイズS(DEi)が符号化される。これは、デコーダに復号されるべきデータのサイズに関して通知することを狙いとし、データに対する容易なランダムアクセス及び高速なストリーム解析を保証する。或る基本データ型式は大量のバイトを含む可能性があるので（例えば、自由なテキスト注釈又は映画のスクリプト）、データサイズを可変数のバイトを使用して符号化することを提案する。
【００５８】
このように、長さはデフォルトにより１バイトを用いて符号化され、最上位ビットは次のように解釈される：
【００５９】
【表３】
0004405146.tif 000007
【００６０】
図５は、圧縮キー《0.1[70][1]》に関する二進符号化の例を示す。該圧縮キー《0.1[70][1]》を符号化するには５バイトを要する。各バイトは２つの制御ビットで開始する。６個の下位ビットは当該値を符号化するために使用される。最初のバイトの制御ビットは‘００’（新レベル）である。その値ビットは‘００００００’であり、これは系列（‘０’）の最初の識別情報の二進表現である。第２バイトの制御ビットは‘１０’（インデックス付）である。その値ビットは‘０００００１’であり、これは系列（‘１’）の第２識別情報の二進表現である。最初のインデックス‘７０’の二進表現は‘１０００１１０’であり、これは６ビットより多くのビットを含む。従って、符号化は２バイト、即ち第３及び第４バイト上でなされる。第３バイトの制御ビットは‘０１’（継続）である。その値ビットは‘０００１１０’（符号化されるべきインデックスの下位ビット）である。第４バイトの制御ビットは‘１０’（インデックス付）である。その値ビットは、‘０００００１’（符号化されるべきインデックスの上位ビット）である。最後に、第５バイトの制御ビットは‘１１’（終了）である。そして、その値ビットは‘０００００１’（符号化されるべきインデックスの二進値）である。
【００６１】
図６は、データサイズ５７５（二進：1000111111）の二進符号化の例を示す。最初のバイトは、長さ値の７つの下位ビットに、他のバイトを要することを指定する制御ビットを加えたものからなっている。第２バイトは、“終了”制御ビット伴う残りのビットを含んでいる。
【００６２】
既述したように、提案された符号化方法の主たる利点は、基本型の値を含む属性及び要素のみを符号化し、構造的コンテナ（例えば、複合型の）に過ぎない要素はスキップする点である。これは、当該構造が上記要素宣言テーブルを用いてデコーダ側で推定することができる場合に可能である。
【００６３】
例：
下記のインスタンス断片（コア実験的試験組において見付かる）を考察する：
<GenericDS>
<MediaInformation>
<MediaProfile>
<MediaInstance>
<InstanceLocator>
<MediaURL>imgs/img00587_add3.jpg</MediaURL>
</InstanceLocator>
</MediaInstance>
</MediaProfile>
</MediaInformation>
</GenericDS>
この場合、MediaURLのみが構造化キーを用いて（ストリングとして）符号化され、該構造化キーは、全体の構造をデコーダが要素宣言テーブルから再現するのを可能にする。他のコンテナ要素は、送信されない。
【００６４】
通常の場合、型式が基本的であるような（即ち、二進表現が、相互運用性を保証するような標準的な方法で利用可能な）全ての要素が符号化されるべきである。
【００６５】
斯様な基本型式の例は、ＸＭＬスキーマ組込型式（例えば、ストリング、フロート、…）及びＭＰＥＧ−７固有の基本型（例えば、unsignedInt1、unsignedInt2、…、MediaTime、Matrix、…）である。
【００６６】
基本型式は、以下の場合において複合型式を含み得るような拡張形式も含む：
−  複合型式構造内で埋込要素にランダムにアクセスする必要がない。
−  効率的な二進表現が既に存在する。
【００６７】
これらの規準は、ＭＰＥＧ−７のビデオ及びオーディオグループにより定義された記述子の場合に、間違いなく満足される。確かに、コンパクトな二進表現が既に定義されており、使用されるべきである。更に、（殆どの場合）記述子の個々の部分にアクセスする必要はない（全体として意味がある）。
【００６８】
効率（内容の圧縮に関して）は基本型式（最適な方法で符号化される）の数の増加に伴い増加するであろうが、全ての標準基本型式に対する複合方法を含まなければならないデコーダの複雑さも増加する。
【００６９】
下記のアレイ２は、アレイ１において既に使用されたインスタンスに関する圧縮インスタンス構造化キーの一例である。既述要素<MediaTime timeUnit=‘PT1N30F’>に関連する圧縮インスタンス構造化キーは7[0].7[1].6である。この圧縮インスタンス構造化キーの二進表現は、’10-000111 00-000000 10-000111 00-000001 11-000110’である。内容の長さは１バイトで符号化される：0-0000111。そして、PT1N30Fは通常の文字符号化を用いてストリング文字からバイトへと変換される。
【００７０】
【表４】
0004405146.tif 000008
【図面の簡単な説明】
【図１】  図１は、本発明による伝送システムの概念図である。
【図２】  図２は、本発明による符号化方法のステップを記載した説明図である。
【図３】  図３は、本発明による復号方法のステップを記載した説明図である。
【図４】  図４は、本発明による信号において具現化される断片である。
【図５】  図５は、インスタンス圧縮キーの二進符号化の一例である。
【図６】  図６は、記述要素の値の二進符号化の一例である。
【図１】
0004405146.tif 000009
【図２】
0004405146.tif 000010
【図３】
0004405146.tif 000011
【図４】
0004405146.tif 000012
【図６】
0004405146.tif 000013
【図５】
0004405146.tif 000014