正規表現の微妙さ。 パート2：払い戻しとその数量

パート1：文字クラスの内外のメタキャラクター 。



この部分では、正規表現エンジンの仕組み、正規表現が非常に遅いと考える人、なぜ多くのエンジンの作成者がPOSIX標準に従っていないのかについてお話したいと思います。



多くのタスクと同様に、「正規表現の文字列で一致を見つける」という問題を解決するための多くのアプローチと原則があります。 この場合の基本原則は、2：正規表現によって制御される一致する検索と、文字列によって駆動される一致する検索です。 これらの各原則の意味を詳しく見てみましょう。

ストリング駆動型マッチング

このタイプの正規表現エンジンは、いわゆるDFA（ 決定性有限状態マシン ）を使用して実装されます。 主な利点は、（別の原則と比較して）一致を見つけるのに非常に速いことです。 当然、この原則には多くの欠点があります（そうでなければ、面白くないでしょう？）。



第一に、コンパイル時間（プログラムのソースコードをコンパイルするのではなく、正規表現をエンジンの内部構造にコンパイルすることを意味します）は非常に長い場合があります（別の原則と比較して）。 実際、コンパイル中に、特定のパターンを比較するためのプログラム全体が作成されます。 DFAは文字列によって「制御」されており、コンパイル時に文字列がわからないため、考えられるすべての文字列を考慮してアルゴリズムが作成されます。 複雑な式の場合、これは明らかにそれほど高速ではありません。



第二に、DKAは、正規表現で慣れている便利で必要な機能の多くをサポートしていません。 たとえば、保持ブラケットはサポートされていません。 もちろん、DKAで利用可能なセットでは、多かれ少なかれ実際の状況で行うことは不可能です。 したがって、DKAは純粋な形ではほとんどどこでも使用されていません。 しかし、いわゆる「ハイブリッド」エンジンでうまく使用されています。最も単純な場合、特定の正規表現に最も適したエンジンを選択します。



したがって、大量のテキストを検索する必要があると同時に、正規表現がそれほど複雑でない場合、DKAよりも優れたものを見つけることは困難です。



それでは、DKAはどのように機能しますか？ このエンジンは、そのように機能するため、「ライン駆動」と呼ばれます。 ステートマシンは、一致を検出する行を読み取り、その行をパターンと比較します。 時間ごとに、アルゴリズムはパターンと文字列のどの部分が一致するかを「認識」します。 アルゴリズムが行全体を完全にスキャンすると、行の先頭に近い最長一致のみを選択し、それを回答として残します。



明確にするために、正規表現^abc\w+e$



と2行abcde



とabce



があると仮定します。 式が最初の行と一致することは明らかですが、2番目の行とは一致しません。



DKAメカニズムで一致の検索がどのように発生するかを考えてみましょう。 最初の行には次のシーケンスがあります。

• 文字列「a」の最初の文字-メタ文字^
  
  
  
  と位置が一致します。 1つの部分一致が見つかりました。
• 文字列「a」の最初の文字-パターンの2番目の文字の値と一致します。 アルゴリズムは引き続き1つの部分一致を導きます。
• 文字列「b」の2番目の文字-値がパターンの3番目の文字と一致します。 アルゴリズムは引き続き1つの部分一致を導きます。
• 文字列「c」の3番目の文字-パターンの4番目の文字と値が一致します。 アルゴリズムは引き続き1つの部分一致を導きます。
• 文字列「d」の4番目の文字-パターンの5番目のメタ文字\w
  
  
  
  値と一致します。 数量詞では、メタ文字の一致が少なくとも1回発生する必要があります。 条件が満たされます。 アルゴリズムは引き続き1つの部分一致を導きます。
• 文字列「e」の5番目の文字-パターンの8番目の文字と値が一致します。 前のメタ文字の量指定子条件が満たされ、「e」記号をパターンの8番目の文字との一致として、または\w
  
  
  
  メタ文字との一致としてカウントできます。 アルゴリズムはこれとそれの両方を行い、2つの部分一致をリードし続けます。 この点を忘れないでください。別の原則では、非常に大きな違いがあります。
• 行の6番目の文字が欠落しています- $
  
  
  
  メタ文字と位置が一致しています。 完全な一致が1つ見つかりましたが、2番目の部分一致は期待どおりではなく、破棄されます。
• 行が終わったので、結果を返します。

2番目のケースで何が起こるか：

• アルゴリズムの開始はまったく同じで、すぐに文字列「e」の4番目の文字に移動します
• 文字列「e」の4番目の文字の値は、パターン\w
  
  
  
  5番目のメタ文字と一致します。 量指定子条件では、1つの文字に対して少なくとも1つの一致が存在する必要があります。 したがって、「e」は\w
  
  
  
  メタ文字によってキャプチャされます。 1部分一致。
• 行の5番目の文字が欠落しています-「e」文字と一致するパターンはありません。 明らかに、文字列は一致しません。
• 行が終了し、一致するものはありません。結果を返します。

これらの2つの例で何がわかりますか？ アルゴリズムは、一致するかどうかは関係ありません。 文字ごとに1行ずつスキャンし、パターンに基づいて一致を照合します。 作業の最後にいくつかの完全な一致がある場合、結果は、行の左端に最も近く、最も長いものになります。



実際、アルゴリズムが非常に高速に機能する理由が明らかになります。 場合を除いて、文字列の各文字は1回だけ表示されます。 また、パターンのコンパイルに時間がかかる理由も明らかになります。複雑なパターンの場合、部分一致を正しく実行するには、多くの条件と依存関係を考慮する必要があります。



現時点では、DKAエンジンはgrepユーティリティでエンジン選択メカニズムの一部として使用され、Tcl言語ではハイブリッドエンジンの一部として使用されます。おそらく他の場所で使用されますが、それについては知りません。

正規表現マッチング

このタイプの正規表現エンジンは、いわゆるNCA（ 非決定的ステートマシン ）を使用して実装されます。 主な利点は、（別の原則と比較して）多数の機能をサポートしていることです。 当然、この原理には多くの欠点もあります。



第一に、動作時間は非常に長くなる可能性があります（別の原理と比較して）。 入力文字列の長さの指数関数的漸近まで。 多くの一般的なエンジンは、これに対する保護さえ備えており、検索を中断します。



第二に、NKAは正規表現の記述方法に大きく依存します。 DFAが録音の形式でまったく同じである場合、時間と検索結果は同等の式でまったく同じになりますが、NKAの場合、これはまったくの問題です。 1つの式は指数漸近線を与えることができ、もう1つの式はほぼ線形です。 したがって、パターンを最適化するという問題は、完全な成長において生じます。 NKAは現在、ほとんどの正規表現エンジンで使用されています。



クラシックNKAの重要な機能は、最初の完全一致が見つかるとすぐに検索を中断することです。 つまり 場合によっては、検索結果はDKAとは大きく異なります。 これはアルゴリズムの機能です。



それでは、なぜエンジンの作者はPOSIXに従うのを急いでいないのでしょうか？ 実際、DKA検索のセマンティクスは標準で修正されています。 つまり もちろん、文字通りDKAを使用すべきだとは言われていませんが、「最大長の左端の一致」について言われています。 しかし、NKAは最初のものだけを返し、最大の長さは返しません。 そして何をすべきか？ POSIXに準拠するために、彼らは通常POSIX NKAと呼ばれるアルゴリズムの修正を思いつきました。 そして、それは単なるNCAよりもずっと長く機能します。 標準を満たすためには、正規表現で許可されるすべてのオプションを実行する必要があるためです。 さらに、なぜずっと長いのかを説明します。



コンパイル済み（DFAと同じ意味です）NKAは、パターンに基づいた命令であるシーケンシャルアルゴリズムです。 NCAの主要な機能は「リターン」です。 検索速度はその数に直接依存します。



戻り値は、例で最もよく説明されています。 DFAの例で使用したものと同じ2行と同じ正規表現を使用してみましょう。



1行目：

• パターン^
  
  
  
  の最初のメタキャラクターは、位置が行の先頭と一致します。 戻りスタックは空です。
• パターン「a」の2番目の文字-値が文字列の最初の文字と一致します。 戻りスタックは空です。
• パターン「b」の3番目の文字-文字列の2番目の文字と値が一致します。 戻りスタックは空です。
• パターン「c」の4番目の文字-文字列の3番目の文字と値が一致します。 戻りスタックは空です。
• 5番目の文字列のメタ文字\w
  
  
  
  文字列の4番目の文字の値と一致します。 数量詞には少なくとも1つの文字が必要なので、戻り値はありません。 戻りスタックは空です。
• 文字列の5番目のメタ文字\w
  
  
  
  文字列の5番目の文字の値と一致します。 数量詞には、すでにキャプチャーされている少なくとも1つの文字が必要です。 この時点で払い戻しが行われる場合があります。 戻りスタックには1つの要素が含まれます。
  
  この中間段階で、NCAは一致として行全体を「abcde」と見つけましたが、パターンはまだ最後まで通過していません。 パターンのシンボル「e」はまだ一致していませんが、ラインの現在位置はシンボル「e」の後ろにあります。 この時点で楽しみが始まります。 手を見てください。
• パターン「e」の8番目の文字は、文字列の6番目の文字と値が一致しません （単に存在しません）。 一致が見つかりません。 戻りスタックの確認-1つのレコードがあります。 返品を実施します。 戻った後、行の「eシンボルの前」の位置にあり、パターンの「eシンボルの前」の位置にいます。 戻りスタックは空です。
  
  NCAが一致を検出しない場合、リターンスタックをチェックします。 リターンを実行すると、行の位置が復元され、リターンがスタックから削除されます。 戻りスタックが空で一致がない場合、行のこの開始位置からの一致はないと見なされます。
  
  
• パターン「e」の8番目の文字-値が文字列の5番目の文字と一致します。 戻りスタックは空です。
• パターン$
  
  
  
  の9番目のメタキャラクターは、位置が行の終わりと一致します。 戻りスタックは空です。
• パターンが終了し、現在一致しています。 返却します。

2番目のケースで何が起こるか：

• アルゴリズムの開始はまったく同じで、すぐにパターン「e」の8番目の文字に移動します。
• パターン「e」の8番目の文字-値が文字列の5番目の文字と一致しません （繰り返しますが、単に存在しません）。 一致が見つかりません。 リターンスタックをチェックします-空です（前のステップでは、量指定子+
  
  
  
  が少なくとも1つの一致を必要とするため、リターンスタックに何も追加しなかったため、空です）。 払い戻しはできません。 行が一致しなかったため、結果を返します。
  
  

理解を深めるために、数量詞+



常にできるだけ多くの行文字をキャプチャすることを説明します。 したがって、最大と呼ばれます。 初心者が犯すよくある間違いはこれに関連しています。 パターン\(.+\)



は、「ここはテキスト（大括弧）、ここはテキスト（大括弧）、ここはテキスト」という部分で一致し\(.+\)



ブラケット）」。 というのは、処理段階で.+



行全体が最後までキャプチャされ、シンボル「）」に到達するとすぐに、完全に一致するものがすぐに見つかります。 正規表現を少し変更してみましょう： \([^)]+\)



そして今では、私たちを悩ます問題はもうありません。 しかし、別のものが登場しました（そして、それなしで何が起こるか）。 さて、「ここにテキストがあります（ブラケット（および別のブラケット内）、またテキスト）、そしてテキストがあります」が「（ブラケット（および別のブラケット内））」とキャプチャされますが、これももちろん正しくありません。キャプチャ段階では、2番目の閉じ括弧に到達せず、見つかった一致をすぐに1番目の括弧に返します。問題を解決することができます バランスチェック（つまり、チェック）。



実際、アルゴリズムが具体的にどのように機能するかを説明したとき、私は少しずるいです。 実際には、エンジンが最適化を適用する場合、このように動作します（パターンが^



文字で始まる場合、行の先頭で一致するか、まったく一致しないことが明らかです）。 実際、前のステップで完全に一致するものが1つも見つからなかった場合、最適化を破棄しても、エンジンは行の次の各文字から始まるまったく同じ検索を実行します。 つまり 2行目では、連続して5回の検索が実行され（文字「a」の前から開始し、次に「b」、「c」、「e」、最後の文字「e」の後）、その後のみ一致がないと言えます。 DKAはすべてのケースを1パスで処理します。 しかし、偶然の一致がないNKAには5が必要です。



POSIX NKAエンジンの違いは、最初のケース（一致が見つかった場合）でも検索が停止されないことですが、一致がない場合のように、5つの検索すべてが実行されます。



リターンを実行する手法を検討したので、指数関数的検索時間がどこから来たかを推測できます。 場合によっては、アルゴリズムがトラップに陥り、膨大な数のリターンが発生します。 たとえば、式(\w+)*a



考えます。 「bbb」行に適用すると、どうなりますか？ 最初に、最初の数量詞+



は文字列全体をキャプチャし、2番目の数量詞に制御を渡します。 行にこれ以上文字がないため、パターンの「a」文字に移動します。 行にない場合は、1文字ずつ戻り、新しいグループで空いた文字をインターセプトし、「a」をチェックし、再び一致するものがない、戻ります。 さらに、意味は明確でなければなりません。 このアルゴリズムは、2つの数量詞によるキャプチャーのために、考えられるすべての改行を反復します。 文字列「bbb」の場合、これらは「[bbb]」、「[bb] [b]」、「[b] [bb]」、「[b] [b] [b]」というオプションになります。 角括弧は、条件付きでキャプチャされたグループを示します。 この場合、パーティションの数は文字列の長さから指数関数的に増加します。



別の状況。 1メガバイトのテキストとビューパターンを想像してください.*a



検索するとどうなりますか？ 各段階で、文字列のメガバイト全体がキャプチャされ、「a」文字が見つかるまでシーケンシャルリターンが実行されます。 そして、文字列にそのような文字がない場合はどうなりますか？ その後、1000001検索を実行するだけのものになります。 毎回、現在の文字から最後までの行全体をキャプチャし、文字「a」を見つけるまでその行に戻ります（そうではありません）。 これを回避するには、この場合[^a]*a



と書くだけで十分です。 しかし、これはこの場合です。 一般的な場合（括弧付きの例のように）、これでは十分ではありません。



リターンの最適化手法については、さらに多くのことを書いてください。 次の記事では、これに専念する予定です。



本「 Jeffrey Friedl、Mastering Regular Expressions 」に基づいています。