正規表現パート２ NFAエンジンの場合は、 正規表現の磨き上げが必要？.

Presentation on theme: "正規表現パート２ NFAエンジンの場合は、 正規表現の磨き上げが必要？."— Presentation transcript:

1 正規表現パート２ NFAエンジンの場合は、 正規表現の磨き上げが必要？

2 覚えていないと思うので・・・おさらい まずは、 DFA（テキスト主導型）エンジン バックトラックが持つ効率の悪さを回避する為に 全ての可能性のあるマッチを同時に管理することによって、高速処理を実現するエンジン 管理用のマップを作るため、場合により時間がかかり、メモリが必要になる

3 語ると長いのでざっくりNFA NFA（正規表現主導型）エンジン バックトラックを根幹にもつエンジン ＊POSIX NFA 最長のマッチを返さなくてはならない ＊従来型NFA 　 正規表現主導型の性質を利用して、どのようなマッチを望むか性格に指定できる ※　覚える必要はないですが・・・ 記憶のない人は、前回の資料を見て下さい。

4 バックトラックと効率化 バックトラック機能のあるNFAエンジンの場合 選択肢が発生した場合、その位置に戻れるよう ぱんくずのように戻り位置を記録していく方法を採用している 分かりにくいので例を次に示します。

5 もしかして・・・バックトラック減らしたら効率化？
つまり 斜めの線の→が入っている箇所が 選択によるバックトラックが発生する位置 バックトラックが多いですね。 もしかして・・・バックトラック減らしたら効率化？

6 こうしたら、バックトラック減らせる？ 減らせそうですが・・・どうでしょう？

7 考えるべきこと 変更によってメリットがあるか否かは 以下を考える必要があります。 エンジンの違いによって得られる効果は同じか この変更が効果をはっきするのは、どんなときか

8 エンジンタイプによる効果のちがい POSIX NFAエンジンタイプ この変更による効果はほとんどありません。理由は、正規表現が方言できる全ての順列が試されるので、選択肢の順序をどの順番で為そうと関係がない為です。 従来型NFA すぐにマッチに結びつくような選択肢の並べ方をすれば、最初のマッチが見つかったところでエンジンが停止するので効果があります。

9 マッチ結果による効果の違い この変更によって処理がはやくなるのは、マッチが有る時だけに限られます。従来型NFAがマッチ不成功を報告するのは、正規表現が表現できる全ての順列を試してからです。 よって、最終的にマッチ不成功になったからには、全ての順列を試し済みなので、順番を変えても意味がありません。

10 まとめ NFAエンジンの場合 マッチするパターンにおいて、バックスラッシュの回数を減らすことはパフォーマンス向上につながる

11 さらに良い方法とは 文字のひとつひとつを反復処理（循環処理）しなければならない。ここにオーバーヘッドがかかる。 この部分を削減できれば、効率手的な正規表現となる。 ではどうするか・・・

12 さらに、もっと良い方法 元々（上段）を下段のように変更するとバックスラッシュを抑えることができる 「[^＼＼”]」は、通常の文字列にマッチするので 「[^＼＼”]+」を使えば、(...)*の１回分で１度に読める通常の文字をまるまる読み込める →バックトラックを削減し、スターによる反復処理も最小限！

13 話は飛びますが・・・ 正規表現にはいろいろな書き方があるお話は前回しました。 例えば a, b, c, d, e, f, g のどれかに一致する文字は、 [a-g] という文字クラスを使う方法のほか a|b|c|d|e|f|gという書き方もできますね。 さて・・・どっちが早いのでしょう？

14 そうだ、ベンチマークテストをやってみよう！

15 正規表現のベンチマークテスト方法 そもそもベンチマークテストとは？ → ある仕事を行うのにどれくらい時間がかかるかを単純に計測すること 時間計測のためにすることは？ システム時間を取得し、問題の処理を実行し、再度システムの時間を取得する この最初に取得したシステム時間と、次に取得したシステム時間のさが処理に要した時間となる

16 計測時の注意点 計測したい仕事の時間だけを計測する 十分な仕事を実行する （コンピュータが優秀すぎると比較できない） 正しい仕事を実行させる （オーバーヘッドを増やさない）

17 ベンチマークに使うコード（PHP版) $TimesToDo = 1000; // テスト文字列の準備 $TestString = ""; for ($i = 0; $i < 1000; $i++) { $TestString .= "abababdedfg"; } // 最初のテストの実行 $start = gettimeofday(); for ($i = 0; $i < $TimesToDo; $i++) preg_match('/^(a|b|c|d|e|f|g)+$/, $TestString); $final = gettimeofday(); $sec = ($final['sec'] + $final['usec']/ ) - ($start['sec'] + $start['usec']/ ); print("Alternation takes %.3f seconds\n", $sec); // 第二のテストの実行 preg_match('/^[a-g]+$/, $TestString); print("Character class takes %.3f seconds\n", $sec);

18 実際、自分では計測していませんが 環境にもよりますが 以下のような結果がでたそうです。 Alternation takes seconds Character class takes seconds ずいぶん違いますね。

19 なぜ？ 「a|b|c|d|e|f|g」は、１つの開始位置で必ず７文字分のバックトラックが必要となり、マッチに達するまでに大量のバックトラックが必要になる 「[a-g]」は、次の位置でマッチするまで、１文字分前進のバックトラックしか発生させない為 正規表現の処理の高速化には、他にも色々ありますが、選択はNFAエンジンの場合、必ずバックトラックが増えるので注意が必要です。

20 皆さん、用法用量を正しく守って使いましょう。
Fin 皆さん、用法用量を正しく守って使いましょう。