(57)【特許請求の範囲】
【請求項１】
デコーダがアクセスできない、少なくとも第１のスキーマに定義されている構造を有し、当該デコーダがアクセスできる少なくとも第２のスキーマの変更の結果得られる、構造化された文書を、上記デコーダが、少なくとも部分的に復号化できるようにする、エンコーダを使用する符号化方法であって、
構造化された文書は、互いにネストされた複数の情報要素を含み、上記文書の情報要素は、少なくとも上記第１のスキーマおよび第２のスキーマにて、それぞれ情報要素の要素構造を定義する要素の型と関連付けされ、
上記第１のスキーマは、上記デコーダがアクセスできず、上記第２のスキーマは、上記デコーダがアクセスでき、上記第１のスキーマは、上記第２のスキーマで定義された対応要素から派生した少なくとも１つの派生情報要素を定義し、
上記符号化方法は、上記第１のスキーマと第２のスキーマとを用いて上記文書を符号化して、文書の情報要素ごとに、上記要素を符号化した値を含む内容フィールドと、上記内容フィールドの前に配置され、上記内容フィールドの長さを符号化した値を含む長さフィールドと、上記派生情報要素を符号化するために上記第２のスキーマが用いられることを示す第１の状態、並びに、上記派生情報要素のサブ要素のすべてを符号化するために上記第２のスキーマが用いられることを示す第２の状態、並びに、上記第１のスキーマおよび第２のスキーマを用いて上記派生情報要素が符号化されることを示す第３の状態のいずれかを有するスキーマ状況モードフィールドとを備える、上記情報要素を符号化したバイナリ・シーケンスを含むバイナリ・ストリームにするステップを含み、
上記符号化方法は、上記スキーマ状況モードフィールドが上記第３の状態にある時、上記派生情報要素を符号化した上記バイナリ・シーケンスに、当該派生要素の上記構造を定義している第１スキーマを指定する参照を挿入するステップを含み、
上記第１のスキーマを指定する上記参照は、上記文書の符号化に用いられる全てのスキーマについての参照を含んだスキーマ参照リストに定義されていて、このスキーマ参照リストに上記デコーダがアクセス可能である符号化方法。
【請求項２】
上記スキーマ状況モードフィールドが上記第１の状態にある時、上記符号化された情報要素は、スキーマ参照及び他の変更情報が除かれており、上記スキーマ状況モードフィールドが上記第２の状態にある時、上記情報要素のサブ要素は、スキーマ参照及び他の変更情報が除かれている請求項１記載の符号化方法。
【請求項３】
上記派生情報要素は、上記第１のスキーマにおいて、上記第２のスキーマの対応する情報要素の構造型に対して制限された構造型に関連付けされ、
上記派生要素を符号化したバイナリ・シーケンスは、内容フィールドと、該内容フィールドに付加される、上記第１のスキーマへの参照と、上記第２のスキーマにて定義された派生要素の構造型への参照とを備えている請求項１又は２記載の符号化方法。
【請求項４】
上記スキーマ状況モードフィールドが上記第３の状態にある時、上記派生情報要素は、上記第１のスキーマにおいて、上記第２のスキーマの対応する情報要素の構造型に対して拡張された構造型に関連付けされ、
上記派生情報要素の構造型は、上記第２のスキーマで定義された上記対応する情報要素の構造型を有する第１の部分と、上記派生情報要素に固有で、上記第１のスキーマで定義された構造型を有する第２の部分とを含み、
上記派生要素を符号化したバイナリ・シーケンスは、上記第２のスキーマへの参照を含むフィールドと、
上記第２のスキーマにおける対応する要素の構造型への構造型参照を含むフィールドと、
上記第１の部分を符号化した値を含むフィールドと、
上記第１のスキーマへの参照を含むフィールドと、
上記第２の部分の構造型への構造型参照を含むフィールドと、
上記第２の部分を符号化した値を含むフィールドとを含む内容フィールドを含んでいる請求項１から３のいずれか１項に記載の符号化方法。
【請求項５】
情報要素を符号化したバイナリ・シーケンスは、当該情報要素の名前が変更されたかどうかを示す置換フラグを含む置換フィールドと、上記置換フラグが変更されたことを示す場合、当該情報要素の新しい名前を指定した参照を含む要素名参照フィールドと、新しい名前の参照が定義されているスキーマへの参照を含むスキーマ参照フィールドとを備えている請求項１から４のいずれか１項に記載の符号化方法。
【請求項６】
構造化された文書の符号化に用いる全てのスキーマへの参照を含む上記スキーマ参照リストは、上記構造化された文書を符号化したバイナリ・ストリームに関連するヘッダに挿入される請求項１から５のいずれか１項に記載の符号化方法。
【請求項７】
デコーダがアクセスできない、少なくとも第１のスキーマに定義されている構造を有し、当該デコーダがアクセスできる少なくとも第２のスキーマの変更の結果得られる、構造化された文書を、上記デコーダが、少なくとも部分的に復号化できるようにする、エンコーダが使用する符号化方法であって、
構造化された文書は、互いにネストされた複数の情報要素を含み、上記文書の情報要素は、少なくとも上記第１のスキーマおよび第２のスキーマにて、それぞれ情報要素の要素構造を定義する要素の型と関連付けされ、
上記第１のスキーマは、上記デコーダがアクセスできず、上記第２のスキーマは、上記デコーダがアクセスでき、上記第１のスキーマは、上記第２のスキーマで定義された対応要素から派生した少なくとも１つの派生情報要素を定義し、
上記符号化方法は、上記第１のスキーマと第２のスキーマとを用いて上記文書を符号化して、文書の情報要素ごとに、上記要素を符号化した値を含む内容フィールドと、上記内容フィールドの前に配置され、上記内容フィールドの長さを符号化した値を含む長さフィールドと、上記派生情報要素を符号化するために上記第２のスキーマが用いられることを示す第１の状態、並びに、上記派生情報要素のサブ要素のすべてを符号化するために上記第２のスキーマが用いられることを示す第２の状態、並びに、上記第１のスキーマおよび第２のスキーマを用いて上記派生情報要素が符号化されることを示す第３の状態、並びに、上記第１のスキーマおよび上記第２のスキーマを用いて上記派生情報要素が符号化されるとともに、上記用いられたのと同じ第２のスキーマが上記派生情報要素のサブ要素のすべてを符号化するために用いられることを示す第４の状態を有するスキーマ状況モードフィールドとを備える、上記情報要素を符号化したバイナリ・シーケンスを含むバイナリ・ストリームにするステップを含み、
上記符号化方法は、上記スキーマ状況モードフィールドが上記第３の状態又は上記第４の状態にある時、上記派生情報要素を符号化した上記バイナリ・シーケンスに、当該派生要素の上記構造を定義している第１スキーマを指定する参照を挿入するステップを含み、
上記第１のスキーマを指定する上記参照は、上記文書の符号化に用いられる全てのスキーマについての参照を含んだスキーマ参照リストに定義されていて、このスキーマ参照リストに上記デコーダがアクセス可能である符号化方法。
【請求項８】
上記スキーマ状況モードフィールドが上記第１の状態にある時、上記符号化された情報要素は、スキーマ参照及び他の変更情報が除かれており、上記スキーマ状況モードフィールドが上記第２の状態又は上記第４の状態にある時、上記情報要素のサブ要素は、スキーマ参照及び他の変更情報が除かれている請求項７記載の符号化方法。
【請求項９】
上記派生情報要素は、上記第１のスキーマにおいて、上記第２のスキーマの対応する情報要素の構造型に対して制限された構造型に関連付けされ、
上記派生要素を符号化したバイナリ・シーケンスは、内容フィールドと、該内容フィールドに付加される、上記第１のスキーマへの参照と、上記第２のスキーマにて定義された派生要素の構造型への参照とを備えている請求項７又は８に記載の符号化方法。
【請求項１０】
上記スキーマ状況モードフィールドが上記第３の状態にある時、上記派生情報要素は、上記第１のスキーマにおいて、上記第２のスキーマの対応する情報要素の構造型に対して拡張された構造型に関連付けされ、
上記派生情報要素の構造型は、上記第２のスキーマで定義された上記対応する情報要素の構造型を有する第１の部分と、上記派生情報要素に固有で、上記第１のスキーマで定義された構造型を有する第２の部分とを含み、
上記派生要素を符号化したバイナリ・シーケンスは、上記第２のスキーマへの参照を含むフィールドと、
上記第２のスキーマにおける対応する要素の構造型への構造型参照を含むフィールドと、
上記第１の部分を符号化した値を含むフィールドと、
上記第１のスキーマへの参照を含むフィールドと、
上記第２の部分の構造型への構造型参照を含むフィールドと、
上記第２の部分を符号化した値を含むフィールドとを含む内容フィールドを含んでいる請求項７から９のいずれか１項に記載の符号化方法。
【請求項１１】
情報要素を符号化したバイナリ・シーケンスは、当該情報要素の名前が変更されたかどうかを示す置換フラグを含む置換フィールドと、上記置換フラグが変更されたことを示す場合、当該情報要素の新しい名前を指定した参照を含む要素名参照フィールドと、新しい名前の参照が定義されているスキーマへの参照を含むスキーマ参照フィールドとを備えている請求項７から１０のいずれか１項に記載の符号化方法。
【請求項１２】
構造化された文書の符号化に用いる全てのスキーマへの参照を含む上記スキーマ参照リストは、上記構造化された文書を符号化したバイナリ・ストリームに関連するヘッダに挿入される請求項７から１０のいずれか１項に記載の符号化方法。
【請求項１３】
デコーダがアクセスできない少なくとも第１のスキーマに定義されている構造を有し、当該デコーダがアクセスできる少なくとも第２のスキーマの変更の結果得られる、構造化された文書を符号化したバイナリ・ストリームを、少なくとも部分的に復号化するための、デコーダが使用する復号化方法であって、
構造化された文書は、互いにネストされた複数の情報要素を含み、上記文書の情報要素は、少なくとも上記第１のスキーマおよび第２のスキーマにて、それぞれ情報要素の要素構造を定義する要素の型と関連付けされ、
上記第１のスキーマは、上記デコーダがアクセスできず、上記第２のスキーマは、上記デコーダがアクセスでき、上記第１のスキーマは、上記第２のスキーマで定義された対応要素から派生した少なくとも１つの派生情報要素を定義し、
上記復号化方法は、上記第２のスキーマを用いて、上記構造化された文書を符号化したバイナリ・ストリームを順次読み出して、バイナリ・ストリームにおいて、上記文書の各情報要素を符号化したバイナリ・シーケンスを検出するステップと、
符号化された情報要素の各検出されたバイナリ・シーケンスにおいて、上記デコーダに知られたスキーマ参照リストにて定義された、上記第１のスキーマへの参照と、上記要素を符号化した値を含む内容フィールドと、上記内容フィールドの前に配置され、上記内容フィールドの長さを符号化した値を含む長さフィールドと、上記派生情報要素を符号化するために上記第２のスキーマが用いられることを示す第１の状態、並びに、上記派生情報要素のサブ要素のすべてを符号化するために上記第２のスキーマが用いられることを示す第２の状態、並びに、上記第１のスキーマおよび第２のスキーマを用いて上記派生情報要素が符号化されることを示す第３の状態のいずれかを有するスキーマ状況モードフィールドとを検出するステップと、
上記第１のスキーマへの参照が、上記検出されたバイナリ・シーケンスにおいて検出されない場合、上記検出されたバイナリ・シーケンスへ符号化された情報要素の第２のスキーマで定義された構造に基づき、上記検出されたバイナリ・シーケンスを復号化するステップと、
上記第１のスキーマへの参照が、上記検出されたバイナリ・シーケンスにおいて検出される場合、上記検出された第１のスキーマへの参照から、上記第１スキーマで定義された構造を有する、構造化された文書の情報要素を符号化したバイナリ・データを特定するとともに、上記情報要素を符号化したバイナリ・シーケンスの終了を決定するために、上記長さを符号化した値を用いて、上記バイナリ・ストリームを順次読み出す間に、上記特定されたバイナリ・データをスキップするステップとを含む復号化方法。
【請求項１４】
上記スキーマ状況モードフィールドが上記第１の状態にある時、上記符号化された情報要素は、スキーマ参照及び他の変更情報が除かれており、上記スキーマ状況モードフィールドが上記第２の状態にある時、上記情報要素のサブ要素は、スキーマ参照及び他の変更情報が除かれている請求項１３記載の復号化方法。
【請求項１５】
上記第１のスキーマへの参照を含むバイナリ・シーケンスの、長さをコード化した値を読み出して復号化するステップと、
上記第１のスキーマへの参照のバイナリ・シーケンスにおける位置、及び、上記復号化された長さの値の関数として、スキップすべきバイナリ・データの長さを決定するステップとをさらに含む請求項１３又は１４記載の復号化方法。
【請求項１６】
上記派生情報要素は、上記第１のスキーマにおいて、上記第２のスキーマの対応する情報要素の構造型に対して制限された構造型に関連付けされ、
上記派生要素を符号化したバイナリ・シーケンスは、内容フィールドと、該内容フィールドに付加される、上記第１のスキーマへの参照と、上記第２のスキーマにおいて定義された派生要素の構造型への参照とを備えている請求項１３から１５のいずれか１項に記載の復号化方法。
【請求項１７】
上記スキーマ状況モードフィールドが上記第３の状態にある時、上記派生情報要素は、上記第１のスキーマにおいて、上記第２のスキーマの対応する情報要素の構造型に対して拡張された構造型に関連付けされ、
上記派生情報要素の構造型は、上記第２のスキーマで定義された上記対応する情報要素の構造型を有する第１の部分と、上記派生情報要素に固有で、上記第１のスキーマで定義された構造型を有する第２の部分とを含み、
上記派生要素を符号化したバイナリ・シーケンスは、上記第２のスキーマへの参照を含むフィールドと、
上記第２のスキーマの対応する要素の構造型への構造型参照を含むフィールドと、
上記第１の部分を符号した値を含むフィールドと、
上記第１のスキーマへの参照を含むフィールドと、
上記第２の部分の構造型への構造型参照を含むフィールドと、
上記第２の部分を符号化した値を含むフィールドとを含む内容フィールドを含んでいる請求項１３から１６のいずれか１項に記載の復号化方法。
【請求項１８】
上記派生情報要素は、上記第１スキーマにおいて、上記第２のスキーマの対応する情報要素の名前に対して変更された名前を有し、
上記派生要素を符号化したバイナリ・シーケンスは、上記派生情報要素の名前が変更されたか否かを示す置換フラグと、上記置換フラグが変更されたことを示す場合、上記第１のスキーマへの参照を含むスキーマ参照フィールドと、上記第１のスキーマにおける上記派生情報要素の名前を指定した要素名参照とを備えている請求項１３から１７のいずれか１項に記載の復号化方法。
【請求項１９】
上記構造化された文書の符号化に用いる全てのスキーマへの参照を含む上記スキーマ参照リストは、上記構造化された文書を符号化したバイナリ・ストリームに関連するヘッダに読み込みされる請求項１３から１８のいずれか１項に記載の復号化方法。
【請求項２０】
デコーダがアクセスできない少なくとも第１のスキーマに定義されている構造を有し、当該デコーダがアクセスできる少なくとも第２のスキーマの変更の結果得られる、構造化された文書を符号化したバイナリ・ストリームを、少なくとも部分的に復号化するための、デコーダが使用する復号化方法であって、
構造化された文書は、互いにネストされた複数の情報要素を含み、上記文書の情報要素は、少なくとも上記第１のスキーマおよび第２のスキーマにて、それぞれ情報要素の要素構造を定義する要素の型と関連付けされ、
上記第１のスキーマは、上記デコーダがアクセスできず、上記第２のスキーマは、上記デコーダがアクセスでき、上記第１のスキーマは、上記第２のスキーマで定義された対応要素から派生した少なくとも１つの派生情報要素を定義し、
上記復号化方法は、上記第２のスキーマを用いて、上記構造化された文書を符号化したバイナリ・ストリームを順次読み出して、バイナリ・ストリームにおいて、上記文書の各情報要素を符号化したバイナリ・シーケンスを検出するステップと、
符号化された情報要素の各検出されたバイナリ・シーケンスにおいて、上記デコーダに知られたスキーマ参照リストにて定義された、上記第１のスキーマへの参照と、上記要素を符号化した値を含む内容フィールドと、上記内容フィールドの前に配置され、上記内容フィールドの長さを符号化した値を含む長さフィールドと、上記派生情報要素を符号化するために上記第２のスキーマが用いられることを示す第１の状態、並びに、上記派生情報要素のサブ要素のすべてを符号化するために上記第２のスキーマが用いられることを示す第２の状態、並びに、上記第１のスキーマおよび第２のスキーマを用いて上記派生情報要素が符号化されることを示す第３の状態、並びに、上記第１のスキーマおよび上記第２のスキーマを用いて上記派生情報要素が符号化されるとともに、上記用いられたのと同じ第２のスキーマが上記派生情報要素のサブ要素のすべてを符号化するために用いられることを示す第４の状態のいずれかを有するスキーマ状況モードフィールドとを検出するステップと、
上記第１のスキーマへの参照が、上記検出されたバイナリ・シーケンスにおいて検出されない場合、上記検出されたバイナリ・シーケンスへ符号化された情報要素の第２のスキーマで定義された構造に基づき、上記検出されたバイナリ・シーケンスを復号化するステップと、
上記第１のスキーマへの参照が、上記検出されたバイナリ・シーケンスにおいて検出される場合、上記検出された第１のスキーマへの参照から、上記第１スキーマで定義された構造を有する、構造化された文書の情報要素を符号化したバイナリ・データを特定するとともに、上記情報要素を符号化したバイナリ・シーケンスの終了を決定するために、上記長さを符号化した値を用いて、上記バイナリ・ストリームを順次読み出す間に、上記特定されたバイナリ・データをスキップするステップとを含む復号化方法。
【請求項２１】
上記スキーマ状況モードフィールドが上記第１の状態にある時、上記符号化された情報要素は、スキーマ参照及び他の変更情報が除かれており、上記スキーマ状況モードフィールドが上記第２の状態又は上記第４の状態にある時、上記情報要素のサブ要素は、スキーマ参照及び他の変更情報が除かれている請求項２０記載の復号化方法。
【請求項２２】
上記第１のスキーマへの参照を含むバイナリ・シーケンスの、長さをコード化した値を読み出して復号化するステップと、
上記第１のスキーマへの参照のバイナリ・シーケンスにおける位置、及び、上記復号化された長さの値の関数として、スキップすべきバイナリ・データの長さを決定するステップとをさらに含む請求項２０又は２１記載の復号化方法。
【請求項２３】
上記派生情報要素は、上記第１のスキーマにおいて、上記第２のスキーマの対応する情報要素の構造型に対して制限された構造型に関連付けされ、
上記派生要素を符号化したバイナリ・シーケンスは、内容フィールドと、該内容フィールドに付加される、上記第１のスキーマへの参照と、上記第２のスキーマにおいて定義された派生要素の構造型への参照とを備えている請求項２０から２２のいずれか１項に記載の復号化方法。
【請求項２４】
上記スキーマ状況モードフィールドが上記第３の状態にある時、上記派生情報要素は、上記第１のスキーマにおいて、上記第２のスキーマの対応する情報要素の構造型に対して拡張された構造型に関連付けされ、
上記派生情報要素の構造型は、上記第２のスキーマで定義された上記対応する情報要素の構造型を有する第１の部分と、上記派生情報要素に固有で、上記第１のスキーマで定義された構造型を有する第２の部分とを含み、
上記派生要素を符号化したバイナリ・シーケンスは、上記第２のスキーマへの参照を含むフィールドと、
上記第２のスキーマの対応する要素の構造型への構造型参照を含むフィールドと、
上記第１の部分を符号した値を含むフィールドと、
上記第１のスキーマへの参照を含むフィールドと、
上記第２の部分の構造型への構造型参照を含むフィールドと、
上記第２の部分を符号化した値を含むフィールドとを含む内容フィールドを含んでいる請求項２０から２３のいずれか１項に記載の復号化方法。
【請求項２５】
上記派生情報要素は、上記第１スキーマにおいて、上記第２のスキーマの対応する情報要素の名前に対して変更された名前を有し、
上記派生要素を符号化したバイナリ・シーケンスは、上記派生情報要素の名前が変更されたか否かを示す置換フラグと、上記置換フラグが変更されたことを示す場合、上記第１のスキーマへの参照を含むスキーマ参照フィールドと、上記第１のスキーマにおける上記派生情報要素の名前を指定した要素名参照とを備えている請求項２０から２４のいずれか１項に記載の復号化方法。
【請求項２６】
上記構造化された文書の符号化に用いる全てのスキーマへの参照を含む上記スキーマ参照リストは、上記構造化された文書を符号化したバイナリ・ストリームに関連するヘッダに読み込みされる請求項２０から２５のいずれか１項に記載の復号化方法。
【発明の詳細な説明】
〔発明の背景〕
１．発明の分野
本発明は、概してコンピュータ・システムの分野に関し、詳しくは、ＳＧＭＬ（標準汎用マークアップ言語：  Standard Generalized Markup Language）や、ＸＭＬ（拡張可能マークアップ言語：  Extensible Markup Language）等の汎用マークアップ言語に準拠する文書記述言語（document description）を使用して構造化文書（structured document ）を圧縮する方法およびシステムに関する。このような文書は、マルチメディア情報を含んでいてもよい。
【０００１】
２．関連技術の説明
ここ数年で、コンピュータ・ネットワークは、コミュニケーションにおける主要媒体となった。今では、コンピュータは、共有ネットワークに接続できるようになり、オペレーティング・システムは、各アプリケーションがメッセージを容易にやりとりできるようにし、インターネット基盤（Internet infrastructure）は、コンピュータが自分の相手を探し、アプリケーションが複雑なアルゴリズムを用いてお互いに同期できるようにしている。
【０００２】
このような相互接続状況において、汎用マークアップ言語が文書処理に対応するための解決手段となる。実際、文書の構造は、文書の使用において重要な役割を果たしている。文書の書式設定、印刷、又は索引作業は、実質的に、その構造に従って行われる。ＳＧＭＬは、初めのうち、文書の見栄え（プレゼンテーション：presentation）と、文書構造及び文書内容とを容易に分離させるために制定された。ＸＭＬには、構造を符号化する機能があるため、ＸＭＬは、様々な文書以外のアプリケーションに関心のあるコミュニティ（集団：community）からも注目された。ＸＭＬの利用者は、（例えば）、電子商取引、データベース及び知識表現のコミュニティにまで広がった。
【０００３】
現在、ＸＭＬ、及び、より一般的なマークアップ言語は、文書（メタデータ）の記述や文書（メタデータ）の構造化に幅広く使われている。構造化された文書には、互いにネスト（nest：入れ子）にされ得る、いくつもの情報要素（information element ）が含まれる。情報要素は、情報要素の要素型を識別するタグによって、識別及び互いに分離されている。構造化された文書には、一般的に、文書全体を表し、文書の開始及び終了を示すタグによって識別される第１情報要素又はベース要素が含まれている。この第１要素は、サブ情報要素（information sub-element）、例えば、テキストの段落を含み、各サブ情報要素は、要素の開始及び終了を示すタグによって識別される。タグは、情報要素の１以上の特性を指定する、タグの属性（attribute ）と関連付けされてもよい。
【０００４】
タグの内容（contents）は、一般的には、ユーザによって表示又は操作させようとしている情報を表す。タグの内容は、タグの種類に応じて、オプションであっても、必須であってもよく、ネストされた他のサブ情報要素、すなわち、順にタグで区切られ、内容及び属性を有するサブ情報要素を含んでもよい。
【０００５】
構造化された文書は、構造化された文書が「妥当（valid）」とされるために検証すべき規則を反映するスキーマと関連付けされることがある。また、それは、デフォルト値（default value ）、要素及び属性の型、型の階層についての情報を含む。妥当であること（validity）により、受け取った文書がスキーマに適合し、したがって、意図された意味を有することが保証される。さらに、それは、どのような種類（nature）か、すなわち、各記述項目（情報要素又は属性）の型を決定する。ＸＭＬ規格（XML standard）は、同様な構造を有するＸＭＬ文書のクラスのための文法を記述するために設計されたＸＭＬ用スキーマ言語を含む。
【０００６】
しかし、ＸＭＬは、冗長な言語であり、そのため処理の能率が悪く、送信するためのコストが高い。このため、ＩＳＯ／ＩＥＣ  １５９３８−１、より詳しくはＭＰＥＧ−７（Moving Picture Expert Group ）において、構造化された文書の記述を符号化（圧縮）するための方法及びバイナリフォーマット、並びに、上記バイナリフォーマットを復号化する方法を提案している。この規格は、とりわけマルチメディア・データ等、高度に構造化されたデータに対応することを目的としている。
【０００７】
圧縮効率を増すために、この方法は、スキーマ解析段階（phase ）を利用している。この段階では、内部テーブルが計算され、バイナリコードが各ＸＭＬの要素、型、属性に関連付けられる。この方法は、エンコーダおよび対応するデコーダに、同じスキーマの全知識の権限を与えている。
【０００８】
構造化された文書を符号化するために用いるスキーマの拡張が必要である際、最善の解決策は、拡張されたスキーマをデコーダが利用できるようにすることである。しかしながら、拡張されたスキーマへデコーダをアクセスさせるためにデコーダを容易に更新することができない場合がある。
【０００９】
〔発明の概要〕
本発明の目的は、必要とされるスキーマを全てデコーダが知らなくても、文書を部分的に復号化できるように、構造化文書を符号化するための方法を提供することにある。
【００１０】
本発明の別の目的は、上位互換性及び下位互換性を確保するための符号化方法を提供すること、すなわち、デコーダがアクセスできない少なくとも第１のスキーマに定義されている構造を有し、当該デコーダがアクセスできる少なくとも第２のスキーマの変更の結果得られる、構造化された文書を、上記デコーダが少なくとも部分的に復号化できるようにする符号化方法であって、構造化された文書は互いにネストされた複数の情報要素を含み、上記文書の情報要素は、少なくとも第１のスキーマおよび第２のスキーマにて、それぞれ情報要素の要素構造を定義する要素の型と関連付けされ、上記第１のスキーマは、デコーダがアクセスできず、上記第２のスキーマは上記デコーダがアクセスでき、上記第２のスキーマで定義された対応要素から派生した少なくとも１つの派生情報要素を上記第１のスキーマが定義することを特徴とする符号化方法を提供することにある。
【００１１】
本発明によると、上記符号化方法は、上記第１のスキーマと第２のスキーマとを用いて上記文書を符号化して、文書の情報要素ごとにその情報要素を符号化したバイナリ・シーケンスからなっているバイナリ・ストリームにするステップと、上記派生情報要素を符号化した上記バイナリ・シーケンスに、上記派生要素の上記構造が定義されている第１スキーマを指定する参照を挿入するステップとを含み、上記第１のスキーマを指定する上記参照は、上記文書の符号化に用いられる全てのスキーマについての参照を含んだスキーマ参照リストに定義されていて、このスキーマ参照リストに上記デコーダがアクセス可能である。
【００１２】
本発明の態様として、上記文書の各要素を符号化した上記バイナリ・シーケンスは、上記要素を符号化した値を含む内容（content ）フィールドと、上記内容フィールドの前に配置され、上記内容フィールドの長さを符号化した値を含む長さフィールドとを備えている。
【００１３】
本発明の別の態様として、上記第１のスキーマにおいて、上記派生情報要素は、上記第２のスキーマの対応する情報要素の構造型に対して制限された構造型に関連付けされ、上記派生要素を符号化したバイナリ・シーケンスは、内容フィールドと、該内容フィールドに付加される、上記第１のスキーマへの参照と、上記第２のスキーマにて定義された派生要素の構造型への参照とを備えている。
【００１４】
本発明の別の態様として、上記派生情報要素は、上記第１のスキーマにおいて、上記第２のスキーマの対応する情報要素の構造型に対して拡張された構造型に関連付けされ、上記派生情報要素の構造型は、上記第２のスキーマで定義された上記対応する情報要素の構造型を有する第１の部分と、上記派生情報要素に固有で、上記第１のスキーマで定義された構造型を有する第２の部分とを含み、上記派生要素を符号化したバイナリ・シーケンスは、上記第２のスキーマへの参照を含むフィールドと、上記第２のスキーマにおける対応する要素の構造型への構造型参照を含むフィールドと、上記第１の部分を符号化した値を含むフィールドと、上記第１のスキーマへの参照を含むフィールドと、上記第２の部分の構造型への構造型参照を含むフィールドと、上記第２の部分を符号化した値を含むフィールドとを含む内容フィールドを含んでいる。
【００１５】
本発明の別の態様として、情報要素を符号化したバイナリ・シーケンスは、当該情報要素の名前が変更されたかどうかを示す置換フラグ（substitution flag ）を含む置換フィールドと、上記置換フラグが変更されたことを示す場合、情報要素の新しい名前を指定した参照を含む要素名参照フィールドと、新しい名前の参照が定義されているスキーマへの参照を含むスキーマ参照フィールドとを備えている。
【００１６】
本発明の別の態様として、上記符号化済み文書における少なくとも１つの情報要素を符号化するバイナリ・シーケンスは、上記第２のスキーマの対応する要素については、上記第１のスキーマにおいて情報要素が変更されないことを示す第１の状態と、上記第２のスキーマの対応する要素については、上記第１のスキーマにおいて情報要素のサブ要素がいずれも変更されないことを示す第２の状態と、上記第２のスキーマの対応する要素については、上記第１のスキーマにおいて情報要素が変更されることを示す第３の状態とを有するスキーマ状況モードフィールドを含み、上記符号化された情報要素は、上記スキーマ状況モードフィールドが上記第１の状態にある時、スキーマ参照及び他の変更情報を含まず、上記情報要素のサブ要素は、上記スキーマ状況モードフィールドが上記第２の状態にある時、スキーマ参照及び他の変更情報を含まない。
【００１７】
本発明の別の態様として、上記符号化済み文書における少なくとも１つの情報要素を符号化するバイナリ・シーケンスは、上記第２のスキーマの対応する要素については、上記第１のスキーマにおいて情報要素が変更されないことを示す第１の状態と、上記第２のスキーマの対応する要素については、上記第１のスキーマにおいて情報要素のサブ要素がいずれも変更されないことを示す第２の状態と、上記第２のスキーマの対応する要素については、上記第１のスキーマにおいて情報要素が変更されることを示す第３の状態と、上記第２のスキーマの対応する要素については、上記第１のスキーマにおいて情報要素が変更されること、及び、上記第２のスキーマの対応する要素については、上記第１のスキーマにおいて情報要素のサブ要素がいずれも変更されないことを示す第４の状態とを有するスキーマ状況モードフィールドを含み、上記符号化された情報要素は、上記スキーマ状況モードフィールドが上記第１の状態にある時、任意のスキーマ参照及び任意の他の変更情報を含み、上記情報要素のサブ要素は、上記スキーマ状況モードフィールドが上記第２の状態又は第４の状態にある時、スキーマ参照及び任意の他の変更情報を含まない。
【００１８】
本発明の別の態様として、構造化された文書の符号化に用いる全てのスキーマへの参照を含む上記スキーマ参照リストは、上記構造化された文書を符号化したバイナリ・ストリームに関連するヘッダに挿入される。
【００１９】
本発明の別の目的は、デコーダがアクセスできない少なくとも第１のスキーマに定義されている構造を有し、当該デコーダがアクセスできる少なくとも第２のスキーマの変更の結果得られる、構造化された文書を符号化したバイナリ・ストリームを、少なくとも部分的に復号化するための復号化方法であって、構造化された文書は互いにネストされた複数の情報要素を含み、上記文書の情報要素は、少なくとも上記第１のスキーマ、および、第２のスキーマにて、それぞれ情報要素の要素構造を定義する要素の型と関連付けされ、上記第１のスキーマは、デコーダがアクセスできず、上記第２のスキーマは、上記デコーダがアクセスでき、上記第２のスキーマで定義された対応要素から派生した少なくとも１つの派生情報要素を上記第１のスキーマが定義することを特徴とする復号化方法を提供することにある。
【００２０】
本発明によると、上記復号化方法は、上記第２のスキーマを用いて、上記構造化された文書を符号化したバイナリ・ストリームを順次読み出して、バイナリ・ストリームにおいて、上記文書の各情報要素を符号化したバイナリ・シーケンスを検出するステップと、符号化された情報要素の各検出されたバイナリ・シーケンスにおいて、上記デコーダに知られたスキーマ参照リストにて定義された、上記第１のスキーマへの参照を検出するステップと、上記第１のスキーマへの参照が、上記検出されたバイナリ・シーケンスにおいて検出されない場合、上記検出されたバイナリ・シーケンスへ符号化された情報要素の第２のスキーマで定義された構造に基づき、上記検出されたバイナリ・シーケンスを復号化するステップと、上記第１のスキーマへの参照が、上記検出されたバイナリ・シーケンスにおいて検出される場合、上記検出された第１のスキーマへの参照から、上記第１スキーマで定義された構造を有する、構造化された文書の情報要素を符号化したバイナリ・データを特定するとともに、上記バイナリ・ストリームを順次読み出す間に、上記特定されたバイナリ・データをスキップするステップとを含む。
【００２１】
本発明の別の態様として、上記文書の各要素を符号化した上記バイナリ・シーケンスは、上記要素を符号化した値を含む内容フィールドと、上記内容フィールドの前に配置され、長さを符号化した値を含む長さフィールドとを備え、上記デコーダは、上記長さを符号化した値を、要素を符号化したバイナリ・シーケンスの終了を決定するために用いる。
【００２２】
本発明の別の態様として、上記復号化方法は、上記第１のスキーマへの参照を含むバイナリ・シーケンスの、長さをコード化した値を読み出して復号化するステップと、上記第１のスキーマへの参照のバイナリ・シーケンスにおける位置、及び、上記復号化された長さの値の関数として、スキップすべきバイナリ・データの長さを決定するステップとをさらに含む。
【００２３】
本発明の別の態様として、上記派生情報要素は、上記第１のスキーマにおいて、上記第２のスキーマの対応する情報要素の構造型に対して制限された構造型に関連付けされ、上記派生要素を符号化したバイナリ・シーケンスは、内容フィールドと、該内容フィールドに付加される、上記第１のスキーマへの参照と、上記第２のスキーマにおいて定義された派生要素の構造型への参照とを備えている。
【００２４】
本発明の別の態様として、上記派生情報要素は、上記第１のスキーマにおいて、上記第２のスキーマの対応する情報要素の構造型に対して拡張された構造型に関連付けされ、上記派生情報要素の構造型は、上記第２のスキーマで定義された上記対応する情報要素の構造型を有する第１の部分と、上記派生情報要素に固有で、上記第１のスキーマで定義された構造型を有する第２の部分とを含み、上記派生要素を符号化したバイナリ・シーケンスは、上記第２のスキーマへの参照を含むフィールドと、上記第２のスキーマの対応する要素の構造型への構造型参照を含むフィールドと、上記第１の部分を符号化した値を含むフィールドと、上記第１のスキーマへの参照を含むフィールドと、上記第２の部分の構造型への構造型参照を含むフィールドと、上記第２の部分を符号化した値を含むフィールドとを含む内容フィールドを含んでいる。
【００２５】
本発明の別の態様として、上記派生情報要素は、上記第１スキーマにおいて、上記第２のスキーマの対応する情報要素の名前に対して変更された名前を有し、上記派生要素を符号化したバイナリ・シーケンスは、上記派生情報要素の名前が変更されたか否かを示す置換フラグと、上記置換フラグが変更されたことを示す場合、上記第１のスキーマへの参照を含むスキーマ参照フィールドと、上記第１のスキーマにおける上記派生情報要素の名前を指定した要素名参照とを備えている。
【００２６】
本発明の別の態様として、上記符号化済み文書における少なくとも１つの情報要素を符号化するバイナリ・シーケンスは、上記第２のスキーマの対応する要素については、上記第１のスキーマにおいて情報要素が変更されないことを示す第１の状態と、上記第２のスキーマの対応する要素については、上記第１のスキーマにおいて情報要素のサブ要素がいずれも変更されないことを示す第２の状態と、上記第２のスキーマの対応する要素については、上記第１のスキーマにおいて情報要素が変更されることを示す第３の状態とを有するスキーマ状況モードフィールドを含み、上記符号化された情報要素は、上記スキーマ状況モードフィールドが上記第１の状態にある時、スキーマ参照及び他の変更情報を含まず、上記情報要素のサブ要素は、上記スキーマ状況モードフィールドが上記第２の状態にある時、スキーマ参照及びその他の変更情報を含まない。
【００２７】
本発明の別の態様として、上記符号化済み文書における少なくとも１つの情報要素を符号化するバイナリ・シーケンスは、上記第２のスキーマの対応する要素については、上記第１のスキーマにおいて情報要素が変更されないことを示す第１の状態と、上記第２のスキーマの対応する要素については、上記第１のスキーマにおいて情報要素のサブ要素がいずれも変更されないことを示す第２の状態と、上記第２のスキーマの対応する要素については、上記第１のスキーマにおいて情報要素が変更されることを示す第３の状態と、上記第２のスキーマの対応する要素については、上記第１のスキーマにおいて情報要素が変更されること、及び、上記第２のスキーマの対応する要素については、上記第１のスキーマにおいて情報要素のサブ要素がいずれも変更されないことを示す第４の状態とを有するスキーマ状況モードフィールドを含み、上記符号化された情報要素は、上記スキーマ状況モードフィールドが上記第１の状態にある時、任意のスキーマ参照及び任意の他の変更情報を含み、上記情報要素のサブ要素は、上記スキーマ状況モードフィールドが上記第２の状態又は第４の状態にある時、スキーマ参照及び任意の他の変更情報を含まない。
【００２８】
本発明の別の態様として、上記構造化された文書の符号化に用いる全てのスキーマへの参照を含む上記スキーマ参照リストは、上記構造化された文書を符号化したバイナリ・ストリームに関連するヘッダに読み込み（read in）される。
【００２９】
本発明の様々な特徴及びその好適な実施形態は、以下の説明と添付図面とを参照すれば一層理解が深まるであろう。
【００３０】
〔図面の簡単な説明〕
図１は、ＭＰＥＧ−７規格に準拠した構造化文書のツリー構造（木構造：tree structure）のバイナリフォーマットを示す図である。
【００３１】
図２は、ＭＰＥＧ−７デコーダのブロック図である。
【００３２】
図２ａは、図２に示すデコーダの詳細部のブロック図である。
【００３３】
図３は、本発明に係る符号化された情報要素のバイナリフォーマットを示す図である。
【００３４】
図４は、ツリー構造における相互に定義された要素型を示す図である。
【００３５】
図５は、ツリー構造に編成された情報要素を含む構造化文書を示す図である。
【００３６】
〔好適な実施形態の説明〕
図１を参照すると、ＭＰＥＧ−７規格に準拠した符号化された構造化文書１のバイナリフォーマットは、符号化モードを指定する文書ヘッダ２と、少なくとも１つの構造化情報要素又は構造化情報要素セット３とを含む。
【００３７】
文書ヘッダ２は、次に示すパラメータを符号化している。
【００３８】
−”allows_skipping"：  このパラメータは、符号化された文書において要素の長さをコード化するかどうかを指定する。また、このパラメータは、次に示す値を持つことがある。
【００３９】
００−長さをコード化しない。
【００４０】
０１−任意で長さをコード化する。
【００４１】
１０−長さのコード化が強制されている。
【００４２】
−"allows_partial_instantiation"：このパラメータは、文書における全てのサブツリー、又は構造化情報要素について、完全にインスタンス化するかどうかを指定する。また、このパラメータは、次に示す値を持つことがある。
【００４３】
０−部分的なインスタンス化を許可しない。全ての文書要素が符号化された文書に存在する。
【００４４】
１−部分的なインスタンス化を許可する。
【００４５】
−"allows_subtyping"：このパラメータは、サブツリーがポリモーフィズム（多態性：polymorphisms ）、つまり、データ型について考えられる様々なサブ型を有する情報要素あるいは要素属性を含むかどうかを指定する。また、このパラメータは次に示す値を持つことがある。
【００４６】
０−サブツリーにおいてポリモーフィズムを符号化しない。
【００４７】
１−ポリモーフィズムを許可する。
【００４８】
図１では、構造化された情報要素セット３は、要素セットヘッダ３１、要素３２及び／又は要素セット３を含む。上記要素セットヘッダ３１は、
−復号化段階において、要素の型についての潜在的な曖昧さ（多義性：ambiguity）を明確にすることを目的とするキー（鍵：key ）と、
−次に高い階層レベルの要素３における同様な要素又は要素セットの出現回数Ｎｂとを含む。
【００４９】
文書構造を定義するスキーマが、要素あるいは要素セットの型について必須の値を１つしか（a single mandatory value）指定しない場合、符号化された文書には、上記出現回数が現れない。
【００５０】
要素３２は、以下に示すフィールドを含む。すなわち、
−要素の符号化された値のビット長を指定する長さパラメータ３３と、
−要素値（element value）及び要素の属性の構造を指定するデータ型番号（data type number）を含む型３５と、
−例えば、アルファベット順に順序付けされた、要素の属性値３６と、
−要素の値自体を符号化している値３７とを含む。このフィールド（値３７）は、要素３２あるいは要素セット３の構造を有する１以上の要素、あるいは、要素が整数、文字列等の単純型（simple type）を有する場合の単純な値（simple value）を含んでよい。
【００５１】
符号化された文書のヘッダ２におけるパラメータ"allows_skipping"の値によっては、長さパラメータ３３は、なくてもよい。要素３２において長さが符号化されている場合、長さ情報を用いて、その前にある要素をスキップすることによって、文書中の特定要素への高速アクセスが可能となる。
【００５２】
フィールド３５、３６、３７は、符号化された要素になくてもよい。文書のスキーマにおいて、取り得る要素のデータ型が１つしかない場合、型番号３５は、符号化されない。スキーマで指定される型が属性を持たない場合、属性値３６は、符号化されない。要素の値３７は、要素が空であれば、例えば、文書を部分的にインスタンス化する場合、符号化されない。
【００５３】
図２を参照すると、ＭＰＥＧ−７のデコーダ１０は、デコーダ１０に入力される符号化済み文書７を復号化するために実行されるバイナリ構文コード（binary syntax code）１３を得るために、ＸＭＬスキーマ等のスキーマ９を受け取って処理するよう設計されたスキーマ・コンピレータ（compilator）１１を含み、デコーダ１０が復号化した文書８を、例えばＸＭＬ形式で出力する。
【００５４】
スキーマのコンパイル過程（compilation process）は、先行するスキーマ解析段階を利用し、バイナリ構文コードの形で定義される有限状態オートマトン（finite state automata ）１２を作成するために行われる。処理済みスキーマにおいて定義される各複合型（complex type）は、複合型コード化規則を表している有限状態オートマトンに変換される。上記符号化済み入力文書７は、バイナリ・ストリームの形でデコーダにかけられ、当該バイナリ・ストリームに対して、バイナリ構文コードが実行される。
【００５５】
図２ａでは、スキーマのコンパイル過程１１が４段階からなっている。スキーマ実現化（realization）の第１段階は、型継承の平坦化（flattening）と、名前空間のサポートの解決とからなっている。この段階では、実現化されたスキーマ（realized schema ）１５が生成される。第２段階は、構文ツリーを各複合型より生成することからなっている。このようにして生成された複数の構文ツリー１６は、次にバイナリ符号化を容易にし、圧縮率を改善できるように変換される。第３段階は、以下を生成するために、すなわち、各ツリー・ノードについて署名を生成し、続いて複数の正規化構文ツリー１７を生成するために、前の段階で生成された構文ツリーを正規化することからなる。これらの署名は、次の段階において、要素ヘッダ３１に現れるヘッダキーとツリー・ノードとの対応（correspondence）を生成するために使用される。第４段階は、復号化過程で使用される有限状態オートマトン１２を生成することからなる。
【００５６】
スキーマ実現化段階において、拡張された名前（expanded name）を要素、属性、型、要素グループ（element group）、それぞれに結び付けるために、スキーマを解析して、スキーマで使用される名前を全て挙げる。これらの名前がいわゆる名前空間を構成している。拡張された名前は、連続する、名前空間の識別子及び項目名として構成される。そして、各複合型の要素参照を、参照された要素の定義で置換することによって、実現化された複合型を生成する。
【００５７】
構文ツリー生成段階において、要素名を要素型に関連付けることによって、項目ノードが生成される。グループ・ノードを通じた包含関係によって連結された項目ノードは、構文ツリーを構成し、それらの構文ツリーは、各複合型に対して生成される。具体的には、構文ツリーは、結果として生じるバイナリフォーマットの簡潔さ（compactness）を改善するために縮小され（切り詰められ：reduce）、この過程は、非破壊的な方法で、複合型の定義を単純化することからなる。
【００５８】
構文ツリーの正規化は、構文ツリーのグループ・ノード毎に固有名を付するために行われる。この過程は、各ノードを順番付けし、最終的に、それらにキーを付することからなる。このキーは、オートマトンの構築段階で必要とされる。
【００５９】
署名は、要素毎、あるいは、要素グループ毎に生成される。あらゆるノードの署名は、その子ノードの署名を連結することにより生成される。代替グループ（alternative group ）や順番付けされないノード・グループの場合、ノードの署名は、アルファベット順にソートされ、それから付与される。順番付けされたノード・グループの場合、ノードの署名は、スキーマでの定義順に付与される。項目ノードの署名は、それらの要素名に等しい。
【００６０】
有限状態オートマトン生成段階において、複合型オートマトンは、以下に示す規則によって再帰的に定義される。
【００６１】
１．構文ツリーのあらゆるノードは、オートマトンを生成する。
【００６２】
２．複合型オートマトンは、そのルート・ノードによって生成されたオートマトンである。
【００６３】
３．あらゆるノードのオートマトンは、その子オートマトンをマージ（merge）することで生成され、このマージの内容は、ノードの種類（nature）に依存する
上記過程の最後に、それらの遷移であって、キーをコード化する遷移を作り出すために、オートマトンが実現される。これらのオートマトンは、２つの型状態（type state ）と、後者にリンクしている、各構文ツリーの各項目ノードのための要素遷移（element transition）とを含む。対応する要素が、復号化しようとする文書の入力ストリームに現れるときに、要素遷移が渡られる（cross）。型状態は、単純型の場合の特定データ型デコーダや、一般的な、あるいは、複合型の場合の特定データ型デコーダである特定のデコーダが動作したときのトリガになる。
【００６４】
場合によっては、文書の構造を定義するスキーマの拡張や修正が必要となる。デコーダに入力された符号化済み文書の新しいスキーマがある場合、符号化済み文書は、テキストフォーマット及びバイナリフォーマットの両方に対して、完全に上位互換性及び下位互換性がある。実際には、全体の記述を検証でき、名前空間を各要素と属性に付けることができる。さらに、型の階層化が可能になり、アプリケーションにとって、拡張性ポイント（extensibility points）を明確にすることができる。このようなスキーマの更新によって、拡張性及び互換性が引き起こす技術的な問題の多くが解決される。しかしながら、現在のところ、ＭＰＥＧ−７規格は、符号化済み文書の復号化に使用されるスキーマについて何ら情報を提示していない。したがって、あるスキーマを使用するように構成されたデコーダは、修正されたスキーマ（上位互換性がない）で符号化された文書を復号化することができない。この問題は、単に符号化済み文書を復号化する前に使用されるスキーマについての情報をデコーダに与えるだけで解決できる。別の方法として、このようなオートマトンあるいは構文ツリーを、デコーダが入力バイナリ・ストリームの形式の文書を復号化するために実行するバイナリ構文コードに変換してもよい。
【００６５】
ある場合には、スキーマの更新により生じる複雑さが問題となり得る。このような状況は、修正されたスキーマ（上位互換性）にアクセスできるように、デコーダを容易に更新できない場合、例えば、更新されるデコーダの数が非常に多い場合や、デコーダが他のスキーマを使用するように設計されていない場合に起こる。本発明の目的は、このような具体的な状況を解決するために、情報要素のバイナリフォーマットと、デコーダが既知のスキーマに対して修正または拡張された構造を有する文書を、デコーダが少なくとも“部分的に”復号化できる符号化方法及び復号化方法とを提案することである。
【００６６】
これに関して、符号化段階で互換性レベルが選択される。このレベルは、互換性が確実とされるべきスキーマセットという形で表される。符号化過程は、予想される互換性を確保するために必要な冗長度を追加する。極端な場合、現在のスキーマ１つだけについて互換性が必要であれば、冗長度は取り除かれ、その結果として生じるバイナリ符号化済み文書が現在のスキーマと適合するようになる。
【００６７】
基本的に、符号化過程は、符号化段階で使用されるスキーマについての情報を、符号化済み文書の中に追加する。この情報は、スキーマ識別子と、長さ情報とを含み、この情報によって、デコーダが使用できないスキーマを使用して符号化された文書における要素をスキップすることが可能となる。
【００６８】
スキーマ識別子は、デコーダによって知られたスキーマ識別子の辞書（dictionary）によって定義され、当該スキーマ識別子の辞書は、例えば、符号化済み文書のヘッダ２に挿入されたり、デコーダが使用するデコーダの初期設定及び構成（configuration ）ファイルの中に挿入されたりする。このスキーマ識別子の辞書は、受け取った符号化済み文書を復号化するためにデコーダが使用すると考えられる全てのスキーマ識別子を含む。デコーダは、以下に示すバイナリ構文を用いて、この辞書を読み出すことができる。
【００６９】
【表１】
0004615827.tif 000002
【００７０】
"NumberOfShemaIdentifiers"、及び、"SchemaIdentifier[]"は、それぞれ辞書内のスキーマ識別子の個数、及び、スキーマ識別子を含む配列を表し、"UINT_VLC"は、不定サイズの符号なし整数を符号化するためのフォーマットを示している。"UINT_VLC"フォーマットにおいて、整数は、整数のチャンク（chunk ）の無限集合によって符号化され、各チャンクは、５ビットからなる。各チャンクの最初の１ビットは、現在のチャンクの後に他のチャンクが続くかどうかを示し、残りの４ビットが整数を符号化する。
【００７１】
このバイナリ構文は、スキーマ辞書が、文字の形のスキーマ識別子のリストが後に続く個数を含んでおり、各スキーマ識別子のリストにおける位置は、スキーマ番号を自動的に規定している。当該スキーマ番号は、符号化済み文書で特定のスキーマを識別するために使用できる。辞書の読み出し過程は、以下の連続するステップおよび命令、すなわち、スキーマの個数"NumberOfSchemaIdentifiers "を辞書から読み出すステップと、カウンタｉを初期設定するステップと、"SchemaIdentifier[]"配列中のｉ番目の値を読み出すステップ、及び、０≦ｉ＜NumberOfSchemaIdentifiersを用いてカウンタｉをインクリメントするステップを含むループ命令とを含む。以下に示す表では、辞書は、３つのスキーマ識別子を含み、各スキーマは、辞書におけるスキーマ識別子の順位（rank）によって定義されるバイナリ・スキーマ番号と暗に関連付けされる。
【００７２】
【表２】
0004615827.tif 000003
【００７３】
バイナリ・スキーマ番号の長さ（ビット数）は、辞書にあるスキーマ識別子の個数の関数として定義され、Ｅ（ｌｏｇ2 (NumberOfSchemaIdentifiers)）と等しく、Ｅ（ｘ）は、次に高位の整数に切り上げされたｘに等しい。
【００７４】
図３に示すように、符号化済み文書の各型番号フィールド３５は、スキーマ番号フィールド３８と関連付けされており、スキーマ番号は、スキーマの辞書に定義されるスキーマ識別子に対応し、このスキーマ番号は、関連付けされた型が定義されるスキーマを識別する。
【００７５】
このようにして、本発明に係るエンコーダ及びデコーダは、数個のスキーマを使用して文書を符号化及び復号化できる。
【００７６】
スキーマＳ０と修正されたスキーマＳ１との間には、ＸＭＬ言語における３つのタイプの変更が考えられる。これらの変更が一緒に組み合わされることもある。３つのタイプのうち、１つ目は、グローバルな（大域的な：global）要素名を、他のグローバルな要素名へ置換することである。グローバルな要素は、あるスキーマにおいて、他の要素（別の要素にネストしていない要素）から独立に定義されている。このような変更は、ＸＭＬスキーマ言語において以下のように定義される。
【００７７】
ＸＭＬスキーマＳ０では、
…
<complexType Name="S0:t0"base="string">
…
<element name="e0" type="S0:t0"/>
となり、ＸＭＬスキーマＳ１では、
<element name="e1" type="S0:t0" substitution Group="S0:e0"/>
…
となる。
【００７８】
この構文（syntax）では、複合型"t0"と、型"t0"を有し、それぞれ、"e0"、"e1"と名付けられた２つの要素とが規定され、当該要素"e1"は、要素"e0"に置換されるものであることが規定される。"value 1 "の値をとる、上記のような要素"e1"は、スキーマＳ１に基づいて、ＸＭＬ文書中で以下のように表現される。
【００７９】
…
<e1>value1</e1>
…
本発明によれば、上記の変更は、置換フラグ４１と、置換された要素番号４３と、要素番号４３が定義されているスキーマ番号４２とを含む置換フィールド４を、要素３２に追加することによって符号化される。
【００８０】
上記置換フラグが０に設定されている場合、後に続く置換フィールド４２及び４３は、符号化された要素内に現れない。
【００８１】
"e1"の定義を含むスキーマＳ１で符号化された要素"e1"は、図３にあるように、以下のフィールド値を有している。
【００８２】
[length]1[S1][e1][S0][t0][value1]
ここで、[length]は、要素のバイナリコード化された長さであり、"1"は、置換が行われたことを表す置換フラグの値であり、[S1]と[S0]とは、スキーマの辞書で規定されたスキーマＳ１及びＳ０の符号化された番号であり、[t0]は、型"t0"の符号化された型番号であり、[value1]は、要素"e1"の値である"value1"を符号化した値であり、[e1]は、要素"e1"の符号化された番号である。
【００８３】
上記のようなバイナリコードは、本発明では、スキーマＳ０のみを（そして、それゆえに"e0"のみを）知るデコーダによって復号化され、復号化された要素は、以下のように解釈（interpreted）される。
【００８４】
<e0 DDL:IsSubstituted="true">value1</e0>
このように、デコーダは[e1]の意味を理解せず、"value1"は別の未知の要素に置換される要素"e0"の値だと考えてしまう。
【００８５】
スキーマＳ０と新しいスキーマＳ１との間で起こる２つ目の変更は、制限（restriction ）によって型"t0"から新たな型t1を派生すること（deriving）からなる。前記制限は、型の定義において、少なくとも１つの要素又は要素グループの最大出現回数を減らしたり、その最小出現回数を増やしたり、型（タイプ）t0をサブタイプ(sub-type)t1に変更したり、あるいは、型t0で予め定義された制約を順守する新たな要素グループを定義することからなる。
【００８６】
上記の変更を、以下に示す例において、ＸＭＬ用スキーマ言語で表現する。ＸＭＬスキーマＳ０は、以下に示すテキストの構文を含む。
【００８７】
0004615827.tif 000004
この例では、型"t0"は、要素"e1"の出現回数が任意であるとしてＸＭＬ用スキーマ言語で定義されている。型"t1"は、型"t0"の制限として定義され、型"t0"の特定のケースである０、又は１つの要素"e1"を含む。このように、型"t1"は、型"t0"の制約を強め、同じバイナリフォーマットが使用可能である。
【００８８】
符号化されるべき文書は、以下に示す情報を含む。
【００８９】
0004615827.tif 000005
これは、スキーマＳ０で定義される要素"e" の予期された（expected）型（タイプ）"t0"のサブタイプである型"t1"を持つ要素"e" を、文書が含むことを意味する。
【００９０】
上位互換性が必要でない場合、この要素は次のように符号化できる。
【００９１】
[length]0[S1][t1][value1]
ここで、"0"は、置換が起こっていないと設定された置換フラグの値である。
【００９２】
スキーマＳ０を知っていて、スキーマＳ１を知らないデコーダは、フィールド[length]及び[S1]を復号化する。スキーマＳ１は、スキーマの辞書では定義されていないので、デコーダは、要素"e" に関連する他のフィールドについては、スキーマＳ０を使用して解釈できないと推定し、長さ情報を利用して要素"e" をスキップする。デコーダがスキーマＳ１（そして、それゆえにＳ０）を知っていれば、デコーダは、要素"e"の元の構造を復旧（retrieve）する。
【００９３】
上位互換性が必要な場合、要素"e" は図３に記載の構造によって次のように符号化される。
【００９４】
[length]0[S0][t0][value1][S1][t1]
スキーマＳ０とＳ１との両方を知るデコーダは、符号化された要素"e" についてのフィールドを全て復号化できる。それから、長さフィールドと、復号化されたストリームの長さとを比較することによって、これ以上、サブタイピング（sub-typing）が無いことを推定し、要素"e" の元の構造を復旧する。デコーダがスキーマＳ０を知っていてスキーマＳ１を知らない場合、デコーダは、フィールドの初めの部分を復号化し、[S1]及び[t1]のフィールドは（長さフィールドを用いて）スキップする。したがって、デコーダは以下に示すテキスト形式のツリーを作成する。
【００９５】
0004615827.tif 000006
スキーマＳ０と新しいスキーマＳ１との間で起こる３つ目の変更は、拡張（extension ）によって、型"t0"から新たな型t1を派生することからなる。上位互換性を確実にする必要がある場合、新しい型t1は、型"t0"を有する第１部分と、新しいスキーマＳ１で定義する必要がある型"t1"を有する第２部分との２つの部分で定義される必要がある。
【００９６】
上記の変更を、以下に示す例においてＸＭＬ用スキーマ言語で表現する。ＸＭＬスキーマＳ０は、以下に示すテキストを含む。
【００９７】
0004615827.tif 000007
ＸＭＬスキーマＳ１では、新しい型t1が型t0の拡張として次のように定義される。
【００９８】
0004615827.tif 000008
上位互換性が必要な場合、符号化されるべきＸＭＬ文書は、以下に示す情報を含む。
【００９９】
<S0:e xsi:type="S1:t1">
<e1>value1</e1>
<e2>value2</e2>
</S0:e>
ここで、value1は、型"t1"において型"t0"の部分であり、"value2"は、型"t1"に特有な部分であり、型"t0"に加えられた部分である。この情報は、次のように符号化される。
【０１００】
[length]0[S0][t0][value1][S1][t1][value2]
デコーダがスキーマＳ０を知っている（Ｓ１は知らない）場合、バイナリ符号化された情報の第１部分を復号化し、t1部分 (すなわち、[t1][value2]）は、長さ情報を利用してスキップする。上記の過程が結果として以下に示すテキスト形式ツリーを導く。
【０１０１】
0004615827.tif 000009
このように、型t1の特定部分は、符号化されない。デコーダがスキーマＳ０とＳ１との両方を知っている場合、元のテキスト形式のツリーが復旧される。
【０１０２】
上記の処置（disposition ）は組み合わされてもよく、したがって、異なるスキーマにおいて定義され得る、型の複雑な階層の定義が可能となる。図４は、型t5と型t6とが型t4の２つの拡張部分（extension）であり、当該型t4が型t3の拡張部分であるような階層の例である。型t3は、型t1の制限部分（restriction）である。同様に、それぞれ型t8および型t9は、型t2の拡張部分である型t7の制限部分および拡張部分であり、型t2は、型t1の拡張部分である。t1からt9の各型が、それぞれ異なるスキーマＳ１からＳ９において定義されるとみなすと、スキーマＳ１、Ｓ３、Ｓ４、Ｓ５について互換性が必要であれば、型t5の要素は、以下に示す形で符号化される。
【０１０３】
[length]0[S1][t1][att1][value1][S3][t3][S4][t4][att4][value4][S5][t5][att5][value5]
ここで、フィールド[att-i ]は、それぞれ型t-i の、符号化された属性値であり、[att-i ][value-i ]は型t5のt-i 部分（-i＝１、４、５）である。スキーマＳ３、Ｓ５について互換性が必要であれば、型t5の要素は、以下に示す形で符号化される。
【０１０４】
[length]0[S3][t3][att3][value3][S5][t5][att5][value5]
ここで、フィールド[att3][value3]は、型t5のt1部分であり、型t3によってコード化され、フィールド[att5][value5]は、型t5のt4+t5 部分であり、型t5によってコード化される。
【０１０５】
当然、上記スキーマ間における１つ目の変更は、符号化される要素に置換フィールド４を追加することで２つ目、３つ目の変更と組み合わせてもよい。
【０１０６】
上記記載では、符号化される文書にバイナリ・置換フィールド（フィールド４１、４２、４３）と、各要素型に関連するスキーマ番号フィールドとを追加することにより、上位互換性が得られる。したがって、この解決法では、結果としての符号化文書のサイズが大きくなる。符号化を最も効果的にするために、符号化された文書の各部分が同じスキーマとリンクしていることが多いように思われる。そこで、本発明では、図３に示すように各符号化された要素３２にスキーマ状況モードを表すスキーマ状況コードを含むフィールド５を追加することを提案する。このフィールドは、対応する要素及びサブ要素が同じスキーマから来る記述を必要とするか否かを定義する。要素及びその要素の全てのサブ要素を符号化（及び復号化）するために同じスキーマを用いる場合、上位互換性を確実にするために追加された（スキーマ番号を含む）フィールド３８、４２は、符号化された要素から削除され、結果として圧縮率が高くなる。
【０１０７】
下記の表にスキーマ状況コードについて考えられる値を示す。
【０１０８】
【表３】
0004615827.tif 000010
【０１０９】
ここで、「変更なし」とは、要素の復号化処理のために使用されるスキーマが、要素自体に使用されるスキーマと同じであることを意味する。したがって、要素３２は、スキーマ番号フィールド３８および置換スキーマフィールド４２を含まない。
【０１１０】
「スキーマを固定」とは、要素、及び、その要素の全てのサブ要素（要素の全てのサブツリー）の復号化処理で使用されるスキーマが、要素自体に使用されるスキーマと同じであることを意味する。したがって、要素３２及び要素３２の全てのサブ要素は、スキーマ番号フィールド３８、４２及びスキーマ状況フィールド５のいずれも含まない。
【０１１１】
「スキーマを変更」とは、要素のスキーマが変更されることを意味する。したがって、スキーマ番号フィールド３８、４２が要素３２に出現する。
【０１１２】
スキーマ状況コードによって制御される仕組み（mechanism ）を図５に示す。図５は、３つのサブ要素５２、５３、５４を含むメイン要素５１を含んだ構造化文書のツリー構造を示す。要素５２は、２つのサブ要素５５、５６を包み、要素５４は、３つのサブ要素５７、５８、５９を包む。要素５５は、２つのサブ要素６０、６１を包む。
【０１１３】
要素５１、５３、５４、５７、５９は、０（「変更なし」）に設定されたスキーマ状況コード５で符号化される。要素５２のスキーマ状況コード５は、１０（スキーマを固定）に設定される。したがって、要素５２の全てのサブ要素５５、５６、６０、６１は、要素５２で定義された同じスキーマを用いて符号化され、これらのサブ要素には、スキーマ番号フィールド３８、４２、スキーマ状況コードフィールド５のいずれも含まれない。
【０１１４】
要素５８は、他のスキーマで修正及び定義されており、２つのサブ要素６２、６３を含む。したがって、要素５８のスキーマ状況コード５は、１１（「スキーマを変更」）に設定される。要素６２、６３が要素５８と同じスキーマで定義される場合、要素６２、６３のスキーマ状況コード５は、０に設定される。
【０１１５】
また、次に示すように、１つの考えられる値をスキーマ状況コード５に追加することによって最適化が行われてもよい。
【０１１６】
【表４】
0004615827.tif 000011
【０１１７】
要素のスキーマ状況コードが、１１０又は１１１に設定されると、要素のスキーマが変更される。このコードが１１０に設定される場合、要素のサブ要素は、スキーマ状況コード５を含む。このコードが１１１に設定されると、要素のサブ要素は要素のスキーマを用いて符号化される。
【０１１８】
図５の例では、要素５８のスキーマ状況コードは、要素６２及び６３が要素５８と同じスキーマで定義されることを規定するために、１１１に設定されてもよい。したがって、要素６２及び６３においてスキーマ状況コード５は必要ない。
【図面の簡単な説明】
【図１】  ＭＰＥＧ−７規格に準拠した構造化文書のツリー構造のバイナリフォーマットを示す図である。
【図２】  ＭＰＥＧ−７デコーダのブロック図である。
【図２ａ】  図２に示すデコーダの詳細部のブロック図である。
【図３】  本発明に係る符号化された情報要素のバイナリフォーマットを示す図である。
【図４】  ツリー構造における相互に定義された要素型を示す図である。
【図５】  ツリー構造に編成された情報要素を含む構造化文書を示す図である。
【図１】
0004615827.tif 000012
【図２】
0004615827.tif 000013
【図２ａ】
0004615827.tif 000014
【図３】
0004615827.tif 000015
【図４】
0004615827.tif 000016
【図５】
0004615827.tif 000017