カテゴリー : Regex

DLT’14に論文採択

単著論文が国際学会 DLT’14 (18th International Conference on Developments in Language Theory) に short paper として採択されました.論文は僕のページにて公開しています.
DLTは1993年に A. Salomaaと G. Rozenberg (2人ともヨーロッパ理論計算機科学協会元会長!) が発起人となり始められた形式言語・オートマトン理論のガチ專門会議です(参考)。理論色が強い学会という印象を持っています.

論文内容

Graph Spectral Properties of Deterministic Finite Automata“という,かなり一般的なタイトルの論文となっています.ある正規言語Lを認識するDFA達は無限に存在するのですが,そのDFA達の隣接行列(の固有値)構造に着目した時に,どういった秩序があるのかということを探った研究です.DFAに関して,その隣接行列(の固有値)構造について考察するというのは,いくつか似てる研究はあるものの,新しいと考えこのような一般的なタイトルをつけました.

ここでいうDFAの隣接行列とは,DFAから文字を忘れて単なる多重有向グラフとして見た時の隣接行列のことです.例えば
fib

というDFAに対応する隣接行列は[[1, 1],[1,0]]となります.任意のDFAから隣接行列は一意に定まりますが,隣接行列からそれに対応するDFAは一意に定まりません.隣接行列はDFAから「文字の情報を削ぎ落した構造」なのです.

最小定理

この論文ではDFAと隣接行列の関係に関していくつかの性質を示しています.その中で最も重要なものとして最小定理

DFAが最小 ⇔ DFAの隣接行列の階数と退化次数が共に最小

という最小DFAの線形代数的必要十分条件があります.階数(rank)は線形写像の像空間の次元,退化次数nullity)は線形写像の核(kernel)の次元ですね.ここでいう最小とは「同じ言語を認識するDFAの中で最小」ということを意味しています.最小DFAの存在や構成法は情報科学科の学生さんであれば学部で習う基礎事実です.最小DFAの必要十分条件というfundamentalな内容を「文字の情報を削ぎ落した構造」である隣接行列から導けたということで,僕的にとても気に入っている成果です.

⇐ の方向は階数・退化次数の定理より自明ですが,⇒の方向は自明ではありません.なぜなら,「状態数が小さい ⇒ 階数と退化次数が共に小さい」は一般的に成り立たないからです.次の図がそれを示しています.

Screen Shot 2014-05-03 at 8.08.02 PM

A1,B1,C1はそれぞれ同じ正規言語を認識するDFAで,M(A1),M(B1),M(C1)がそれぞれの隣接行列です.なお,A1は最小DFAとなっています.よく見るとB1はC1よりも状態数が少ないにも関わらず階数はC1の方が小さいことが分かります.同様の事実が退化次数に関しても言えます.A1においては定理に矛盾していない,つまり階数と退化次数がB1やC1に比べ小さいことに注意して下さい.

スペクトラルグラフ理論

この定理の証明には「スペクトラルグラフ理論」というグラフの隣接行列の固有値構造を調べる理論の基礎的な道具:Equitable partition が使われています.スペクトラルグラフ理論は一年前から一年かけて僕が主催して後輩と書籍を輪講をしていたのですが,輪講開始から半年たって Equitable partition がDFAに使えることに気づきました.実は Equitable partition を使わないバージョンの上記定理の証明は輪講を始める前から思いついてたのですが,Equitable partition のおかげで証明を大分ゴルフすることができたのです :-D  とはいえ,スペクトラルグラフ理論の輪講を決定したのは「DFAの解析に使える道具があるのでは?」と思ったから始めたので,当時の僕GJ!

証明は,スペクトラルグラフ理論の道具である Equitable partition と,オートマトン理論の道具である Nerode partitionの2つの登場人物を出会わせるものです.準備や初等的な事実・補題を除くと実質1ページぐらいのとてもコンパクト証明です.異なる2つの理論で使われていた2種類のpartitionが強く関連しているのは興味深いものです.証明が読みたい方は論文を参照して下さい

正規言語による文字列圧縮とのつながり

そもそもこの研究は「正規言語による文字列圧縮の計算量が低いような正規言語のクラス」に興味を持ったところから始まりました.正規言語による圧縮については,過去のエントリ

をご覧下さい.

研究の流れとしては

  1. 正規言語による文字列圧縮はDFAの隣接行列の冪乗が計算大変!
  2. 階数が1の行列は効率よく冪乗が計算できる超単純な構造を持っている.
  3. DFAの階数が1であるような正規言語のクラス:rank-one langugaes を解析しよう!
  4. でも,DFAの階数ってどれが最小なんだろう? 同じ言語を認識するDFAって無限にあるんだけど…
  5. 最小DFAの階数が最小っぽいよな… 常識的に考えて…
  6. 示そう! あ,退化次数も同時に最小になるっぽい!

という流れで上記の定理にいきつきました.線形代数の初等的事実ですが,階数が1の行列はその冪乗(の要素)がO(1)で計算できます(参考: “On rank one matrices and invariant subspaces” ).

発展

実は,この論文では rank-one languages のDFAにおける canoncial form を示しただけで,その性質を十分に解明することができませんでした.正直言うとわからないことだらけです.2つの正規言語が与えられた時,それらから新しい正規言語を作り出す様な演算は正規言語においてはたくさんあります.例えば和集合や積集合,shuffleや連接などなど.このような正規言語の演算とDFAの隣接行列(の固有値)構造がどのように対応するのかということを調べたかったのですが,これがまた難しいのです.むしろDFAだと無理なのでは?という感じです(投げやり).

論文では「ここがわかっていない〜」「こうすれば上手くいくはずなんだけど難しいんだ〜」ということを正直に書き連ねています.発展途中の研究ということで, short paper という結果は納得しています.が,もうちょっと頑張って full paper で通したかったなぁ…

論文採択について

学部〜修士では正規表現マッチングの並列化やコード生成,修士〜博士では正規言語による文字列圧縮,そして今はDFAの固有値構造の解析という流れを見ると,僕自身の興味が応用から基礎理論に向かっていることが分かります.これからは理論バリバリな成果をガンガン出していきたい所存ですが,その意味でDLTという理論色の強い会議にこのような成果で採択されたのは嬉しいです.論文に適切なコメントを着けてくれた @ranha 君,研究生活を全面的に支援してくださった首藤先生,アイディア段階の時に議論に付き合ってくれた @kinaba さんや京大・京産大の研究者方々に感謝を.

応用畑で育った人間として,理論の世界に身を投げるのはなかなか勇気のいる行動でした.実際この一年間は成果もろくに出さずほとんど輪講や論文読みのいわゆる「基礎学習」に時間を費やしてました.分野を変えるまではいきませんが,一般に研究者としての方針を変えるのは時間がかかると思います.今回の結果がDLTに reject されていたら「やっぱり応用の世界で生きていこうかな…」と迷ってた可能性が高いです.怖い.怖くない?怖い!

とはいえこのような結果になったわけですし,いろんな分野の道具をバリバリ使いこなして新たな正規言語の定理をガンガン生み出せるような人間になるために,これからも頑張って行きたい所存です.

URLにマッチする真の正規表現 – RFC3986定義のURIの話

RFC3986定義の厳密なURIの正規表現 (file)

[a-z][-+.0-9a-z]*:(//(([-.0-9_a-z~]|%[0-9a-f][0-9a-f]|[!$&-,:;=])*@)?(\[(([0-9a-f]{1,4}:){6}([0-9a-f]{1,4}:[0-9a-f]{1,4}|(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5]))|::([0-9a-f]{1,4}:){5}([0-9a-f]{1,4}:[0-9a-f]{1,4}|(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5]))|([0-9a-f]{1,4})?::([0-9a-f]{1,4}:){4}([0-9a-f]{1,4}:[0-9a-f]{1,4}|(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5]))|(([0-9a-f]{1,4}:)?[0-9a-f]{1,4})?::([0-9a-f]{1,4}:){3}([0-9a-f]{1,4}:[0-9a-f]{1,4}|(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5]))|(([0-9a-f]{1,4}:){0,2}[0-9a-f]{1,4})?::([0-9a-f]{1,4}:){2}([0-9a-f]{1,4}:[0-9a-f]{1,4}|(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5]))|(([0-9a-f]{1,4}:){0,3}[0-9a-f]{1,4})?::[0-9a-f]{1,4}:([0-9a-f]{1,4}:[0-9a-f]{1,4}|(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5]))|(([0-9a-f]{1,4}:){0,4}[0-9a-f]{1,4})?::([0-9a-f]{1,4}:[0-9a-f]{1,4}|(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5]))|(([0-9a-f]{1,4}:){0,5}[0-9a-f]{1,4})?::[0-9a-f]{1,4}|(([0-9a-f]{1,4}:){0,6}[0-9a-f]{1,4})?::|v[0-9a-f]+\.[!$&-.0-;=_a-z~]+)\]|(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])|([-.0-9_a-z~]|%[0-9a-f][0-9a-f]|[!$&-,;=])*)(:\d*)?(/([-.0-9_a-z~]|%[0-9a-f][0-9a-f]|[!$&-,:;=@])*)*|/(([-.0-9_a-z~]|%[0-9a-f][0-9a-f]|[!$&-,:;=@])+(/([-.0-9_a-z~]|%[0-9a-f][0-9a-f]|[!$&-,:;=@])*)*)?|([-.0-9_a-z~]|%[0-9a-f][0-9a-f]|[!$&-,:;=@])+(/([-.0-9_a-z~]|%[0-9a-f][0-9a-f]|[!$&-,:;=@])*)*)?(\?([-.0-9_a-z~]|%[0-9a-f][0-9a-f]|[!$&-,/:;=?@])*)?(#([-.0-9_a-z~]|%[0-9a-f][0-9a-f]|[!$&-,/:;=?@])*)?

*大文字小文字の区別をしてません.エンジン側で大文字小文字を無視するオプションを付けて解釈してください.

RFC3986定義の厳密なHTTP URIの正規表現

schemeをhttpまたはhttpsに固定すれば良いだけなので,

https?:(//(([-.0-9_a-z~]|%[0-9a-f][0-9a-f]|[!$&-,:;=])*@)?(\[(([0-9a-f]{1,4}:){6}([0-9a-f]{1,4}:[0-9a-f]{1,4}|(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5]))|::([0-9a-f]{1,4}:){5}([0-9a-f]{1,4}:[0-9a-f]{1,4}|(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5]))|([0-9a-f]{1,4})?::([0-9a-f]{1,4}:){4}([0-9a-f]{1,4}:[0-9a-f]{1,4}|(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5]))|(([0-9a-f]{1,4}:)?[0-9a-f]{1,4})?::([0-9a-f]{1,4}:){3}([0-9a-f]{1,4}:[0-9a-f]{1,4}|(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5]))|(([0-9a-f]{1,4}:){0,2}[0-9a-f]{1,4})?::([0-9a-f]{1,4}:){2}([0-9a-f]{1,4}:[0-9a-f]{1,4}|(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5]))|(([0-9a-f]{1,4}:){0,3}[0-9a-f]{1,4})?::[0-9a-f]{1,4}:([0-9a-f]{1,4}:[0-9a-f]{1,4}|(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5]))|(([0-9a-f]{1,4}:){0,4}[0-9a-f]{1,4})?::([0-9a-f]{1,4}:[0-9a-f]{1,4}|(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5]))|(([0-9a-f]{1,4}:){0,5}[0-9a-f]{1,4})?::[0-9a-f]{1,4}|(([0-9a-f]{1,4}:){0,6}[0-9a-f]{1,4})?::|v[0-9a-f]+\.[!$&-.0-;=_a-z~]+)\]|(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])|([-.0-9_a-z~]|%[0-9a-f][0-9a-f]|[!$&-,;=])*)(:\d*)?(/([-.0-9_a-z~]|%[0-9a-f][0-9a-f]|[!$&-,:;=@])*)*|/(([-.0-9_a-z~]|%[0-9a-f][0-9a-f]|[!$&-,:;=@])+(/([-.0-9_a-z~]|%[0-9a-f][0-9a-f]|[!$&-,:;=@])*)*)?|([-.0-9_a-z~]|%[0-9a-f][0-9a-f]|[!$&-,:;=@])+(/([-.0-9_a-z~]|%[0-9a-f][0-9a-f]|[!$&-,:;=@])*)*)?(\?([-.0-9_a-z~]|%[0-9a-f][0-9a-f]|[!$&-,/:;=?@])*)?(#([-.0-9_a-z~]|%[0-9a-f][0-9a-f]|[!$&-,/:;=?@])*)?

*こちらも同様に大文字小文字の違いを無視

解説

URIの厳密な文法は,

RFC3986 – Uniform Resource Identifier (URI): Generic Syntax

で定義されています.なお,RFCの定義ではURIでは大文字小文字を区別していません.

文法はRFC仕様のABNF(拡張文脈自由文法)という記法で定義されています.

理論的にはABNFは文脈自由文法をフルで記述できる能力を持ちますが,

URIの定義に関して言えば実は正規表現(正規文法)に変換可能です.

 

ABNFから正規表現への変換系は,Tanakaさんの abnf というツールを使いました :-)

 

歴史小ネタ

URIの文法は1998年にRFC2396で定義されたのが最初です.

現在のURIはいわばバージョン2で,2005年のRFC3986で定義が大幅に変更しました.

 

では,初期の文法(RFC2396)に比べて,URIの文法はどの程度複雑になっているのでしょうか?

意味的な複雑さを比べるのは一般に難しいですが,正規表現的に複雑さを評価するのは簡単です.

「(最小)DFAの状態数で比べる」という方法があります.

 

バージョン1のRFC2396によるURIの文法(正規表現)は,以下のDFAが対応します.

uri.rfc2396

バージョン2のRFC3986によるURIの文法(正規表現)は,以下のDFAが対応します.

 

なんと,7年の期間を経たアップデートによって,URIの文法は10倍以上(DFAの状態数が13→180)も複雑になってしまったのです!

 

宣伝

以上の話は,ソフトウェアデザイン5月号の特集「正規表現をマスターしていますか?」に起稿した記事でも扱っています.

 興味がある人は是非読んでみてくださいね!
Software Design 5月号に10ページほど記事を書きました.「正規表現をマスターしていますか?」という特集の最終章(コアな章)です.是非読んでみて下さい.発売(4/18)が楽しみです.http://t.co/beVFMUVFUk#gihyojp #fb
@sinya8282
Ryoma Sin'ya

 

追記: ソフトウェアデザインの原稿を公開

処理速度にも影響する!? 正規表現エンジンの種類と仕組み

 

また,この記事で使っているDFA図はRANSというツールで作成したものです.

基本的な使い方はチュートリアルページにまとまっているので,興味が有る方は触ってみて下さい.

プログラミング言語Grassは正規表現と相性が良い – RANSによるプログラム列挙

僕のポスター「正規言語の列挙:プログラミングへの応用」はこんな感じです.テックちゃんが右上に居るのがポイント!(ぉぃ http://t.co/CNgcCsxo9t
@sinya8282
Ryoma Sin'ya

PPL2013でポスター発表をしてました.

失礼ながらPPLは規模の小さい学会だと思ってたので,実際参加してみて各方面のガチ勢が多かったのが嬉しびっくりでした.

 

さて

PPLでのポスターでも話したネタですが,プログラミング「Grass」の話をしたいと思います.もちろん正規表現ぽい話.

Grassは”W”,”w”,”v”の三文字のみでプログラムを書けるチューリング完全な言語です.イカれてますよね :-)

さて,この言語Grassですが,文法はもちろんきちんと定義されていて

  • app ::= W+ w+
  • abs ::= w+app*
  • prog ::= abs | prog v abs | prog v app*
といったシンプルな文法となっています.

正規表現!!

この文法はBNFで記述されていますが,実は線形文法で書けます.つまり「正規表現で書ける」.
w([vw]*(W+w)*)*
が構文的に正しいGrassのプログラムを表現する正規表現です.シンプルですね.
プログラムの列挙
さて,RANSと言う僕が開発しているソフトウェアがあります.これは正規表現と数を食わせて「長さ–辞書順でその数に対応する受理文字列を返す」というものです.その逆もできます.
凄い点は「文字列から数は線形時間で,数から文字列は準線形時間で計算できる」
さて,プログラミング言語Grassの構文は正規表現で書けます.では,プログラムと数の対応をいくつか列挙してみましょう.

Hello, world

% cat hello.www
wwvwwwWWWwwWwwWWWWwvwWWwwwWwwvwWwwwWwwvwWWwWWWWWwvwWWWwwwwWWWWwWWWWw
WWWWWWwWWWWWWWwWWWWWWWwWWWWWWWWwWwwwwwwwwvwWWWwwwwwWWWWWwWWWWWwWWWWW
WWwWWWWWWWWwWWWWWWWWWwWwwwwwwwvwWWWWwwwwwwWWWWWWwWWWWWWwWWWWWWWwWWWW
WWWWWwWWWWWWWWWwWwwwwwwwvwWWWWWwwwwwwwWWWWWWWwWWWWWWWWwWWWWWWWWwWWWW
WWWWWWwWWWWWWWWWWwWwwwwwwwvwWWWWWWWwwwwwwwwWWWWWWWWwWWWWWWWWWwWWWWWW
WWWwWWWWWWWWWWWwWwwwwwwvwWWWWWWWWwwwwwwwwwWWWWWWWWwWWWWWWWWWwWWWWWWW
WWWWwWWWWWWWWWWWwWWWWWWWWWWWWWwWwwwwwwwvwWWWWWWWWwwwwwwwwwwWWWWWWWWW
wWWWWWWWWWWwWWWWWWWWWWWwWWWWWWWWWWWWWwWwwwwwwvwWWWWWWWWWWwwwwwwwwwww
WWWWWWWWWWwWWWWWWWWWWWwWWWWWWWWWWWWWwWwwwwwvwWWWWWWWWWWwwwwwwwwwwwwW
WWWWWWWWWWWwWWWWWWWWWWWWWwWWWWWWWWWWWWWWwWWWWWWWWWWWWWWwWWWWWWWWWWWW
WWWWwWwwwwwwwvwWWWWWWWWWWwwwwwwwwwwwwwwwwwWwwwwwwwwwwwwwwwwwwwWWWwww
wwwwwwwwwwwwwwwwWwwWWWWWWWWWWWWWWWWWWWWwvwWWwwwwWWWwwwwwwwwwwWWWWwww
wwwwwwwWWWWWwwwwwwwwwwwwwWWWWWWwwwwwwwWWWWWWWwwwwwwwwwwwWWWWWWWWwwww
wwwwwwwwwwwwwwwwwwvwWWWWWWWWWWWWWWWWwwwwwwwWwwvwWWWWwwwwwwwWWWWWwwwW
WWWWWwwwwwwwWWWWWWWwwwwwwwwWWWWWWWWwwwwwwwwwwwwwwWWWWWWWWWwwwwwwwwww
wwwwvwWWwWWWWWw
これは「Hello, world」を出力するGrassプログラムです(こちらから拝借しました).イカれてますよね.
このプログラムはGrassの文法的に「何番目」のプログラムなのでしょうか?RANSがあればお気軽に計算出来ます.
% cat hello.www | rans 'w([vw]*(W+w)*)*' --tovalue
16276174481634706127730787006880531370466380062973401969614529593658
83958803429956101907280299748822841594957446604850712567590269550047
04442396791176156604038955035748328503682524926066804754823248092598
88431440137005387911828231622152001940020161961290610781750518034051
89101265159339318336722855919281300746470264479856011884839769266736
50505379491629371259037681514934225197925358244649970308443675866436
6464026061342507810037583

などという10進数400桁以上の巨大な数が出てきます.ちなみにRANSは凄いので0.1秒程度でこの数が求まります.

百億番目のGrassプログラム

では逆に,「キリの良い数」に対応するプログラムを生成してみましょう.
「百億番目のGrassプログラム」は何か?簡単です.
% echo '10000000000' | rans 'w([vw]*(W+w)*)*'
wwWwvWWwwwwvwvwvWwvwWwwvv
さて,これは何を出力するプログラムでしょうか?実は
% echo '10000000000' | rans 'w([vw]*(W+w)*)*' > hoge.www
% ./yagi.rb hoge.www
w
なんと!「w」を!出力するプログラムなんです!
「百億番目のプログラムがwを出力する」なんて,Grass凄い.どこまで草を生やすんだ.
(yagi.rbはrubyによるGrass処理系実装です.まめめもさんから拝借しました.)

ちなみに

PPLではGrassの開発者である上野先生が参加されていて,この記事に相当する話をしたら.
え,文法は正規なんですねwww これは面白いwww
などという予想外の反応をされました.「文法が正規なのは意図してなかったのかよ」というオチです.面白いですね.
チューリング完全なプログラミング言語で,文法が正規言語のクラスなモノなんて恐らく他にあまり無い?と思うので,Grassは正規表現と相性が良いと言ってOKでしょう(ぇ

RANS使いましょう

このように,RANSを使えば色々なことができます.今回はGrassという面白いネタを扱いました.
ソースコードも公開していますので,皆さんも是非RANSを使ってみて下さい.

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

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 (敬称略)。 皆さん非常に濃ゆくて面白いメンバーで夜の議論も大いに盛り上がりました。楽しかった。 #そして筑波の夜は更けていく

 
Better Tag Cloud