PHP - PCRE 正規表現のパフォーマンス

パターン内の一部のアイテムは他のアイテムより効率的である可能性があります。 たとえば、[aeiou] のような文字クラスを使用すると、オプションのパス (a|e|i|o|u) よりも効率的です。 一般に、要件は可能な限り単純な構成で記述されている場合に最も面白くなります。 Jeffrey Friedl の著書 (Mastering Regular Expressions) には、正規表現のパフォーマンスについて多くの議論が含まれています。

パターンが .* で始まり、PCRE_DOTALL オプションが設定されている場合、パターンは文字列の先頭と一致するため、PCRE によって暗黙的にアンカーされます。ただし、PCRE_DOTALL が設定されていない場合、 . メタ文字は改行と一致できないため、PCRE はこの最適化を行うことができません。また、ターゲット文字列に改行が含まれている場合、パターンは先頭ではなく改行の後に一致する可能性があります。 たとえば、パターン (.*) 2 番目はターゲット文字列「firstnand Second」 (n は改行文字) に一致し、最初に取得されたサブグループの結果は「and」になります。これを行うために、PCRE はターゲット文字列内の各改行文字の後ろから照合を試みます。

改行なしでターゲット文字列と一致するパターンを使用している場合、最高のパフォーマンスを得るために、PCRE_DOTALL または ^.* で始まるパターンを設定することでアンカーリングを明示的に示すことができます。 これにより、PCRE がターゲット文字列に沿って改行を探してスキャンし、最初からやり直す時間を節約できます。

パターン内の無限繰り返しのネストに注意してください。これを一致しない文字列に適用すると、実行時間が長くなる可能性があります。 パターンのフラグメント (a+)* を考えてみましょう。

このパターンは 33 通りの方法で「aaaa」に一致し、文字列の長さが増加するにつれてこの数は急速に増加します (*繰り返しは 0、1、2、3、4 回一致し、0 を除くすべての場合に一致します)。 + は対応する一致数が異なります)。 パターンの残りの部分によって一致全体が失敗する場合、PCRE は原則として考えられるすべてのバリエーションを試行しますが、これには非常に時間がかかる可能性があります。

いくつかの単純なケースの最適化は、(a+)*b のように元の文字列をすぐに使用することです。 正式なマッチング作業を開始する前に、PCRE はターゲット文字列の後に「b」文字があるかどうかをチェックし、ない場合はただちに失敗します。ただし、直後にオリジナルキャラが存在しない場合にはこの最適化はできません。 (a+)*d と上記のパターンの動作の違いを比較して観察できます。 前者は行全体が「a」で構成される文字列に適用するとほぼ即座に失敗を報告しますが、後者は対象の文字列が 20 文字を超える場合にかなりの時間がかかります。