正規表現で、特定の文字列を含まないパターンを記述するのは難しい。
その文字列の文字数が少なければ、例えば"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 ReferenceのSpecial 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にマッチするかどうかを確かめれば良いと思う。
コメント