Japan [変更]

目次:
	速度について
	データ・アクセス形式の対比
	LT XMLを使う
	参考文献
	著者について
	記事の評価

関連リンク
	XML 記事一覧

developerWorks Japan > XML >

XMLの論考: RXPパーサ

Pythonバインディングによる超高速妥当性検証パーサ

ページオプション

JavaScript を要するドキュメントオプションは表示されません

原文はこちら

レベル: 中級

David Mertz, Ph.D (mertz@gnosis.cx), Author, Gnosis Software, Inc.

2003年 8月 04日

RXP は、XML文書の非DOMツリー表現を生成する、Cで書かれた妥当性検証パーサです。RXP 自体は詳しく説明されているとは言えません（きっと臆病な人には向きません・・・）、けれど少なくとも2つの優秀で高度なAPIがRXP 上に作られています。PythonバインディングであるpyRXP と、ユーティリティやライブラリ群であるLT XML です。この記事でDavidは、RXP の紹介、expat パーサとの比較を行います。そして、RXP の複雑さに踏み込まずにRXP の高速性を利用する方法としてpyRXP とLT XML について簡単に説明します。

このコラムの読者は、私がここでXMLについて書くときに、Pythonツールを特に好んで取り上げていることに気がついているかもしれません。今回の記事では、そのパターンを打破して、CアプリケーションでRXP を利用することに集中するつもりだったのですが、より詳細にRXP ライブラリを見てみると、RXP を最も簡単に利用するにはPythonモジュールのpyRXP を使うべきだと気づいてしまいました。

基盤となるRXP GPLライブラリは、最も速い妥当性検証を行うXMLパーサであることはほぼ間違いないのですが、パーサ・コードについて現時点ではほとんど文書化されておらず、一つのコマンドライン・ツールの簡単な例があるだけです。このツール（rxp）は、ユーティリティxmlcat.py （ヒント: コマンド・ラインXML処理で説明しています）や、他の同じようなユーティリティと類似しており、XML文書を読み込んで、妥当性を検証し、標準的な形式で出力します。rxp.cのソースコードを調べて見てみれば、RXP が構文を解析してコンパクトなドキュメント・ツリーをデータ構造として生成する様子が分かるでしょう。

Language Technology GroupはRXP の上でLT XML を構築しています。これには各種の高度なツールやAPIを含んでいます。さらに、（XMLエディタである） XEDを含めてLT XML を使って作られたツールもいくつか存在します。この記事ではLT XML のツールも簡単にとり上げますが、pyRXP バインディングにより明らかになったRXP のツリーAPIを調べる方に重点をおきます。私の知る限りでは、RXP バインディングがあっても良さそうな他の高級言語（PerlやTCL、それにRubyなど）では、まだRXP バインディングを生かしきっているとは言えません。

速度について

RXP は高速です。（オプションとして）妥当性検証を行うRXP パーサを使ったCアプリケーションは、（非常に早いことで知られる）非妥当性検証expat パーサを使ったアプリケーションと、速度の面ではおそらくほとんど差がありません。RXP は、構文解析済XML文書のツリー構造を、メモリ内にコンパクトに構築します。構文解析の失敗はツリー構築の失敗となりますが、構文解析に成功するとXMLのDOM表現よりもずっと効率的なデータ構造が得られることになります。

XML文書から完全なデータ構造を構築する必要があると言う場合であれば、RXP はおそらくexpat をわずかに上回る程度です。けれども、妥当性の検証が必要な場合となるとexpat は、まったく考慮の対象になりません。ただし、単に連続的な処理やXML文書内の情報の小さなサブセットを抽出するような場合には、既に処理された（あるいはスキップされた）タグの各種の情報を保存する必要がないので、expat の方がより優れているでしょう。実際、十分に大きな文書を処理する場合、expat には圧倒的な利点があります（1GBのXML文書をメモリ上に展開することは滅多にないでしょうが・・・多分RXP でこんなことはできないでしょう）。expat を使ったアプリケーションならば、文書サイズと比較しておそらく小規模のメモリしか使わずに、そうした大きなXMLを読み進みながら、関係のあるタグをいくつか抽出することができるでしょう。

RXP が真価を発揮するのはpyRXP バインディングの場合においてです。前回のコラムで、PythonにおけるいくつかのXMLのドキュメント・モデル（ElementTree 、gnosis.xml.objectify 、xml.minido 、cDomlette ）における速度とメモリ使用量の比較に関してかなり詳しく説明しました。そこで行ったテストでは、各APIを使用して最小限のメモリ内表現を単純に生成し、生成に要した時間とメモリ使用量を計測しました。pyRXP で同じことをするのは簡単です。

リスト1. time_rxp.py

                
                
from pyRXPimport Parser
import sys, time
start = time.clock()
tups = Parser().parse(sys.stdin.read())
print
                "Time: %.3f" % (time.clock()-start)

pyRXP を使った場合、3MBのweblog.xmlファイルをパースするのに4秒しかかかりません。それに対して前回のテストでは、最速のcDomlette でも、私のテストマシンで約25秒かかっています。メモリ使用量の方は、time_rxp.pyは最大でも約28MBで、前回一番の倹約家だったgnosis.xml.objectify とほとんど同じです。つまりpyRXP は、前回最小のメモリ使用量と同等で、かつ速度は6倍速いというわけです。

pyRXP が他のPython用XMLドキュメント・モデルのAPIよりもずっと速いのには、ある明確な理由があります。RXP がC上で完全なデータ構造を構築し、そしてpyRXP は、この完成した構造をそれに良く似たPythonのデータ構造に変換するだけ・・・だからです。これに対してgnosis.xml.objectify やElementTree などのモジュールでは、（実際のパースには基本的にexpat パーサを利用してはいるものの）それぞれのタグやコンテンツのようなものに遭遇する度にPython機能へのコールバックが必要になってしまいます。Pythonでのファンクション・コールのオーバー・ヘッドは、（特にC呼出しの手軽さに比べると）ばかになりません。原理的には、Pythonインタプリタに渡す前に完全なデータ構造を構築する、expat ベースでCコードによるPython拡張モジュールを書くことができるでしょう（速度的にはpyRXP と同じくらいでしょう）。ただし、そうした拡張モジュールを作成するのは、pyRXP ラッパを使った場合よりも、はるかにプログラミング作業が大変になります。これはたとえCであっても、それぞれのタグやコンテンツごとにコールバックするexpat の動作をプログラミングする必要があるためです。これに対してRXP は、パーサそのものの内部にデータ構造を作ります。

pyRXPのタプル・ツリー・データ構造

pyRXP は（RXP 自体も）、XML文書を効率的で軽いツリー構造で表現します。pyRXP におけるツリーの各ノードは、単純に次の形式のタプル(tuple)として表現されます。

(tagname, attr_dict, child_list, reserved)

特別なPythonクラスは何も使われていません。ただ・・・タプル、辞書、リスト、そして文字列（"reserved"にNoneが使われますが・・・）だけです。驚くかもしれませんが、XML文書上のすべての情報を表現するのにこの形式で問題ないのです。タグ名（tagname）には、そのままの文字列を格納し、属性辞書（attr_dict）は、（ご想像の通り）"属性"と"値"をマッピングした辞書になっています。子リスト（child_list）はさらに巧妙で・・・リスト内に（要素やコンテンツと混じって）一連のタプルとして配置されます。さらに、コンテンツの無い要素は空の子リストで表され、それ自身で閉じたタグはNoneで表されます。リスト２に、この構造の様子を示します。

リスト2. pyRXPタプル・ツリー・データ構造

                
>>> import pprint
>>> xml = '''<foo this="that" spam="eggs">
... <bar>1</bar><bar>2</bar>
... <baz></baz><baz/></foo>'''
>>> tree = Parser().parse(xml)
>>> pprint.pprint(tree)
('foo',
{'this': 'that', 'spam': 'eggs'},
['\n',
('bar', None, ['1'], None),
('bar', None, ['2'], None),
'\n',
('baz', None, [], None),
('baz', None, None, None)],
None)

XMLの情報はすべてここにありますが、その情報をたどっていくのは簡単ではないかもしれません。

上に戻る

データ・アクセス形式の対比

前回の記事で、テスト用のweblog.xml文書をフィルタリングして、そこからいくつかの情報を表示する簡単なアプリケーションのいろいろな実装を対比したことを思い出してください。このファイル中で一つの<entry>要素は、こんな風に見えるでしょう。

リスト3. weblog.xmlのエントリ・レコード

                
<entry>
  <host>64.172.22.154</host>
  <referer>-</referer>
  <userAgent>-</userAgent>
  <dateTime>19/Aug/2001:01:46:01</dateTime>
  <reqID>-0500</reqID>
  <reqType>GET</reqType>
  <resource>/</resource>
  <protocol>HTTP/1.1</protocol>
  <statusCode>200</statusCode>
  <byteCount>2131</byteCount>
</entry>

weblog.xmlファイルには、こうしたエントリが何千とあります。gnosis.xml.objectify を使ったフィルタは、こんな感じになるでしょう・・・

リスト4. select_hits_xo.py

                
                
from gnosis.xml.objectifyimport XML_Objectify, EXPAT
weblog = XML_Objectify('weblog.xml',EXPAT).make_instance()
interesting = [entryfor entryin weblog.entry
              if entry.host.PCDATA=='209.202.148.31'
                

                              and entry.statusCode.PCDATA=='200']
for ein interesting:
print
                "%s (%s)" % (e.resource.PCDATA, e.byteCount.PCDATA)

同じアプリケーションをpyRXP タプル・ツリーではどう書いたら良いでしょうか・・・。残念ながら、ネストされたリストや数値化されたタプル位置をいちいち見ていかなければならないので、アクセスは単純には行きません。

リスト5. select_hits_rxp1.py

                
                
from pyRXPimport Parser
TAGNAME,ATTRS,CHILDREN = range(3)
weblog = Parser().parse(open('weblog.xml').read())
interesting = []
for childin weblog[CHILDREN]:
    if child[TAGNAME]!='entry':continue
    gotHost, gotStatus =0,0
                

                    for fldin child[CHILDREN]:
         tag = fld[TAGNAME]
        if tag=='host'
                and fld[CHILDREN]==['209.202.148.31']:
             gotHost =1
                

                        elif tag=='statusCode'
                and fld[CHILDREN]==['200']:
             gotStatus =1
                

                    if gotHostand gotStatus:
         interesting.append(child[CHILDREN])
for ein interesting:
    resource, byteCount ='',''
                

                    for fldin e:
        if fld[TAGNAME]=='resource':
             resource = fld[CHILDREN][0]
        elif fld[TAGNAME]=='byteCount':
             byteCount = fld[CHILDREN][0]
    print
                "%s (%s)" % (resource, byteCount)

タプル位置を表すために定数名を使っていますが、このコードが読みにくいことは間違いないでしょう（それでもタプル・ツリーを直接扱う上で、最善の方法だと思います）。出力は同じですが、このpyRXP 版では（25秒ではなく）5秒でこの出力が得られます。

pyRXP モジュールは、その他のいくつかのファイルと共に提供されていますが、そうしたファイルのうち面白いのはxmlutils という一つのモジュールです。うまく作れば、xmlutils.TagWrapperクラスは、pyRXP タプル・ツリーのプロキシ・ラッパとして動作します。全体的な効果として、gnosis.xml.objectify やElementTree で提供されていたのと同様に、ネイティブのPythonスタイルでタプル・ツリーにアクセスすることができるようになります。

リスト6. select_hits_rxp2.py

                
                
from pyRXPimport Parser
import xmlutils
tree = Parser().parse(open('weblog.xml').read())
weblog = xmlutils.TagWrapper(tree)
interesting = [childfor childin weblog
              if child.tagName=='entry'
                

                              if str(child.host)=='209.202.148.31'
                

                              if str(child.statusCode)=='200']
for ein interesting:
print
                "%s (%s)" % (e.resource, e.byteCount)

ここまでは、まずまずでした。コードは大変優雅です。ただしプロキシによるオーバー・ヘッドが増えてしまいます。この方法でのスクリプトは5秒ではなく、7.5秒で実行されます。これでもgnosis.xml.objectify での25秒よりずっと早いと言えますが・・・。別の見方をすれば、フィルタがプロキシのオーバー・ヘッドに費やすこの2.5秒は、select_hits_xo.pyがフィルタリングに費やす時間の約1/10秒に対応しています。パースの段階でこの差は吸収されてしまいますが、XML文書を一度パースしてから、（ユーザ仕様によるなどの理由で）何百と言うフィルタリング動作をするアプリケーションを考えると、プロキシ・ラッパの魅力は薄れてきます。ただし、pyRXP の開発者たちはxmlutils がまだ実験途上のものだと言っているので、今後もっと効率的なラッパが開発される可能性があります。

上に戻る

LT XMLを使う

LT XML ツール・キットはRXP 上で作成され、XMLを取り扱う各種のコマンドライン・ツールや、RXP 自体にあるAPIよりも高度なAPIをいくつか持っています。LT XMLの強力なツールの一つにsggrepと言われるものがありますが、これは言ってみればXMLファイルのgrepのようなものです。文法はちょっと分かりにくいですが、基本的には正規表現とXPathsを組み合わせた表現を定式化したものです。

LT XML ツールとしては他に以下のようなものが含まれます。

textonly: タグを取り外して、PCDATAの内容を出力します
sgsort: XML要素をソートします
sgcount: 要素を数えます
xmlnorm: XMLドキュメントを正規化します

これらのツールは、入力、出力のそれぞれでパイプを使うので、コマンド・ライン上やシェル・スクリプト内で組み合わせて使用することができます。さらに、多くのツール名の頭についている「sg」を取り去ってみると、非XML版の、類似ツールに関係していることも分かります。

sggrepのクエリのいくつかをパイプで互いにつなげると言う面白いテクニックがあります。それぞれのsggrepコマンドで、メイン・クエリとサブ・クエリの両方を指定することができます。例えば、「内容がbaz である<bar>要素を含んだ<foo>要素が欲しい」とします。メイン・クエリで<foo> を要求し、サブ・クエリでは子要素<bar> とそのパターンを指定します。sggrepの問い合わせには2つの書式・・・クエリ、サブ・クエリ、パターンのそれぞれを "-q"、"-s"、"-t" スイッチを使って明確に指定する冗長な書式と、スイッチを省略した、よりコンパクトな書式（パターンあるいはパターンとサブ・クエリを省略する場合には "--" スイッチを使います）・・・があります。リスト7に示すような、いくつかのコマンドの組み合わせで、先ほど説明したフィルタ処理を行うユーティリティとほぼ同じことができます。

リスト7. webhost.xmlをフィルタ処理する複合クエリ

                
% cat weblog.xml |
  sggrep '.*/entry' '.*/entry/host' '209.202.148.31' -- |
  sggrep -q '.*/entry' -s '.*/entry/statusCode' -t '200' |
  sggrep '.*/resource|byteCount' -- |
  textonly -s '\n'

このコマンドの出力はあまり適切ではなく、こんな風に行が分かれてしまっています。

/publish/programming/regular_expressions.html
45674

Pythonのフィルタであれば、１行ごとに出力されるのですが・・・

/publish/programming/regular_expressions.html (45674)

awk、sed、trのような標準のUnixシェルのツールをうまく使えば、多分望む通りの出力が得られるはずです。

sggrepや他のLT XML ツールの良い点は非常に高速なことで、TagWrapperのオーバー・ヘッドを伴わないpyRXP と同じくらいです。さらに、同梱されているユーティリティで使われているすべての機能は、類似のAPIを使おうとするCプログラマにも提供されています。それになによりもうれしいのは、既にLT XML 自体にPythonバインディングがあることです（ただ興味深いことに他のスクリプト言語のバインドはありません・・・）。

参考文献

RXP パーサのホームページを見てください。
Davidによるヒント、コマンド・ラインXML処理がdeveloperWorks (2003年5月）にありますので読んで下さい。
David Mertzによる、XMLライブラリに関する以前のコラムは次のようなものです
- XMLの論考: 第2回 では、その時点では単にxml_objectifyと呼ばれたgnosis.xml.objectifyを紹介しました。(developerWorks 2000年8月)。
- XMLの論考: 第11回では、幾つかの初期改良をしたgnosis.xml.objectifyの最新情報をお知らせしました。新しい機能の幾つかは、このコラムでは紹介しきれませんでしたが、モジュールのHISTORYと他の文書ファイルを見てください。（2001年6月）
- XMLの論考第14回では、Haskellの遅延パターンを使った関数型プログラム言語用にHaXmlモジュールを取り上げました。（2001年10月）
- XMLの論考第18回では、RubyのREXMLライブラリをとり上げました。（2002年3月）
- XMLの論考第28回ではFredrik LundhのElementTree XML APIをとり上げました。（2003年6月）
XMLに関する参考文献がdeveloperWorksXMLゾーンに多数あります。.
IBM WebSphere Studioは、Javaや他の言語でXML開発を自動化するツール群です。
XMLおよび関連技術においてIBM認定開発者になる方法についてはこちらを参照してください。

著者について


		David Mertz氏は多くの分野で活躍しています。ソフトウェア開発や、それについて著述もしています。その他、学術政策理念について分野を問わず、関係する雑誌に記事も書いています。かなり以前には、超限集合論、ロジック、モデル理論などを研究していました。その後、労働組合組織者として活動していました。そして、David Mertz氏自身は人生の半ばにもまだ達していないと思っているので、これから何かほかの仕事をするかもしれません。David Mertz氏の連絡先はmertz@gnosis.cxです。

記事の評価

この記事を共有する


del.icio.us	newsing	FC2ブックマーク

Choix！	ニフティクリップ	Yahoo!ブックマーク

MM/memo	CZブックマーク	livedoorクリップ

はてなブックマーク	Buzzurl（バザール）

上に戻る

日本IBMについて

プライバシー

お問い合わせ