/ 最近 .rdf 追記 設定 本棚

脳log[正規表現: 2008-11-10~]



2008年11月10日 (月) 自動二輪でデュアルパーパス車(デュアルといいつつ実質オフ寄り)を嗜好し、自転車ではクロスバイク(の中でもロード寄り)を好むのに、共通点はどこにあるのかと思えば、軽くて扱いやすい所だったらしい。オートバイにライトウェイトスポーツというカテゴリはないのか。スーパーモタードだけなのか。(それでいいんだけど)

[正規表現] >Ruby 初心者スレッド Part 22 >>861 (http://www.kt.rim.or.jp/%7ekbk/zakkicho/08/zakkicho0811a.html#D20081109-6 経由)

if line =~ /.*Sector:<.*(Basic Materials|Conglomerates|Consumer Goods|Financial|Healthcare|Industrial Goods|Services|Technology|Utilities)/
    p $1
end 

HTMLをその場その場の正規表現で処理したくはないけど、それはそれとして、こうする。要は「Sector:HOGEHOGE」というテキストにタグがいろいろ付いていて、それらを無視してセクタ名を取り出したいということかと。

   /Sector:(?:<[^>]+>)*(Basic Materials|Conglomerates|Consumer Goods|Financial|Healthcare|Industrial Goods|Services|Technology|Utilities)/

元のパターン冒頭の .* は全く無駄。一度文字列全部を食べてしまうことに無駄以外の意味はない。(後ろから「Sector:」を探すか、前から「Sector:」を探すかという違いはあったりして)

二番目の .* が以降の文字列すべてを食べてしまうのも無駄。それにそれじゃあ「Sector:」から最も離れたセクタ名と同じ単語に一番最初にマッチしてしまう。

以上お目汚しでした。それより、この質問への最初の回答は金言。良いなあ(こんなレスがすぐに付くなんて)。

 正規表現は書き方を覚えないと駄目
 なぜなら、ほんの少し変えようと思っただけで別物になるから
 コピペでやろうとすると異常に遠回りになる

基本的に覚えることは

  • 文字クラスとメタ文字(\w,\n,\s,...)
  • アンカー(^,$,\b,...)と先読み(戻り読み)
  • パターンのグルーピングと選択
  • 量指定子(これは文字にもグループにも付けられる)

だけだもの。


2008年05月28日 (水) コンテントネゴシエイションによる表示言語の切り替えはうまくない。内容が同じなら日本語で表示された方が読みやすいが、英語の方が情報が新しいのが常。Accept-Languageを切り替えるより URLを書き換える方が圧倒的に楽でしょう。読み手に選択肢を! >>>>>>http://www.mozilla.com/firefox/

[正規表現] 今日やられた正規表現

/^(?=\W)/
/^(?!\w)/

二つの違いは? (ヒント:空文字列/空行)


/^(?=\W)/  //=> 単語に使われる以外の文字から始まる行の頭にマッチ
/^(?!\w)/  //=> 単語に使われる文字から始まらない行の頭にマッチ
           //   (最初のパターンと違い、一文字もない場合(空行)にもマッチする)

2008年05月15日 (木) 正規表現の存在を知り、その文法を知ったのは JScript5.5の HTMLヘルプだった。ほんとう、役に立つドキュメントだった。(>20080215p01) 「だった」といいつつ、今も持っていて参照もしているけれど。

[Ruby][正規表現] /n, /s, /e, /u, $KCODEのもやっとを解消

正規表現リテラルの /nseuフラグは正規表現のマッチ動作に影響を与える。(/nseuフラグのいずれも指定しなかった場合は実行時の $KCODEに従う)

/nが指定されていたり $KCODE='NONE'のとき、「.」は改行を除いたり改行を含んだりする 1バイトにマッチするメタ文字だが、/seuフラグが指定されていたり $KCODEが SsEeUuのいずれかで始まる文字列のとき、「.」は日本語を含む、Shift_JIS、EUC-JP、UTF-8の一文字(1-3?バイト)にマッチする。

/nseuフラグや $KCODEは正規表現のパターンの解釈にも影響を与える。

Shift_JISで保存したスクリプトファイルに /表w/ というパターンと '表w' という文字列リテラルがあり、マッチを行った場合。実行時に $KCODE='NONE'であればパターンは /\225\w/ と解釈され、"\225"の後にメタ文字 \wにマッチする文字を探し、失敗する。$KCODE='SJIS'であればパターンは /表w/ と解釈され、"表"のあとに "w"を探し、成功する。

irb(main)> /表w/n =~ '表w'
=> nil
irb(main)> /表w/s =~ '表w'
=> 0

正規表現パターンの中のマルチバイト文字は文字列の場合と同じく、あくまでバイト列であり、/nseuフラグや $KCODEがどうであれ EUC-JPで保存されたスクリプトの中の正規表現リテラル /あ/ は Shift_JISの「あ」を表すバイト列 "\202\240" にマッチすることはない。


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のものはカウンタの増減を指示する構文。