正規表現 の 実行エンジン

0 件のコメント

今回は「正規表現 の 実行エンジン」についてまとめます。

実行エンジンの種類

正規表現の実行エンジンには大きく以下の2種類が存在します。

  • DFA (決定性有限オートマトン。Deterministic Finite Automaton。)
  • NFA (非決定性有限オートマトン。Nondeterministic Finite Automation。)

以下でそれぞれについて特徴と実装しているプログラムを見ていきます。

主な特徴

DFA

DFAは、文字列を走査中に現在可能性のあるすべてのマッチを管理しながら合致する文字列を探していきます。

その仕組みは「文字列を軸にマッチする文字列を探す」ものになっています。

NFA

NFAは、正規表現を左から順に取り出して文字列を探しに行き、見つからなければ戻って再度文字列を探すを繰り返しながら合致する文字列を探していきます。

その仕組みは「正規表現を軸にマッチする文字列を探す」ものになっています。

主要なプログラム

以下の表を見ての通り「NFA」を利用したプログラムがほとんどです。 動作原理を抑えるのであれば「NFA」の動作原理をおさえておくのが良いでしょう。

種類 プログラム例
DFA egrep, MySQL
NFA Java, .NET, Perl, PHP, Python, Ruby, vi

実行エンジン の 基本原則

正規表現のマッチングにおける基本原則(DFA、NFA関わらず)は以下の2点です。

  • 最初にマッチした文字が優先される
  • 標準の量指定子は欲張り

何も指定がなければ、マッチングは与えられた文字列のうち最初にマッチした文字を起点にマッチングされます。 以下のサンプルでは seashellssea にマッチして seashoresea にはマッチしていません。

// 対象文字列
She sells "seashells" by the "seashore".

// 正規表現
/sea/i

// 検索結果
She sells "seashells" by the "seashore".

また、量指定子(*?+{num, num})は欲張りなためできるだけ長くマッチングできる文字列を探します。 以下のサンプルでは最初の " でマッチングは終わらず最後の " までをマッチングした文字列とみなします。

// 対象文字列
She sells "seashells" by the "seashore".

// 正規表現
/".*"/i

// 検索結果
She sells "seashells" by the "seashore".

NFA 実行エンジン の 動作

NFA実行エンジンでは最初に述べた通り「正規表現を軸にマッチする文字列を探す」動作をします。 また、前述の通り最初にマッチした文字からマッチングが始まり、できる限り長いマッチングを行います。

例えば上記の「How much wood would a "woodchuck" chuck if a "woodchuck" could chuck wood?」に対して「".*"」でマッチングするとき、以下のような検索が行われます。

正規表現「".*"」は3つの文字("(= a)、 .*(= b)、 "(= c))から構成されます。 まずは最初の検索対象文字 " (= a) を文字列の先頭から順に探します。 すると①の位置でヒットするので、次の検索対象文字 .* (= b) をできるだけ取り込んでいきます。 できるだけ取り込むと行末の②まで取り込めてしまいます。 これでは最後の検索対象文字 " (= c) が残ってしまうので、1文字ずつ左へ戻りながら検索対象文字 " (= c) を探します。 すると③の位置(k)で右隣に検索対処文字 " (= c) とマッチできる状態が作れることを見つけます。 これで要求された正規表現が完成できたので結果として「"woodchuck" chuck if a "woodchuck"」を返します。

正規表現のマッチング結果だけ見ているとなぜ「"woodchuck"」が結果にならないか疑問に感じますが、動作原理が分かるとなんとなく納得はできます。 本当に「"woodchuck"」だけマッチングさせたければ「"[^"]*"」のような正規表現を書かないといけないですね。

今回は「正規表現の動作原理」についてまとめました。 ポイントは以下の通りです。

  • 正規表現は最初にマッチしたところを起点にマッチングが行われる
  • 正規表現は基本的に欲張りなのでできるだけ長くマッチングさせようとする

参考になったでしょうか? 本記事がお役に立っていると嬉しいです!!

最後に… このブログに興味を持っていただけた方は、 ぜひ 「Facebookページ に いいね!」または 「Twitter の フォロー」 お願いします!!