カテゴリー : 未分類

正規言語で修士号を取得しました.修論を公開します.

 

2013年3月に東京工業大学大学院情報理工学研究科数理・計算科学専攻の修士過程を卒業しました.

現在は同専攻で博士課程学生としてお勉強&研究に打ち込んでいます(あ,所属研究室が佐々研から首藤研に変わりました).

 

修論を

せっかくなので修士論文を公開します.

cover

正規言語上の Abstract Numeration System の 文字列圧縮への応用(PDF)

 修士論文のタイトルは

「正規言語上の Abstract Numeration System の文字列圧縮への応用」

というものです.タイトルは厳めしいですが,内容は非常にシンプルです. この論文では正規言語の数え上げ理論,及びその計算量や圧縮率(+いくつかの応用策)について論じています.

簡単に言うと以前ブログで扱ったRANSの理論の話です(正規表現を使ってデータ圧縮等するツールを作りました)

 

目次

  • 図目次
  • 図や記号に関する注意
  • 1章 はじめに
  • 第1部 準備
    • 2章 正規言語とオートマトン
      • 2.1 形式的定義
      • 2.2 決定性,無曖昧性,非決定性
      • 2.3オートマトンの行列表現
    • 3章 Combinatorial Complexity
      • 3.1 数え上げ関数
      • 3.2 数え上げ関数に関するShurの定理
    • 4章 Abstract Numeration System
      • 4.1 形式的定義
      • 4.2 $n$数法との関係
      • 4.3 平方数に関するEilenbergの定理
  • 第2部2 正規言語上のAbstract Numeration Systemの文字列圧縮への応用
    • 5章 DFAを用いたANSのアルゴリズム
      • 5.1 valS の計算
      • 5.2 repS の計算
      • 5.3 計算量
    • 6章 ANSによる文字列圧縮
      • 6.1 ANS間の基数変換
      • 6.2 圧縮率
    • 7章 応用
      • 7.1 URIの圧縮
      • 7.2 符号
      • 7.3 分割基数変換
    • 8章 議論
      • 8.1 文脈自由言語への拡張の困難さ
      • 8.2 エントロピーベース圧縮法との対比
      • 8.3 圧縮に適した正規言語
    • 9章 まとめ
  • 謝辞
  • 付 録
    • RFC 3986 定義のURI文法
      • 拡張BNFによる定義
      • 拡張正規表現による定義
    • RFC 3986 定義のURI文法
      • 正規言語の同定問題の困難性
      • 順序の問題
  • 索引
  • 参考文献

 

実は

一般の方(正規表現とかオートマトンとか良く知らない人)向けに,解説を付加したり,お話風にしたり,構成を変更したバージョンも作成して公開しようとしていたのですが,色々あって見送りという形になりました.いずれ書きたいものです(書かないフラグ).

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

こんにちは。 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)”という曲があったりします。 もっと探してみると、色々出てくるのでしょうがとりあえずここまで。

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

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

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

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

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

サイボウズ・ラボユース

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

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

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

ユースの中身

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

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

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

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

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

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

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

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

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

宣伝

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

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

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

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

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

二期生の募集も

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

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

サイボウズ・ラボユースに採択されました.

【サイボウズ・ラボユース】第一期メンバー募集〆切は来週の月曜日4/18です!応募手順も簡単にしましたのでぜひtryしてみてください。http://labs.cybozu.co.jp/recruit/youth.html
@takesako
TAKESAKO

採択されました:-o

内容は 正規表現エンジンの実装,高速化 ということで.

もちろん, プロジェクトの成果は公開していく方針です. まだユースでの開発は始まっていませんが, 現段階での成果物は regen という名前でgooglecodeで公開しています.

  • Regen/gengrep
  • Regen は正規表現コンパイラ,ジェネレータです. 現状では正規表現からC言語やDOT言語で記述されたソースコードを出力することができます.
  • Regen で生成したコードを基盤とした GNU grep ライクな テキストファイル検索が使用可能です. gengrep.py というスクリプトが grep フロントエンドです.
  • Regen はUTF-8なマルチバイト文字列の正規表現検索に対応しています.

とりあえず

  • うれしい! うれしい!
  • 積極的に行動しプログラマーとして成長していきたい
  • 成果を出してユースに貢献したい
  • とりあえず C++ 勉強しなきゃ <- ぇ
  •  

     

    経緯

    eXtreme HAGO LT という沖縄でのイベントで, 僕の卒論成果としての正規表現エンジン/grepの発表(自慢)をしました. -> (ust : 25分ぐらいから僕の発表です. 絶妙のタイミングで僕のBOSSが途中入場してきたりして盛り上がりましたw)

    発表資料を公開 していたら @takesako さんが興味を持ってくれ, 「そのネタでラボユースに応募してみては?」 と. 4月から東京に出てきた僕にとっては最高の誘いだったので応募した感じです. (イベントには参加するものですね ;-)

     

     

    これから

    今現在実装されている正規表現エンジン/grep について

    • 機能拡張
    • 性能向上
    • どのようなケースで役に立つものを作るか?

    といった事を 真剣 に考えて, 開発を行っていきます. (もれなく @herumi さんの熱血指導がついてきてくれるそうです.

     

    開発以外でも

    サイボウズはスーパーハッカーの巣窟 です. そんなメンバーさん達とtechな会話ができると思うと胸が熱くなります. 仕事を邪魔しない程度に絡んでいけたらなぁ, と思います.

    話のネタも考えておかなくちゃ:-p

     

    おまけ

    サイボウズのキャラクター, ボウズマンとの記念撮影.

    東工大(院)合格した!

    夏休みは

    大学院試験や初の学会発表など, 非常に濃ゆい夏休みでした(休みじゃない?).

    タイトル通り, 大学院合格しました!! 東京工業大学です! 来年から東京生活です!

    ってことで

    院試と学会発表という2大タスクが終了したので, SICP勉強会や各種勉強会も力入れていきます.
    ブログの更新もね :-p

     
    Better Tag Cloud