目次


lxml を使用して Python での XML 構文解析をハイパフォーマンスにする

充実した機能を備えたこの XML 構文解析およびシリアライズ用スイートの限界に挑む

Comments

lxml の紹介

Python が XML ライブラリーの不足に悩まされたことは今まで一度としてありませんでした。バージョン 2.0 からは、お馴染みの xml.dom.minidom とそれに関連した pulldom、そして SAX (Simple API for XML) モデルが組み込まれ、バージョン 2.4 からは人気の ElementTree API が組み込まれるようになっています。それに加え、より上位レベルのインターフェースや、より Pythonic なインターフェースを提供するサード・パーティーのライブラリーは常に出回っています。

サイズが小さいファイルの単純な DOM (Document Object Model) や SAX の構文解析には、どの XML ライブラリーでも十分対応できますが、開発者は次第に大きなデータ・セットに直面するようになり、Web サービスのコンテキストにおいてリアルタイムで XML を構文解析する必要に迫られています。今のところ、経験を積んだ XML 開発者たちはその簡潔さと表現力を理由に XPath や XSLT などの XML 固有の言語を使うという選択をするだろうと思いますが、XPath の宣言型の構文にアクセスすると同時に、Python に用意された汎用機能もそのまま使えるとしたら理想的です。

lxml はハイパフォーマンス特性を実証するとともに、XPath 1.0、XSLT 1.0、カスタム要素クラス、さらには Pythonic なデータ・バインディング・インターフェースのネイティブ・サポートを備えた最初の Python XML ライブラリーです。lxml は libxml2libxslt をベースにして作成されており、この 2 つの C ライブラリーが、構文解析、シリアライズ、および変換といった中核となるタスクに対する処理能力の大部分を担っています。

lxml のどの部分をコードで使用するかは、XPath を扱うのに慣れているのか、Python のようなオブジェクトを操作したいのかなど、それぞれのニーズ次第です。あるいはシステムに大規模なツリーを保持しておくためのメモリーがどれだけあるかによっても左右されます。

この記事では lxml のすべてを網羅することはせず、極めてサイズの大きい XML ファイルを効率的に処理し、高速処理とメモリー使用量の節約を実現するために最適化を行う手法を、無料で入手できる 2 つのサンプル文書を使用して説明します。サンプル文書の 1 つは Google によって XML に変換された米国著作権更新データ、そしてもう 1 つは Open Directory RDF のコンテンツです。

この記事で lxml の比較対象としているのは cElementTree のみで、他にも使用可能な多数の Python ライブラリーとは比較していません。ここで cElementTree を選んだ理由は、このモジュールは Python 2.5 に標準装備されており、lxml と同じように C ライブラリーをベースとしているからです。

大量のデータに伴う困難とは

多くの場合、XML ライブラリーは小さなサンプル・ファイルを対象に設計され、テストも小さなファイルを使って行われます。実際、多くのプロジェクトはデータが完全に揃わないうちに開始されるのが現実です。プログラマーはサンプル・コンテンツを使って何週間、あるいは何か月もこつこつと作業を続け、リスト 1 に示すようなコードを作成します。

リスト 1. 単純な構文解析操作
from lxml import etree
doc = etree.parse('content-sample.xml')

lxml の parse メソッドは、文書全体を読み取ってメモリー内ツリーを作成します。lxml ツリーはノードの親への参照をはじめとして、ノードのコンテキストに関して保持する情報量が多いため、cElementTree と比べると lxml ツリーのほうが遙かにコストがかかります。サイズが 2GB にもなる文書をこのように構文解析した場合、マシンの RAM が 2GB であればマシンはすぐにスワップ状態になり、パフォーマンスの壊滅的な劣化を示すことになります。このような大量のデータをメモリー内で使用可能にするという前提でアプリケーション全体が作成されているとしたら、大々的なリファクタリングは避けられません。

反復型構文解析

メモリー内ツリーを作成するのが適切でない、あるいは実際的でない場合には、ソース・ファイル全体の読み取りに依存しない反復型構文解析手法を使用してください。lxml では、以下の 2 つの方法を使用できます。

  • ターゲット・パーサー・クラスを指定する
  • iterparse メソッドを使用する

ターゲット・パーサー・メソッドを使用する

ターゲット・パーサー・メソッドは、SAX イベント駆動型コードを使い慣れている開発者にはお馴染みのはずです。ターゲット・パーサーは、以下のメソッドを実装するクラスです。

  1. start は、要素が開かれると呼び出されるメソッドです。要素のデータと子ノードはまだ使用可能になっていません。
  2. end は、要素が閉じられると呼び出されるメソッドです。要素の子ノードはテキスト・ノードを含めてすべて、使用可能になっています。
  3. data は、子ノードであるテキスト・ノードの処理の際に呼び出され、そのテキストにアクセスするメソッドです。
  4. close は、構文解析の完了時に呼び出されるメソッドです。

リスト 2 は、必要なメソッドを実装するターゲット・パーサー・クラス (ここでは TitleTarget という名前) を作成する例です。このパーサーは、Title 要素の子ノードであるテキスト・ノードを内部リスト (self.text) に収集し、close() メソッドに達した時点でこのリストを返します。

リスト 2. Title タグの子ノードであるテキスト・ノードの全リストを返すターゲット・パーサー
class TitleTarget(object):
    def __init__(self):
        self.text = []
    def start(self, tag, attrib):
        self.is_title = True if tag == 'Title' else False
    def end(self, tag):
        pass
    def data(self, data):
        if self.is_title:
            self.text.append(data.encode('utf-8'))
    def close(self):
        return self.text

parser = etree.XMLParser(target = TitleTarget())

# This and most other samples read in the Google copyright data
infile = 'copyright.xml'

results = etree.parse(infile, parser)    

# When iterated over, 'results' will contain the output from 
# target parser's close() method

out = open('titles.txt', 'w')
out.write('\n'.join(results))
out.close()

上記のコードを著作権データに対して実行した結果、処理時間は 54 秒でした。ターゲット構文解析はかなり短時間で行われ、メモリーを大量に消費する構文解析ツリーを生成することはありませんが、データに含まれるすべての要素に対してすべてのイベントが発生します。非常に大きな文書で、少数の要素だけを対象とする場合には、この例のような方法は望ましくありません。処理対象を選択したタグだけに限定して、パフォーマンスを改善することは可能でしょうか。

iterparse メソッドを使用する

lxml の iterparse メソッドは、ElementTree API の拡張です。iterparse は選択された要素のコンテキストを対象に Python イテレーターを返します。このメソッドは、モニター対象とするイベントのタプルとタグ名という 2 つの有用な引数を受け入れます。この例で興味があるのは、<Title> のテキスト・コンテンツのみです (これは、end イベント到達時に使用可能になります)。リスト 3 の出力は、リスト 2 のターゲット・パーサー・メソッドの出力とまったく同じですが、lxml がイベント処理を内部で最適化することが可能なため、処理速度は遙かに向上するはずです。さらに、コードの行数もかなり少なくなっています。

リスト 3. 名前付きタグとイベントの単純な繰り返し処理
context = etree.iterparse(infile, events=('end,'), tag='Title')

for event, elem in context:
       out.write('%s\n' % elem.text.encode('utf-8'))

上記のコードを実行して出力をモニターすると、最初のタイトルは素早く出力されますが、それからまもなくして速度が落ちてくることがわかります。top の簡単なチェックでは、コンピューターがスワップ状態になったことが示されます。

PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  COMMAND                
170 root      15  -5     0    0    0 D  3.9  0.0   0:01.32 kswapd0

何が起こっているのかと言うと、iterparse は最初の段階ではファイル全体を使用しないものの、繰り返し処理ごとにノードへの参照を解放しません。これは、文書全体に繰り返しアクセスするときの特徴ですが、この例では各ループの最後でその分のメモリーを取り戻したほうが遙かに得策です。解放すべきノード参照には、処理済みの子ノードまたはテキスト・ノードへの参照と、現行ノードより前にある兄弟ノードでルート・ノードからの参照が暗黙的に保持されているノードへの参照も含まれます (リスト 4 を参照)。

リスト 4. 不要なノード参照をクリアするように修正した繰り返し処理
for event, elem in context:
    out.write('%s\n' % elem.text.encode('utf-8'))        

    # It's safe to call clear() here because no descendants will be accessed
    elem.clear()

    # Also eliminate now-empty references from the root node to <Title> 
    while elem.getprevious() is not None:
        del elem.getparent()[0]

便宜上、リスト 4 をリファクタリングして、呼び出し可能な func を引数に取って現行ノードに対する操作を行う関数にしています (リスト 5 を参照)。これ以降の記事のサンプルでは、このメソッドを使用します。

リスト 5. コンテキストをループして毎回 func を呼び出し、不要な参照をクリーンアップする関数
def fast_iter(context, func):
    for event, elem in context:
        func(elem)
        elem.clear()
        while elem.getprevious() is not None:
            del elem.getparent()[0]
    del context

パフォーマンス特性

リスト 4 の最適化した iterparse 手法は、リスト 2 のターゲット・パーサーと同じ出力を生成しますが、処理時間はその半分です。この例でのようにタスクを特定のイベントとタグ名に制限すると、cElementTree にも増して処理が速くなります (ただし構文解析が主要なアクティビティーとなっている場合、大抵は cElementTree のほうが lxml よりもパフォーマンスに優れた結果となります)。

表 1 に、各パーサー手法の処理時間を記載します。測定に使用したのは、ベンチマークの囲み記事で説明したコンピューターで、対象は著作権データです。

表 1. 反復型構文解析メソッドの比較: <Title> からの text() 抽出
XML ライブラリーメソッド平均処理時間 (秒)
cElementTreeIterparse32
lxmlターゲット・パーサー54
lxml最適化 iterparse25

パフォーマンスとデータ量の関係

リスト 4 と同じ iterparse メソッドを Open Directory データに対して実行すると、1 回の実行につき 122 秒かかります。これは、著作権データの構文解析にかかる時間の約 5 倍です。Open Directory データの量も著作権データの約 5 倍 (1.9 ギガバイト) なので、ファイルのサイズが非常に大きいとしても、このメソッドの処理時間はファイル・サイズにほぼ比例すると予測できます。

シリアライズ

XML ファイルで必要な操作が、1 つのノード内から何らかのテキストを取得することだけならば、単純な正規表現を使用することも考えられます。おそらくそのほうが、XML パーサーよりも高速に動作するでしょう。けれども XML データはそもそも複雑なので、実際には正規表現で正しく操作することは不可能に近く、私もお勧めできません。正確なデータ操作が必要な場合には、XML ライブラリーが極めて貴重な存在となります。

XML をストリングまたはファイルにシリアライズするには、libxml2 C コードに直接依存する lxml が他の何にも増して勝っています。タスクに何らかのシリアライズが必要な場合、lxml 以外の選択肢は考えられませんが、このライブラリーから最高のパフォーマンスを引き出すにはいくつかの秘訣があります。

サブツリーのシリアライズには deepcopy を使用する

lxml は子ノードと親ノード間の参照を維持します。これによる効果の 1 つとして挙げられるのは、lxml ではノードがたった 1 つの親しか持てないことです (cElementTree には親ノードという概念はありません)。

リスト 6 では、著作権ファイルの各 <Record> を取り、タイトルと著作権情報のみが含まれる単純化した 1 つのレコードを書き込んでいます。

リスト 6. 要素の子ノードのシリアライズ
from lxml import etree
import deepcopy 

def serialize(elem):
    # Output a new tree like:
    # <SimplerRecord>
    #   <Title>This title</Title>
    #   <Copyright><Date>date</Date><Id>id</Id></Copyright>
    # </SimplerRecord>
    
    # Create a new root node
    r = etree.Element('SimplerRecord')

    # Create a new child
    t = etree.SubElement(r, 'Title')

    # Set this child's text attribute to the original text contents of <Title>
    t.text = elem.iterchildren(tag='Title').next().text

    # Deep copy a descendant tree
    for c in elem.iterchildren(tag='Copyright'):
        r.append( deepcopy(c) )
    return r

out = open('titles.xml', 'w')
context = etree.iterparse('copyright.xml', events=('end',), tag='Record')

# Iterate through each of the <Record> nodes using our fast iteration method
fast_iter(context, 
          # For each <Record>, serialize a simplified version and write it
          # to the output file
          lambda elem: 
              out.write(
                 etree.tostring(serialize(elem), encoding='utf-8')))

単一ノードのテキストを複製するためだけに deepcopy を使用しないでください。それだけのためなら、新しいノードを作成し、そのテキスト属性を手動で入力してからシリアライズしたほうが時間はかかりません。私が行ったテストの結果では、deepcopy<Title><Copyright> の両方に対して呼び出した場合、リスト 6 のコードよりも 15 パーセント速度が落ちました。deepcopy による大幅なパフォーマンスの向上は、大きな子孫ツリーをシリアライズする場合にもたらされます。

リスト 7 のコードを使用して cElementTree のベンチマークを実行したところ、lxml のシリアライザーのほうが約 2 倍速く処理が完了しました (95 秒に対し、50 秒の結果)

リスト 7. cElementTree を使ったシリアライズ
def serialize_cet(elem):
    r = cet.Element('Record')

    # Create a new element with the same text child
    t = cet.SubElement(r, 'Title')
    t.text = elem.find('Title').text

    # ElementTree does not store parent references -- an element can
    # exist in multiple trees. It's not necessary to use deepcopy here.
    for c in elem.findall('Copyright'):
       r.append(h)
    return r

context = cet.iterparse('copyright.xml', events=('end','start'))
context = iter(context)
event, root = context.next()

for event, elem in context:
    if elem.tag == 'Record' and event =='end':
        result = serialize_cet(elem)
        out.write(cet.tostring(result, encoding='utf-8'))
        root.clear()

この繰り返しパターンについての詳細は、ElementTree 資料の「Incremental Parsing」を参照してください (リンクは「参考文献に記載されています)。

要素を素早く見つける方法

構文解析が完了すると、一般的なほとんどの XML タスクでは、解析したツリー内で特定の対象データを見つけることになります。lxml では単純化された検索構文から完全な XPath 1.0 に至るまで、複数の検索方法を使用することができます。ユーザーとしては、それぞれの方法のパフォーマンス特性と最適化手法を認識しておかなければなりません。

findfindall は使用しないようにすること

ElementTree API から継承された find メソッドと findall メソッドは、ElementPath と呼ばれる単純化された XPath のような式言語を使用して 1 つ以上の子孫ノードを見つけます。ElementTree から lxml に移行しているユーザーは当然、find/ElementPath 構文を引き続き使用することができます。

lxml は他にもサブノードの検索オプションとして、iterchildren/iterdescendants メソッドと真の XPath の 2 つを提供しています。式がノード名と一致しなければならない場合、iterchildren または iterdescendants メソッドにオプションのタグ・パラメーターを設定して使用したほうが、それぞれに相当するElementPath 式を使用するよりも断然、処理時間が短くなります (場合によっては 2 倍の速さ)。

それよりも複雑なパターンの場合は、XPath クラスを使用して検索パターンをプリコンパイルしてください。タグ引数を設定した iterchildren の振る舞いを真似た単純な検索パターン (例えば、etree.XPath("child::Title")) は、これに相当する iterchildren と事実上同じ時間で実行が完了しますが、プリコンパイルしておくことが重要です。ループの実行ごとに検索パターンをコンパイルしたり、ある要素に対して xpath() を使用したりすると (lxml のドキュメントで説明しています。「参考文献」を参照)、その検索パターンを一度コンパイルしてそれを繰り返し使用する場合よりも 2 倍近く時間がかかることがあります。

lxml での XPath 評価は短時間で行われます。ノードのサブセットだけをシリアライズする必要がある場合には、正確な XPath 式で事前に制限すると、すべてのノードを後で検査するより遙かに効率的です。例えば、リスト 8 の例のようにシリアライズを制限して night という言葉が含まれるタイトルだけを含めるようにすると、一式すべてをシリアライズする時間を 60 パーセントにまで短縮することができます。

リスト 8. XPath クラスを使用した条件付きのシリアライズ
def write_if_node(out, node):
    if node is not None:
        out.write(etree.tostring(node, encoding='utf-8'))

def serialize_with_xpath(elem, xp1, xp2):
    '''Take our source <Record> element and apply two pre-compiled XPath classes.
    Return a node only if the first expression matches.
    '''
    r = etree.Element('Record')

    t = etree.SubElement(r, 'Title')
    x = xp1(elem)
    if x:
        t.text = x[0].text
        for c in xp2(elem):
            r.append(deepcopy(c))
        return r

xp1 = etree.XPath("child::Title[contains(text(), 'night')]")
xp2 = etree.XPath("child::Copyright")
out = open('out.xml', 'w')
context = etree.iterparse('copyright.xml', events=('end',), tag='Record')
fast_iter(context, 
   lambda elem: write_if_node(out, serialize_with_xpath(elem, xp1, xp2)))

文書の別の部分にあるノードを検索する場合

iterparse を使用しているとしても、現行ノードより先にあるノードをベースに XPath 述部を使用できることに注意してください。night という言葉が含まれるタイトルのレコード直前にあるすべての <Record> ノードを検索するには、以下のようにします。

その一方で、リスト 4 で説明したメモリー効率の良い繰り返しの手法を使用している場合には、以下のコマンドを実行しても何も返ってきません。構文解析が文書で進むにつれ、前に処理されたノードがクリアされるためです。

この特定の問題を解決する効率的なアルゴリズムを作成することも可能ですが、通常は、eXist などの XQuery を使用する XML データベースには、ノード (特に、文書に不規則に分散される可能性のあるノード) の分析を伴うタスクのほうが適しています。

その他のパフォーマンス改善方法

実行速度に影響を与えるには、lxml に含まれる特定のメソッドを使用する以外にも、他のライブラリーによる手法を使うこともできます。そのうちのいくつかは単純なコード変更ですが、その他の方法ではサイズの大きいデータの問題に対処する方法に関する新しい見方が必要になります。

Psyco

Psyco モジュールは見過ごされがちな方法ですが、Python アプリケーションの速度を最小限の作業で向上させます。純粋な Python プログラムでの標準的な速度向上は 2 倍から 4 倍です。ただし、lxml はその作業の大部分を C で行うことから、実行時間の差は非常に小さいものとなります。Psyco を有効にしてリスト 4 を実行した結果、実行時間はわずか 3 秒短縮されただけでした (47.3 秒に対して、43.9 秒)。Psyco には大幅なメモリー・オーバーヘッドがあるため、マシンがスワップ状態にならざるを得ないような場合には効果がまったくなくなる可能性もあります。

一方、lxml で駆動するアプリケーションのコア・コードが、頻繁に実行される Python コード (テキスト・ノードでの拡張ストリング操作など) である場合には、これらのメソッドにのみ Psyco を有効にすると効果があるかもしれません。Psyco についての詳細は、「参考文献」を参照してください。

スレッド化

アプリケーションが内部の C で駆動される lxml 機能に大幅に依存している場合には、マルチプロセッサー環境でスレッド化アプリケーションとして実行するとパフォーマンス上のメリットがもたらされることがあります。ただし、スレッドの開始方法にはいくつかの制約事項があります (XSLT では特に顕著です)。詳細は、lxml 資料のスレッドに関する FAQ セクションを参照してください。

分割による効果

著しく大きな文書を個別に分析可能なサブツリーに分割できるとしたら、(lxml の高速シリアライズを利用して) 文書をサブツリー・レベルで分け、これらのファイルでの作業を複数のコンピューターに分配するという手段もあります。オンデマンド仮想サーバーを利用する方法は、CPU バウンドのオフライン・タスクを実行するためのソリューションとしてますますよく使用されるようになっており、Python プログラマー向けに Amazon の仮想 EC2 (Elastic Compute Cloud) クラスターをセットアップおよび管理するための順を追った説明も用意されているほどです。詳細は、「参考文献」を参照してください。

大量のデータを扱う XML タスクに一般的なストラテジー

この記事で紹介した具体的なサンプル・コードは、個々のプロジェクトには当てはまらないかもしれません。しかし、ギガバイト以上の XML データに直面したときには、テストと lxml 文書によって裏付けられた原則を考慮してください。これらの原則を以下に示します。

  • 大規模な文書は、反復型構文解析の手法を使ってインクリメンタルに処理すること。
  • 文書全体を順不同に検索しなければならない場合は、索引付き XML データベースに移行すること。
  • 選択するデータには極めて慎重になること。特定のノードにだけ興味がある場合には、ノードの名前を基準にデータを選択するメソッドを使用してください。また、述部構文が必要な場合には、使用可能な XPath クラスおよび Xpath メソッドのいずれかを試してください。
  • 目前にあるタスクと開発者にとっての快適さを考えること。速度が懸念事項でない場合には、lxml の objectify や Amara などのオブジェクト・モデルが Python 開発者にとって使いやすいこともあります。また、構文解析のみが必要な場合には、cElementTree の速度が勝っています。
  • 単純なベンチマークを実行するときでもよく検討してから行うこと。何百万ものレコードを処理する場合には、小さな差が積み重なってくるものなので、どのメソッドが最も効率的であるかは必ずしも明らかでありません。

まとめ

多くのソフトウェア製品では、2 つしか特性を選択できないことによる注意が付きものです。つまり、速度、柔軟性、あるいは読みやすさのうちから 2 つだけを選ばなければなりません。しかし lxml を慎重に使用すれば、この 3 つすべてを実現することも可能です。DOM のパフォーマンスや、SAX のイベント駆動型モデルに四苦八苦している XML 開発者にとって、lxml はより上位レベルで Pythonic なライブラリーを扱う機会をもたらしてくれます。そして、Python の経験はあるが XML には慣れていないプログラマーたちにとっては、XPath と XSLT による表現能力を調べる簡単な方法となります。lxml ベースのアプリケーションでは、両方のコーディング・スタイルが見事に共存することができます。

lxml の機能は、この記事で説明した内容だけではありません。特に、ほとんど XML をベースとしていない小規模なデータ・セットやアプリケーションの場合には lxml.objectify モジュールを是非調べてみてください。また、HTML のコンテンツで整形式でない可能性のあるコンテンツには、lxml の 2 つのパッケージ、lxml.html モジュールと BeautifulSoup パーサーが役立ちます。さらに、XSLT から呼び出し可能な Python モジュールを作成している場合や、Python または C の拡張機能をカスタマイズしている場合には、lxml 自体を拡張することもできます。これらの内容については、「参考文献」で紹介している lxml のドキュメントを調べてください。


ダウンロード可能なリソース


関連トピック

  • Help getting lxml to work reliably on MacOS-X: このスレッドは、lxml を MacOS X にインストールする際の貴重な参考資料として役立ちます。
  • ElementTree Overview: ElementTree API および cElementTree についての詳細を調べてください。
  • Amazon EC2 Basics for Python programmers: Amazon のサービスをホストするこの仮想マシンがどのように機能するかを学んでください。
  • Incremental Parsing: ElementTree ドキュメントのこのセクションで、リスト 6 で使用した繰り返しパターンについての詳細を調べてください。
  • lxml: lxml のドキュメントはわかりやすいものの、カバーしている範囲の広さはほとんど圧倒されるほどです。特に大切な内容については、FAQ およびベンチマークのセクションを調べてください。
  • Google U.S. copyright renewal data: Google によって XML に変換されたこの米国著作権更新データをダウンロードして試してください (371MB、ZIP 形式、レコード数 426,907)。
  • Open Directory RDF コンテンツ: Open Directory データベースの RDF ダンプをダウンロードしてください (1.9GB、ZIP 形式、レコード数 5,354,663)。
  • eXist: XQuery を使用したこのオープンソースのデータベース管理システムを調べてみてください。
  • Psyco: Python コードの実行速度を大幅に向上させることが可能なこの Python 拡張モジュールについて詳しく学んでください。
  • Amara: 充実した機能セットと Pythonic API を備えたこの Python XML ライブラリーを試してみてください。Amara には lxml や cElementTree ほどのパフォーマンス特性はありませんが、ほとんどの XML タスクに大いに役立ちます。

コメント

コメントを登録するにはサインインあるいは登録してください。

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=60
Zone=XML, Open source
ArticleID=354448
ArticleTitle=lxml を使用して Python での XML 構文解析をハイパフォーマンスにする
publish-date=10282008