JP5670859B2

JP5670859B2 - 記述方法、ｅｘｉデコーダおよびプログラム

Info

Publication number: JP5670859B2
Application number: JP2011232007A
Authority: JP
Inventors: 井裕介土; 井弓子坂
Original assignee: Toshiba Corp
Current assignee: Toshiba Corp
Priority date: 2011-10-21
Filing date: 2011-10-21
Publication date: 2015-02-18
Anticipated expiration: 2031-10-21
Also published as: US20130104033A1; JP2013089185A

Description

本発明の実施形態は、記述方法、EXI（Efficient XML(Extensible Markup Language) Interchange）デコーダおよびプログラムに関する。

EXIは、XML の文法知識(スキーマ) を用いて、XML のコンパクトなバイナリ表現を作成する技術であり、非特許文献1（John Schneider and Takuki Kamiya. Efficient XML Interchange (EXI) Format 1.0. W3C Recommendation, March 2011. http://www.w3.org/TR/exi/.）で定義されている。特許文献1は、このEXI を用いてデータを圧縮格納する方式を開示している。

EXI のモードのうち、スキーマ由来文法(Schema-Informed Gramar) は、スキーマから文章の各部分が取り得る状態遷移を表す状態機械を生成し、この状態機械を用いて文章を符号化する。

特開2011−146036号公報

John Schneider and Takuki Kamiya. Efficient XML Interchange (EXI) Format 1.0. W3C Recommendation, March 2011. http://www.w3.org/TR/exi/.

EXI による情報交換を目的とした際に、標準あるいは基盤となるスキーマ(基本スキーマ) に対して、個々のベンダ等が拡張したデータ型(拡張スキーマ) を定義することが考えられる。このとき、拡張スキーマの個別定義により、個々のベンダ拡張スキーマ全体に対する状態機械（型文法）がそれぞれ必要になってしまい、実装に必要となるROM サイズ等の記憶領域サイズが増大してしまう。

これは、EXI においては符号化・復号に用いる状態機械の状態数が変化することで符号のビット幅が変化してしまうことに由来する固有の問題である。

本発明の一実施形態は、少なくとも１つのデータ型を定義した、XMLによる基本スキーマと、前記基本スキーマを拡張した拡張スキーマとの両方に対応可能な、EXIに基づくエンコードまたはデコードを行うための、前記拡張スキーマおよび前記拡張スキーマに対応するXML文書の記述方法である。

前記拡張スキーマは、前記基本スキーマをインポートするとともに、前記少なくとも１つのデータ型のうちの1つを派生させた、拡張されたデータ型をさらに定義する。

前記拡張スキーマに対応するXML文書は、XMLスキーマインスタンス仕様で定義された型拡張のための属性を用いて、前記拡張されたデータ型を指定して記述される。

また、本発明の一実施形態は、EXIストリームをデコードするEXIデコーダであって、文法ストア、ストリーム入力部、パーサ部を備える。

前記文法ストアは、少なくとも１つのデータ型を定義したXMLによる基本スキーマからEXI仕様にしたがって生成される第1の型文法と、前記基本スキーマをインポートするとともに、前記少なくとも１つのデータ型のうちの1つを派生させた、拡張されたデータ型を定義した拡張スキーマから、前記EXI仕様にしたがって生成される型文法のうち、前記第1の型文法と共通する文法を除いた第2の型文法とを記憶する。

前記ストリーム入力部は、EXIストリームを受信する。

前記パーサ部は、前記EXIストリームが前記基本スキーマに対応するものであるときは、前記第1の型文法に基づき前記EXIストリームをデコードし、前記EXIストリームが前記拡張スキーマに対応するものであるときは、前記第1の型文法と前記第2の型文法の両方に基づき、前記EXIストリームをデコードする。

本発明の実施形態に係る複数スキーマ対応EXIデコーダの構成を示す図。 EXIストリームの構成例を示す図。従来方式に基づくEXI文法のメモリ格納方式のイメージ図。本実施形態に基づくEXI文法のメモリ格納方式のイメージ図。文法ストアの構成例を示す図。基本スキーマの構成例を示す図。基本スキーマに対応するXML文書の例を示す図。従来方式による拡張スキーマの例を示す図。従来方式による拡張スキーマに対応するXML文書の例を示す図。本実施形態による拡張スキーマの例を示す図。本実施形態による拡張スキーマに対応するXML文書の例を示す図。基本スキーマに定義されたorderTypeに対応する状態遷移図。基本スキーマに定義されたplateTypeに対応する状態遷移図。従来方式による拡張スキーマに定義されたorderTypeに対応する状態遷移図。従来方式による拡張スキーマに定義されたplateTypeに対応する状態遷移図。従来方式による拡張スキーマに定義されたpatternedPlateTypeに対応する状態遷移図。本実施形態による拡張スキーマに定義されたorderTypeに対応する状態遷移図。本実施形態による拡張スキーマに定義されたplateTypeに対応する状態遷移図。本実施形態による拡張スキーマに定義されたpatternedPlateTypeに対応する状態遷移図。

図1 に、本発明の実施形態に係る複数スキーマ対応EXIデコーダの構成を示す。

ストリーム入力部11は、EXI ストリームの入力を受け取る。入力されるストリームは、TCP/IP あるいはUDP/IP のようなネットワーク、もしくは、ファイルシステムからの読み出しによる任意のバイト列である。ストリーム入力部11は、EXIストリームに含まれるヘッダおよびヘッダオプションをヘッダ解析部12に、ストリーム本体をパーサ部17に渡す。

ヘッダ解析部12は、EXI ストリームのヘッダおよび、ヘッダオプションを解析し、EXIストリームのオプションを抽出する。オプションは、スキーマId(schemaId) を含んでいる。schemaId は、文法選択部13と、ストリングテーブル初期化ベクタ選択部15に渡される。

文法ストア14は、パーサ部17が利用する可能性がある全てのスキーマに対応する全てのEXI 文法と、個々の文法がどのschemaId において利用されるのかという情報（文法セット表）とを保持している。当該情報は、ビットマップ等の手段により構成される。また、文法ストア14は、一部の文法については、型（Type）を表わすQName（Qualified Name）と文法との対応関係を示すテーブルを持つ。当該一部の文法は、たとえばxsi:typeから呼び出される文法である。xsi:typeは、後述するように、特にXML-Schema-Instance 仕様により定義される、XML要素解釈の際の型指定を明示的に行うための仕様である。文法ストア14の構成例を図5 に示す。

図5における“1”は、該当する文法が利用、“0”は該当する文法が利用されないことを示す。たとえばschemaId 4の場合、文法A、Bは利用されるが、文法Zは利用されない。なお文法A、B、・・・Zは、文法名を抽象的に表したものである。ns0:a、ns0:b、ns1:a等は、QNameを抽象的に表したものである。ns0,ns1が名前空間に相当し、a,b等が、ローカル名に相当する。

より詳細に、型文法はそれぞれの型に対応する状態機械（文法）であり、左側のschemaId をキーとしたビットマップで個々のschemaId で利用可能な文法が示される。また、図中右側のテーブルはQName(名前空間と名前との組) をキーとして、型文法をルックアップする。

文法選択部13は、ヘッダ解析部12から通知されたschemaId から、利用する文法の組と、文法セット表の該当部分（schemaId に対応する文法セット表）を、文法ストア14より選択し、パーサ部17に送る。

ストリングテーブル初期化ベクタストア16は、パーサ部17が利用する可能性がある全てのストリングテーブル初期化ベクタと、schemaId との対応関係を保持している。ストリングテーブル初期化ベクタストア16の具体的な構成は、全てのストリング（全てのストリング初期化ベクタ）が保存されているROM 領域と、schemaId それぞれに対応するストリングへの参照の列で構成するなどといった方法で実現する。

ストリングテーブル初期化ベクタ選択部15は、ヘッダ解析部12から通知されたschemaId から、利用するストリングテーブル初期化ベクタを決定し、パーサ部17に送る。

パーサ部17は、ストリングテーブル初期化ベクタ選択部15から送られたストリングテーブル初期ベクタにより、ストリングテーブルを初期化（上書き）し、初期化されたストリングテーブルと、文法選択部13から与えられた文法および文法セット表とから、ストリーム入力部11から渡されたストリームを処理する。すなわち当該ストリームを、XML 文書を構成するイベント列（たとえばSAXイベント）へ変換し、変換したイベント列を、アプリケーション（図示せず）に渡す。アプリケーションでは当該イベント列から、元となるXML文書の内容を解釈し、所定の動作を行う。

ストリングテーブルおよび初期化ベクタの詳細な説明については、後述する。

以下に、EXI ストリームの構造、EXI ストリームヘッダの構造、EXI 文法の構造、ストリングテーブル初期化ベクタ、パース処理(特にxsi:type を利用したもの) について説明する。

EXIストリームは、EXI ストリームヘッダとヘッダオプション、本文に相当するストリームから成る。ヘッダオプションは、特定のスキーマにもとづくEXI文書（EXIのストリーム）である。

ストリームは、イベントコード(EventCode) と値(Value) の組が繰り返される構造になっている。XML におけるタグ(あるいはエレメント) による文書の構造化は、上記値の部分に、子要素に相当する、イベントコードと値の組の繰り返しが再帰的に登場することにより表現される。EXIストリーム本体の構造例を図2に示す。このイベントコードが、EXI文法により定義されることで、XML文書構造のEXIへの効率的なエンコーディングが実現される。

EXI ストリームヘッダの構造は、非特許文献1の第5節に定義されている。ヘッダ構造は、必ず含まれる固定長のヘッダ部分に加え、EXI オプションが存在する場合がある。存在するかどうかは、ヘッダ部分のPresence Bit により区別される。EXIオプションは、それ自身がEXI 仕様により定められるスキーマにより記述されたEXI 文書である。

EXI オプションにはさまざまな記述が可能であるが、本実施形態において重要な要素はschemaId である。schemaIdは、送信側のEXI エンコーダが、本EXI デコーダに、EXIストリームに含まれるデータが、どのスキーマを利用してエンコードされたものであるか（つまり、元となるXML文書が、どのスキーマを利用してEXIストリームにエンコードされたか）という情報を伝えるための文字列である。

XML文書は、イベント列に変換された上、当該スキーマからEXI仕様にしたがって生成されるEXI文法にしたがって、EXIエンコーダにより、EXIストリームにエンコードされる。スキーマからEXI 文法を生成する方法は、非特許文献1に記述されている。

ここでは、文法に含まれる要素について説明する。一つの文法は、スキーマで定義される各々の型(Type) に対して、各々一つの状態機械を定義したものである。具体的には個々の文法は、次の構成を含む。

・各々の型のラベルと、これに対応する状態機械
・状態機械を構成する状態の集合(および初期状態と終端状態の定義)
・各々の状態からその状態機械を構成する自身または他の状態に対する遷移

また、EXI の文法は、各々の状態遷移に以下の要素を定義する。

・イベント型(SD: StartDocument, SE: StartElement, AT: Attribute, CH: Character, EE:EndElement, ED: EndDocument, など)
・イベントに対する補助要素(XML要素を構成するタグのラベルや、属性のキーなど)
・イベントの値の型(EXI 仕様におけるTerminal): 他の「型」か、あるいは整数（integer）、文字列(string)などの組み込み型を示す
・次の遷移状態(EXI仕様におけるNonTerminal)

文法ストア14は、以上の形式で定義される文法を格納する記憶領域である。個々の型に対応する型文法はそれぞれ独立して格納される。その上で、文法ストア14は、型を示すQName と、型文法との関係を、schemaId 毎に記録する文法セット表（図5参照）を持つ。

文法選択部13は、ヘッダ解析部12から入力されたschemaId をもとに文法セット表から該当する部分を読み出し、schemaId に対応する文法セット表と、該当する文法を、パーサ部17に渡す。文法セット表には、個々の型文法への参照が含まれるため、パーサはschemaId とQName の組から、各々の型文法を知ることができる。

ここでストリングテーブルおよび初期化ベクタについて詳しく述べる。

EXI においては、既知の文字列の再送を避けるためにストリングテーブルが用いられる。

ストリングテーブルは、非特許文献1 の第7.3 節で定義されている、規定文字列ならびにドキュメント中に登場した文字列の再利用のために用いる表である。エンコーダとデコーダで同じ内容に初期化され、また文字列の送出の際にエンコーダ側とデコーダ側で同様に変更される。スキーマ内に登場する文字列や、XMLドキュメント内に2度以上登場する同じ文字列を、番号で参照するために用いる。具体的には、ストリーム中に登場した文字列に順に番号を振り、これを再利用する。具体的には、イベントコードに対応する値の部分に当該番号が指定される。なお、番号が振られない文字列については、その文字列がそのまま、イベントコードに対応する値の部分として含まれる。

文法生成に利用したXML スキーマに含まれる名前空間のURL は、ストリングテーブルの初期化に用いられる。例えばスキーマ中に含まれるタグ名の表現(QName) は、この初期化されたストリングテーブルにおける名前空間を用いた番号で指定を行う。従って、同じ文法構造であっても、利用するスキーマによって、ストリングテーブルに含まれるURL の初期値が異なる。

これを解決するために、個々のschemaId に対応するストリングテーブル初期化ベクタを用意し、これをメモリに格納しておく(ストリングテーブル初期化ベクタストア16)。また、入力されたEXI ストリームのschemaId に対応して、ストリングテーブルの初期化ベクタを選択する(ストリングテーブル初期化ベクタ選択部15)。選択したストリングテーブル初期化ベクタをパーサ部17に渡し、パーサ部17は、渡されたストリングテーブル初期化ベクタで、ストリングテーブルを初期化する。

ストリングテーブルについてさらに具体的に説明する。ストリングテーブルは、URI(URL) / プレフィックス/ QName 中のURI とローカル名/ 値の4 つで用いられる。また、効率的な符号化のために、ストリングテーブルは、以下のパーティションに分割される。

・URI: “URI” と、QName 中のURI 部を格納する
・プレフィックス: プレフィックスが所属するURI 毎に作成する(特定のモード以外では利用しないため、本稿では触れない)
・ローカル名: ローカル名が所属する名前空間毎にテーブルを作成する
・値: その値が登場したエレメント(要素) あるいはアトリビュート(属性) が所属する名前空間と、グローバルな値を格納するパーティションとの両方に動的に記述する。

以下、URI パーティションならびにローカル名パーティションの初期化について具体的に述べる。

まず、説明のため基本スキーマを図6に示す。図6に示した基本スキーマは、架空の食器メーカーSaucersCo. (saucers.example.com) が以下の要件で定義した注文書のXML スキーマの抜粋である。

1. 一つの注文書は複数(上限なし) の種類の皿の注文からなる
2. 皿は色で指定する

このスキーマに基づく注文書の例を図7 に示す。この文書では、青色の皿を14 枚注文している。また図6の基本スキーマに定義された型に対応する状態遷移図を図12および図13に示す。図12はorderTypeの状態遷移図、図13はplateTypeの状態遷移図を示す。

URI パーティションの初期化方法は、具体的に非特許文献1 の付録D.1 に記述されている。

これに従うと、例えば図6に示す基本スキーマにおける初期化ベクタは以下のような形になる。

Compact ID の0 から3 までに対応するURI が仕様により定まる定数であり、Compact ID の4 以降がスキーマに由来する名前空間である。

また、図10に示す本提案方式による拡張スキーマ（基本スキーマをimportしており、詳細は後述）には、2つの名前空間が存在する。これらの名前空間は辞書順（アルファベット順）に追加する必要があるため、この例における初期化ベクタは以下のようになる。

同様に、ローカル名に対応するストリングテーブルの初期化ベクタは、それぞれの名前空間毎に作られる。XML の規約から導出される初期化ベクタについては、非特許文献1 の付録D.3 を参照されたい。ここでは、特にスキーマに由来するもののみ記述する。

図6に示した基本スキーマに由来するローカル名は以下の通りである。

同様に、図10に示した拡張スキーマに由来するローカル名は以下の通りである。

上述したように、ストリングテーブル初期化ベクタ選択部15は、ヘッダ解析部12から通知されたschemaId に応じて、ストリングテーブル初期化ベクタ（上記の例では、URI パーティションならびにローカル名パーティション等の各テーブル）を選択し、パーサ部17に通知する。パーサ部17では、通知された初期化ベクタで、ストリングテーブルを初期化する。

EXI におけるパーサ部17でのパース処理は、次の手順で行う。具体的には、これはプッシュダウンオートマトンに相当する。パーサ部17には、文法選択部13から、schemaIdに対応する文法セット表が与えられている。初期文法はEXI 仕様により決まっているので、当該文法セット表に対応する初期状態から、以下のようなステップでデコードを開始する。

1. 現在の文法が指示するビット幅でストリームからデータを読み出し、これをイベントコード（前述したイベントコード(EventCode) と値(Value) の組に含まれるイベントコード）とする
2. イベントコードに対応する遷移を、現在の状態に対応する遷移表から読み出す
3. イベント型を記録し、対応する値（前述したイベントコード(EventCode) と値(Value) の組に含まれる値）を読み出す。ここでの「値」は遷移に記録された「値の型」により読み出し方法が規定される。
なお、イベント型がSE あるいはAT の場合は、対応する値は、他の型文法そのものを示す場合がある。このときは、パース処理は再帰的に、指示された型文法に移行し、移行した型文法が終了(terminate) すると、現文法の処理に復帰する。このため、遷移先の文法を示す値のことをterminal と呼ぶ。
4. 本文法が継続する(まだ読み出すべきイベントが存在する) 場合には、次の状態を示す。現文法が終了しないため、このときの値をnonterminal と呼ぶ。

パース処理のさらに詳細な説明については、非特許文献1を参照されたい。

EXI の仕様はさまざまな定義が存在するが、特にxsi:type の仕様について本実施形態に関係するため説明する。

xsi:type とは、前述したように、特にXML-Schema-Instance 仕様（名前空間http://www.w3.org/2001/XMLSchema-instance により規定される。ここではxsi をXMLSchema-instance の接頭辞とする。）により定義される、XML要素解釈の際の型指定を明示的に行うための仕様である。

XML では、この型指定は、xsi:type 属性により型名を指定することにより行う。EXI においても同様で、要素を解釈する際にAT(xsi:type) イベントが登場したら、その時点で文法を切り替えることになる。文法切り替えを実装したデコード処理のステップを以下に示す。

1. 現在の文法が指示するビット幅でストリームからデータを読み出し、これをイベントコードとする
2. イベントコードに対応する遷移を、現在の状態に対応する遷移表から読み出す
・もし、イベントコードがAT(xsi:type) であった場合、属性が示すQName（当該イベントコードに対応する値）を用いて文法表をルックアップして、QNameに対応する文法を特定し、現在使用中の文法を、当該特定した文法に切り替え、ステップ1 から読み出しを開始する。
・そうでない場合は、処理を続行する。
3. イベント型を記録し、対応する値を読み出す。ここでの「値」は遷移に記録された「値の型」により読み出し方法が規定される。なお、イベント型がSE あるいはAT の場合は、対応する値は、他の型文法そのものを示す場合がある。このときは、パース処理は再帰的に指示された型文法に移行し、移行した型文法が終了(terminate) すると現文法の処理に復帰する。このため、遷移先の文法を示す値のことをterminal と呼ぶ。
4. 本文法が継続する(まだ読み出すべきイベントが存在する) 場合に次の状態を示す。現文法が終了しないため、この値をnonterminal と呼ぶ。

ここで、xsi:any属性の利用と、その際のQNameの符号化の詳細に説明する。

ここでは、特に厳格スキーマ由来文法(strict schema-informed grammar) における例を示す。他のモードについては非特許文献1を参照されたい。

非特許文献1 の節8.5.4.4.2 において、型がnamed subtype (名前を持つ派生型) を持つ、あるいは、union である場合に、型文法に、AT(xsi:type) を追加することとなっている。

例えば、図10に示した本提案方式による拡張スキーマにおいては、plateType はpatternedPlateType という派生型を持つことになるため、plateType にはAT(xsi:type) の遷移が追加される。図6の基本スキーマにおけるplateType の状態遷移図を図13、図10の本提案方式による拡張スキーマ（インポート（import）による拡張スキーマ）におけるplateType の状態遷移図を図18に示す。

ここで、import による拡張スキーマでは、xsi:type 属性によりplate タグの型をplateTypeからpatternedPlateType に変更できる。このときの型の指定はQName で行うが、この指定に、前述したストリングテーブルを用いる。具体的には、名前空間http://saucers.example.com/patternedOrder を示すCompact ID(5) と、これに対応する名前空間に所属するローカル名patternedPlateType に対応するCompact ID(1) の組により、型が指定される。

本実施形態のデコーダは、このCompact IDの値の組により名前空間、ローカル名を特定し、文法ストア14をルックアップし、現在のschemaId で使用可能かつ対応する型名（ここではpatternedPlateType）を持つ文法に切り替えを行うことができる。

以下、前述した基本スキーマ（図6）、および当該スキーマに基づく注文書（図7）をベースに、本実施形態の具体例を示す。

上述したように、図6は、架空の食器メーカーSaucersCo. (saucers.example.com) が以下の要件で注文書のXML スキーマを定義したものであった。

ここで、SausersCo. が事業拡大に伴い、模様つきの皿の取り扱いをはじめたとする。先の要件定義には、皿の模様は含まれなかったため、基本スキーマに基づく注文書では、同じ色で違う模様の皿を取り扱うことができない。そこで何らかの方法でスキーマを拡張する必要がある。

単純に考えると、従来スキーマをそのまま拡張すれば良いということになる。

例えば、図8 は、基本スキーマにおけるplateType を拡張したpatternedPlateType を実装したもの（従来方式による拡張スキーマ、あるいは単純な拡張スキーマと称する）である。当該従来方式による拡張スキーマで定義された各型に対応する状態遷移図を図14、図15、図16に示す。図14は、orderTypeに対応する状態遷移図、図15は、plateTypeに対応する状態遷移図、図16は、patternedPlateTypeに対応する状態遷移図を示す。

注文者は、模様なしの皿を注文する際はplate タグ(plateType 型) を用い、模様のある皿を注文する際にはpatternedPlate タグ(patternedPlateType 型) を用いて、XML文書を記述すればよい。模様のある皿を注文する場合のXML文書の記述例を図9に示す。

XML の処理であればこの方式で何の問題もないが、この注文を業務の効率のためにEXI で行おうとすると、非効率な面が存在することがわかる。具体的には、order タグ(orderType 型) の変更である。

スキーマ由来文法（Schema-Informed Grammar）で動作するEXI においては、XML スキーマにより定義される型情報に従って文法を生成する。文法とは即ち状態機械であり、これをエンコーダとデコーダが共有し、状態遷移に一定の方式により小さい番号を割り当て、これを送信するのに最小限のビット数を用いることによりエンコーダ側とデコーダ側で文書情報を共有する。

ここで、order タグが変化してしまうと、エンコーダ側とデコーダ側で情報の共有ができなくなってしまう。具体的には、状態遷移の番号が変化してしまう点、また、ある状態からの遷移の総数を表現するのに最小限のビット数が変化する点の2点から、デコードに失敗してしまう。

例えば、遷移の総数が4 から5 に増えると、状態を表現するのに必要なビット数は2 ビットから3 ビットになる。このビット数は状態機械から決定するため、エンコーダ側とデコーダ側で状態機械を共有できていないと読み取りのビット数がずれてしまい、以降のデコードができなくなる。

図12および図14 に基づき、従来方式の拡張スキーマを用いた場合のorder タグの変化を示す。上述したように、図12は、基本スキーマにおけるordertype(orderタグ)に対応する状態遷移図、図14は、従来方式による拡張スキーマにおけるodertypeに対応する状態遷移図を示す。両図を比較して分かるように、従来方式による拡張の場合、ordertypeの状態遷移図が変化するため、状態機械の共有が、困難であることがわかる。つまり、タグを追加したことにより状態数が変化してしまい、その結果EXI のイベントコードの作成方法も変化してしまう。なお、図中、２種類の各弧についているラベルはそれぞれ、イベント名と繰り返しルールである。

従って、図8 に示す従来の拡張の方法では、EXI においては図6の基本スキーマと、図8の従来方式の拡張スキーマの両方に対応する状態機械を持つ必要がある。このことを図3に示す。図3は、従来方式に基づくEXI 文法のメモリ格納方式のイメージ図である。このように、スキーマが増えるにつれ実装しなければならないコードの量が線形に増えてしまい、非効率である。

これに対し、本提案方式においては、拡張スキーマは、基本スキーマをimportする、という形式で定義する。その上で、拡張スキーマでは、基本スキーマの型を派生させる。この方式を取った場合のみ、基本スキーマに対応する状態機械を一切変更することなく、拡張スキーマの差分のみに対応する状態機械を追加実装することにより、基本スキーマと拡張スキーマの両方を利用可能になる。

図10は、本提案方式による拡張スキーマの例を示す。また、当該本提案方式による拡張スキーマで定義された各型に対応する状態遷移図を、図17、図18、図19に示す。図17は、orderTypeに対応する状態遷移図、図18は、plateTypeに対応する状態遷移図、図19は、patternedPlateTypeに対応する状態遷移図を示す。

図10の拡張スキーマは、基本スキーマとは異なるXML 名前空間に定義される。その上で、基本スキーマをimport 文により取り込んだ上で、plateType を拡張することでpatternedPlateType を定義する。なお、patternedPlateType に対応するタグ名の明示的な定義はされていない点に注意されたい。

図11 は、図10の本提案方式に基づいた拡張スキーマによる注文文書の例を示す。

このXML文書は、XML として見ると一見煩雑に見えるが、データモデルとしてはシンプルである。拡張スキーマに対応する名前空間としてpoを定義している。名前空間xsi はXML 仕様に基づくものである。

order タグは、基本スキーマに基づいて作られており、3つのplate タグを内包している。このうち2つめのplate タグに、xsi:type 属性により明示的にpo:patternedPlateType の型指定が行われている。po:patternedPlateTypeはplateType から派生しているため、ここで型を置き換えることが可能となる。具体的には、これによりpattern 属性を記述可能になる。なお、図11の例の場合、イベントコードAT(xsi:type)に対応する値として po:patternedPlateTypeが指定されるが、po:patternedPlateTypeはストリングテーブルに存在しないため、このテキストがそのまま値として指定される（前述した表4および表5参照）。イベントコードAT(xsi:type)に対応して文法を切り換える場合、po（すなわちhttp://saucers.exmaple.com/patternedOrder）が、図5に示した名前空間（ns0,ns1等に対応）として、patternedPlateTypeがローカル名（a,b等に対応）として用いられて、対応する文法が選択される。

本実施形態による方式は、拡張スキーマの利用において基本スキーマを一切操作せずにimport し、拡張した型の利用にxsi:type を利用することで、拡張スキーマに対応するEXI 文法の差分実装を実現するものである。本方式により、文法構造がコンパクトになり、より効率的になる。すなわち、import により基本文法をそのまま導入するので、共通する部分が最大化され、差分のみの文法を持てば良くなる。図４に提案方式に基づくEXI 文法のメモリ格納方式のイメージ図を示す。

本実施形態は、そのまま組込み機器の通信に利用可能である。例えばXML スキーマにより定義したペイロードを、EXI 符号化して通信を行うホームネットワークプロトコルがあったとする。無線を利用することが多いホームネットワークにおいて、ペイロードサイズを削減できる厳格スキーマ由来文法(strict schema-informed grammar) は有利な方式であるが、一方で拡張のためには個々の拡張スキーマに対応する必要がある。この時、従来方式によるとXML スキーマを拡張する度に対応するスキーマに対応する全ての文法をメモリに格納しなければならず、資源制約の厳しいシステムで利用するには不適切である。

提案方式により、拡張差分に対応する文法のみで拡張スキーマを実装可能になる。これにより、より低価格・低スペックの家電・センサ・メータ等の組込み機器にさまざまな拡張を実装することが容易になる。

EXI の文法サイズは状態遷移の数にほぼ比例する。このことから、95%を共有し5%を拡張した2 つの文法があった場合、従来方式では2つの文法をそれぞれ実装する必要が出たのに対して、提案方式では105%分(基本スキーマ100%と拡張スキーマ5%) で十分である。

上記の説明ではデコーダを中心にして本実施形態およびその効果を説明したが、エンコーダの場合も同様に本実施形態を適用可能である。基本スキーマの状態機械（文法）をベースとして、拡張スキーマに対しては拡張された型に対応する部分にのみ状態機械を追加することで、基本スキーマと拡張スキーマで状態機械を共有できる。これにより、エンコーダの記憶領域サイズを節約できる。

以上のように、本実施形態によれば、ベンダ拡張スキーマを定義する際に、拡張部分については基本スキーマに定義されている型を派生させて型を定義し、拡張型を利用する際はXML スキーマインスタンス仕様のxsi:type 属性による型指定により記述する。これにより、基本スキーマを表現する状態機械（文法）を一切変更することなく拡張スキーマを実装可能になる。その結果、基本スキーマ由来の状態機械と拡張スキーマ由来の状態機械の共通部分が最大となり、プログラムサイズ・メモリ使用量が減り、EXI 処理系が搭載可能な組込み機器の種類が増える。

なお、以上に説明した実施形態におけるEXIデコーダは、例えば、汎用のコンピュータ装置を基本ハードウェアとして用いることでも実現することが可能である。すなわち、EXIデコーダにおけるストリーム入力部、ヘッダ解析部、文法選択部、ストリングテーブル初期化ベクタ選択部、およびパーサ部は、上記のコンピュータ装置に搭載されたプロセッサにプログラムを実行させることにより実現することができる。このとき、EXIデコーダは、上記のプログラムをコンピュータ装置にあらかじめインストールすることで実現してもよいし、CD−ROMなどの記憶媒体に記憶して、あるいはネットワークを介して上記のプログラムを配布して、このプログラムをコンピュータ装置に適宜インストールすることで実現してもよい。また、文法ストアおよびストリングテーブル初期化ベクタストアは、上記のコンピュータ装置に内蔵あるいは外付けされたメモリ、ハードディスクもしくはCD−R、CD−RW、DVD−RAM、DVD−Rなどの記憶媒体などを適宜利用して実現することができる。

Claims

EXI（Efficient XML(Extensible Markup Language) Interchange）ストリームをデコードするEXIデコーダであって、
少なくとも１つのデータ型を定義したXMLによる基本スキーマからEXI仕様にしたがって生成される第1の型文法と、
前記基本スキーマをインポートするとともに、前記基本スキーマにおける前記少なくとも１つのデータ型のうちの1つを派生させた、拡張されたデータ型を定義した拡張スキーマから、前記EXI仕様にしたがって生成される型文法のうち、前記第1の型文法と同じ型文法を除いた第2の型文法と、
前記基本スキーマのスキーマIDを前記第1の型文法に関連づけ、前記拡張スキーマのスキーマIDを前記第1の型文法と前記第2の型文法とに関連づけた、文法セット表と
を記憶する文法ストアと、
EXIストリームを受信するストリーム入力部と、
前記EXIストリームのヘッダオプションを解析し、前記ヘッダオプションに含まれる、前記基本スキーマのスキーマIDおよび前記拡張スキーマのスキーマIDのいずれかであるスキーマIDを特定し、前記文法セット表に従って、特定したスキーマIDに対応する型文法を特定し、特定した型文法を用いて、前記EXIストリームをデコードするパーサ部と、
を備えたEXIデコーダ。
前記文法セット表は、前記拡張されたデータ型に割り当てられた名前に、前記第2の型文法を関連づけており、
前記EXIストリームは、前記特定したスキーマIDが前記拡張スキーマのスキーマIDを含む場合に、前記拡張されたデータ型に対応するEXIストリーム部分に関連づけられた前記名前を含んでおり、
前記パーサ部は、前記EXIストリームに含まれる前記名前に関連する前記EXIストリーム部分をデコードするために用いる型文法を、前記名前に基づき前記文法セット表を参照することによって、前記第2の型文法に特定する
請求項１に記載のEXIデコーダ。
EXI（Efficient XML(Extensible Markup Language) Interchange）ストリームをデコードするプログラムであって、
少なくとも１つのデータ型を定義したXMLによる基本スキーマから、EXI仕様にしたがって生成される第1の型文法と、
前記基本スキーマをインポートするとともに、前記基本スキーマにおける前記少なくとも１つのデータ型のうちの1つを派生させた、拡張されたデータ型を定義した拡張スキーマから、前記EXI仕様にしたがって生成される型文法のうち、前記第1の型文法と同じ型文法を除いた第2の型文法と
前記基本スキーマのスキーマIDを前記第1の型文法に関連づけ、前記拡張スキーマのスキーマIDを前記第1の型文法と前記第2の型文法とに関連づけた、文法セット表と
を記憶する文法ストアにアクセスするステップと、
EXIストリームを受信するストリーム入力ステップと、
前記EXIストリームのヘッダオプションを解析し、前記ヘッダオプションに含まれる、前記基本スキーマのスキーマIDおよび前記拡張スキーマのスキーマIDのいずれかであるスキーマIDを特定し、前記文法セット表に従って、特定したスキーマIDに対応する型文法を特定し、特定した型文法を用いて、前記EXIストリームをデコードするパーサステップと、
をコンピュータに実行させるためのプログラム。
前記文法セット表は、前記拡張されたデータ型に割り当てられた名前に、前記第2の型文法を関連づけており、
前記EXIストリームは、前記特定したスキーマIDが前記拡張スキーマのスキーマIDを含む場合に、前記拡張されたデータ型に対応するEXIストリーム部分に関連づけられた前記名前を含んでおり、
前記パーサステップは、前記EXIストリームに含まれる前記名前に関連する前記EXIストリーム部分をデコードするために用いる型文法を、前記名前に基づき前記文法セット表を参照することによって、前記第2の型文法に特定する
請求項３に記載のプログラム。