NFAとの正規表現とDFAの正規表現は一致していますか？どちらが速いの？

Question

私はNFAとDFAについて読んでいました。正規表現からNFAを作成し、DFAに変換し、そのDFAを最小化し、任意の言語で実装して使用することが、正規表現マッチャーを実装する最も一般的で最も速い方法です。

NFAは入力に対して1つのトランジションしか持たないため、DFAはNFAよりも優れた選択肢です。したがって、DFAには1つのパスしかありませんが、NFAは多数あります。

しかし、これは私が理解できないところです。なぜ私たちがNFAの状態を追跡し、私たちを遅くするそれらに戻らなければならないのですか？複数の状態への入力に遭遇したときに異なるスレッドに分割し、各パスを並列に計算できますか？ DFAよりも高速ではありませんか？または何かが欠けている？

Answer 1

一般に、DFAは高速ですが、NFAはよりコンパクトです。 NFAは、正規表現のサイズに比例します。 （非形式的な証明：正規表現の構文の各演算子ノードは、NFAグラフに新しいノードを追加するだけです）.DFAはNFA状態の集合の部分集合から形成されるため、かなり大きくなる場合があります。最悪の場合、DFAは正規表現で指数関数的にサイズ変更されます。これの例は、(a|b)(a|b)(a|b)(a|b)...(a|b)という形式の表現で、N (a|b)単位は、サイズがO（2 ** N）であるDFAに変換されます。これには、aとbのすべての組み合わせの固有の状態を通る遷移が含まれます。同等のNFAをキャッシュに適合させるために必要なデータ構造がある場合、縮退したDFAがCPUキャッシュのサイズを超える可能性があります。

余分な手順があるため、DFAにいくらか手間がかかります。したがって、トレードオフが適用されます：DFAの構築を正当化するのに十分なデータがNFAシミュレータによって処理されます。

NFAシミュレーションでは、入力にまったく当てはまらない正規表現の部分に触れることを完全に避けることができます。たとえば、正規表現の形式がR1 | R2で、R1が非常に単純で小さく、R2が巨大で複雑な獣であるとします。入力が通常、R1とR2にほとんど一致しないと仮定します（たとえば、接頭辞の不一致により、入力の一部がまったくない）。これはトレードオフに影響します.DFAへのコンパイルは、すべてがコンパイルされ、単純なR1部分と怪物R2部分を意味します。

最後に、実装は厳密にNFAまたはDFAである必要はありません。 NFAシミュレータcan cache the stateが計算するものを設定します。これらのキャッシュされた状態はDFAの状態と同等であり、DFAへのコンパイルと同様の利点があります。あなたはこれが "NFAのためのJIT"だと考えることができます。キャッシュはある固定サイズにトリムされ、置き換えポリシーに従うことができるので、完全なDFAが大きい式は少ないメモリ量で処理できます（データがキャッシュ内の参照の局所性が高い場合はほぼ同じ速度で処理できます） 。