d0iの連絡帳

気がむいたら書く

EXIにおける文字列 (String) と QName

技術 EXI 技術

だいぶ時間があいてしまいました。EXIにおける文字列の扱いと、おまけでQName (Qualified Name) の扱いについて説明します。

XMLにおいては、同じ文字列が何度も登場します。タグに囲まれた文字列だけではなく、タグそのものも文字列ですね。
これらを表現する場合に、まともに符号化していたら損なので、できるだけ簡単な仕掛けで再利用するようにしています。

ただし、私の理解も中途半端な部分があるので(特に自分で実装していない所は)間違っている可能性もあります。
くわしくは原典 7.1.10 String あたりをチェックしてください。
また、以下、部分的に今までの説明の内容を使いますので、例えば [EXI][技術] データ型とその符号化 - doiの連絡帳 あたりは読んだものとして扱います。

文字列表 / String Table

まず、文字列表 / String Table について説明します。

XMLにおいて、特に短い文字列は何度も登場します。これらを効率的に符号化するために、EXIの符号化・復号の際にはあわせて文字列表を作り、管理します。
簡単に言うと、符号化側で入力されたXML表現の中の文字列は、文字列表に登録され、二度目以降同じ表現が登場した場合はこの文字列表を手掛りに、「文字列表の○番目の文字列です」という情報を符号化します。復号側でも同様に入力となるEXIに登場した文字列を文字列表に格納して、「文字列表の○番目の文字列です」という符号を見つけたら、これを手がかりに対応する文字列を拾い出してきて復号します。なお、文字列表自体はストリームに固有のもので、使いまわしはできません。

文字列表は、実際にはいくつかあります。仕様としては、 7.3 String Table が対応しますが、わかりにくいので以下に少し整理します。

文字列のうち、以下のもについては文字列表で管理します。

  1. uri : つまり、URLなど
  2. prefix : 例えば <ns0:temperature> の、ns0にあたる部分ですね。
  3. uri and local-name in qnames : QNameというのは、要素名や属性名、型の名前などを正式に表現したもので、URI部とLocal Name部からなります。なぜかXMLで正しく表現することができません。説明はいろいろとややこしいので、とりあえず Web Kanzaki さんの解説 をリンクしておきます。
  4. values : 実際の値。<ns0:temperature>34.9C<ns0:temperature> の、34.9C にあたる部分とか、属性値とかが対応します。

で、これらのうち、一般的なURIと、QNameに含まれるURIは似ているのでまとめてしまい、以下の文字列表でそれぞれ分担します。

  1. URI Partition : 一般的なURI、およびQNameに含まれるURI部が格納されます。
  2. Prefix Paritition : Prefix文字列が必要な場合は*1格納されます。
  3. Local Name Partition(s) : QNameのLocal Name部(上の例だとtemperature)を格納します。なお、このPartitionは名前空間別になっているので、表は複数になります。
  4. Value Partition(s) : 実際の値を格納します。この表は実際には、グローバルに、そのEXIストームに登場した全ての文字列を格納する一つの文字列表と、その文字列が追加される文脈における要素もしくは属性が持つ名前空間毎に持つローカルな文字列表にわかれており、ローカルな文字列表は名前空間別になるので、やはり表は複数になります。

ナイーブに実装したイメージを図にするとこんな感じでしょうか。実際には、文字列自体はポインタで持っていれば良いので、こんな実装の仕方しないと思いますが。

以下、この文字列表を操作しながらストリーム中の文字列を符号化・復号します。
つまり、文字列に対応するビット列だけコピーしても、必ずしもその文字列が復号できるとは限りません。常にそのストリーム中での文字列表の状態がわからないと復号できず、これがEXIの取り扱いを厄介にしているポイントでもあります。

String (without restrictive character set)

Section 7.1.10 文字列についての基本です。ただし、restrictive character set(制約された文字集合)については別項で扱います。

文字列そのものはとてもシンプルです。文字列自体の表現は、文字列の長さでPrefixされた文字の集合です。文字列の長さはUnsigned Integer (符号なし整数) です。また、個々の文字は Unicode で、文字コードを直接符号なし整数で符号化します。UTF-8でも、UTF-16でもありません。面倒なサロゲートペアが登場しない反面、1文字あたり何バイト用意しておけば良いのか文字列長を見ただけでは判別できない*2という問題があります。UNICODEの0x0000-0x007fまではASCII互換で、EXIの符号なし整数も127まではそのままバイトとして書けますので、US-ASCIIの範囲ではそのままmemcpy*3しても動くはずです。US-ASCIIの特権ですね。

以下、"Hello" を符号化した例と、"こんにちは"を符号化した例です。

  • uInt(5)|uInt(72)|uInt(101)|uInt(108)|uInt(108)|uInt(111) // "Hello"
  • uInt(5)|uInt(12371)|uInt(12435)|uInt(12395)|uInt(12385)|uInt(12399) // "こんにちは"

以後の説明では、Str(x)で文字列xを符号化したものをあらわします。

文字列表を利用した符号化方法

さて、ここで文字列表が登場すると、途端に複雑怪奇になります。文脈により文字列表が利用可能である局面においては*4、文字列は文字列表を併用した符号化になります。文字列表は実は2つにわかれて、一つはグローバルなものしか存在しない、URI Paritition および Prefix Partition、もう一つは現在の文脈を規定するURIにより複数存在する、Value PartitionとLocal Name Partitionです。

URI PartitionとPrefix Partition

URI PartitionとPrefix Partitionは、それぞれ、よく使われるURI/Prefixを初期状態として持ちます(Initial Entries in Uri PartitionおよびInitial entries in Prefix Partitions。また、スキーマを利用する場合は、スキーマ中に登場するURIが、仕様で定められた初期値の後に、辞書順で追加されます。

符号化・復号は次の手順で行います*5。

  • まず、エンコーダおよびデコーダは、常に同じ文字列表の状態を維持しています。ここで、文字列表のエントリ数をmとします。
  • このパーティションでは、文字列表のエントリは nビット符号なし整数で表現します。ここで、n = ceil(log_2 m+1) です。
  • もし、パーティションに存在しない文字列xを符号化する時は、nInt(0, n)|Str(x) の形式で、nビット符号なし整数の0を先に符号化し、その後に文字列xを符号化します。
    • また、符号化・復号後には、文字列xは対応する文字列表に追加されます。当然、ここで m が1増え、以後、必要に応じてnも変化します。
  • もし、パーティション中のi番目(iは0から始まります)の文字列を符号化する時は、nInt(i+1, n) の形式で、文字列表の参照位置を示します。

以下、URIについて説明します。

例えば、 http://example.org/ の名前空間で定義されているスキーマに対応するEXIストリームにおいては、文字列表のURI Partitionは以下の初期値になります。

ID 文字列
0 "" (空文字列、つまりドメインなし)
1 "http://www.w3.org/XML/1998/namespace"
2 "http://www.w3.org/2001/XMLSchema-instance"
3 "http://www.w3.org/2001/XMLSchema"
4 "http://example.org/"

さて、ここで、 "http://example.org/" を符号化してみます。m=5ですから、n=ceil(log_2 5+1)=3で、3ビットで符号化されます。文字列に対応するIDは4ですから、nInt(4+1, 3) = 0b101 になります。

また、その後、"http://example.com/" を符号化しています。依然 m=5 ですから、 n=3で、 nInt(0, 3)|Str("http://example.com/") の形で符号化されます。ただし、符号化後または復号後、"http://example.com/" は文字列表の5番に追加されます(追加時にはソートはされません)。追加後、m=6になります。

さらに、この調子でURI "http://example.net/" を符号化しましょう。m=6になりましたので、n=ceil(log_2 6+1)を計算するとやっぱり3ですので、 nInt(0, 3)|Str("http://example.net/") になります。さらに、これは文字列表の6番に追加され、追加後、m=7になります。

ついでに、URI "http://example.net/2" を符号化しましょう。m=7でしたので、 n=ceil(log_2 7+1)を計算すると、やっぱり3ですので(中略) 追加後、m=8になりました。

この時点で、文字列表は以下のように変化しています。

ID 文字列
0 "" (空文字列、つまりドメインなし)
1 "http://www.w3.org/XML/1998/namespace"
2 "http://www.w3.org/2001/XMLSchema-instance"
3 "http://www.w3.org/2001/XMLSchema"
4 "http://example.org/"
5 "http://example.com/"
6 "http://example.net/"
7 "http://example.net/2"

さて、ここで再度、 "http://example.org" を符号化します。先程 0b101 だったので、それで良さそうに見えますが、実は先程nが変化しています。n=ceil(log_2 8+1)=4になります。なので、ここで "http://example.org" を符号化する時は 0b0101 と符号化しなければなりません*6。

なお、この種類のPartitionは、あまり多く書き変わらない文字列に最適化されています。

Local Name Partition(s)

Local Name Partition(s)は、異なる手法で符号化を行います。これは、場合によっては比較的多くの未知の文字列が登場することがあります(特にスキーマを利用しない符号化を行う場合)。一方、シンボルの再利用も頻繁に発生します。従って、文字列の符号化の形式をそのようなパターンに最適化しています。

Local Name Partitionの符号化を行う場合は、文字列長に1を足して符号化します。当然復号する時は、実際の符号から1を引いた数が文字列長になります。そして、符号化された文字列長が0のときは、文字列表(エントリ数m)を参照します。つまり、文字列表のエントリi(<m)は、uInt(0)|nInt(i, ceil(log_2 m)) で符号化されます。

簡単のために、現在のURIコンテキストcにおいて、"abc" というLocal Nameがまだ文字列表に入っていないものとします。また、文字列表の現時点でのエントリ数mは4であるとします。ここで、"abc"というLocal Nameを符号化する(例えば、"<c:abc/>" という未知のタグが登場するなど)場合、Local Name部分は次のように符号化されます。

  • uInt(4)|uInt(97)|uInt(98)|uInt(99)

実際のStr(x)であれば、最初はuInt(3)であるべきところ、1足されて4になっています。

ここで、再度同じURIコンテキストcでの符号化を考えます。さきほど"abc"は文字列表の当該Partitionの5番目(id=4)に追加されました。エントリ数mは5になっています。従って、"abc"の符号は次のようになります。

  • uInt(0)|nInt(4, 3)

なお、Local Name Partitionの初期値については Initial Entries in Local-Name Partitionsにあります。一般に使われそうなlocal nameは大抵含まれる上、XMLスキーマに含まれるlocal name(要素名、属性名、型名)は全て初期化時に含まれますので、特にスキーマを利用した文法を用いる場合は、ほとんどの要素名、属性名は数値に置き換え可能です。

Value Partition(s)

Value Partition(s)は、Local Name Partition(s)と似ていますが、1つのGlobal Value Partition とURI毎のLocal Value Partition(s)があることが異なります。ここでは、文字列を符号化する時は、長さに2を加算します。例えば"abc"を新規に符号化する時は、uInt(5)|uInt(97)|uInt(98)|uInt(99) と符号化します。符号化後、当該URIコンテクストの Local Value Partition と Global Value Partition には"abc"が追加されます*7。

Local Name Partitionと同様に、文字列長符号0は現在のURIコンテクストの Local Value Partition に対応し、文字列長符号1は Global Value Partition Tableに対応します。それぞれ、Partitionのエントリ数を m、符号長 n = ceil(log_2 m) としたとき、Partition中のi番目の文字列は、nInt(i, n) で符号化します。例えば Local Name Partition (m=5)の5番目(i=4)に追加された文字列"abc"を符号化する時は、uInt(0)|nInt(4, 3) = 0b 0000 0000 100 (11ビット) で符号化できます。

Value Partitionの制約 その1

Value Partitionはデフォルトではどれだけ長い文字列でも全て格納してしまいます。理屈の上では、元になるドキュメントを記憶装置のどこかに格納できているわけで、そのポインタだけ持っておけば良いので、メモリが足りないということはないはずです。ところが、たまにXMLをストリーム的に使う場合があります*8。この場合は元の文字列を忘れたい場合があります。そういった場合は、Value Partitionに制約をかけることでメモリ使用量をある程度制限できます。

EXI Optionのうち、valuePartitionCapacityとvalueMaxLengthがこの制約を制御します。valuePartitionCapacityは Global Value Partition に最大いくつの文字列を格納するかを制御します。最大値に達したら、リングバッファ的に0番から使います。また、上書きされた値に対応するLocal Value Partitionは利用不可になります。

valueMaxLength は、Value Partitionに格納する文字列の最大長を決めます。文字列の長さは文字数で決まります(= バイト数ではありません)。最大長を超える文字列については無視されます。

Value Partitionの制約 その2

さて、前節で述べたように、Local Value PartitionのIDには最大値がありません。まじめに実装するとこれが結構厄介で、URIで識別される空間の数だけ、IDとGlobal Value Partitionとの対応、そしてvaluePartitionCapacityで最大値が設定されている場合は、それぞれの文字列の死活管理を行わないといけません。

組込機器向けプログラミングにおいては、できるだけ動的メモリ管理を避けたい*9場合があります。静的なメモリ管理のみのプログラミングモデルにおいては、有限なGlobal Value Partitionは実現できても、Local Value Partitionの効率的な実現は難しいです。従って、Local Value Partitionを無効化する方法が提案されています。

EXI Profile は、組込機器向けの追加オプションを設定可能にするものです。このうち Section 4. Local Value Capping において、localValuePartitions というオプションが導入され、これを0に設定することで全てのlocal value partitionをdisableすることができます。

ただし、この仕様は2013年9月はじめ時点でまだCR (Candidate Recommendation) の段階ですので、仕様の細かい部分が変更になる可能性があります。また、利用できる実装は限られています。

Restricted Character Sets

XML Schemaにより文字列に許容されるパターンを設定できます。これは、Regular Expressionなどで設定されますが、ここからこの文字列に許される文字列の集合を求めることができます(付録D: Deriving Set of Characters from XML Schema Regular Expressions)。こうして求めた文字列集合の要素数が256以下の場合、かつ、それぞれの文字要素が全てBasic Multilingual Planeに含まれる*10場合、n-bit unsigned integerで各文字を符号化します。具体的には、要素数nの文字集合に対して、unicode順にソートされたそれぞれの要素に対して文字集合中のインデックスiを割り当てて、nInt(i, n) で符号化します。

例えば、"(明治|大正|昭和|平成)"というパターンがあった場合、文字集合は*11「和大平成明昭正治」になります。文字数は8ですので、それぞれ以下のように符号化されます。

  • 明治: nInt(4, 3), nInt(7, 3) = 0b100111
  • 大正: nInt(1, 3), nInt(6, 3) = 0b001110
  • 昭和: nInt(5, 3), nInt(0, 3) = 0b101000
  • 平成: nInt(2, 3), nInt(3, 3) = 0b010011

まぁ、この場合は、実際はパターン制約付き文字列ではなくenumerationにしてしまえば2ビットで表現できるんですけどね(Efficient XML Interchange (EXI) Format 1.0 (Second Edition))。

QName

QNameは文字列の組み合わせ型で、文字列表と密接に関わっているのでここで扱います。
QNameは、実際にはURIとLocal Nameの組み合わせです。EXI Optionにもよるのですが*12、以下にデフォルトの符号化方式を説明します。

URIとLocal Nameはそれぞれ文字列です。ですので、文字列表を引くことになります。XMLスキーマに由来するURIはURI Partitionの初期値に、Local NameはLocal Name Partitionに、それぞれ含まれるので、スキーマに含まれる組み合わせであれば実際の文字列を符号化することなく、「文字列表のi番目」でコンパクトに指定できます。もちろん、XMLスキーマに含まれない組み合わせが登場した場合は先に述べた通り符号化する必要があります。

簡単のため初期文字列表(付録D参照)を例に QName("xsi:type") を符号化します。xsiは "http://www.w3.org/2001/XMLSchema-instance" の prefix とします。このとき、URIはnInt(2, 2)、"type"はXSI-NS Partitionのid=1なので、nInt(1, 1)となります。結合すると 0b101 になります。

なお、スキーマ由来文法を用いている場合は、イベントコードに個々の要素名、属性名が内包されるので、実際にQNameを符号化する必要がある場合は限られます。
限られる符号化方式のうちの一つがxsi:type属性の値です(xsi:type属性そのものは普通はAT(xsi:type)というイベントがあるので符号化する必要はありません)。
この属性はいろいろと面白いのでまた取り上げようと思います。

まとめ

文字列はさまざまなXMLで登場するので、これを効率的に符号化する工夫がさまざま存在します。ただ、正直実装者の立場からすると少々複雑すぎる側面があり、もうちょっとシンプルかつ使いやすくできれば良いなとは思います…。その意味で、EXI Profileのデフォルトオプションはなかなか良い落とし所だと思います。

*1:Fidelity Optionで扱いが変わります。

*2:1文字あたり3バイト用意すれば十分なのかな？

*3:ただし、バイト境界が揃ってない場合は無理ですが...

*4:そういえば、文字列表を使わない局面って何だろう？

*5:どうでもいいんですが、これ、存在しない文字列xを符号化する時には nInt(m, n) にして、文字列表の値を符号化する時は nInt(i, n)のほうが良かった気がしますね‥‥‥。

*6:つまり、厄介なことに、EXIはストリームの位置と文字列表の状態が対応しているので、コピペができません。圧縮モノの宿命と言えば宿命ですが‥‥‥。

*7:実際にはvaluePartitionCapacityとvalueMaxLengthによって動作が変化しますが、ここではデフォルト値である無制限を仮定しています。

*8:XMPPなど

*9:網羅的なテストが難しくなりますからね

*10:Unicode の codepoint で 0x0000-0xFFFF まで

*11:計算が間違ってなければ

*12:特にPreserve.prefixes