レッドチェリーを食べるとブルーゴーストを食べられるようになる。デリバティブを使用して正規表現マッチング アルゴリズムを作成できるという考えは、ほとんどばかげています。このアルゴリズムがどのように機能し、パックマンとどのように関係しているかを説明しましょう。

1964 年、Brzozowskiは正規表現の導関数に関する最初の論文を発表しました。これは、私のお気に入りのアルゴリズムの 1 つです。正規表現の派生物を使用して、正規表現マッチングを行うアルゴリズムを実装できます。このアルゴリズムはとても:

• 単純
• 機能的
• 独自のオペレーターで簡単に拡張可能

この記事では、2 つの純粋な関数といくつかのパックマンの例えだけを使用して、文字列を正規表現と一致させる方法を紹介します。必要に応じて、記事を読む代わりに次のビデオを見ることができます。これは、同じ内容をカバーしているためです。

正規表現の要約

最初に、正規表現を簡単に確認して、同じページにいることを確認しましょう。この式a(a|b)*は、 で始まり、aその後に任意の数aの およびが続く文字列に一致しますb。

• 文字列abが一致しa(a|b)*ます。これは食用の青いゴーストで示されます。
• この文字列は、andで始まり、その後に複数のおよび が続くため、aabbba一致します。a(a|b)*aab
• 次に、文字列acが一致しません。これa(a|b)*は、正規c表現がどの にも一致せず、正規表現が部分文字列の一致も行わないためです。これは、パックマンを追いかけている赤いゴーストを使用して示します。
• 最後に、文字列が .で始まらないため、文字列baも一致しません。a(a|b)*a

アルゴリズムの概要

詳細に入る前に、このアルゴリズムがどのように機能するかの概要を見てみましょう。私はパックマンの奇妙なゲームを考案しました。このゲームでは、正規表現に一致する順序で果物を食べた場合にのみ幽霊を食べることができます。私たちのパックマンは regex を表していaba*ます。リンゴ、バナナ、リンゴの順に食べますaba。

1. 開始すると、幽霊が私たちを追いかけています。一致させるために残した正規表現は ですaba*。
2. 私たちは最初のリンゴを食べました。今マッチするために残っている正規表現は ですba*。これまでに食べた果物であるリンゴが正規表現と一致しないため、幽霊はまだ私たちを追いかけています。
3. 次にバナナを食べます。一致させるために残した正規表現は ですa*。ab技術的には、すでに と一致しているため、ゴーストは逃げ始めますaba*。
4. ゴーストを食べたり、別のリンゴを食べたりすることができますa*。aba正規表現にもマッチするので、ゴーストはまだ逃げていますaba*。

ここでは、もう 1 つの機能が働いています。この関数は、ゴーストがパックマンを追跡しているかどうか、またはパックマンが既に正規表現に一致してゴーストを追跡しているかどうかをチェックします。この関数は、null 許容関数と呼ばれます。一致するために残っている正規表現が空の文字列と一致するかどうかをチェックします。一致するために残された正規表現が空の文字列と一致する場合、それが食べた果物は正規表現を満たすのに十分であったに違いないため、それが可能です。

導関数照合アルゴリズム

つまり、微分マッチング アルゴリズムを記述するのに必要な関数は 2 つだけです。

1. 導関数
2. null 許容関数

命令型プログラマー向けの Golang の 1 つ:

関数型プログラマー向けのHaskellの別のもの：

これら 2 つの関数は同等であり、異なるスタイルのプログラミングで記述されているだけです。Haskell コードではfoldl、他の言語では左折または縮小とも呼ばれ、for ループの作業を行います。また、Haskell では、関数にパラメーターを渡すのにコンマは必要ありません。関数適用は関数型プログラミング言語で最も一般的な操作であるため、スペースを使用してパラメーターを区切ります。

それでは、null 許容関数と派生関数を実装する方法を詳しく見ていきましょう。

パックマンの起源の話の余談

しかし、その前に、パックマンの起源の物語について疑問に思ったことがあるかどうかはわかりません. 私は、パックマンが落ちた核廃棄物の樽がなかったため、パックマンが幽霊を食べる力を得たと主張しています. ロジックははるかに単純です。

パックマンはフルーツ！パックマンが他の果物を食べるとき、パックマンは共食いです。そのため、幽霊に追われた場合は、人間の肉を食べなければなりません。そうすれば、幽霊は少なくとも一時的にあなたから逃げ出すはずです。今、私はこれを自分で試したことはありませんが、論理は正しいようです.

これは、ゾンビが常に人間を追いかけている理由を説明しています。デビッド・アッテンボローがかつて言ったように：

「私たちを追っているゾンビは、私たちには見えない幽霊に追われています。ゾンビが人間の肉の一部を食べ​​た後、彼らが空中をむさぼり食うという奇妙な行動を示すのを見るでしょう。これは、ゾンビが以前に追いかけていた幽霊を食べていることです。」

基本演算子

nullable 関数と導関数の実装では、最初に正規表現で使用できる基本的な演算子を定義する必要があります。

正規表現は一連の文字列を記述するものと考えることができます。

• これは、空のセットが文字列に一致しない演算子を表すことを意味します。
• 空の文字列は、空の文字列にのみ一致する単一の文字列のシングルトン セットを表します。
• この文字は、単一の文字にのみ一致するシングルトン セットも表しaます。
• 次に、 、 、などの演算子を使用して、これらの基本正規表現を組み合わせることができます。ここでor、concatenationとは、組み合わせる 2 つの正規表現を表します。Kleene starrs

Null 許容関数

nullable 関数から始めることができます。いくつかの例を見て、これらの正規表現のどれが空の文字列に一致するかを調べて、この関数がどのように実装されているかを理解してみましょう。

• a*ゼロ以上はゼロを含むため、空の文字列に一致します。
• (a*|b)or の左側が空の文字列に一致するため、 は空の文字列に一致します。
• ab文字列のみに一致するため、空の文字列には一致しませんab
• ab*ab*で始まる文字列が必要なため、空の文字列にも一致しません。a
• (a|b)の左側も右側も空の文字列と一致しないため、空の文字列とは一致しませんor。

nullable 関数の実装を次に示します。左側は関数に渡される値を表し、右側はその場合の関数の実装を表します。赤いゴーストは false を表し、青いゴーストは true を表します。

• 空のセットは、どの文字列とも一致しないため、空の文字列と一致しません。
• 空の文字列のみに一致するため、空の文字列は空の文字列に一致します。
• この文字aは、文字 のみに一致するため、空の文字列には一致しませんa。
• 論理的な がある場合はor、両側をチェックする必要があります。いずれかが空の文字列と一致する場合、logicalorは空の文字列と一致します。
• 2 つの正規表現のconcatenationが空の文字列に一致するには、両方とも空の文字列に一致する必要があります。
• 最後に、zero or more何かがある場合、それにはゼロが含まれます。つまり、常に空の文字列に一致します。

1. 一番上の演算子はorthis で、左側と右側の null 可能性をチェックする必要があります: band a*.
2. b左側の文字が nullable でないことを確認します: false.
3. a*次に、右側の が nullable: であることを確認しますtrue。
4. 今、私たちは戻ってきfalseました。trueortrue

Nullable 演習

実装をウォークスルーして、次の正規表現が null 可能かどうかを確認してください。それらをクリックして、答えを確認できます。

1. a
2. a*(b*|∅)
3. εa
4. ∅*
5. (∅|b)*(abc|ε)

関数の実装を見る前に、導関数の例を見てみましょう。ここでは、すべて文字に関して、いくつかの正規表現の導関数を取得しますa。

• pplea*を食べた後に一致するように残されている正規表現は stillです。aa*
• ab*に対するの導関数はです。接頭辞 は既に一致しているためaです。b*a
• に関する の導関数(a|b)bはaですb。
• に関する の導関数b|(a*b)はaですa*b。左bが合わなかったので捨てて、右のaに消費されました。zero or more a
• 次に、 がありますがab*、これは少しトリッキーです。リンゴを食べた後、マッチするために残された正規表現はb(ab)*. のみ一致したためa、少なくとももう 1 つの が表示されると予想されますb。

• 空集合の導関数は常に空集合です。空集合は何にも一致しないため、回復する方法はありません。
• 任意の文字に関する空の文字列の導関数は、空のセットです。キャラクターにマッチするとは思っていませんでした。空の文字列のみに一致します。
• 単一の文字から類似の文字 (この場合はapple) への派生物は空の文字列です。これは、それ自体が一致した後は空の文字列だけが一致するためです。
• 等しくない別の文字 (この場合はbアナナ) に関する文字の導関数は、特定の文字と一致していないため、空のセットです。
• or式の導関数はor、導関数の です。問題をその子に押し付けるだけです。
• 式の導関数はconcat、最初の式をスキップできるかどうかを考慮する必要があります。最初の式が空の文字列と一致し、null 許容である場合にのみ、最初の式をスキップできます。そこで、まずこれを確認します。r式が nullable でない場合、最初の式をスキップできない場合を考えてみましょう。次に、導関数は、最初の式concatenatedと 2 番目の式の導関数ですs。最初の正規表現をスキップできる場合は、2 番目の式の導関数のみである別の方法を検討する必要があります。次に、スキップする場合とスキップしない場合orの 2 つの選択肢があり、結果としてそれを返すことができます。rr
• 最後に、star演算子があります。式に 0 回以上一致します。文字が渡されるため、これはゼロのケースではありません。したがって、one or moreケースを検討する必要があります。これは、 内で式の導関数を取得し、式starでconcatenate再度それを取得する必要があることを意味しzero or moreます。

派生例1

について の導関数をとってみましょ(ab)*うa。

(ab)*はzero or more式なので、zero or moreルールに従います。これには、 内で式の導関数を取得する必要があることがわかりますstar。

これはconcatenationとaですb。そのため、左側が null 許容で、文字aが null 許容でないかどうかを確認します。これは、スキップできないことを意味します。aに関しての導関数を取らなければなりませんa。しかし、これは空文字列なのでconcatenate、右辺が だった空文字列を にするとb、 になりbます。

ここで、 に再帰的に戻ります。に関してzero or moreの微分を取り、a が返されたことを思い出してください。これを再び と連結すると、 が得られます。abab(ab)*b(ab)*

派生例 2

について の導関数をとってみましょ(a*ba)うb。

• a*と連結されてbaいるので、連結規則を見てみましょう。
• 左側a*が nullable であるかどうかを確認します。orこれは、それをスキップできることを意味します。これは、2 つの導関数のを作成する必要があることも意味します。
• a*が一致しないため、左辺は一致しなくなりbます。
• 幸いなことに、代替手段がありbaます。baに関するの微分bは およびaです。

ここでは詳細をスキップしました。自分で関数をウォークスルーして、私の作業を確認する練習だと考えてください。

導関数の演習

実装をウォークスルーして、次の正規表現の導関数が に関するものであることを確認してくださいb。それらをクリックして、答えを確認できます。

1. εb
2. b*(b|c)
3. a*(b|c)
4. bεb
5. ∅*b

赤いサクランボを食べると青い幽霊が食べられるようになる理由と、微分アルゴリズムを使用して正規表現マッチャーを実装する方法が理解できたと思います。

ここでは基本的な動作アルゴリズムについて説明しましたが、非常に小さな調整でこのアルゴリズムをさらに改善する方法はたくさんあります。この投稿では、簡略化のルールをごまかし、説明せずに使用しています。これは、演習を行うと特に明らかになります。また、メモ化を使用して効率的なオートマトンを遅延して構築する方法についても説明していません。

また、アルゴリズムを簡単に拡張して、 、 などの新しい演算子を含めたり、notContext interleave-Free Grammar をサポートしたりすることもできます。次の記事では、これらのトピックのいくつかについて説明します。

それまでの間、あなたが最も使い慣れたプログラミング言語でこのアルゴリズムを実装するのを楽しみにしています。コメントでリンクを送ってください。

ありがとうございました

• このアルゴリズムを説明するために時間を割いてくれたBrink van der Merwe 氏。

• Brzozowski、Janusz A.「正規表現の導関数」。Journal of the ACM (JACM) 11.4 (1964): 481–494.
• オーエンズ、スコット、ジョン・レピー、アーロン・トゥーロン。「正規表現デリバティブの再検討。」ジャーナル オブ ファンクショナル プログラミング19.2 (2009): 173–190。