第37回　文字符号化方式にまつわるジレンマ　Page 1

XML 1.0は、1998年にW3Cから勧告として公開された。当然中身は英語で、しかもEBNFと呼ばれる式によって重要な部分が記述してある。この連載では、XML 1.0を深く理解するために、そのXML 1.0勧告の最新版「Extensible Markup Language (XML) 1.0 (Third Edition)」をだれでも分かるように、やさしく読み解きながら解説していくことを目指している。（編集局）

川俣 晶
株式会社ピーデー
2005/9/13

■決定的内容モデルと文字符号化方式

主な内容 --Page 1-- 決定的内容モデルと文字符号化方式 決定的内容モデル --Page 2-- 日本語利用者に関係の深い文字符号化の自動検出 --Page 3-- 外部の符号化情報がない場合の検出

　前回は「C XML and SGML (Non-Normative)」と「D Expansion of Entity and Character References (Non-Normative)」を読んだ。JIS X 4159では「附属書C（参考）XMLおよびSGML」と「附属書D（参考）実体参照および文字参照の展開」である。前者は、XMLとSGMLの関係について記述されている。どちらかといえば好奇心から見るべき文書であり、歴史の一端を垣間見るのに有用だろう。逆に後者は、生々しい現在進行形のXMLのディープな領域を正しく理解するのに有益だろう。もちろん、ここまでDTDやパラメタ実体を含む参照を活用する利用者は多くないかもしれない。しかし、ある種のXMLの応用は、間違いなくこれらのディープな参照の挙動を活用して行われている。もちろん、ここに書かれているのは、規定ではなく、分かりやすくするための例にすぎない。しかし、それを見ることで、より深い正しい理解に到達する助けになるものであり、大変に有益である。

　さて、今回は「E Deterministic Content Models (Non-Normative)」と「F Autodetection of Character Encodings (Non-Normative)」の途中までを読んでいこう。JIS X 4159では「附属書E（参考）決定的内容モデル」と「附属書F（参考）文字符号化の自動検出」に当たる。前者は、SGMLとの互換性のために要求される決定的内容モデルとは何かを具体的に説明するものである。これと逆の意味になる非決定的内容モデルと併せ、それぞれどのような特徴があるかを見てみたい。後者は、符号化方式つまりUTF-8であるとか、シフトJISであるとか、そのような相違を自動検出する方法について説明している。そのような違いは符号化宣言を見ればすぐ分かるではないか……と思うかもしれないが、符号化宣言を読むためには、ある程度、符号化方式の当たりを付けねばならないのである。そのあたりの話題を、今回から次回にかけて読んでいこう。

編集注：この連載では、XML 1.0勧告であるW3Cの「Extensible Markup Language (XML) 1.0 (Third Edition)」（英語）を参照し、その日本語訳として、日本工業規格 JIS X 4159:2002（Second Edition相当。リンク先は該当規格の原案ですが、最終版とほぼ同等の内容です）と追補1として出版予定の原稿（Third Edition対応）を参照しています。本文中のピンクの地の部分は、XML 1.0勧告の原文を示しています。

■決定的内容モデル

　では、「E Deterministic Content Models (Non-Normative)」、JIS X 4159では「附属書E（参考）決定的内容モデル」を読んでいこう。ここは、Non-Normative（参考）と書かれていることから分かるとおり、規定の一部ではない。分かりやすくするための参考として書かれたものである。

　決定的内容モデルとは、「決定的」な「内容モデル」ということである。内容モデルとは、すでに「3.2.1 Element Content（3.2.1 要素内容）」において、「内容モデルは、子要素の型および子要素の出現順序を制御する簡単な文法とする」と読んだ。つまり、子要素として出現してよい要素の種類（＝要素型）や、その出現順について、許される組み合わせを指定するものである。一方、「決定的（deterministic）」というのはもっと一般的な言葉である。といっても、日常会話で使うような言葉ではない。「決定的」の反対の意味を持つのは「非決定的（non-deterministic）」という言葉である。ここでは、「複数の選択肢がある場合、その時点で持っている情報だけでどれを選ぶかが確定するのが決定的。確定しないのが非決定的」というようなムードで理解しておけばよいだろう。もちろん、ムードだけでそれが厳密な意味で正しいわけではないが、ここでは十分だろう。

　さて、本文を読んでいこう。

As noted in 3.2.1 Element Content, it is required that content models in element type declarations be deterministic. This requirement is for compatibility with SGML (which calls deterministic content models "unambiguous"); XML processors built using SGML systems may flag non-deterministic content models as errors.

3.2.1 要素内容で示したとおり、要素型宣言中の内容モデルは決定的である必要がある。この要求は、SGMLとの互換性のために導入し（SGMLでは、決定的内容モデルを"非あいまい"と呼ぶ。）、SGMLシステムを用いて作成したXMLプロセサは、非決定的内容モデルを誤りとしてもよい。

　冒頭の文章で注意すべきことは、内容モデルが決定的でなければならないと規定しているのは、いま読んでいる「E Deterministic Content Models (Non-Normative)」ではなく、「3.2.1 Element Content（3.2.1 要素内容）」だということである。つまり、これについてはすでに読んでいることになる。これに関係がありそうな段落を「3.2.1 Element Content（3.2.1 要素内容）」から引用してみよう。

要素の内容が内容モデルにマッチするのは、列、選択および繰り返し演算子に従って、内容の中の要素と内容モデル内の要素型とをマッチさせながら、内容モデル内の1つのパスをたどれるときに限る。互換性のため、文書内の要素が、内容モデルにおける要素型の複数の出現位置とマッチすることは、誤りとする。詳細な規定については、「E. 決定的内容モデル」を参照。

　ここで書かれていることは難しいが、それが具体的に何を示しているかを分かりやすくするための補足説明が、この「E Deterministic Content Models (Non-Normative)」である。それ故に、この文章はこのまま置いて、続きを読んでいこう。

　次は、SGMLでは内容モデルは決定的でなければならないので、SGMLとの互換性を意識するなら、XMLもその制約を受け入れねばならない。しかし、SGMLとの互換性を意識しないなら、その制約を受け入れないという選択もあり得る。XMLはその選択を禁止してはいない。明確に確認はしていないが、おそらく世の中にあるXMLプロセッサには、非決定的な内容モデルを受け入れるものと、エラーにするものがあるのではないかと思う。

　さて、次はより具体的な「決定的内容モデル」の説明である。

For example, the content model ((b, c) | (b, d)) is non-deterministic, because given an initial b the XML processor cannot know which b in the model is being matched without looking ahead to see which element follows the b. In this case, the two references to b can be collapsed into a single reference, making the model read (b, (c | d)). An initial b now clearly matches only a single name in the content model. The processor doesn't need to look ahead to see what follows; either c or d would be accepted.

例えば、内容モデル((b, c) | (b, d))は非決定的となる、なぜならこれは、最初にbを与えたとき、モデル内のいずれのbとマッチするのか、その次の要素を先読みすることなしには、XMLプロセサは知ることができないことによる。この場合は、bの2つの出現は、1つにまとめることができ、モデルは(b, (c | d))となる。こうすれば、明らかに最初のbは、内容モデル内の1つの名前とだけマッチする。プロセサは先読みして、次にくるものを知る必要がなく、cもdも受理される。

　冒頭の文章では、この内容モデルは「|」記号によって、その前後のどちらでもよいことを示している。つまり、b、c、dの内容モデルが空であると仮定すれば、以下のどちらの要素の並びも許容される。

<b/><c/>
<b/><d/>

　つまり、(b, c)の場合は前者が、(b, d)の場合は後者がマッチする。しかし、どちらがマッチするかは、先頭から調べていった場合、<b/>を調べる段階では確定しない。その次にくる要素がcであるかdであるかを調べねば、XMLプロセッサは(b, c)なのか(b, d)なのか、判断を下すことができない。つまり、b要素について調べているときに、その次の要素も調べねば判断を下せないことが、「先読みが必要」ということである。そして、このような内容モデルは「非決定的」ということになる。

　次に、この内容モデルは少し書き直せば、決定的内容モデルに置き換えることができると述べられている。((b, c) | (b, d))の場合は、bという名前が2つあるが、(b, (c | d))と書き換えれば1つになるわけである。そして、bという要素名が出てきた場合、必ずこの1つのbとマッチするから迷うことはない。つまり、非決定的にならない。

　そして、bを受け入れるパターンは1つしか存在しないので、先読みは不要となる。つまり、要素bを発見した時点で、それが示す内容モデルは1種類しか存在せず、それに続く要素を調べる時点でcまたはdという2つの選択候補が存在するが、それは先読みせずに処理できる。先読み不要ということは決定的な内容モデルということである。わずかな違いにすぎないが、それが「扱える」「扱えない」という境界を分けるケースが存在するのである。

　さて、ここで少し補足説明を付けておこう。XMLが決定的であることを要求するのは、あくまでSGMLとの互換性という理由に限られるが、その対象もしっかりと確認しておく価値がある。つまり、決定的である必要があるのは、内容モデルだということである。ここでいう「決定的」「非決定的」とは、内容モデルつまり子要素などの書き方のルールに対して適用される言葉であって、文書そのものには適用されない。決定的内容モデルから逸脱するXML文書は、単に「妥当ではないXML文書」となるだけで、それ自身が非決定的となるわけではない。

　さらにいえば、内容モデルとはDTDで使用される概念である。DTDを使用しないXML文書はいかなる意味でもDTDに拘束されることはない。より正確には要素型宣言を使用しないXML文書はいかなる意味でも内容モデルに拘束されることはない、といってもよいだろう。つまり、DTDとは異なるスキーマ言語を使う、あるいはスキーマ言語を使わないという選択を取ったとき、非決定的なルールに従ってXML文書を書くことができ、そのようなXML文書はどのようなXMLプロセッサを使うとしても（それが非決定的な内容モデルをエラーにする場合でも）、整形式のXML文書として正しいものとなる（誤りではない）。

　さて、内容モデルが決定的か非決定的かということが、それほど重要なのであろうか？ この問題は、XMLのスキーマ言語の深淵に触れるため、私には確実なことはいえないが、分かる範囲でのみ述べておこう。内容モデルが決定的であるか否かは、アルゴリズム選択の幅、実装の難度やパフォーマンス、使い勝手などに影響を与える可能性がある。

　アルゴリズム選択の幅というのは、世の中には決定的な場合にのみ使用できるアルゴリズム……というようなものが存在するためである。XMLプロセッサや応用プログラムを開発する際、DTDが決定的であるか否かは、それを実装する際に利用できるアルゴリズムの選択の幅の差として出てくる可能性がある。

　実装の難度やパフォーマンスというのは、DTDが決定的であるか否かが、処理を行うアルゴリズムの複雑さ、実装するプログラムの難度や量、処理に要する時間などに影響を与える可能性があることを示す。決定的であれば、妥当性の検証は文書の先頭から最後まで要素型の定義などと突き合わせていくだけで終わる。さほど難しい話ではない。しかし、非決定的であると、複数の候補のどれを選択すればよいのか、先読みしないと分からないことがある。これを、文字どおり先読みするか、それとも複数の可能性を同時並行で追跡していくか、あるいは1つの候補を選び出して駄目なら戻って別の候補を試すか（バックトラック）、実装方法はいろいろ考えられるが、決定的な場合ほど単純には済まされない。

　使い勝手というのは、「決定的」「非決定的」という概念が一般には分かりにくく、DTDを記述する際に「決定的」に書かねばならないという意図が正しく理解できない可能性を示す。また、ごく自然に利用者の思うとおりにDTDを記述すると、非決定的な形に書き下ろされてしまうという可能性もあるだろう。

　以上のように、「決定的」であることを要求する場合と「非決定的」を許す場合には、具体的な違いが発生する。

　さて話を先に進めよう。次の段落は、この問題を形式的に示す場合である。

More formally: a finite state automaton may be constructed from the content model using the standard algorithms, e.g. algorithm 3.5 in section 3.9 of Aho, Sethi, and Ullman [Aho/Ullman]. In many such algorithms, a follow set is constructed for each position in the regular expression (i.e., each leaf node in the syntax tree for the regular expression); if any position has a follow set in which more than one following position is labeled with the same element type name, then the content model is in error and may be reported as an error.

　これは、JIS X 4159の訳では以下のようになる。

形式的に示せば次のとおり。Aho, Sethi, and Ullman [Aho/Ullman]の3.9のアルゴリズム3.5などの標準的なアルゴリズムを用いて、内容モデルから有限オートマトンを構成することができる。この種の多くのアルゴリズムでは、正規表現におけるおのおのの位置（つまり、正規表現の構文木におけるおのおのの末端ノード）に対して、follow setを構成する。ある位置に対するfollow setにおいて、複数の位置が同じ要素型名でラベル付けされていれば、その内容モデルは誤りとなり、誤りとして報告してもよい。

　この部分は、おそらく単なるXML勧告の読者には読む必要のない部分ではないかと思う。その理由は2つある。1つは、最初の「形式的に示せば次のとおり」という言葉に示されるとおり、別の表現についてのいい換えにすぎないからである。もう1つは、これを把握するためには別の書籍のそれなりの量の文章を読まねばならないからである。いい換えに対してそれだけの労力を取る意義は、「形式的ないい換え」に特に価値を見い出す者に限られ、それはXML勧告の読者の中でも、ごく一部に限られるのではないかと思う。ちなみに、別の書籍とは『Aho, Sethi, and Ullman [Aho/Ullman]』として示されているものであるが、これは「A.2 Other References」に含まれる以下の文書を指し示す。

Brüggemann-Klein

Brüggemann-Klein, Anne. Formal Models in Document Processing. Habilitationsschrift. Faculty of Mathematics at the University of Freiburg, 1993. (See ftp://ftp.informatik.uni-freiburg.de/documents/papers/brueggem/habil.ps.)

　次は、非決定的内容モデルを決定的内容モデルに変換するアルゴリズムについて述べられている。

Algorithms exist which allow many but not all non-deterministic content models to be reduced automatically to equivalent deterministic models; see Brüggemann-Klein 1991 [Brüggemann-Klein].

すべての非決定的内容モデルを等価な決定的内容モデルに変換することはできないが、多くの非決定的内容モデルを変換するアルゴリズムが存在する。Brüggemann-Klein 1991 [Brüggemann-Klein]を参照。

　すでに、非決定的内容モデルを決定的内容モデルに置き換える実例は紹介されているので、それが可能であることはお分かりと思う。しかし、すべての非決定的内容モデルが決定的内容モデルに変換できるわけではない。変換できないほどのあいまいさや複雑さを持った内容モデルもあり得るためだ。しかし、多くの非決定的内容モデルを変換するアルゴリズムがあるという。それについては、『Brüggemann-Klein 1991 [Brüggemann-Klein]』という文書を参照せよ、としているが、これは上記と同じ文書を指し示している。

　以上で、「E Deterministic Content Models (Non-Normative)」、JIS X 4159では「附属書E（参考）決定的内容モデル」は終わりである。（次ページへ続く）

1/3

Index
やさしく読む「XML 1.0勧告」 第37回 文字符号化方式にまつわるジレンマ
	Page 1 ・決定的内容モデルと文字符号化方式 ・決定的内容モデル
	Page 2 ・日本語利用者に関係の深い文字符号化の自動検出
	Page 3 ・外部の符号化情報がない場合の検出

連載　やさしく読む「XML 1.0勧告」

＠ITメールマガジン　新着情報やスタッフのコラムがメールで届きます（無料）