4

正規表現を表す特定の DFA があります。入力ストリームに対して DFA を照合し、最小最長一致だけでなく、可能なすべての一致を取得したいと考えています。

例えば：

正規表現: a*ba|baa

入力: ああああああああああああああ

結果：

  1. あああああ
  2. あば
  3. バ
  4. ばあ
4

1 に答える 1

16

仮定

あなたの質問とその後のコメントに基づいて、文を重複しない一致する部分文字列に分割し、文の一致しない部分を破棄する一般的な方法が必要です。また、最適なランタイム パフォーマンスも求めているようです。また、正規表現を DFA 形式に変換する既存のアルゴリズムがすでにあると仮定します。さらに、最初に NFA を構築し、それをサブセット構築によって DFA に変換する通常の方法でこれを行っていると仮定します。これを達成する他の方法を知らないからです。

影を追いかける前に、仕事に適したツールを適用しようとしていることを確認してください. 正規表現に関する議論は、ほとんどの場合、正規表現が実際に最適であるよりもはるかに多くのことに正規表現を使用しているという事実によって混乱しています。正規表現の利点を享受したい場合は、より広範なものではなく、正規表現を使用していることを確認してください。やりたいことを正規表現自体にコード化できない場合は、正規表現アルゴリズムの利点を (完全には) 活用できません。

明らかな例は、どれだけ賢くても FSM やアルゴリズムが未来を予測できないということです。たとえば、 のような式を(a*b)|(a)文字列 ... と照合した場合、省略記号は、ユーザーがまだ入力していないためaaaまだスキャンされていない式の部分であり、可能なすべての適切なサブグループを提供することはできません。

正規表現の実装、特に Thompson NFA の詳細については、このリンクを確認してください。このリンクでは、巧妙な最適化を行った単純な C 実装について説明しています。

正規言語の制限

正規表現アルゴリズムの O(n) および Space(O(1)) 保証は、かなり限定的な主張です。具体的には、通常の言語は、定数空間で認識できるすべての言語のセットです。この区別は重要です。文を受け入れたり拒否したりするよりも洗練された処理を行うアルゴリズムの強化は、通常よりも多くの言語セットで機能する可能性があります。それに加えて、一部の拡張機能を実装するために一定以上のスペースが必要であることを示すことができれば、パフォーマンスの保証外でもあります。そうは言っても、これらの狭い制約内にアルゴリズムを維持するように細心の注意を払っていれば、依然として非常に多くのことを行うことができます.

明らかに、再帰的なバックトラッキングでやりたいことはすべて排除されます。スタックには一定のスペースがありません。文がどれくらいの長さになるか分からないため、文へのポインタを維持することさえ禁止されます。文が十分に長いと、整数ポインタがオーバーフローします。これを回避するために、オートマトンの新しい状態を作成することはできません。すべての可能な状態 (およびいくつかの不可能な状態) は、レコグナイザーを入力に公開する前に予測可能でなければならず、その量は、照合する特定の言語によって異なる可能性がある定数によって制限される必要がありますが、他の変数によって制限されることはありません。

これにより、追加の動作を追加する余地が残ります。より多くのマイレージを取得する通常の方法は、部分式が一致を開始または停止したときなど、処理中の特定のイベントが発生した場所にいくつかの追加の注釈を追加することです。一定のスペース処理しか許可されていないため、処理できる部分式の一致の数が制限されます。これは通常、その部分式の最新のインスタンスを意味します。これが、 によって一致するサブグループ化を要求すると、(a|)*常に空の文字列が返される理由です。これは、 のシーケンスのa後に無限に多くの空の文字列が暗黙的に続くためです。

もう 1 つの一般的な拡張機能は、状態間で巧妙なことを行うことです。たとえば、perl 正規表現で\bは、空の文字列に一致しますが、前の文字が単語文字で次の文字がそうでない場合、またはその逆の場合のみです。一般的な行アンカー演算子を含む多くの単純なアサーションがこれに適合^し$ます。先読みおよび後読みアサーションも可能ですが、はるかに困難です。

さまざまな正規言語認識エンジンの違いについて議論する場合、一致認識と検索認識のどちらについて話しているのかを明確にする価値があります。前者は、文全体が言語内にある場合にのみ受け入れられ、後者は文の部分文字列があれば受け入れられます。言語にあります。Eこれらは、ある式が search メソッドによって受け入れられる場合、match メソッドで受け入れ られるという意味で同等です。.*(E).*

a*b|aこれは、式 like が受け入れられるかどうかを明確にしたい場合があるため、重要ですaa。検索方法では、そうです。どちらのトークンも論理和の右側に一致します。ただし、少なくとも 1 回のパスでは、式をステップ実行して遷移からトークンを生成することによって、その文を取得することはできないため、一致しません。このため、一致のセマンティクスについてのみ説明します。明らかに、検索セマンティクスが必要な場合は、式を.*'sで変更できます

注: 式で定義された言語は、可能なすべての文に一致するため、サブ言語に関係なく、実際にはあまり扱いやすい言語ではありません。これは、正規表現レコグナイザーにとって真の課題です。なぜなら、正規表現レコグナイザーは、より具体的な作業を行うのではなく、言語を認識するか、文が同じ言語ではないことを確認することにしか適していないためです。 E|.*E

通常の言語認識機能の実装

通常、正規表現を処理するには 3 つの方法があります。式を NFA に変換することで、3 つすべてが同じように開始します。このプロセスは、元の式の各プロダクション ルールに対して 1 つまたは 2 つの状態を生成します。ルールは至ってシンプル。ここにいくつかの粗いアスキー アートがあります:aは言語のアルファベットの任意の 1 文字のリテラル文字であり、E1およびE2は任意の正規表現であることに注意してください。Epsilon(ε) は入力と出力を持つ状態ですが、文字のストリームを無視し、入力も消費しません。

a     ::=  > a ->

E1 E2 ::=   >- E1 ->- E2 ->

               /---->
E1*   ::= > --ε <-\
               \  /
                E1

             /-E1 ->
E1|E2 ::= > ε
             \-E2 ->

以上です！ E+、E?、[abc] などの一般的な使用法は、それぞれ EE*、(E|)、(a|b|c) と同等です。また、プロダクション ルールごとに非常に少数の新しい状態を追加することにも注意してください。実際、各ルールはゼロまたは 1 つの状態を追加します (このプレゼンテーションでは)。文字、量指定子、および dysjunction はすべてただ 1 つの状態を追加し、連結は何も追加しません。それ以外はすべて、フラグメントの終了ポインタを更新して、他の状態またはフラグメントの開始ポインタに変更します。

イプシロンの遷移状態は、あいまいであるため重要です。遭遇した場合、マシンは状態を次の状態または別の状態に変更することになっていますか? 状態をまったく変更する必要がありますか、それともそのままにしておく必要がありますか? これが、これらのオートマトンが非決定的と呼ばれる理由です。解決策は、オートマトンを適切な状態に遷移させることです。したがって、トリッキーな部分は、それを行う方法を理解することです。

これを行うには、基本的に 2 つの方法があります。まずはそれぞれ試してみる方法です。最初の選択肢に従ってください。それがうまくいかない場合は、次の選択肢を試してください。これは再帰的なバックトラッキングであり、いくつかの (そして注目に値する) 実装に見られます。巧妙に作成された正規表現の場合、この実装は余分な作業をほとんど行いません。式がもう少し複雑な場合、再帰的なバックトラッキングは非常に悪く、O(2^n) になります。

これを行うもう 1 つの方法は、代わりに両方のオプションを並行して試すことです。各イプシロン遷移で、イプシロン遷移が示唆する両方の状態を現在の状態のセットに追加します。セットを使用しているため、同じ状態を複数回発生させることができますが、その状態にあるかどうかに関係なく、追跡する必要があるのは 1 回だけです。特定の状態をたどるオプションがないという点に到達した場合は、無視してください。そのパスは一致しませんでした。状態がこれ以上ない場合は、式全体が一致しませんでした。いずれかの状態が最終状態に達するとすぐに完了です。

その説明だけで、やらなければならない仕事の量が少し増えました。1 つの状態を追跡する必要がなくなり、複数の状態を追跡するようになりました。反復ごとに、重複のチェックなどを含め、m 個の状態ポインターの順序で更新する必要がある場合があります。また、必要なストレージの量も増えました。これは、NFA で可能な 1 つの状態への単一のポインターではなく、それらのセット全体になるためです。

ただし、これは思ったほど悪くはありません。まず、状態の数は、元の正規表現の生成数によって制限されます。これからは、この値をmと呼び、入力のシンボル数 ( n )と区別します。2 つの状態ポインターが同じ新しい状態に遷移する場合、そのうちの 1 つを破棄できます。これは、他に何が起こっても、それ以降は両方とも同じパスをたどるためです。これは、必要な状態ポインターの数が状態の数によって制限されることを意味するため、 to はmになります。

これは、バックトラックと比較した場合、最悪のシナリオではより大きな勝利です。各文字が入力から消費された後、最大で m 個の状態ポインターを作成、名前変更、または破棄します。その数よりも多くの命令を実行させたり(正確な実装に応じて一定の係数を掛けたり)、スタックまたはヒープにより多くのスペースを割り当てさせたりする正規表現を作成する方法はありません。

この NFA は、そのm状態のサブセットで同時に、それがモデル化する NFA が存在する可能性のある状態のセットを表す他の状態マシンと見なすことができます。その FSM の各状態は、状態のべき乗セットからの 1 つの要素を表します。 NFA。これは、正規表現の照合に使用される DFA の実装とまったく同じです。

この代替表現を使用すると、m 個の状態ポインターを更新する代わりに、1 つだけ更新すればよいという利点があります。また、m 個の状態のパワーセットをモデル化するため、実際には最大 2 m 個の状態があるという欠点もあります。起こり得ない状態をモデル化しないため、これは上限です。たとえば、式には、最初の文字を読み取った後に、 を見た場合とa|bを見た場合の 2 つの可能な状態があります。ab. どのような入力をしても、同時に両方の状態になることはできないため、状態セットは DFA に表示されません。実際、イプシロン遷移の冗長性を排除しているため、多くの単純な DFA は、実際にはそれらが表す NFA よりも小さくなりますが、それを保証する方法はまったくありません。

状態の爆発が大きくなりすぎないようにするために、そのアルゴリズムのいくつかのバージョンで使用されているソリューションは、実際に必要な DFA 状態のみを生成し、あまりにも多くの状態が発生した場合は、最近使用していないものを破棄することです。いつでも再生成できます。

理論から実践へ

正規表現の実用的な用途の多くには、入力の位置の追跡が含まれます。入力は任意に長くなる可能性があるため、これは技術的に不正行為です。64 ビットのポインターを使用した場合でも、入力が 2 64 +1 シンボルの長さになる可能性があり、失敗する可能性があります。位置ポインターは入力の長さに合わせて大きくする必要があり、アルゴリズムの実行には一定以上のスペースが必要になりました。実際には、これは関係ありません。なぜなら、正規表現がそれほど多くの入力を介して機能することになった場合、それよりずっと前に終了するため、おそらく失敗することに気付かないからです。

もちろん、入力全体を受け入れたり拒否したりするだけではありません。これに関する最も有用なバリエーションは、サブマッチを抽出して、入力のどの部分が元の式の特定のセクションと一致したかを発見することです。これを実現する簡単な方法は、式の左中括弧と右中括弧のそれぞれにイプシロン遷移を追加することです。FSM シミュレーターは、これらの状態の 1 つに遭遇すると、その特定の遷移に遭遇したときの入力内の場所に関する情報を状態ポインターに注釈付けします。同じポインターがその遷移に 2 回戻ると、古い注釈は破棄され、新しい入力位置の新しい注釈に置き換えられます。注釈が一致しない 2 つの状態ポインターが同じ状態に折りたたまれた場合、後の入力位置の注釈が再び優先されます。

Thompson NFA または DFA の実装に固執している場合、貪欲または非貪欲なマッチングの概念は実際にはありません。バックトラッキング アルゴリズムには、最初の試行に失敗したときに、できるだけ多くの一致を試みて再帰的に試行回数を減らすか、またはできる限り少なく試行して再帰的に多くの試行を開始するかについてのヒントを与える必要があります。Thompson NFA メソッドは、可能なすべての量を同時に試行します。一方、貪欲/非貪欲なヒンティングを使用したい場合もあります。この情報は、入力の適切な部分をキャプチャするために、新しいサブマッチ アノテーションと古いサブマッチ アノテーションのどちらを優先するかを決定するために使用されます。

もう 1 つの実用的な拡張機能はアサーションです。これは、入力を消費せず、入力位置のいくつかの側面に基づいて一致または拒否するプロダクションです。たとえば、perl regex では、 a\bは、入力のその位置に単語境界が含まれている必要があることを示します。たとえば、一致した記号は単語文字である必要がありますが、次の文字は単語文字であってはならず、その逆も同様です。ここでも、特別な命令を含むイプシロン トランジションをシミュレータに追加することで、これを管理します。アサーションが成功した場合、状態ポインタは続行され、それ以外の場合は破棄されます。

先読みアサーションと後読みアサーションは、もう少し作業を行うことで実現できます。典型的な後読みアサーションは、2 つの別個の式とに変換されます。両方の式が入力に適用されます。アサーション式にa を追加したことに注意してください。実際には、どこから始まるかは気にしないためです。シミュレーターは、2 番目に生成されたフラグメントでイプシロンを検出すると、最初のフラグメントの状態をチェックします。そのフラグメントがその場で受け入れることができる状態にある場合、アサーションは状態ポインタが に流れて合格しますが、それ以外の場合は失敗し、両方のフラグメントが続き、2 番目はイプシロン遷移で状態ポインタを破棄します。r0(?<=r1)r2.*r1r0εr2.*r2

先読みは、アサーションに追加の正規表現フラグメントを使用することでも機能しますが、アサーションが成功する必要がある入力のポイントに到達したときに、対応する文字のいずれにも遭遇していないため、もう少し複雑です (後読みの場合、それらはすべて遭遇しました）。代わりに、シミュレーターがアサーションに到達すると、アサーション部分式の開始状態でポインターを開始し、シミュレーションの主要部分で状態ポインターに注釈を付けて、部分式ポインターに依存していることを認識します。各ステップで、シミュレーションは、依存する状態ポインターがまだ一致していることを確認する必要があります。見つからない場合は、どこにいても失敗します。メイン部分よりもアサーション部分式の状態ポインタのコピーを保持する必要はありません。

イプシロンの遷移に特別な指示を追加していましたが、シミュレータを一時停止させる指示を提案することは悪い考えではありません時々、ユーザーが何が起こっているかを確認できるようにします。シミュレーターがこのような遷移に遭遇するたびに、呼び出し元に返され、検査または変更され、中断したところから再開できる何らかのパッケージに現在の状態がラップされます。これは入力をインタラクティブに照合するために使用できます。したがって、ユーザーが部分的な一致のみを入力した場合、シミュレーターはさらに入力を要求できますが、ユーザーが無効なものを入力した場合、シミュレーターは空であり、ユーザーに文句を言うことができます。もう 1 つの可能性は、部分式が一致するたびに生成することです。これにより、入力内のすべての部分一致を覗くことができます。ただし、これを使用して一部のサブマッチを除外することはできませんでした。たとえば、あなた((a)*b)がaaa、b がなく、対応する b のサブマッチがないため、式全体が最終的に失敗したとしても、a の 3 つのサブマッチが表示される可能性があります。

最後に、後方参照で動作するようにこれを変更する方法があるかもしれません。エレガントであっても、非効率であることは間違いありません。具体的には、正規表現と後方参照が NP-Complete に含まれているため、これを行う方法を考えようとさえしません。 ) 効率的な可能性。

于 2009-08-01T19:13:45.320 に答える