regex - 文字クラスが交互よりも速いのはなぜですか?

Question

次のような例では、文字クラスを使用する方が代替よりも高速であるように思われます:
[abc]vs(a|b|c)
推奨されていると聞いたことがありTime::HiResます。
また(?:a|b|c)、キャプチャ括弧が違いを生む場合に使用しても、結果は変わりません。
しかし、私はその理由を理解できません。バックトラックのせいだと思いますが、各位置で見ると3文字の比較があるので、バックトラックが交代にどのように影響するかはわかりません。それは実装の代替の性質の結果ですか?

Answer 1

これは、"OR" コンストラクトが代替間で| バックトラックするためです。最初の代替が一致しない場合、エンジンは代替の一致中にポインタ位置が移動する前に戻って、次の代替との一致を続行する必要があります。文字クラスは順番に進むことができますが。最適化が無効になっている正規表現エンジンでこの一致を参照してください。

Pattern: (r|f)at
Match string: carat

Pattern: [rf]at
Match string: carat

---

要するに、pcreエンジンがこれ (単一のリテラル文字 -> 文字クラス) を最適化するという事実は、代替が非効率的であるという適切なヒントです。

Answer 2

のような文字クラス[abc]は還元不可能で最適化できるため、代替のようなもの(?:a|b|c)は(?:aa(?!xx)|[^xba]*?|t(?=.[^t])t).

作成者は、代替のすべての要素が単一の文字であることを確認するために正規表現コンパイラを最適化しないことを選択しました。

「次の文字がこの文字クラスにあることを確認する」と「残りの文字列がこれらの正規表現のいずれかに一致することを確認する」には大きな違いがあります。