内向けの記事を書く。 正規表現の問題の解説記事である。 解説記事と言いつつ複数の解を提示してしかも結局どれも正解ではないというとんでもない結論に達してしまった……
追記: 最近このページに来る人が多いので付け加えておくのだが、 これはあくまで問題として出されたから正規表現を使っているのだ。 ここまでのことを正規表現で行うと可読性も落ちるし、バグがあっても気づきにくい。 自分なら正規表現を使わずに普通に判定用のプログラムを書く。
問題文
以下の単語にマッチする正規表現を書いてgrepで使うという問題である。
同じ文字の繰り返しが3回続く単語(2回であればballoon, coffee, succeedなど多数存在する)
この問題には複数の解釈があり、それぞれの解釈ごとにまた複数の解法がある。
なお、この記事内では問題のファイルではなくKotetのPCの/usr/share/dict/cracklib-smallの中身に対してgrepをかけているので注意である。
複数の解釈
1: Kotetの解釈 - “agreeeth”
同じ文字が3回ということで自分が考えたもの。 自分はすでにこの解釈で提出してしまっているのでもし出題意図が違っても修正できない。
ここでは後方参照という概念が必要になる。 まず自分の書いた正規表現を書いておく。
(.)\1{2}
以降構成要素を一つづつ取り上げていく。
ドット ( . )
“.” は任意の1文字にマッチする。
ABCという文字列の場合AとBとCがマッチする。
カッコ ( () )
“()“はグループ化をする。
例えば(AB)という正規表現はABCのABの部分にマッチする。
また、ここでマッチしたパターンをあとで再利用できる。
これを後方参照という。
たとえば(.)\1という正規表現を考えてみる。
まず最初に”.“があるので任意の1文字にマッチする。
ABCの場合Aである。
そしてこのマッチ結果が1から始まる番号の振られたバッファに保存される。
1番目のバッファにAが保存されたということになる。
バッファは\n(nはバッファの番号)で参照することができ、マッチ結果を普通に書いたのと同じように使える。
ABCのAまで読み込んだ時点で\1は(A)と同じになり、正規表現は(A)(A)であるかのように動き、したがって2文字目もAであるか調べるようになる。
ABCの場合2文字目はBなのでマッチしない。
以降も(B)(B)、(C)(C)と続き、結局この正規表現はABCのどの部分ともマッチしない。
ここまでくればおわかりだろう……というほど自分の説明能力に自身がないが、つまり(.)\1は同じ文字が2回続いた場合にマッチする正規表現である。
たぶんもっとわかりやすい説明がたくさんあるのでわからなかったら後方参照でググってみてほしい。
ここまでの知識でも問題を解くことができる。
先程の例に1つ継ぎ足して(.)\1\1とすれば答えである。
これは拡張正規表現なので -E オプションをつけて、さらに正規表現をクオート( ' )で囲っておくと確実である。
$ grep -E '(.)\1\1' < /usr/share/dict/cracklib-small
aaa
aaas
death666
devil666
gsxr1000
hal9000
ieee
iii
postov1000
satan666
viii
波括弧 ( {} )
“{}” は “*” や “+” のように繰り返しを表す。
“*” や “+” はそれぞれ0回以上と1回以上の繰り返しにマッチするが (たとえばA+はA、AA、AAAなどにマッチする) 、{}を使えば繰り返しの回数を細かく指定できる。
{2}はちょうど2回、{2,}は2回以上、{2,3}は2回以上3回以下を意味する。
ここまでの要素をすべて使ったのが自分の書いた正規表現である。 まず任意の文字列にマッチし、その後最初にマッチしたパターンが2回続く、という意味になる。 繰り返しは2回同じことを書くのが嫌で使ったが、むしろ文字数は増えているし再利用するような正規表現でもないので素直に2回書いたほうが良かったかもしれない。
$ grep -E '(.)\1{2}' < /usr/share/dict/cracklib-small
ちなみに拡張正規表現を使わないとこんな感じになる。
バックスラッシュがいっぱいで読みにくいので素直に -E をつけたほうがいいと思う。
$ grep '\(.\)\1\{2\}' < /usr/share/dict/cracklib-small
不具合: 4文字以上の繰り返しは不正か?
この正規表現は3文字の繰り返しがあったらそれ以上先は見ないので、aaaaなどの4文字以上の繰り返しの行も残ってしまう。
これを回避できないかちょっと試してみたが、どうも思うようにいかない。
だれか正規表現に詳しい人がいたら教えてほしい。
追記: 上記の問題を解決することができたのでここに書く。 解決はできたがこれは拡張正規表現ではなくPerl互換正規表現(PCRE)である。 仕組みを知りたい人は否定先読みでググってほしい。 やたら複雑になって可読性が低下した上に、たぶんこういう答えは求められていない。
$ cat test.txt
a
aa
aaa
aaaa
abbb
abbbb
aaab
aaaab
abbbc
abbbbc
aaaabbb
$ grep -P '(^|(.)(?!\2))(.)\3{2}(?!\3)(.|$)' < test.txt
aaa
abbb
aaab
abbbc
aaaabbb
2: @jjjohn_sonの解釈 - “bookkeep”
「繰り返し」が3回続く、という解釈。 これに基づいた回答を見るまで全くこの解釈ができることに気づかなかった。
こちらも同じ要素を使って解くことができる。 グループ化を多重に使うのでどのカッコが何番かちょっとわかりづらい。 どうも開きカッコが出現した順に番号が振られるようだ。 一番外側のカッコ(1番)は単にグループ化のためだけに使っているもので、後方参照は内側のカッコ(2番)でのみ使われていることに注意である。
この解釈の場合繰り返しの文字数については言及されていない(aaabbbbccなどもマッチする)ということになるのでそれも考慮した正規表現を書こうとしてみる。
$ grep -E '((.)\2+){3}' < /usr/share/dict/cracklib-small
bookkeep
bookkeeper
bookkeeper's
bookkeepers
bookkeeping
4文字の連続した文字が2つの連続として扱われる不具合
じつはこれだとaabbbbなどでもマッチしてしまう。
それを回避するバージョンも今の所思いついていないので誰かできたら教えてほしい。