照合アルゴリズム | PCRE2 ドキュメント

PCRE2の照合アルゴリズム

この文書では、コンパイル済みの正規表現を指定された対象文字列と照合するためにPCRE2で利用できる、2つの異なるアルゴリズムを説明します。「標準」のアルゴリズムは、pcre2_match()関数が提供するものです。Perlの照合関数と同じように動作し、Perl互換の照合処理を行います。pcre2jitの文書で説明するJIT（実行時コンパイル）最適化も、この関数に対応しています。

代替アルゴリズムは、pcre2_dfa_match()関数が提供します。これは異なる方法で動作し、Perl互換ではありません。標準アルゴリズムと比べた利点と欠点を、以下で説明します。

指定された対象文字列がパターンに一致する方法が1通りだけの場合、2つのアルゴリズムは同じ結果を返します。しかし、複数の可能性がある場合は違いが生じます。たとえば、開始位置を固定した次のパターンを

  ^<.*>

次の文字列と照合すると、

  <something> <something else> <something further>

3通りの結果が考えられます。標準アルゴリズムは、そのうち1つだけを見つけますが、代替アルゴリズムは3つすべてを見つけます。

木として表す正規表現

正規表現に一致する文字列の集合は、木構造で表すことができます。パターン内に無制限の繰り返しがあると木の大きさは無限になりますが、それでも木であることに変わりはありません。指定された対象文字列を、指定の開始位置からパターンと照合することは、この木を探索することと考えられます。木の探索には深さ優先と幅優先の2つの方法があり、これらがPCRE2の2つの照合アルゴリズムに対応します。

標準の照合アルゴリズム

Jeffrey Friedlの著書「Mastering Regular Expressions」の用語では、標準アルゴリズムは「NFAアルゴリズム」です。パターンの木を深さ優先で探索します。つまり、木の1つの経路をたどり、対象文字列が求められるものに一致するかを確認します。一致しない場合は、その位置で選べる代替を試し、すべて失敗したら、木の前の分岐点へ戻り、その階層の次の分岐を試します。この処理には、多くの場合、対象文字列の中でも前へ戻る（左へ移動する）ことが伴います。繰り返しの分岐を試す順序は、量指定子が貪欲か非貪欲かによって決まります。

葉ノードへ到達すると、一致する文字列が見つかったことになり、その時点でアルゴリズムは停止します。したがって、一致する可能性が複数あっても、このアルゴリズムが返すのは最初に見つかったものです。それが最短、最長、または中間の長さになるかは、パターンでの選択肢と、貪欲／非貪欲の繰り返し量指定子の指定方法によります。

最終的に木の1つの経路だけをたどるため、このアルゴリズムでは、括弧で囲んだパターンの部分に一致する部分文字列を追跡することが比較的容易です。これにより、捕捉用の括弧と後方参照に対応できます。

代替の照合アルゴリズム

このアルゴリズムは、木を幅優先で探索します。対象文字列の最初の照合位置から始めて、文字列を左から右へ1回、1文字ずつ走査し、その間、有効な一致を表すすべての経路を記憶します。Friedlの用語では、一種の「DFAアルゴリズム」ですが、従来の有限状態機械として実装されているわけではありません（複数の状態を同時に有効に保ちます）。

この照合アルゴリズムは、バックトラッキングをせずに対象文字列を1回だけ走査するのが基本ですが、例外が1つあります。先読み・後読みのアサーションに遭遇した場合は、現在の位置の後または前の文字を、独立に調べる必要があります。

走査は、対象文字列の末尾へ到達するか、終端に達していない経路がなくなるまで続きます。この時点で、終端に達した経路が、それぞれの一致の可能性を表します（1つもなければ照合失敗です）。したがって、一致する可能性が複数ある場合、このアルゴリズムはすべてを見つけ、とくに最長の一致も見つけます。一致は、長さの降順で出力ベクトルへ返されます。最初の一致（必ず最短の一致）が見つかった時点で停止するオプションもあります。

すべての結果を格納するために必要なベクトルの大きさは、パターン内の捕捉用括弧の数ではなく、同時に成立する一致の数によることに注意してください。したがって、DFA照合を行う際に、pcre2_match_data_create_from_pattern()を使って照合データブロックを作成することは勧められません。

見つかる一致は、すべて対象文字列の同じ位置から始まることにも注意してください。次のパターンを

  cat(er(pillar)?)?

文字列「the caterpillar catchment」と照合すると、対象文字列の5文字目から始まる「caterpillar」「cater」「cat」の3つが結果になります。このアルゴリズムは、後ろの位置から始まる一致を見つけるために、自動的に先へ進むことはありません。

PCRE2の「自動所有的量指定子化（auto-possessification）」最適化は、通常、パターン内部だけでなく末尾の文字の繰り返しにも適用されます。たとえば、パターン「a\d+」は「a\d++」と同じようにコンパイルされます。繰り返す数字の部分へバックトラッキングする可能性を考慮しても意味がないためです。DFA照合では、この最適化により、一致する可能性が1つだけ見つかることになります。そのような場合にも複数の一致が必要なら、非貪欲な繰り返し（「a\d+?」）を使用するか、コンパイル時にPCRE2_NO_AUTO_POSSESSオプションを設定してください。

代替照合関数では、PCRE2の正規表現の機能のうち、サポートされないものや、動作が異なるものがあります。サポートされない機能に遭遇すると、エラーになります。

1. このアルゴリズムは可能な一致をすべて見つけるため、繰り返し量指定子が貪欲か非貪欲かは関係ありません（ただし、前述の自動所有的量指定子化には影響する場合があります）。照合中は、貪欲な量指定子と非貪欲な量指定子を、まったく同じように扱います。しかし、量指定された部分に続くパターンも同じ文字へ一致できる場合、所有的量指定子は結果に違いを生じさせることがあります。たとえば、次のパターンがその例です。

  ^a++\w!

このパターンは「aaab!」には一致しますが、「aaa!」には一致しません。所有的でない量指定子なら、後者にも一致します。同様に、アトミックグループがある場合、現在の位置で独立したパターンであるかのように照合し、最長の一致を、全体のパターンの残りの照合に対して「固定」します。

2. 木の複数の経路を同時に扱いながら、それぞれの一致の可能性について捕捉した部分文字列を追跡することは容易ではありません。PCRE2のこのアルゴリズムの実装は、その追跡を試みません。そのため、捕捉した部分文字列は利用できません。

3. 部分文字列を捕捉しないため、関連する次の機能は利用できません。

(a) 後方参照。

(b) 条件に後方参照を使う条件式、または特定のグループの再帰を検査する条件式。

(c) スクリプトラン。

(d) 部分文字列走査アサーション。

4. 木の多くの経路が同時に有効になり得るため、遭遇したときに一致の開始位置をリセットする\Kエスケープシーケンスはサポートされません（\Kが含まれる経路と含まれない経路が存在する場合があります）。

5. コールアウトには対応していますが、capture_topフィールドの値は常に1、capture_lastフィールドの値は常に0です。

6. \Cエスケープシーケンスは、標準アルゴリズムではUTFモードでも常に1コード単位に一致しますが、代替アルゴリズムのUTFモードではサポートされません。代替アルゴリズムは、木の有効なすべての経路について、対象文字列をコード単位ではなく1文字ずつ進むためです。

7. (*FAIL)を除き、(*PRUNE)などのバックトラッキング制御動詞はサポートされません。(*FAIL)はサポートされ、失敗する否定アサーションと同じように動作します。

8. pcre2_compile()のPCRE2_MATCH_INVALID_UTFオプションは、pcre2_dfa_match()ではサポートされません。

代替アルゴリズムの利点

代替アルゴリズムの主な利点は、対象文字列の1つの位置で、可能な一致をすべて自動的に見つけ、とくに最長の一致を見つけることです。標準アルゴリズムで同じ位置の複数の一致を見つけるには、コールアウトを使った技巧的な処理が必要です。

このアルゴリズムでは、いくつかの制限はありますが、部分照合も可能です。pcre2partialの文書では、部分照合の詳細と、複数の区間にまたがる照合を説明しています。

代替アルゴリズムの欠点

代替アルゴリズムには、いくつかの欠点があります。

1. 標準アルゴリズムよりかなり遅くなります。すべての一致の可能性を探索する必要があることも理由の1つですが、最適化しにくいことも理由です。

2. 捕捉用の括弧と、それに依存する後方参照などの機能はサポートされません。

3. 不正なUTF文字列の中での照合はサポートされません。

4. アトミックグループはサポートされますが、それを使っても、標準アルゴリズムで得られるような性能上の利点はありません。

5. JIT最適化はサポートされません。

著者

Philip Hazel
University Computing Serviceを退職
英国ケンブリッジ。