« スパコン「京」を目撃 | メイン | ローカルメールサーバーのセットアップ »

 特定の文字列を含まないという正規表現

正規表現で、特定の文字列を含まないパターンを記述するのは難しい。

その文字列の文字数が少なければ、例えば"ABC"を含まないとするなら

([^A]|A[^B]|AB[^C])*
という方法がありそうで、筆者は時々やってしまうのだが、これは正しくない。"AABC"があると"AA"がA[^B]にマッチ、"ABABC"があると"ABA"がAB[^C]にマッチしてスルーしてしまうし、"A"や"AB"で終わるとマッチしないからである。
この方向で進めると、一例としては、
([^A]|A(B?A)*([^AB]|B[^AC]))*(A(B?A)*B?)?
という式になるそうだが(大崎 博基さんの「Perl正規表現雑技」より)、これは少なくとも筆者には読めない。

特定の文字を含まない、という式は、例えば"A"を含まないなら[^A]*と簡単に書けるのに、特定の文字列を含まない、となると途端に難しくなるのは不思議である。

特定の文字列を含まない行にマッチする、よく知られたパターンとして、

(?!.*ABC).*
というやつがある。(?!...)はnegative lookahead assertion(否定先読み)というやつで、その先に...が続かない、という条件を表す。(?=...)はその先に...が続くというpositive lookahead assertionであり、ABC(?=DEF)は"ABCDEF"の"ABC"にマッチし、ABC(?!DEF)は"ABCDEF"の一部でない"ABC"にマッチする。
(?=...)(?!...)は、POSIX仕様などの正規表現の古い仕様には含まれず、grepなど一部使えない処理系があるが(Emacsもサポートしていない。外部コマンドを活用しろということらしい)、PerlやJavaScriptでもサポートされており、現在はほとんどの処理系で使えると言える。

(?!.*ABC).*の弱点は、文字列全体のマッチにしか使えないことである。例えば、文字列中の"STA"〜"END"の部分を検索したいが、途中に"ABC"を含む場合は除外したいと思って、STA(?!.*ABC).*ENDと書くと、"STAxxENDxABC"のように、"END"の後に"ABC"がある場合もマッチしなくなってしまう。

今回、そういうのが必要になって、悩みながら、何かいい方法は無いかと思ってWeb上を探してみたら、

((?!ABC).)*
というのを見つけた。この文字から先が"ABC"でない任意の文字が0個以上、である。すごい発想だと思った。

Web上には(.(?!ABC))*と書いている例もあり、同じだと勘違いして、早速(.(?!ABC))*を使い始めたのだが、よく考えると(.(?!ABC))*には問題があることに気付いた。これだと、"ABC"を2文字目から検索することになり、先頭がABCの場合に除外されず、マッチしてしまうのである。さらに、例えば、途中に"EN"を含まない"STA"〜"END"の部分を検索するつもりでSTA(.(?!EN))*ENDと書くと、途中に"EN"が無くても、"END"の直前の1文字が必ず.(?!EN)に当てはまらない("END"の"EN"で引っ掛かる)ので、何にもマッチしなくなってしまう。
((?!ABC).)*にはこれらの問題は起こらない。
それと対称にして、(?<!)のnegative lookbehind assertionを使って(.(?<ABC))*としても上記の問題は起こらないが、より複雑だし、手元のPerlで試すと10%ほどの速度低下が見られたので、これを使うメリットは無いだろう。

結局、外側の()によって後で参照可能なグループが増えないように、(?:(?!ABC).)*という形にすることによって、筆者の問題は解決した。

regex - Regular expression to match line that doesn't contain a word? - Stack Overflow
を読むと、もし速度を求めるなら、((?!ABC).)*より高速かも知れないな方法がいくつかあるようだ。


(?:(?!ABC).)*

?:を付けて、後で読み出せるように保存しないようにするだけで25%ほど速くなったらしいが、筆者がPerlで試した限りではほとんど変わらなかった。


(?>[^A]+|A(?!BC))*

(?>...|...|...)というのはatomic groupというやつで、括弧内の最初にマッチしたパターン以外にはマッチしない。[^A]でどこまで"A"を含まないかを見つけてそこまで進み、"A"があれば"ABC"かどうかを調べる、というのを繰り返す動作になるようだ。筆者がPerlで試した所、マッチする文字列の割合が多いほど速く、大体10%〜30%くらい速くなる結果になった。
しかし、このatomic groupは、Perlでは使えるが、Pythonでは使えない。Regular Expressions ReferenceSpecial Groupsのページを見ると、サポートされる処理系が限られるようだ。
なお、atomic groupを使わず、
(?:[^A]+|A(?!BC))*
と書いているページがあるが、筆者がPerlやPythonで試した所、これだとマッチしない文字列に対して非常に遅く、Perlだと2.5倍、Pythonだと100倍以上の時間が掛かった。


^(?>(?:.*?ABC)?)^.*$

除外したいパターンにマッチさせた後に、まだ行頭に居るかどうかで調べている。
行全体にマッチさせる場合に限られるが、確かに速そうである。
筆者がPerlで試した所、90%ほど速かった。


^(?(?=.*?ABC)(?#fail)|.*)$

(?(?=...)...|...)というのはlookaround conditionalという条件分岐であり、Perlでは使えるが、Pythonでは使えない。
これも行全体にマッチさせる場合に限られる("ABC"が範囲外のずっと後方にあってもマッチしてしまうから)が、筆者がPerlで試すと倍以上速かった。


ところで、(?!...)が使えない場合は、(.*ABC.*|(.*))としてできる2つのグループの後者を使って、マッチするかどうかを確かめたり、マッチする部分を取り出すという方法があるようだが、これだと正規表現を使うコードの助けが必要であり、それなら文字列全体を検査するなら.*ABCがマッチするかどうかで分岐すれば良いし、部分文字列を検索するなら、例えばSTA(.*)ENDを検索して、別途グループ1が.*ABCにマッチするかどうかを確かめれば良いと思う。

トラックバック

このエントリーのトラックバックURL:
http://ynomura.dip.jp/cgi-bin/mt/mt-tb.cgi/230

コメント投稿フォーム

※投稿されたコメントはオーナーが承認するまで表示されません。


Powered by Movable Type 3.35