no_mkd
はじめに：（余談ですが、ここをクリックしてスキップ>>）
概要で述べたように、正規表現は膨大な知識体系であり、単純なメタ文字の表でも、数言で説明できるものでもありません。
「...もしコンピュータの歴史において偉大な発明を挙げるとすれば、正規表現（Regular Expression）はその一つであり、Web、Lisp、ハッシュアルゴリズム、UNIX、リレーショナルモデル、オブジェクト指向などと並び、その数は決して20項目を超えないだろう...」と評する人もいます。
このように言っても、まだ重要性を感じないかもしれません。正規表現という言葉は聞いたことがあり、メタ文字の表を見れば既存の式も理解できるものの、実際の開発で使う機会は少ないと感じているからではないでしょうか...
確かにその通りです。では、正規表現はまだ生きているのでしょうか？どこへ行ったのでしょうか？
答えは、正規表現はすでにプログラミング言語、オペレーティングシステム、および関連アプリケーションに浸透しています。例えば、多くの高級言語が提供する `String.find()` のようなメソッドや、多くのOSが提供するファイル内容検索コマンド（Linuxの `grep` コマンドなど）は、すべて正規表現に関連しています。
では、正規表現が「消えた」（浸透した）のであれば、学習する必要はあるのでしょうか？もちろんです。正規表現は一つの技術であり、一つのツールをマスターすることよりも、技術の意義を理解することの方が遥かに大きな価値があるからです。
2.正規表現エンジン
4.バックトラック
5.正規表現の最適化
8.まとめ
9.付録表【メタ文字表】【モード修飾子表】【特殊メタ文字表】
一. 正規表現の動作原理
一つの正規表現が対象文字列に適用される具体的なプロセスは以下の通りです：
-
正規表現のコンパイル
正規表現の構文の正しさをチェックし、正しければ内部形式にコンパイルします。
-
駆動開始
伝達機構が正規表現エンジンを対象文字列の開始位置に「位置決め」します。
P.S.「伝達」を簡単に説明すると、エンジン内部のメカニズムです。例えば、`[abc]` を `family` という文字列に適用する場合、まず先頭の `f` を試し、失敗し、次に2番目の `a` を試し、成功してマッチが終了します。この「一文字ずつ」の処理（1番目を試し、失敗したら2番目を試す...）を制御しているのが、いわゆる伝達機構です。
-
要素の検査
エンジンが正規表現とテキストのマッチングを開始します。一文字ずつ前に進むだけでなく、バックトラック（後ろに戻る）プロセスも含まれます（バックトラックは重点事項なので、後で詳しく説明します）。
マッチ結果の導出
成功か失敗かの結果を確定させます。具体的なプロセスはエンジンの種類によって異なり、例えば最初に完全一致した文字列を見つけた時点で成功を返すものや、最初に見つけた後も探し続け、最長の一致を返すものなどがあります。
-
駆動プロセス
現在の位置で適切なマッチが見つからなかった場合、伝達機構がエンジンを動かし、次の文字の位置から新しい試行を開始します。
マッチの完全な失敗
伝達機構がエンジンを文字列の末尾まで動かしても適切なマッチが見つからなかった場合、マッチ失敗を宣告します（簡単に言えば、最初から最後までマッチしなければ失敗ということです。あえて難しく記述しているのは、内部原理に近づけるためです）。
二. 正規表現エンジン
いわゆる正規表現エンジンのタイプとは一つの分類です。前述したように、正規表現は技術であり、誰もがそれを使って問題を解決できますが、解決の考え方は人それぞれです。つまり、具体的な実装やルールが異なります。長期的な発展を経て、最終的にいくつかの流派が形成され、それぞれ異なるルールを推進しています。
一般的な流派（エンジンのタイプ）には以下のものがあります：
- NFA（非決定性有限オートマトン）
- DFA
- POSIX NFA
- DFA、NFA混合型
各エンジンの分類基準を知る必要はなく、相互の違いと、普段使っているツールがどの分類に属するかを理解すれば十分です。非常にシンプルです：
NFA
該当ツール：Java, GNU Emacs, grep, .NET, PHP, Python, Rubyなど
違い：NFAは、いわば正規表現主導型のエンジンです。マッチングの効率が正規表現の内容（例えば選択肢の順番など）に密接に関係するからです。
DFA
該当ツール：awk, egrep, flex, lex, MySQL, Procmailなど
違い：DFAはテキスト主導型のエンジンです。マッチングの効率はテキ��ト（対象文字列）にのみ依存します（等価であれば異なる形式の式でも効率は同じです。例えば `[a-d]` と `[abcd]`。NFAではこれら2つの効率は異なり、一般的には前者が優れています）。
POSIX NFA
該当ツール：mawk, Mortice Kern System's utilitiesなど
違い：マッチングの成否にかかわらず、すべての可能性を試し、マッチ可能な最長の文字列を見つけようとします。
DFA、NFA混合型
該当ツール：GNU awk, GNU grep/egrep, Tcl
違い：最も成熟した優れたエンジンと言えます。内部最適化が比較的完璧に行われており、DFAとNFAの両方の長所を兼ね備えています。しかし、現在このエンジンを採用しているツールは少ないです。
長々と述べましたが、知っておくべきことはこれです：
正規表現をサポートするツールを使用する前に、そのエンジンがどのタイプに属するかを知ることは極めて重要です。エンジンによって具体的な動作メカニズムが異なるためです。例えば、PHPの正規表現ライブラリはNFA型に属し、マッチングは式の内容に密接に関係します。したがって、効率を高めるために式を合理的に最適化する必要があります。
三. ルックアラウンド（lookaround）
[この項目を独立させる必要はないかもしれませんが、ルックアラウンドを知らない人や、聞いたことはあっても難しそうだと感じている人が多いため、あえて個別に議論します（決して難しくありません）]
1. ルックアラウンドとは何か？
文字通り、周囲を見渡すことです。正規表現のルックアラウンドも同じ道理です。――ある位置まで進んだら、まず左右を見て、その位置が探している条件に合致するかどうかを確認します。
例えば、`(this|that)` を使って `there is a boy lying under that tree.` をマッチさせる場合、NFAエンジンでは効率が非常に低くなります。以下のように動作します：
- まず、1文字目の `t` で `this` をチェックし、`i` と `e` が一致しないため、次に `that` をチェックし、`a` と `e` が一致しません。
- 1文字進んで `h` へ行き、`this` をチェック... `that` をチェック...
- さらに進んで `e` へ行き...
- ...
無駄な作業が多いです。ではどう最適化すべきでしょうか？
接頭辞を抽出する（一般的な最適化手法の一つ）ことができ、`th(is|at)` になります。
ここではルックアラウンドの議論なので、ルックアラウンドで解決すると、`(?=th)(this|that)` になります。えっ、最初の `(?=)` がわからない？
大丈夫です。これは「肯定の先読み」です。意味は：先頭から後ろに向かって進み、`th` に出会ったら立ち止まり、`(?=th)` の後ろの部分 ―― `(this|that)` と比味します。【逆に言えば、`th` に出会わなければ立ち止まらず、そのまま後ろへ進み続けるということです。効率が変わりそうですよね？】
最適化後は比較回数が明らかに減少します。もちろん、この例でルックアラウンドを使うのは大げさかもしれませんが、あくまで簡単な例として捉えてください。
2. ルックアラウンドの種類と役割
| タイプ | 正規表現 | マッチ成功の条件 |
| 肯定先読み (Positive Lookahead) | (?=...) | 右側のテキストが部分式にマッチする |
| 肯定後読み (Positive Lookbehind) | (?<=...) | 左側のテキストが部分式にマッチする |
| 否定先読み (Negative Lookahead) | (?!...) | 右側のテキストが部分式にマッチしない |
| 否定後読み (Negative Lookbehind) | (?<!...) | 左側のテキストが部分式にマッチしない |
P.S. 上記の左右とは、マッチングが行われている現在の位置の左右を指します。これは一般的なマッチングとは異なります：
肯定先読み `(?=a)abc` で `family` をマッチさせる場合、初期位置は `f` の位置ではなく `f` の前になります。なぜでしょうか？
【ルックアラウンド構造はいかなる文字にもマッチせず、テキスト内の特定の「位置」にのみマッチする】からです。もし現在位置が `f` と `a` の間であれば、肯定先読みは成功し、そこから `abc` の検査を開始します。
肯定先読みを使うことで、実際に比較を開始する位置を制限でき、試行回数を減らすことができます。
3. ルックアラウンドの応用
ルックアラウンドは主に式の最適化や、他の特殊な場面（ルックアラウンドを使わざるを得ない場面。通常は他の複雑な構造で代用可能ですが）で使用されます。
例えば、`the land blongs to these animals` から単語 `the` だけをマッチさせ、`these` の中の `the` を避けるにはどうすればよいでしょうか？
単語の境界（エンジンがサポートしていれば）を使えば簡単で、`\bthe\b` でグローバルマッチを行えば解決します。
この例では、`the(?!\w)` を使うこともできます。前の `the` が `these` の中の `the` にマッチしても、後ろの否定先読み `(?!\w)` が `these` を排除します（この否定先読みは、`e` の後ろが英単語の構成文字であってはならないと限定しています。厳密には `\w` は `[a-zA-Z0-9]` と等価であり、この場面で完全に適切かは別として、例としては成立します）。
四. バックトラック（最適化を語る前の非常に重要な問題）
簡単に言えば、バックトラックとは、試していない分岐まで戻ること（あるいは予備の状態に戻ること）です。
簡単な例として、`.*!` を使って `"An idel youth, a needy age!", an old saying said.` という文字列をマッチさせます。
- まず、`*` は `.` を修飾し、任意の数の任意の文字にマッチします。さらに `*` は「最長一致（貪欲）」です。
- そのため、`.*` は文字列全体（`A` から末尾の `.` まで）にマッチします。この時、後に続く `!` がマッチできないことが判明します。どうすればよいでしょうか？
- `.*` がマッチした部分を少し返却して、`!` がマッチする機会を与えます。末尾の `.` を返却しますが、`!` はマッチしません。
- さらに返却を続け、次は `d` ですが、一致しません。
- ...
- `age` の後の `!` が返却されたところで、マッチが成功します。
この `.*` が文字列全体を占有して���ら、`!` のために返却を余儀なくされるまでのプロセスが、バックトラック（エンジンが逆走している状態）です。
このようなバックトラックは明らかに無意味で時間の無駄です。私たちが行う最適化の大きな部分は、バックトラックの回数を減らすことです。
別の見方をすれば、バックトラックを減らすことはマッチングの効率を高めること、あるいはエンジンが処理を開始してから結果（成功/失敗）を返すまでの時間を短縮することであり、それこそが最適化です。
五. 正規表現の最適化
効率の指標
正規表現の効率を測る指標は主に2つあります：試行（比較）回数とバックトラック回数です。
式の正確性を保証した上で、これらは少ないほど良いです。回数が少ないほど、適切なマッチを素早く見つける（または素早く失敗を返す）ことができます。
最適化の操作
最適化には2つの方向があります：
特定の操作を高速化する
エンジンの内部実装を考慮する必要があります。例えば、一般的にNFAエンジンでは、`[\d]` は `[0-9]` より速く、`[0-9]` は `[0123456789]` より速いです。
冗長な操作を避ける
すなわち正確な制限です。前述のルックアラウンドの例のように、マッチ開始位置を制限することで効率を大幅に高められます。
ただし、位置の制限に多くの時間を費やしてマッチ全体の効率が落ちてしまうようでは本末転倒です。バランスが重要です。
最適化すべきか？どの程度まで最適化すべきか？は、具体的な利用シーンに合わせて判断する必要があります。
一般的な最適化手法
非常に多くの手法がありますが、ここでは最も一般的なものを挙げます：
不要な括弧を削除する
多くの場合、`()` は単に範囲を限定するためだけで、テキストをキャプチャする必要がないことがあります。その場合は、キャプチャグループ `()` の代わりに非キャプチャグループ `(?:)` を使うべきです。メモリ消費を抑えるだけでなく、効率も向上します。
不要な文字クラスを削除する
特殊文字を表すのに `[.]` のような文字クラスを使う習慣がある人もいますが、`\.` で代用できます。同様に `[*]` は `\*` などになります。
繰り返しのコンパイルを避ける
他の言語で正規表現を使う際の注意点です。例えば、Javaである正規表現をテキストに適用する場合、まずコンパイルが必要です。同じ式であれば一度コンパイルすればよいため、ループの中にコンパイル処理を置かないようにし、余計な時間を節約します。
開始アンカーを使用する
これは習慣づけるべき良い習慣です。例えば、`.*` で始まる多くの式は、前に `^` または `\A` を付けて行や段落の先頭であることを示せます。これにどんな利点があるでしょうか？
古いエンジンではこの効果は絶大です。もし `.*` が対象文字列を一通り試してマッチしなかった場合、先頭に `^` がなければ、エンジンは文字列の2文字目からまた新しい試行を開始します...。しかし、これは明らかに無意味です（一通り終われば結果は出ているので、2周目以降は必要ありません）。
発展したエンジンでは、`.*` で始まる式に `^` がない場合、エンジンが自動的に開始位置フラグを付与して無意味な試行を避ける自動最適化を行いますが、自分たちで `^` を付ける習慣を持つべきです。
文字テキストを独立させる
例えば `[xx*]` は `[x+]` より速く、`x{3, 5}` より `xxxx{0, 2}` の方が速く、`th(?:is|at)` は `(?:this|that)` より速いです。
六. 効率的な正規表現の書き方
正規表現を書く際は、以下の手順に従うべきです：
- 期待するテキストにマッチさせる
- 期待しないテキストを排除する
- 制御しやすく、理解しやすいものにする
- 効率を保証し、素早く結果（成功/失敗）を出す
最初の2点は正確性を保証し、後ろの2点は効率と使いやすさのバランスをとるためのものです。これが原則です。
ここで非常に有名な言葉を引用します。――「赤ん坊を産湯と一緒に流さない」（大切なものを不要なものと一緒に捨ててはいけない）
七. 間違いやすいポイント
[-./] と [.-/] と [./-] の違い
一見同じに見えますが、1番目と3番目は等価であり、その位置の文字がハイフン、ドット、またはスラッシュのいずれかであることを示します。
2番目の式は誤りです。その位置の文字が、ドットからスラッシュまでの間のすべての文字のいずれかであることを示します（ここでの `-` は `[a-z]` のような範囲指定として扱われます）。ドットとスラッシュの間にどのような文字が存在するかは文字セット環境に依存し、Unicodeであれば意図しない多くの文字が含まれることになります。
文字クラスの中で `-` を使うときは、その位置に注意し、このようなエラーを避ける必要があります。
[] の内側と外側での ^ の違い
外側にある `^` は行の先頭を、`$` は行の末尾を表します。内側にある `^` は「否定（`[^...]` はいわゆる否定文字クラス）」または単なる文字（`[...^]`）を意味します。
[ab]* と (a*|b*) の違い
等価に見えますが、特殊なケースがあります：前者は `aba` にマッチしますが後者はしません。また、前者の方が効率的です。
量詞修飾子 (?+*) を使用する際の注意点
量詞が入れ子になっている場合、意味を慎重に考える必要があります。無限ループ（無限のバックトラック）を引き起こす可能性があるからです。例えば `"(\.|[^\"]+)*"` を使ってダブルクォーテーション内の文字列（バックスラッシュでエスケープされたものを含む）をマッチさせようとすると、この式はループに陥り、マッチ結果が永遠に得られないことがあります。
入れ子があれば必ずループするわけではありませんが、式の中に量詞の入れ子が現れる場合は非常に慎重に扱うべきです。
八. まとめ
個人的な正規表現への見解は以下の通りです：
もし正規表現を深く理解していないのであれば、複雑な問題を正規表現で解決しようとしないでください（あるいは非常に長い式を書こうとしないでください）。そこにある落とし穴は理解しがたく、完璧な正規表現を構築するには極めて緻密な思考が必要です。一般的な用途であれば、プログラムによる文字列処理の方が制御しやすい場合が多いです。
もちろん、正規表現を全く使うなという意味ではありません。特定の場面（テキストからURLを抽出するなど）で、正規表現が代替不可能な魔法のような役割を果たすことは認めざるを得ません。
そして、たとえ自分が使わなくても、正規表現を十分に理解しておくべきです。他人が書いたコードを読む際に必ず遭遇するからです。
後方参照（Backreference）
あまり一般的ではありませんが、正規表現内で既にマッチした部分を引用することができます：
// js code
var regex = /(\w{2,4}).+\1.+\1/i;
console.log(regex.test('qwer11qwe213234qw')); // true
console.log(regex.test('qwer11qwe213234q')); // false
未知の繰り返しシーケンスを含む文字列（*繰り返しシーケンスの出現回数はわかっているが、具体的なシーケンスの内容がわからない場合*）を検出するために使用されます。上の例での繰り返しシーケンスは `qw` です。
九. 付録表【メタ文字表】【モード修飾子表】【特殊メタ文字表】
1. メタ文字表（多くのツールで共通してサポートされているもの）
| メタ文字 | 名称 | 意味 |
| ^ | 行頭アンカー | 行の開始位置 |
| $ | 行末アンカー | 行の終了位置 |
| . | ドット | 任意の1文字（通常、改行文字 \n を除く） |
| [] | 文字クラス | 括弧内のいずれかの1文字にマッチ（必ず1文字にマッチする必要あり） |
| [^] | 否定文字クラス | 括弧内の文字以外のいずれかの1文字にマッチ |
| \char | エスケープ | charの別の意味を表す。例えば \^ は行頭ではなく文字としての ^ を表す |
| () | キャプチャグループ | 量詞の適用範囲の限定、またはマッチしたテキストのキャプチャ（後方参照で利用可能） |
| (?:) | 非キャプチャグループ | グループ化は行うが、テキストのキャプチャは行わない |
| ? | クエスチョン | 量詞：直前の要素が0回または1回出現することを示す |
| * | アスタリスク | 量詞：直前の要素が0回以上出現することを示す |
| + | プラス | 量詞：直前の要素が1回以上出現することを示す |
| {min, max} | 範囲指定 | 量詞：直前の要素が少なくともmin回、多くともmax回出現することを示す |
| {num} | 固定回数 | 量詞：直前の要素がちょうどnum回出現することを示す |
| | | パイプ | 「または」。複数の選択肢のいずれかにマッチさせる |
| \< | 単語の開始境界 | 単語の開始位置を示す |
| \> | 単語の終了境界 | 単語の終了位置を示す |
| \num | 後方参照 | num番目のキャプチャグループでマッチしたテキストを参照する |
2. モード修飾子表（ツールによって異なる場合があります）
| 修飾子 | 意味 |
| i | 大文字小文字を区別しない |
| g | グローバルマッチ。対象テキスト内のすべてのマッチ箇所を探す（デフォルトは最初の一つのみ） |
| x | 拡張モード。式を複数行に分けたりコメントを含めたりできる |
| m | マルチラインモード。^ と $ が文字列全体ではなく、各行の先頭と末尾にマッチする |
| s | ドットオールモード。ドットが改行文字を含むすべての文字にマッチする |
3. 特殊メタ文字表（一部のツールでサポートされているもの）
| メタ文字 | 意味 |
| \d | 数字。`[0-9]` と等価 |
| \D | 非数字。`[^0-9]` と等価 |
| \w | 英数字およびアンダースコア。`[a-zA-Z0-9_]` と等価 |
| \W | 非単語構成文字。`[^a-zA-Z0-9_]` と等価 |
| \s | 空白文字（スペース、タブ、改ページ、復帰、改行など） |
| \S | 非空白文字 |
| \b | 単語の境界（開始または終了位置） |
| (?>...) | アトミックグループ（固化分组）。一度マッチした文字をバックトラックで手放さない |
| ??, +?, *?, {min, max}? | 最短一致の量詞（Lazy quantifiers）。可能な限り短い内容にマッチさせる |
| ?+, ++, *+, {min, max}+ | 強欲な量詞（Possessive quantifiers）。アトミックグループと同じ意味 |
※上記の内容は、筆者が以下の参考書籍を読んで理解した内容に基づいています。
参考書籍：『詳説 正規表現』（Jeffrey E.F. Friedl 著）
書評：この本は章立ての進め方、内容の強調、さらにはレイアウトまで非常に優れています（すべての思考問題の答えが次のページをめくらないと見えないようになっているユニークな構成です）。正規表現を深く理解するのに非常に役立ちます。興味のある方はぜひ読んでみてください。
コメントはまだありません