概要

python で re モジュールを使って、正規表現書いていたときにたまたま知ったのでメモメモ。

python の標準モジュール re では、アトミックグループの指定がサポートされていないんですね。

アトミックグループって何ぞや

正規表現を使って処理をする場合、対象の行が10万行とかあると結構な時間がかかります。そういうときって、各行で0.1秒処理時間が違うだけでも全体として見ると結構違いがでたりします。正規表現で処理する場合、処理時間に差がでる要因の一つに

「バックトラックの発生頻度」

があります。バックトラックの発生を減らすと処理速度が速くなる場合が多い。

通常の正規表現は「最長一致」で、指定されたパターンで「可能な限り」前に進んでいきます。

例えば

という文字列があった場合に

\d*

というパターンと指定すると、数字の連続を全て飲み込みます。

\d*:

というパターンを指定した場合でも、最初の「\d*」が数字部分全部を飲み込んで、その後で、残りの「:」についてマッチするかどうかを判定することになります。今いる最後の文字は「6」なので当然マッチしない。なので、正規表現エンジンはバックトラックして位置を探し直します。

（後ろに下がって、次は「5」を判定、これもマッチしないので、後ろに下がって「４」、、、とどんどんバックトラックしていく）

これが発生すればするほど、処理時間がかかります。通常だと、バックトラックは当然発生していいものなのですが、人間の目で予め確認していて

「このパターンの場合はこのタイミングでマッチしなかったら、後ろを振り返らなくていいから、即アンマッチにして」

って頼む指定が「アトミックグループ」となります。

上記のパターンをアトミックグループ指定すると

(?>\d*):

となります。

アトミックグループが指定されている場合、正規表現エンジンはマッチしなかった場合にバックトラックせずに即判定を終了します。

予め、パターンがきっちり特定できていて、かつ、処理しないといけないデータ量が多い場合にちょっと便利です。

正規表現に卓越しているわけじゃないので、うまく説明できていないかもしれませんが。。。。

regex モジュールを使う

アトミックグループ指定したいところですが、標準モジュール re がサポートしていないので

サードパーティライブラリの regex モジュールを使います。

(というか、この regex モジュールについて公式ドキュメントにも記載があります。)

bit.ly

参考サードパーティの regex モジュールは、標準ライブラリの re モジュールと互換な API を持ちながら、追加の機能とより徹底した Unicode サポートを提供します。

インストールはいつものとおり

(venv) $ python -m pip install regex

で終わりです。

サンプル

んで、ちょっとしたサンプルです。最初に無駄にめっちゃ大きなデータを作っておいて、わざとマッチしないようにして処理しています。

"""
正規表現のサンプルです。

アトミックグループ (Atomic Groups) について

REFERENCES:: http://bit.ly/2O3jVNn
             http://bit.ly/2NXqocl
             http://bit.ly/2NVGi71
             http://bit.ly/2NXEg6m
"""
import re

import regex

from trypython.common.commoncls import SampleBase
from trypython.common.commonfunc import stopwatch, pr

_message = '1' * 300000000


# noinspection PyMethodMayBeStatic
class Sample(SampleBase):
    def exec(self):
        # ------------------------------------------------------------------------
        # アトミックグループについて
        # -----------------------------------------
        # 正規表現で処理する場合、処理速度に差がでるのは以下の部分
        #     - バックトラックの発生頻度
        # バックトラックの発生を以下に防ぐかによって処理速度に差が出る。
        # 通常の正規表現は「最長一致」であり、指定されたパターンで「可能な限り」
        # 前に進んでいく。例えば, 「123456」という文字列があった場合に
        # 「\d*」というパターンを指定すると、数字の連続をすべて飲み込む。
        # 「\d*:」というパターンを指定した場合でも、最初の「\d*」が
        # 数字部分全部を飲み込み、その後で、残りの「:」についてマッチするかどうかを
        # 判定することになる。マッチしないので、正規表現エンジンはバックトラックして
        # 位置を探しなおす。このバックトラックが発生すればするほど処理に時間がかかる。
        #
        # このような場合に、「ここまできて失敗したのなら、バックトラックする必要なし」
        # ということを事前に通知することができる。
        # このときに指定するのが「アトミックグループ」となる。
        # アトミックグループの挙動は、「グループ内のパターンに一旦マッチした後は
        # その中のステートを全て破棄し、バックトラックさせないようにする」というもの。
        #
        # アトミックグループは、以下の書式で定義する
        #     (?>pattern)
        # 上のパターンをアトミックグループの指定に変更すると以下のようになる。
        #     (?>\d*):
        #
        # ただし、問題が一つあって、python の標準モジュール re は
        #     アトミックグループに対応していない
        # 無理矢理同じことを行うようには出来るみたい。(http://bit.ly/2O3jVNn 参照)
        #
        # 標準モジュールではないが、PYPI に regex というモジュールがあり
        # こちらは、アトミックグループに対応している。(http://bit.ly/2NXqocl 参照)
        # インストールする場合は以下を実行
        #   $ python -m pip install regex
        #
        # アトミックグループ指定している場合、バックトラックが発生しないので
        # マッチしない場合の判定がとても速くなる。(通常のモードだとマッチしないか
        # どうかを最終判定するまでにバックトラックを繰り返さないといけないため)
        # ------------------------------------------------------------------------

        # アトミックグループ指定なし
        stopwatch(self.normal)()

        # 標準モジュール re で、無理矢理
        stopwatch(self.atomic_stdlib_re)()

        # 外部ライブラリ rexex でアトミックグループ指定
        stopwatch(self.atomic_regex_module)()

    def normal(self):
        global _message
        m = re.match(r'\d*:', _message)
        if m:
            pr('normal', 'マッチした')
        else:
            pr('normal', 'マッチしない')

    def atomic_stdlib_re(self):
        global _message
        m = re.match(r'(?=(?P<tmp>\d*:))(?P=tmp)', _message)
        if m:
            pr('atomic_stdlib_re', 'マッチした')
        else:
            pr('atomic_stdlib_re', 'マッチしない')

    def atomic_regex_module(self):
        """Python の 標準モジュール re は、アトミックグループをサポートしていない。
        http://bit.ly/2O3jVNn に記載されているように、無理やり評価させることも可能
        らしいのだが、「regex」モジュールを pip でインストールして利用する方が楽。
        「regex」モジュールは、(?>pattern)の書式をサポートしている。
        """
        global _message
        m = regex.match(r'(?>\d*):', _message)
        if m:
            pr('atomic_regex_module', 'マッチした')
        else:
            pr('atomic_regex_module', 'マッチしない')


def go():
    obj = Sample()
    obj.exec()


if __name__ == '__main__':
    go()

try-python/re04.py at master · devlights/try-python · GitHub

結果は例えば以下のようになりました。

normal='マッチしない'
----------------ELAPSED TIME: 3.553----------------
atomic_stdlib_re='マッチしない'
----------------ELAPSED TIME: 3.857----------------
atomic_regex_module='マッチしない'
----------------ELAPSED TIME: 0.229----------------

わざとめっちゃ大きなデータにしたので、差が大きく出ていますが「マッチしない」ってなったときにバックトラックが発生していないので、その分処理時間が速くなるってことですね。

過去の記事については、以下のページからご参照下さい。