名前が計算理論・形式言語・プログラミングっぽい(謎?)曲たち

こんにちは。 2012年 6/23日にチューリング大先生の生誕100周年!! を迎えるということで今から Google のトップページがどんな風になるのか楽しみにしている今日この頃です。

ところで最近

ふとしたきっかけでタイトルにあるように名前が面白い曲に出会うことが多かったので、ここにいくつかリストアップしていきたいと思います。

“Regular Expression” by Broken Drum

iTunes Store

音楽のジャンル分けには詳しくないのですが、エレクトロニックでくくっていいのでしょうか。 ビシバシしててノリの良い曲です。個人的には Jubeatに入って欲しい 。僕は普通にBGMとして良く聴いてます。

え, iTunes store で Regular Expression っていう曲発見wwこれは買うしかない(キリッhttp://t.co/FFgOAnEa
@sinya8282
Ryoma Sin'ya

“Algorithm” by juncmodule

“Algorithm”を冠する曲は以外に多い(“アルゴリズムたいそう”然り)のですが, ここに選んだ曲の収録アルバム名も面白いです。ずばり「Syntax Error」

http://a1.mzstatic.com/us/r30/Music/67/50/2e/mzi.ypowghsk.170x170-75.jpg

iTunes Store

このアルバムは、全曲においてタイトルが我々プログラマにとって馴染み深いものばかりです。 “Debug”とか”Array”、”Assembler”とかそんなんです。なにこれw 個人的にはジャケットのデザインにも惹かれます。

皆さんも “Debug”を聞きながらデバッグ しましょう(謎)。

“Church – Turing Thesis” by DMX Krew

このエントリを書くきっかけになった曲です。Turing関連の書籍を探ってたら 今日見つけました 。 この曲が収録されているシングルのメイン曲”That Was Harder Than I Expected”というタイトルにもくすりときました。

http://a1.mzstatic.com/us/r1000/062/Music/bf/d8/32/mzi.jqulryiz.170x170-75.jpg

iTunes Store

聴いてみると、たしかに帰納的関数な趣、チューリングマシンのかっちりとしたイメージを同時に彷彿とさせる… わけでは特にありませんでした

“Context-Free Grammar for Alto” by Jackson Moore

http://a1.mzstatic.com/us/r30/Music/cc/38/c8/mzi.gwdpadev.170x170-75.jpg

iTunes Store

形式言語きたー!! しかも Jazz!! と発見したときはかなり興奮したのですが、 前衛的すぎて全く理解できなかった のでiTunesでの視聴のみに留まっています。

その他もろもろ

上原ひろみさんの「Another Mind」(XYZが最高!)にも”010101(Binary System)”という曲があったりします。 もっと探してみると、色々出てくるのでしょうがとりあえずここまで。

「他にも面白い曲あるよー」という話がありましたら是非教えて下さい :-)

正規表現を使ってデータ圧縮等するツールを作りました

RANS

というツールをGW中に作ってみました。

RANSはなかなか面白いツールでして、正規表現を使ってデータ圧縮ができたりします。 仕組みは単純で、正規表現を与えて「受理文字列とその順番(長さ-辞書順)」を一対一対応させる、というものです。

例えば、/a*(b*|c*)/という正規表現について考えると以下が成り立ちます。

  • 0番目の受理文字列は””(空文字)
  • 1番目の受理文字列は”a”
  • 4番目の受理文字列は”aa”
  • 10番目の受理文字列は”aab”

RANSではこれを以下のようにして計算できます

% rans 'a*(b*|c*)' --text aab
10
% rans 'a*(b*|c*)' --value 10
aab

何が凄いの?

正規表現のみを用いて、単純な基数変換やデータ圧縮等の応用を柔軟に実現できるところです。

しかも、RANSでは「受理文字列<->順番」の対応を受理文字列の長さnに対して

  • 受理文字列->順番はO(n)
  • 順番->受理文字列はO(n log(n))

時間で計算できます。(しかも空間量は n に依らず固定!)

細かい話

上の計算量は「任意長整数の加乗算」が定数オーダーで計算できることを仮定した上での話です。 しかも「正規表現の複雑さ」、つまり「DFAの状態数」による項も無視しています。

これらの話も考慮した上では、n桁の整数乗算がm(n)、DFAの状態数をDとすると

  • 受理文字列->順番はO(m(n) n D^2)
  • 順番->受理文字列はO(m(n) n log(n) D^3)

という計算量になります。(空間量も整数乗算のソレに依存)

導入・使い方

http://sinya8282.github.com/RANS/ に一通り記述しています。

RANSを導入するとCUIプログラム(rans)とC++ API(rans.hpp)が使えます。

導入は、Homebrew on Mac な環境であれば

% brew install https://raw.github.com/sinya8282/homebrew/rans/Library/Formula/rans.rb --HEAD

と一発です。(本家に登録したいけど、若い弱小projectじゃ駄目っぽい..? :-()

追記

コメントにて”brew tap”の存在dictavさんに教えてもらいました。感謝!

tapコマンドでRANSをHomebrewに取り込めます。

% brew tap sinya8282/rans
% brew install rans --HEAD

brew tap/untap 便利 :-o

URL圧縮

上記ページにもありますが、ここでもRANSを使ったURL圧縮について説明します。

RFC によると、完全なHTTP-URL (httpプロトコルなURI)は正規表現で記述することができるそうです。これに従って手書きしてみると

http://((([a-zA-Z0-9]|[a-zA-Z0-9][-a-zA-Z0-9]*[a-zA-Z0-9])\.)*([a-zA-Z]|[a-zA-Z][-a-zA-Z0-9]*[a-zA-Z0-9])\.?|[0-9]+\.[0-9]+\.[0-9]+\.[0-9]+)(:[0-9]*)?(/([-_.!~*'()a-zA-Z0-9:@&amp;=+$,]|%[0-9A-Fa-f][0-9A-Fa-f])*(;([-_.!~*'()a-zA-Z0-9:@&amp;=+$,]|%[0-9A-Fa-f][0-9A-Fa-f])*)*(/([-_.!~*'()a-zA-Z0-9:@&amp;=+$,]|%[0-9A-Fa-f][0-9A-Fa-f])*(;([-_.!~*'()a-zA-Z0-9:@&amp;=+$,]|%[0-9A-Fa-f][0-9A-Fa-f])*)*)*(\?([-_.!~*'()a-zA-Z0-9;/?:@&amp;=+$,]|%[0-9A-Fa-f][0-9A-Fa-f])*)?)?

な感じになりました(手書きなのでミスってるかも..)。

この正規表現を http-url.regex というファイルに保存して、「http://sinya8282.github.com/RANS/」 というURLの(URL正規表現上の)順番は

% time rans --f http-url.regex --text 'http://sinya8282.github.com/RANS/'
1462290815058406142878645747899975197440717007135
rans --f ~/dev/works/RANS/test/http-url.regex --text 0.01s user 0.00s system 28% cpu 0.039 total

と計算できます。もちろん、逆計算も。

% time rans --f http-url.regex --value 1462290815058406142878645747899975197440717007135
http://sinya8282.github.com/RANS/
rans --f ~/dev/works/RANS/test/http-url.regex --value 0.52s user 0.00s system 82% cpu 0.636 total

http://sinya8282.github.com/RANS/」 は33Byte(文字)の情報ですが、順番を考えると20Byteの情報になります。正規表現圧縮の利点は圧縮率が「正規表現」のみに依存するところです。正規表現にマッチする文字列であれば、「長さ」に応じて全てが等しく圧縮されます。 (「圧縮」というより「正規化」という言葉のほうがしっくりくるかもしれません)

他の圧縮アルゴリズムでは全く圧縮できないような文字列も、RANSではできるかもしれません。 (辞書式圧縮や算術符号化とは全く異なる仕組みなので、比較は無理じゃないでしょうか? 既存圧縮法に疎いのでよくわかりません…)

追記: ファイル圧縮

記述し忘れてましたが、 ransから直接ファイルを圧縮する機能もあります。
rans –compress / –decompress オプションがそれです。デフォルトでは”.rans”な圧縮ファイルを作成します。
上記URL圧縮をやってみましょう。

% echo -n "http://sinya8282.github.com/RANS/" &gt; url.txt
% rans --f http-url.regex --compress url.txt
% ls -lh url.txt url.txt.rans
-rw-r--r-- 1 ryoma staff 33B Jun 4 21:40 url.txt
-rw-r--r-- 1 ryoma staff 20B Jun 4 21:40 url.txt.rans
% od url.txt.rans
0000000 021377 047542 131745 065460 062323 152423 017210 131061
0000020 154424 017250
0000024
% rm url.txt
% rans --f http-url.regex --decompress url.txt.rans
% cat url.txt
http://sinya8282.github.com/RANS/

その他

ちなみにSECCON ハッカソン in つくば では「正規表現とパスワード生成」 というプレゼンをしてきました。中身は、「RANSを使ったパスワード生成への応用。さらにそれをRANSのPythonラッパーを作ってDEMOしてみたよ」という感じです。

RANS(というか正規言語上のANS)は「めちゃくちゃ色んな応用が考えられそう」と一人妄想しているのですが、どうでしょうか。皆さんもアイディアがあればRANSを使って実践してみてください! (報告や疑問があればご気軽にどうぞ ;-)

SECCONハッカソンで正規言語の話をしてきた

つくばでの

エキサイティングな1日半が終了しました。記憶に新しいうちに記事に。

ハッカソンについて

「2日という短い時間制限」な状況でのプログラミング・イベント、時間制限がある状況でのプログラミングは嫌いなのですが、 先日公開したRANSの応用について考える良い機会と思い参加しました。声をかけてくれた実行委員 @takesako さんに感謝。

さて、僕は「正規言語とパスワード生成」というタイトルでハッカソンの期間で

  • URL(任意)と秘密正規表現(自分で選ぶ: 固定)からオリジナルなパスワードを自動でつくる仕組み
  • RANSの Python wrapper (using SWIG)

を作り、なんとか発表にこぎつけました。RANSについて次の記事あたりで紹介したいと思います。

RANS(C++) Python wrapper の作成には SWIG を使いました。とても便利なツールですぐ wrapper が動いたので、資料作りに時間をかけれたのが嬉しい。 プレゼン資料はSpeaker Deck に挙げておきました。

セキュリティばりばりな方からマジで非常に面白い着眼点・アイディアを得られたりしました。最初はネタ扱いでしたがかなり面白いかもしれません。考えてみる。

CTFについて

ハッカソンとCTFは別室で並列に行われていたので、終始感染していたわけではありませんでしたが、学生さんたちがもくもくと問題を解いている姿は<del>少し引きました</del>すごかったです。 結果はつくば勢の1,2フィニッシュと流石な感じでした。

最後に

SECCONに参加して嬉しかったことTOP3を列挙します

  1. @ucq 君が人間であることを確かめれた(「ボット」「概念」「情報思念体」と思っていました。割りとまじで)
  2. @super_rti 伯爵(まじ)に謁見できた
  3. ちぃちゃん.ぺろぺろ.jp正規表現.ぺろぺろ.jp が取得できた。これは @ym405nm さんの ぺろぺろ.jp というサービス。

@super_rti 伯爵は一見ネタキャラっぽいですが、未来の部屋(音声認識で荷電制御)Regexp::Assemble for PHP, sexyhook 等いろいろハイレベルなことをやってるスーパーハッカーでした。「//コメント至上主義」怖い。

ハッカソンで一緒に行動させて頂いた @suma90h, @ucq, @super_rti, @ym405nm, @takuho_kay (敬称略)。 皆さん非常に濃ゆくて面白いメンバーで夜の議論も大いに盛り上がりました。楽しかった。 #そして筑波の夜は更けていく

サイボウズ・ラボユースっていいよね!

この記事はサイボウズ・ラボユースの紹介記事です.

サイボウズ・ラボ 中谷さん(@shuyo)の記事「 サイボウズ・ラボユースって知ってる?」を引用する形で,ラボユース生視としての所感を基に書いてみました.

サイボウズ・ラボユースとは

サイボウズ・ラボユース

今後の研究開発の発展と世界に通用する日本の若手エンジニア育成のため、有望な中高生、大学生を集めた「サイ ボウズ・ラボユース」を設立することといたしました。

ラボに採択された学生さんは,スーパー技術者集団サイボウズ・ラボの支援を受けながら,自分の好きなプロジェクトを進めていきます. 近く ラボユース最終成果報告会 にて,僕を含む第一期メンバーの成果報告が行われます.

僕は「世界最速の正規表現JITエンジンの実装」というタイトルで,ユースでの一年間,開発してきた正規表現エンジンのお話をします. プロジェクトの成果物である正規表現エンジン Regen(レーゲン)は githubにて公開 しています.

ユースの中身

ユースに採択された学生は,サイボウズ・ラボで,つまりラボメンバーの近くで開発に勤しみます.

サイボウズ・ラボユースって知ってる?

サイボウズ・ラボユースで「何をやってもらう」か。 実は設問がすでに間違っている。ラボユースは「やってもらう」ところではなく、自分から「やりたいこと」をやるところ。 サイボウズ・ラボはなんというか放置プレイが得意な会社で、何も言わないと何も言われない面があったわけだが、ラボユースもその血を脈々と受け継いでいる。

基本的には,ユース生から議論を持ち込んで,ラボメンバー勢がそれに全力で応じるという感じです.そして,ユース生は議論を糧に開発を行います!

特に僕の場合は,サイボウズ・ラボ 光成さん(@herumi)にx86最適化周りでと〜ても多くのモノを叩きこんで貰いました. また,「正規表現」というテーマについても,数学や言語について深い知識を持つメンバーさん達と興味深い議論が絶えませんでし た(数学は共通言語ですね :-) ).

サイボウズ・ラボユースって知ってる?

それぞれが深い専門知識を持つ幅広いメンバーが集まっており、少し頭を悩ませるような問題でも一緒に考えればだいたい解決 への道が見えてくる。ブレストとかすれば、分野横断したいろいろなアイデアがきっと出てくる。若干手前味噌だがw

長い期間,ラボメンバーさん達と近い距離で(それこそ一緒にランチを取りながら),議論ができます.僕自身日々の議論から得たものは多く, ,それを学会発表(学生奨励賞受賞)という形にすることもできました.

口頭以外での議論や情報共有は,サイボウズLive (Web上のコミュニケーションツール)上で行われます.ここでは,プロジェクトを 横断したユース生同士の議論も盛り上がりました.

宣伝

この記事では僕のプロジェクト「世界最速の正規表現JITエンジンの実装」について内容には触れませんでした. 先にも述べたとおり,3/26(月)秋葉原での ラボユース最終成果報告会 にて詳細な報告が行われるので,是非聞きに来て下さい. プロジェクトはザラッと

  • 桐井祐樹「Ruby・Raccを使用した言語処理系の日本語プログラミング化」
  • 新屋良磨「世界最速の正規表現JITエンジンの実装」@sinya8282
  • 林 拓人「型システムの拡張と型推論」
  • 鈴木勇介「世界で一番仕様に忠実なJavaScript処理系の作成」
  • 粟本真一「現役高校生の考えるクラウドOSの設計と実装」

という感じになっています. (「世界」を冠したタイトルが2つもある! :-) )

どれも面白く,志の高いプロジェクトです.

個人的には鈴木くんの発表が楽しみで仕方がない.彼は凄い(笑),もちろんプロジェクトも.

二期生の募集も

また,成果報告会ではラボユース二期生の募集説明会も行われます.やりたいテーマを持った学生さんは,参加の一択ですね. 改めて見てみると,第一期メンバーは比較的低レイヤーなプロジェクトが多い!第二期はどんなプロジェクトが揃うんでしょうか.

さぁ,この記事を読んだ学生さんは今すぐ参加登録 をするんだ!

正規表現でSATを(完全に)解こう!

SATを解きましょう

Augurio Buonanno! 正規表現でやってみたシリーズ第一弾(?)です. SATを解きましょう. → 充足可能性問題

変数の組み合わせ to 正規表現

まず正規表現で問題を扱うには, 対象を文字列にエンコードしなおす必要があります.

X1,X2,…Xnなn個数の変数を真を1, 偽を0と解釈して並べると

/[01]{n}/ #これは(0|1),「0または1」のn回繰り返し

で変数の組み合わせを表現できますね. つまりn文字の2進列に対して

  • n番目の文字が1<->Xnは真
  • n番目の文字が0<->Xnは偽

とするわけです. よしよし, 変数の組み合わせは攻略しました. あとは論理式を正規表現に直せれば良いわけです.

論理式 to 正規表現

Wikipediaにある具体例を標的にしましょう.

まず第一節目について考えてみます. X1かX2が真な節. 正規表現でも or, ∨ (= |) が使えるので

/(1[01]|[01]1)/

と書くことができます. そうですよね, この正規表現にマッチする文字列は

  • 11
  • 10
  • 01

ですね. この節だけ限定して考えればこの文字列は論理式を満たす変数の組み合わせ「X1かX2が真」です!!

問題は and, ∧ です. しかし and 演算(どちらの正規表現にもマッチする)は正規表現の能力を超えていないので認めちゃいましょう. そうすると先の論理式全体は, 正規表現

/(1[01]|[01]1)&(1[01]|[01]0)&(0[01]|[01]0)/

と記述できます. ね, 簡単でしょ?

この「正規表現にマッチする全文字列」は, 先の「論理式を充足する変数の組み合わせ」に一対一対応します.

実質, 変数の組み合わせを文字列にエンコードした時点で仕事は終わっちゃいました ;-)

正規表現 to 受理文字列

理屈だけ納得してもつまらないですよね. 「どこが”完全”に解いてるの?」「普通の正規表現には’&’無いじゃん!」みたいな.

ということで宣伝にもなっちゃいますが, 僕の作ってる正規表現エンジン Regen ではなんと

  • 正規表現にマッチするテキストの生成
  • &, !(not), &&(xor) 演算

に対応しています.

Regen 内の正規表現ツール recon で上述の正規表現(論理式)にマッチする文字列を全列挙してみましょう.

SHINYA% ./recon -E -t '(1[01]|[01]1)&(1[01]|[01]0)&(0[01]|[01]0)'
10
SHINYA%

10はX1が真, X2が偽なので上述の論理式を充足しますね! 充足不可能な式は?

当然なにも出力しません.

SHINYA% ./recon -E -t '(1[01]|[01]1)&(0[01]|[01]1)&(1[01]|[01]0)&(0[01]|[01]0)'
SHINYA%

生成するテキストは正規表現が受理する全文字列(後述)なので, 充足する変数の組み合わせを全列挙してくれます.

SHINYA% ./recon -E -t '(1[01]|[01]1)'
01
10
11
SHINYA%

正規表現, 楽しいですね :-)

補足

正規表現でのand

形式言語的な意味での拡張正規表現(Extended Regular Expression)は, 正規表現に’&'(積集合演算)と’!'(否定演算)が使えます.この拡張正規表現は正規表現の能力は超えません(記述の複雑さは変わりますが). 否定の正規表現の話題はshibuya.pmでも発表しました. 否定とorさえあればandもできますね.

Regenについて

この記事で紹介したツールは Regen をインストールすると使えます(ちなみに「レーゲン」と読みます. ドイツ語カッコいい.). githubから取ってきて使ってやって下さい.まだ色々実装が足りないので資料など皆無(コマンドのヘルプすら!)ですが,

% git clone git@github.com:sinya8282/Regen.git
% cd Regen/src
% make recon REGEN_ENABLE_PARALLEL=no REGEN_ENABLE_XBYAK=no
% ./recon -h
USAGE: regen [OPTIONS]* PATTERN
Regex selection and interpretation:
  -E   PATTERN is an extended regular expression(&,!,&&,||,,,)
  -f   obtain PATTERN from FILE
Output control:
  -t   generate acceptable strings
  -d   generate DFA graph (Dot language)
  -m   minimizing DFA
%

という風に, 今回紹介した生成系は使え(ま|るはずで)す.

(‘-E’ オプションは拡張演算子on, ‘-t’で受理文字列のモード)

他の機能やオプションも説明したいですが, それは次の機会で…(手抜き)

全文字列の列挙?

説明中では「正規表現にマッチする全文字列を列挙」と書きましたが, これは嘘です.例えば

/a*/

みたいなKleene閉包が使われる正規表現は

"", "a", "aa", "aaa",...

と無限の文字列にマッチしうるので, 全列挙は不可能です.

じゃあ, どうするか? (無限はむりでも数を限定すればなんとかなりそうです.)

この辺りは面白い話なので是非次の記事辺りで説明したいと思います!

後方参照でSATを解く

ここでは完全にpureな正規表現でもSATを解けることを紹介しました.調べてみるとPerlなどでお馴染みの後方参照を使って解く方法も解説されてました. まめめも: 後方参照のある正規表現の能力(ただし, 後方参照使うと非正規表現ですよ!)正規表現でSATを解く, 思いついた時にはいかにもありそうなネタと思っていましたが, 検索した範囲で見当たらなかったので記事にしました.正規表現, 楽しいですね :-)

追記

会場で @shinh さんに「Perlなら先読み(?=)あるから/R1&R2/みたいな正規表現は/(?=R1)R2/でいけるよね.」というアドバイスをお受けしました. なるほど.
今回のSATの例も先読みを使えば「SATを充足する変数組み合わせを受理する正規表現」は記述できます.
ちなみに Perlな正規表現の受理文字列生成とかできる module とかあるんでしょうか? (全文字列を生成して通す, というアプローチでなく)
Perlでの先読みは(実装は)オートマトン的ではなく, 再帰を使って実装されています(と思う). ゆえに「先読みってオートマトン理論的にどうなの?」というお話もありますが, このあたりも非常に面白い話なので次回の記事あたりでまとめたいと思います.
 
Better Tag Cloud