練炭ブログ

萌え壁紙、Irvine、DMonkey、Proxomitron などの情報を扱ってます。

正規表現技術入門 ――最新エンジン実装と理論的背景

コメントなし»

webdb_regexp

読みました。
勉強になりました(小並感

正規表現の入門書というより、正規表現エンジンの実装のための入門書。
正規表現エンジンを書きたいと思っているけどどうすればいいのか分からない、っていう人におすすめ。

一部のページは、Software Design 2013年5月号の正規表現特集に掲載された新屋氏自身の記事(sd_engine.pdf)がベースになっているっぽいです。

第2章
歴史が面白い。
Ken Thompson すごい。
Kleene はクリーネと読むのでしょうか。

p64
「合計が閾値θ(ノード内部)を超えると」は「θ以上」と書くべきではないか気になりましたが、ニューロン業界だとそういう表現をするらしい?

p75
『以降、本書では「POSIXの正規表現」と言えば「ERE」を指す』とあるので心して読み進めましたが、p246とp253でしか言われてない上にどちらもどの仕様かは関係ない意味合いで使われてました。

第3章
p99
TRE はこれでしょうか。
TRE — The free and portable approximate regex matching library.

p105
妥協するという選択肢っていいですね。
メールアドレスの正規表現はもう HTML5 方式だけでいいでしょ。

第4章
p127
「ε遷移の除去」という見出しですがε遷移のやり方を説明しつつ、中盤の「しかし、実はどんなε-NFAでもε遷移を取り除くことができます。……」という段落だけは除去の話をしているのでちょっと分かりにくかったです。

p131

しかし、現代の正規表現エンジンで有限オートマトンベースのマッチングをするもので、
NFA だけを用いるエンジンはほとんどありません。
NFA ベースのマッチングを実装しているエンジンは同時に DFA ベースのマッチングにも
対応しているのです。そのため、本書では有限オートマトンベースのマッチングを用いる
正規表現エンジンを DFA 型の正規表現エンジンと呼んでいます。

これはつまり

  • DFA に変換せず NFA のまま直接処理するエンジン(ごく少数)
  • NFA を DFA に変換して処理するエンジン
  • NFA のまま処理するコードと、NFA を DFA に変換して処理するコードを併せ持つエンジン

を DFA 型と呼んでいるということなのでしょうか。

NFA を DFA に変換して処理するという定義に限定すべきでは。

第4章は

  1. 分岐のない NFA の説明とコード
  2. ε-NFA の説明とコード
  3. 部分集合構成法の説明とコード
  4. DFA の説明とコード

というような順番で説明して欲しかったです。

第5章
p163,173
後方参照に使われるキャプチャにバックトラックが必要なのはなぜ?
いつか鬼雲のソースを読もう。

第6章
p221
固定文字列検索の分野も面白そう。

第7章
p241
(\D+|<\d+>)*[!?]
(\D++|<\d+>)*[!?] が同じというのが分かりません。
手元で試しても違うように見えます

p249
固定文字列検索でもオーバーラップしないという仕様はありえるし、正規表現にかぎらず文字列検索一般に該当する問題で、ただ正規表現の場合はオーバーラップしない仕様でも先読みを使えばオーバーラップさせられる、ということでは。

正規表現でもオーバーラップするものとしては、Mery 2.2.2.4953 | Haijin Boys Online とか Perl6 の overlap とか。

p257
可変長後読みはどこからマッチを開始するのかどうやって決めるのか、パターンを逆向きに構築して一文字ずつ後ろ向きにマッチしていく手法はどうか?とか、いろいろと大変だと昔なにかで見た気がします。

p257
空文字列の繰り返しをVM型エンジンでマッチしようとすると、無限ループになりいずれスタック溢れで止まると思うのですが、そういう問題ではないのでしょうか。

他の章で触れられてはいますがそちらでは最適化の一手としての説明ですし。

JavaScript のこの挙動は、
ECMA-262 Edition 5.1 15.10.2.5 Term

NOTE 4 Step 1 of the RepeatMatcher's d closure states that, once the minimum number of repetitions has been satisfied, any more expansions of Atom that match the empty String are not considered for further repetitions. This prevents the regular expression engine from falling into an infinite loop on patterns such as:

によるものだと思いますが、空文字列にマッチするかどうかは実際にマッチを試して成功してからでないと分からないのに「0回のマッチ(1回もマッチしていない)」として扱われるのが謎。

第8章
p264
VerbalExpressions より Regexp::Assemble を紹介した方がよかったかも。

Appendix
この本のメインディッシュ。
第1~8章のいろいろなところで「○○については Appendix で」という案内が書かれていたりします(各節冒頭のあらすじを除いても14か所くらい)。

もちろん第1~8章だけでも役に立ちます。

・組版的なところ

スペースを網掛け+ルビで表記しているのは分かりやすいです。

第1章以外で正規表現が等幅フォントになっていないのは構わないけど、* が上付きになっているのは注釈記号に見えて紛らわしいので、それだけはなんとかして欲しかった。

図が多くて分かりやすいです。
ただ、この本に限らない一般的な作法ではありますが、図をページの一番下、紙面に余裕がない場合は次ページの一番下に落としてあるのが、本文と図が離れすぎて読みづらいです。正直廃れて欲しい風習……。

スクリーンショットに書き込まれているコメントが、背景色とほとんど同じ色で見づらいです。

ノンブルが文字ごとに上端下端が違うフォントなので、ページをパラパラとめくった時に数字が上下に動いているようで見づらいです。

・以下些細な点。

p43 - 下の方のコードはスクリーンショットなので黒地に白抜きでは。

p64 図2.1 -
(3) 1=x1&x2v=(略) では。
(4) v=¬x1 字が小さくて見えづらいけどマイナスじゃなくて否定記号であってる?

p109 図3.4 - このように塗ったほうがよかったのでは。

p113 - 正規表現が 0*(10*10*)*` と書いてあるように見えるけど、自分の本の印刷の汚れ?

p175 リスト5.16 - 2354行のコメントが薄字になっていない。

p194 -・(?(condition)yes|no)(?(condition)yes)条件式
見出しレベルが違うのと、説明がよく分からない。

p204 図5.21 - a*+a のバイトコード

p217 図6.5 - #1 と #0 を繋ぐ線が矢印になっていない。

p235 - スクリーンショット 6、7行目の正規表現に ^ $ がない。

p242 - 一番上のスクリーンショット 3行目の正規表現に ^ $ がある。

p243 - スクリーンショット 3行目の正規表現に ^ $ がある。1、3行目が [!] になっている。

p265 リスト8.3 - 16行目のコメントが薄字になっていない。

p274 リスト8.6 - 「ですし」がおかしいのと、「数式」が別の意味で二つ使われていて紛らわしい。

p278 - 「これはintegerのdigitが1つ以上存在する」は「integerは数字が1つ以上存在する」あたりの方がよいのでは。

p279 リスト8.8 - integer だけラベルがついていて、上記の表現と相まって余計分かりづらくなっている。

p315 - A A A から C C C までだから 3^3=27 が正しい?

p334 - 索引にハ行がない(ハ行がないとは言ってない)

『神聖にして侵すべからず』体験版読書感想文コンクール 2011Summer

コメントなし»

締切が8月31日ということで、まるで夏休みの宿題です。それどころか私が体験版をインストールしたのがその8月31日、どうみても小学生です。

そういえば昨日は「定期試験前日になってまったく勉強していなくて焦る」という夢を見ました(中学生か高校生という設定)。

さて、いわゆるエロゲの体験版をプレイするのははじめての経験です。エロゲー自体も久しくプレイしていません。

最近のエロゲはみなそうなのかも知れませんが、コンフィグが豊富で細かいところまで調整できますね。

「カーソル自動移動」は個人的には合わなかったです。画面遷移してからカーソルがうねーっと動くのがちょっと変なふうに感じてしまって。

Windowsのマウスの設定では自動移動にして快適に使っているので、カーソルがゆっくり動くのではなく瞬時にボタンに飛べばいいのかも。

もっともストーリー上の選択肢に「規定のボタン」はないので、自動移動にはもともと向かないのかも知れません。

よって人によっては「カーソル自動移動」をオフにした方がよいでしょう。

話の方は体験版ということで短く、起承転結の起の一部、あるいは登場人物の紹介だけといったところですが、雰囲気を掴むことは出来ます。

日常のあれこれを楽しむ、という話でしょうか。本編で激しく非日常を味わうことになるのか、そこそこ穏やかな日常が続くのかは分かりませんが。

ヒヤロン

コメントなし»

ヒヤロンを長期保存すると、勝手に溶けて使用済みの状態になってしまう。


上は去年の使い残し、下は今年買ったもの。いずれもヒヤロンミニ、未使用。

中袋が破けたのかと思ったけど、触った感じでは中袋の中身は入ったままっぽい。もしかしたら空気中の水分が外袋を透過して吸収されたのかも。

買った年に使い切るの前提の製品なのかねえ。いざという時のために常備しておくことが出来ないよ。

乾燥剤と一緒に密封するか、冷蔵庫か冷凍庫に入れておけば持ったりするかも。

Panasonic LDA7D-A1 LED電球

コメントなし»

で、せっかく買ったPanasonicのLED電球(LDA7D-A1)がもったいないので、

階段:トップバリュ LDA4L-H-TV
玄関ポーチ:電球型蛍光灯

だったのを

階段:Panasonic LDA7D-A1
玄関ポーチ:トップバリュ LDA4L-H-TV

とドミノ移植してみました。

LDA7D-A1は正直階段に使うには明るすぎて不向きなのですが、玄関まで光が届くようになったので玄関のライトを消しても平気になって、玄関ポーチの分も合わせてちょっと省電力化しました(東電の供給量がまだ厳しかった頃の話)。

ただ、しばらくしたらLDA7D-A1がチラつくようになりました。
家電-コラム-藤山哲人の実践! 家電ラボ-第2回:LED電球は「光がチラつく」ってホント?
のような高速のチラつきではなく、目で容易に近くできるくらいの遅いペースでのチラツキです。

故障か初期不良っぽい感じですが、我慢出来ないほどではない(階段だし)のと、面倒なので、とりあえずそのまま使ってます。

ELPA SA-26JB センサー付ソケットアダプター

コメントなし»

先々月だったかにホームセンターで見かけて、PanasonicのLED電球(LDA7D-A1)と一緒に衝動買い。

玄関ポーチに取り付けようと思ったら、ガラスのカバーが引っかかって入らない。いけると思ったんだけどなー。

階段に取り付けてみたら、上の階から降りる時は真下まで行かないと反応せず、下の階から登る時もシェードのせいで真下近くまで行かないと反応せず。

トイレにはよさそうだけど使うときだけ点灯する習慣が身についてるし。

というわけで無駄な買い物をしてしまいました。何か使い道が出来ればいいのですが。

やわらかセキュリティ Qes

コメントなし»

あまりに微妙すぎるファイル暗号化ソフトが発売。

(ウェストサイドのページより引用)

Qes で作られたサンプルデータ(実行ファイル)が用意されており、実行してクイズに答えてパスワードを入力するとこつえー絵の壁紙が保存できます。
※体験版ではなくサンプルデータの方ね。

このソフトの機能に「展開できる期間を設定できる」とあり、サンプルデータでも実際に「2011年4月29日0時から1年間」と指定されています。

ちなみに先日(たぶん発売日)までは別バージョンの壁紙(800x600)が暗号化されたサンプルデータが置かれていたようです。まだ残ってますけど。こちらは期限切れで現時点で実行するとエラーになりますが、日付の確認はタイムサーバに問い合わせるのではなく実行したPCの時刻を見ているだけなようなので以下略。という訳で取り逃した人も安心です。

Tropicana オレンジのまろやかレアチーズ風味

コメントなし»

トロピカーナ フルーツスイーツ オレンジのまろやかレアチーズ風味 2010年8月3日(火)から新発売
(画像はリンク先から引用)

買いました。

安かったから。

安かったから。

オレンジのさっぱりとした酸味と、レアチーズの濃厚な味がぶつかり合ってなんとも言えない味。

賞味期限ぎりぎりまで売れ残っていたのには訳があったということです。

オレンジはオレンジだけで飲みたかった……。

アイリスオーヤマ 人感センサー付 ECOLUX

コメントなし»

アイリスオーヤマ、3千円で買える人感センサー付きLED電球 - 家電Watch
人がいる時だけ点灯するから さらに省エネ「ECOLUX」人感センサー付LED電球発売| 2011年|お知らせ|アイリスオーヤマ株式会社 | IRISOHYAMA.Inc

放熱フィンが大きい、と思ったけど既存製品はそれほどでもなかったので、人感センサーが付いている分だけ大きくなるのは仕方がないのかも。

白熱電球 20W 相当だと多分暗すぎるのではないかと思うので、40W 相当の機種が出ればいいな。

[2010-04-27 追記]
アイリスオーヤマ、人感センサー搭載のE26口金LED電球2アイテムを発売 | 家電 | マイコミジャーナル

自動消灯は急に暗くなるのではなく、緩やかに行われる。

ゆっくりと暗くなるのはポイントが高いです。一瞬で消えると目立つ、というか「何か起きた!?」と思って目を向けても何が起きたのかよく分からないモヤモヤした状態になるので。

試しに買ってみてもいいかな。

ライオン CHARMY クリスタ パウダー

コメントなし»

ライオン、グラスのくもりまではがしとる食洗機専用洗剤 - 家電Watch
食器洗い機専用洗剤『CHARMYクリスタ パウダー』改良新発売|プレスリリース|会社案内|企業情報|ライオン株式会社

「スプーン入れ」が付いているのはいいですね。

ただ、スプーンは刺して立ておいて、手は洗って拭いてから触るようにすれば済む話なので
多分この新製品は今問題を抱えている家庭にとって何の解決にもならない気がします。
(スプーンをスプーン入れにきちんと入れられるような人間ならスプーン入れが付いてなくても各自で工夫できるはず)

うちはクリスタジェル(液体)を使ってますが、節電のために最近は食洗機を使ってないので洗剤も減ってません。

Amazon.co.jp で注目の商品

コメントなし»

Amazon.co.jp: 電池式 LED36灯ランタンライト 携帯懐中電灯照明
これはまた評価が……。

このランタン、ちょっと前に秋葉に行った時に店頭で見かけたものと同じっぽいです。
電源が単一電池なのでどうにもならないという。
単三電池一本を単一電池化するスペーサーが一個290円だったかで売ってました。

Amazon.co.jp: 単3電池2個を単1サイズに変換 電池ケース スペーサー 4個セット 災害時、充電池等に。

4個セットで110円は安い、送料が高いので何パックかまとめて買えば……
と思ったら1セットごとに送料500円かかる暴利w

1個あたり152.5円。まあ単三電池1本を単一電池にするスペーサーを1個100円で買うよりはいいかも。