正規表現のアルゴリズム - または

Question

私はC++アプリケーションを開発しています。最初に正規表現の文字列を解析してから、いくつかの計算を実行します。 (a|ab)* | (aa|bb)*のように、与えられた正規表現で認識できる長さLの文字列の数Nを出力できる既存のアルゴリズムはありますか？あるいは、階乗を含むような私が使うことができる数式がありますか？私はちょうど与えられた数Lのためのそのような正規表現フレーズによって認識されることができる文字列の数Nを得たいと思う。(a|ab)*の例正規表現が認識できる長さ5（L）の文字列。私は答えが5だと思います。しかし、Lの数が多い場合は、それを計算できるアルゴリズムや数式があるかどうか疑問に思っていました。

Answer 1

ここでは、これらの数値を計算するために使用できる行列累乗に基づく効率的なアルゴリズムを示します。

私は、コードではなく、高度な説明をします。

1. まず、あなたは（簡単な）正規表現は、有限状態マシンと等価であることを、コンピュータサイエンスの基礎からよく知られている等価性を利用したいです。

   （有限状態機械は、基本的には各ノードからアルファベットの各文字のラベル付きエッジがある特定の他のノード（またはループかもしれない）状態のいくつかのサブセットは「受け入れセット」と呼ばれ、フロー・チャートのいくつかの特定の状態は開始状態である。文字列は、開始状態で開始し、ラベル付けされたaccepts最後の状態が受け入れセットにある場合は文字列、それ以外の場合はrejects文字列 古典的な構造では、どのような正規表現でも、同じサイズの有限状態機械を構築することができます。同様のサイズの正規表現を構築することができます。すべての有限ストリングの集合）は、「正規」と呼ばれ、有限状態機械に対応する場合にのみ、言語は規則的である。

   たとえば、アルファベットが{a,b,c}の場合、正規表現(a|b)*は、2つの状態を持つマシンに対応します。開始状態は、aとラベル付けされたループと、bとラベル付けされたループと、cとラベル付けされた第2の状態とを有する。 2番目の状態には3つのループがありますので、そこに行くとトラップされます。受け入れセットには、開始状態のみが含まれます。

   プログラムの最初のステップは、正規表現を対応する有限状態マシンに変換することです。 （これは、既存の正規表現ライブラリの中には、すでに基本的にはこれがありますが、私は確信していませんが、PCREがそうかもしれないと思います）。この行列では、各状態の行と各状態の列があり、各エントリは確率です。エントリー(i,j)の確率p_{i,j}は、私が州iにいて、ランダムな文字を読むと、次にjの状態になる確率に等しい。だから私は与えた例では、行列が

   ある[2/3 1/3]
   [0 1]

2. のためにあなたがして、マトリックスの累乗を使用して、長さkの文字列を知りたい場合は、コンピューティング行列M^kここで、Mは上記の確率遷移行列です。

3. 最後に、qが開始状態である場合は、受け入れセット内の各状態sに対してすべてのエントリM^k_{q, s}を追加します。これらの確率の合計は、長さがkのランダムな文字列が正規表現によって受け入れられる確率とまったく同じです。したがって、N^kを乗算することによって、そのような文字列の数を得ることができます。Nはアルファベットの文字数です。

私は一度計算クラスの理論における最終試験に余分な信用問題としてこの困難バージョンを与えた、私はこのアルゴリズムの存在はハードではないと思いますが、それはどちらかの些細ではありません。私はそれの既存の実装を知らない、知ることに興味があるだろう。

行列のべき乗を使うとき、単純な方法よりもこのようにするのはかなり高速です。これにより、大きなkのためにそれを迅速に行うことができます。

より効率的でおおよその解決策があるかどうかわかりませんが、面白いと思います。私は無作為抽出は常にあなたに何かを与えるだろうと思うが、行列Mまたは何かの特異値分解を行うことに基づいて、ある種のスペクトルアルゴリズムがあるかもしれない。

注：実際に実装したい場合は、浮動小数点数を使用しないでください。行列Mは実際には整数の行列にする必要があります。基本的には、Nを掛けます。Nはあなたのアルファベットの文字数です。そして、その合計にN^kを掛けてスキップします。確率を使って理解する方が簡単だと思いますが、そのバージョンではM^k_{i,j}はちょうどnumber of paths from i to j of length kです。

注：コメントで指摘されているように、このアルゴリズムは固定正規表現のビット数がkの多項式であるため、大文字のkでも有効です。しかし、正規表現のサイズでは、最悪のケースでは指数関数的です。大規模で複雑な正規表現を処理するには、このメソッドを使用する場合はDFAの最小化を使用する必要があります。質問に表示される単純な正規表現については、それはうまくいくはずです。