正規表現を否定する方法 - /home/by-natures/dev*

「正規表現」に対する理解は学術的・実用的な点で大きく異なります。学問の中で出てくる「正規表現」は、特定の言語を表す規則を定義するもので、有限オートマトン（DFA）と言語クラスが等しいものです。この場合の正規表現の定義は非常にシンプルで、規則をまとめるカッコ、任意回の繰り返しを表すアスタリスクなど、いくつかの記号しか出てきません。

一方で Java, Perl, Ruby など多くのプログラミング言語で利用できる「正規表現」は非常に多くの拡張が加えられています。多用される後方参照もそのうちの一つであり、先読み・後読みも正規表現の実装における拡張です。今回は「否定の先読み」にフォーカスを当てつつ、学術的な正規表現と実用的な正規表現の違いを少し見てみます。

正規表現は否定を上手く表せない？
オートマトンで考えてみる
改めて否定の正規表現を考えてみる
参考

正規表現は否定を上手く表せない？

「正規表現では否定を上手く表せない」とたまに聞きますし、私も学生時代に演習問題を通じて習いました。具体的な例を見てみましょう。まずは「xを含まない文字列」から。

# 例1: x を含まない文字列
^[^x]*$

簡単ですね。では「文字列 xy を含まない文字列」を作ってみましょう。

# 例2: 文字列 xy を含まない文字列
^([^x]|x[^y])*x?$

急に複雑になりました。例2 は、(1) x 以外か、(2) x が来た直後に y 以外の文字が来るかどちらか表現しています。最後の x? は、x で終わる場合((2)のケースで途中で終わる場合)を表現しています。

では同様に「文字列 xyz を含まない文字列」を作ってみましょう。

# 例3-1: 文字列 xyz を含まない文字列（通常）
^([^x]|x[^y]|xy[^z])*(x|xy)?$

例3-1 は例2 の延長で考えられます。x 以外か、x が来た直後に y 以外の文字が来るか、xy が来た直後に z 以外の文字が来るか、と表現しています。

次は、データベースに郵便番号を格納した場合を考え、正しい郵便番号のフォーマット（例：123-4567）以外で登録された行を検索したいとします（簡潔さのため、実際に存在する郵便番号かはチェックせず、フォーマットのみを確認します）。この場合の正規表現は次の通りです。基本的な考え方は、例3 の「文字列 xyz を含まない文字列」と同様です。

# 例4-1: 正しい郵便番号でない文字列（改行は分かりやすさのため）
^(?:\d|\d\d|\d\d\d|\d\d\d-|\d\d\d-\d|\d\d\d-\d\d|\d\d\d-\d\d\d|
    (?:[^\d]|\d[^\d]|\d\d[^\d]|\d\d\d[^-]|\d\d\d-[^\d]|
       \d\d\d-\d[^\d]|\d\d\d-\d\d[^\d]|\d\d\d-\d\d\d[^\d]|\d\d\d-\d\d\d\d.+).*)$

もっと簡単に書けるかもしれませんが、郵便番号程度でも愚直に正規表現を作製するとかなり複雑になることが分かります。これが「正規表現では否定を上手く表せない」と言われる理由です。反対に、正しい郵便番号のみを受理する正規表現を書いてみると、上の例がいかに複雑かが分かります。

# 例4-2: 正しい郵便番号である文字列
^\d\d\d-\d\d\d\d$

オートマトンで考えてみる

正規表現と等価な言語クラスで、有限オートマトン（DFA）があります。この有限オートマトンを用いて、例4-1 の郵便番号の例を記述してみます。

正しい郵便番号でない文字列（例4-1）と、正しい郵便番号の文字列（例4-2）は、上記オートマトンの受理状態と拒否状態を入れ替えるだけで構築できます。否定の正規表現が複雑だったのに対し、表現として等価な有限オートマトンでは、否定の表現がとても簡単です。

改めて否定の正規表現を考えてみる

例4-1 で仰々しい正規表現を作ってしまった一方で、等価な言語クラスである有限オートマトンでは否定の表現が簡単であることを見ました。有限オートマトンで出来るんだから、正規表現でももっと簡単に書けるはず！と思って少し調べてみました。

プログラム側で判定を反転させる

コーディングしている段階であれば、正誤を反転させるのが最もシンプルです。以下の例では、正規表現の否定演算子「!~」を用いています

test_str = "000"
if /^\d\d\d-\d\d\d\d$/ !~ str
then
    # 行いたい処理
end

注意点としては、正規表現にマッチしないので、後方参照も使えなくなってしまいます。

後方参照を用いる

ややトリッキーな解決方法として、後方参照を用いる方法があります。

test_str = "000"
m = /^(?:\d\d\d-\d\d\d\d|(.*))$/.match(test_str)
if m[1].nil?
then
    # 行いたい処理
end

正しい郵便番号の場合は左側の評価で止まり、正しくない郵便番号の場合は、グループ化されている右側の正規表現「.*」が評価されます。マッチした後に分岐させるため、コードを読む側が少し戸惑う可能性はあります。

否定の先読みを使う

上記解決案はどちらもプログラム側で解決するものでした。しかし既に存在するメソッドやライブラリに引数として正規表現を渡さなければいけない場合など、否定を表す正規表現が必要な場面もあるでしょう。

先日業務中に、郵便番号の例と似たようなことがありました。「この形式以外の ID をデータベースから取得して欲しい」というものです。処理自体はバッチに正規表現を渡せばよいのですが、「この形式『以外』」と指定されたため、正規表現だけで対応可能なのかを調べていると、否定の先読みに辿りつきました。

否定の先読みを備えた処理系であれば、xyz を含まない文字列は次のように書けます：

# 例3-2: 文字列 xyz を含まない文字列（否定先読み）
^(?!.*xyz).*$

例3-1 と比べても簡潔になりました。これを利用して、郵便番号の例を Ruby で書くと次のようになります：

test_str = "000"
if /^(?!\d\d\d-\d\d\d\d).*$/ =~ str
then
    # 行いたい処理
end

この否定先読みですが、肯定先読みと合わせて DFA への変換が提示されており、言語クラスとしては等価なようです（森畑明昌氏：PPL2011 推薦論文「先読み付き正規表現の有限状態オートマトンへの変換」PDF 資料）。理論上はあくまでも正規表現で表せることを簡単にしているだけですが、実用上は大変便利ですね。

少し調べたところ、一部の正規表現確認ツールでは利用できませんでしたが、Java, Scheme(Gauche), PHP, Ruby, Perl, Python 等、ほとんどの処理系で利用可能なようです。使いこなすには慣れが必要そうですが、普通に正規表現を書いていてはどうしても複雑になってしまいそうな場合に思い出すとよいかもしれません。

先読み・後読みの詳しい使い方ついて詳細を割愛してしまいましたが、a_bicky 氏のブログ：あらびき日記の「(正規表現の先読み・後読みを極める！)https://abicky.net/2010/05/30/135112/」に大変詳しい解説がされていますので、合わせてご覧ください。