/ 最近 .rdf 追記 設定 本棚

脳log[正規表現: 2008-05-14~]



2008年05月14日 (水) DFAエンジンのマッチの仕組みは謎のまま残された。正規表現を利用する側からはコントロールできる部分が皆無で、常に同じ結果が返ってくるおもしろみのないものらしいけど、その魔法の実現方法は大いに知りたい。

[正規表現][javascript][大型本] Jeffrey E.F. Friedl【詳説 正規表現 第3版】 オライリージャパン

読んだ。この日記で以前書いたようなこと(20080116p01, 20080111p01)は全て書いてあった。もちろんそれ以上に知らないこと(NFAのマッチングのしかた、NFA型正規表現エンジンに適用できる正規表現のチューニングの具体例、Unicodeサポート、Perl, .NET, Java, PHPの正規表現、\Gの使い方などなど)が書かれていた。

非常に読みやすい文章で書かれているし、必要なところでは必ず前後のページへの参照先が書かれている。章の始めには Overviewがあり、その章から読み始めた読者への配慮も忘れない。当たり前のことだけど、徹底されている。「まずこの本を読め。正規表現について話すのはそれからだ。」と言い切れる良い本。正規表現を初めて学ぶ人にも、効率について考える余地ができてくるほど既に正規表現を使っている人にも役に立つ。

すごく実用的なテクニックで、でも全く想像が及ばなかったものがある。168ページの「4.5.8.1 肯定の先読みを使ったアトミックグループの模倣」がそれ。

 肯定の先読みを使ったアトミックグループの模倣

/(?>pattern)/     // アトミックグループを使ったパターン
/(?=(pattern))\1/  // 先読みでアトミックグループを模倣したパターン

高機能化する他の実装にくらべて、昔のままの JavaScriptの正規表現はバックトラックを抑制する構文を持っていない。JavaScriptでは非常に有用。

20080116p01でも書いたが、次の終わらない正規表現

/"(?:[^\\"]+|\\.)*"/       // マッチに失敗するとき死ぬほど遅い

はアトミックグループや絶対最大量指定子が使えるなら次のように書けるが JavaScriptは両方ともサポートしていない。

/"(?:[^\\"]+|\\.)*+"/      // JavaScriptでは使えない
/"(?>(?:[^\\"]+|\\.)*)"/g  // JavaScriptでは使えない
/"(?:[^\\"]++|\\.)*"/      // JavaScriptでは使えない。※上2つとは少し意味が違う

次のように先読みでアトミックグループを模倣すると組み合わせの爆発を避けることができる。

/"(?=((?:[^\\"]+|\\.)*))\1"/
/"\1"/            // 上のパターンから先読み部分を取り除いたもの。

先読みを取り除いたパターンを見ると一目瞭然だが、引用符がペアになっていなくて \1 の後ろの " のマッチに失敗したとしても戻る場所がない。あるのは " と \1 にマッチしたという結果で、どちらもオプションではないので取り消すことはできず、繰り返しでもないのでマッチした部分を少しずつ手放させることもできない。なので、ちょっとずつ後じさりしながら延々とあらゆる組み合わせのマッチを試行することなしに、マッチが失敗に終わったことが即座に判断できるようになるというわけ。本物のアトミックグループよりは劣るが効率も悪くない。同じ働きをする次の二つのパターンとかかる時間を比較してみた。

/"[^\\"]*(?:\\.[^\\"]*)*"/
/"(?:[^\\"]|\\.)*"/

 手順

バックトラックによる組み合わせの爆発が起きない 3つのパターンでかかる時間を比較。3回実行した。(3回繰り返しても一回一回の中の試行順が固定されていたら傾向は同じになるわな。無意味。あてみやむいみ)

var re = [
	/"(?:[^\\"]|\\.)*"/,
	/"(?=((?:[^\\"]+|\\.)*))\1"/,
	/"[^\\"]*(?:\\.[^\\"]*)*"/
];
var s = [
	'"'+ new Array(5000+1).join('\\"'),        //  1/100
	'"'+ new Array(500000+1).join('\\"') +'"',
	'"'+ new Array(500000+1).join("\\'"),
	'"'+ new Array(500000+1).join("\\'") +'"',
	'"'+ new Array(500000+1).join('a'),
	'"'+ new Array(500000+1).join('a') +'"'
];
var results = [];
for(var j = 0; j !== s.length; ++j) {
	var result = [];
	for(var i = 0; i !== re.length; ++i) {
		var t0 = new Date();
		var m = re[i].exec(s[j]);
		result[i] = new Date() - t0;
	}
	results[j] = result;
}
WScript.Echo(results.join("\n"));

 結果

数の単位は msec。

パターン1パターン2パターン3
工夫なしアトミックグループの模倣ループ展開
/"(?:[^\\"]|\\.)*"//"(?=((?:[^\\"]+|\\.)*))\1"//"[^\\"]*(?:\\.[^\\"]*)*"/
文字列1マッチしない(F)"\"\"......\"\"2910×100, 2928×100, 2914×1002551×100, 2581×100, 2595×1002372×100, 2387×100, 2377×100
マッチする(T)"\"\"......\"\""124, 124, 124138, 137, 134108, 107, 108
文字列2マッチしない(F)"\'\'......\'\'138, 140, 151125, 127, 125122, 118, 118
マッチする(T)"\'\'......\'\'"138, 126, 126140, 128, 133135, 105, 106
文字列3マッチしない(F)"aa..........aa174, 172, 16614, 11, 1396, 90, 92
マッチする(T)"aa..........aa"155, 119, 12632, 15, 1415, 12, 11

 みどころ

  • マッチに失敗するときの、成功するときに比べた遅さ。
    • パターン2は例外
  • パターン2(アトミックグループの模倣)ではしばしばマッチに失敗する方が速い。
    • \1のマッチが成功だと判断するにはキャプチャした長い長い文字列を最後までたどって比較する必要があるため、\1のマッチに失敗するほうが速くなる?
  • 文字列1Fの特筆すべき遅さ。
    • 遅いとはいえ「終わらない」と形容するほど遅くはない。(これでも!)
    • 文字列長に比例したバックトラックが行われているせい?
    • 文字列2Fの結果と比較するに、\" という形で " が文字列の途中に含まれていることが最適化を阻んでいる?
  • パターン3(ループ展開)は特定の場合を除いてパターン2(アトミックグループの模倣)より若干速い。
    • ループ展開は『詳説 正規表現』に載っていた言葉。
    • 特定の場合とは文字列3Fのことで、不用意なパターンを用いると処理が終わらなくなる場合のこと。
  • パターン2(アトミックグループの模倣)は、(今回の眼目である)組み合わせの爆発が起こるような場合に、顕著な速さを見せる。
    • 他の文字列ではパターン3(ループ展開)に半歩譲るが。

ところで、文字列1Fがどのパターンでも一様に遅いのは文字列長に比例したバックトラックが行われているからなんだろうが、パターン2(先読みによるアトミックグループの模倣)でもそれを抑制できていないのは、なんとかできないものか。それでこそ若干のオーバーヘッドをのんででもアトミックグループの模倣を採用する理由になるのだが。


2008年01月16日 (水) Pythonかわいいよ、Python

[正規表現] 遅い正規表現

/\/(?:\\.|[^\n\\\/])+\/[gim]*(?!\w)/g
/\/(?:\\.|[^\n\\\/]+)+\/[gim]*(?!\w)/g // 死ぬほど遅い

どちらも同じく /regexp/i みたいな正規表現リテラルにマッチするのだが、下の方がブラウザが固まるほど遅い*。バックトラックの影響だろうか、これまで気にしてこなかったが……。原因が推測できない(無能)のがイタイ。(この日記、SHJSによるソースコードハイライトを多用していると読み込み完了直前にブラウザの反応がいっとき消えている。正規表現を最適化する余地があるならしたい)

昨日 rubyco(るびこ)の日記 (2007-06-20 正規表現の選択) 経由でウィッシュリストに入れた『詳説 正規表現 第2版』がタイムリーすぎる。

 いけないバックトラックの例

 reg = /.*x|a/
 s = "a" * 11_000_000
 m = reg.match(s)

http://d.hatena.ne.jp/kkos/20060801#1154438784

* 一度に多くの文字をつかんで繰り返しを減らそうという目論見がまんまと外れてしまった。

 原著は第3版が既に出ている。ちょっと(1、2年?)待ってみよう。<追記:2008-04-26に第三版(日本語)が発売*予定*。未だ Amazonに入荷せず(@2008-04-28)。22日にオライリーの通販で届いたって人もいるのに。>


2008年01月11日 (金) 文字クラス内で後方参照は使えない。/(")[^\1]*\1/ のようなものは [^1]とも [^"]のときとも違う結果になった。(Ruby1.8, JScript, JavaScript(Fx3rc1)で実験)

最終更新: 2016-11-12T11:41+0900

[正規表現][Ruby] 鬼車すごい。正規表現で再帰ができる。

Rubyの、括弧を使った %記法だって。

irb19> re = /%[Qq]?(?<brace>\{[^\{}]*(?:\g<brace>[^\{}]*)*})/
irb19> strings = %w(%{z}a %{a{b}z}c %{a{b}c{d{e}f}z}g %{{{{}}}z}a %{a{b}c %{z}a}b)
irb19> strings.each{|str| p str[re] }
"%{z}"
"%{a{b}z}"
"%{a{b}c{d{e}f}z}"
"%{{{{}}}z}"
nil
"%{z}"
=> ["%{z}a", "%{a{b}z}c", "%{a{b}c{d{e}f}z}g", "%{{{{}}}z}a", "%{a{b}c", "%{z}a}b"]

どの例も正しい範囲( %{ から z} まで)を切り取っているのがわかる。

  1. この機能が使える鬼車がのってる Rubyは 1.9.0。
  2. PCRE(ver 4.x)の (?P<name>...)と(?P>name)が同じものにあたるらしい。へー、そんなものが。javascript(JScript)の正規表現も新しくならんかな
  3. .NETの (?<open>...)と(?<close-open>...)も同じことができるらしいが、正直わからん*
  4. http://www.kt.rim.or.jp/~kbk/regex/regex.html < 正規表現の各種実装の違いがよくわかる。

 追記@2008-05-09: 対応する括弧にマッチする正規表現のヴァリエイション(<くどい表記だな)

/%[Qq]?(?<brace>\{(?:[^\{}]++|\g<brace>)*})/

若干速い。同じパターン( [^\{}] )の繰り返しも存在しない。http://fleur.hio.jp/perldoc/perl/5.10.0/pod/perl5100delta.mix.html#Regular_expressions を参考にした。

/%[Qq]?(?<brace>\{(?:[^\{}]+|\g<brace>)*})/

上のものの + が一つ落ちたもの。開き括弧が余分にある文字列を食わせると待てども待てども返ってこない。 http://mlog.euqset.org/archives/ruby-list/42232.html で既に書かれている。それに対する返答が http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-list/42233

* http://msdn2.microsoft.com/ja-jp/library/bs2twtah(VS.80).aspx#BalancingGroupDefinitionExample

 \1 (後方参照)が、単純にすでに出現したのと同じ文字列にマッチするパターンなのに対して、任意のパターンを指定できるものだと想像してみる。

 追記@2008-05-09: それでは括弧のネストに対応できない。それは条件分岐の一形態。.NETのものはカウンタの増減を指示する構文。