開発合宿でのClojureを使ったBWT(Burrows-Wheeler Transform)の実装
先週末に千葉県銚子近くの温泉宿で行われた2泊3日開発合宿に参加してきた．参加者はiNut,syou6162,twittoru,wakuteka,y_benjoで，この合宿は今年で3回目になる．
やったコト
今回の開発合宿では，データ圧縮や全文検索などに用いられるBurrows-Wheeler Transform（以下BWT）をテーマにして，最近勉強しているプログラミング言語のClojureで実装してみることにした．
索引を使用した全文検索において特に有名なBWTだが，自分の研究分野であるBioinformaticsにおいても所謂「short read alignment」のアルゴリズムとして広く使われている技術である．日頃からこのアルゴリズムを使ったソフトウェアと接する機会が多く，一度自分で実装してみたいという思いが前々からあったので，今回フルスクラッチで書いてみることにした．今の自分のアルゴリズムの知識では実装しきれないだろうということは重々承知の上だった．しかしながら，折角の機会なのだから一歩でも踏み出しておきたい，開発合宿の短期間でどこまで出来るか試してみたい，という気持ちがあり，開発合宿直前になって急遽テーマを決めたという経緯がある．
プログラミング言語としてClojureを選んだ理由は，まあこのblogの過去記事を見れば明らかだろう．やっとのことで少しはまとまったスクリプトを書けるようになってきたので，この辺りで一つ大きなプログラムを作ってみたいと思っていたところだった．ただ，アルゴリズムの実装の面での不安がかなり強かったので，プログラミング言語の方はせめて書きなれたRubyを選択すべきといったあたりで結構悩んだ．最終的にはClojureで使っても大丈夫だろうと判断したのは，参加者にClojureが出来る人(syou6162)が居たからだった．
ソースコード
https://github.com/TrainingCamp2012/BWT-Clojure
この記事及びgithubのソースコードの実装には多分に誤りが含まれている恐れがあるので，決して参考にしないよう宜しくお願いします．
主に書いていた処理部分：https://github.com/TrainingCamp2012/BWT-Clojure/blob/master/src/BWT_Clojure/bwt.clj
処理部分は実質40行くらいしか書いていないが，改めて自分で見てみるとやはりClojureは短く簡潔に書けるのだと実感する（大したことやってないというのもあるが...）．syou6162に関数はもっと小さく分けてテスト書いたほうがいいと言われたので，今度から気をつけよう．
評価
先に結論から書いてしまうと，今回の開発では実用に耐えうるような実装が出来なかった．具体的に言えば，まずBWTアルゴリズムの実装方法が非常に効率の悪いもので，数万文字くらいの英文の索引を作るのに手元のマシンのメモリ（3GBくらい）では足りないような状態だった．それに索引から検索クエリに一致した箇所を持ってくるスクリプトもかなりプリミティブであり，一般的にBWTと合わせて使われるFM-IndexやCSAを実装するまでには至らなかった．といったように，今回の開発ではBWTのアルゴリズムを素人なりになぞっただけとなってしまい，結果として残ったのは残念なスクリプト片だけという感じになってしまった．
ただ，これを書くと言い訳がましくなるので良くないのだが，当初定めていた目標はきちんと超えることが出来たので個人的に満足している側面もある．効率が悪いにせよ，限られた時間内で曲がりなりにもBWTの体裁を取って全文検索のようなものが出来上がったのは非常に満足している．プログラムの面においても，今回はじめてClojureでテストを書きながら実装し，ClojureのビルドツールであるLeiningenを使ったコンパイルなどClojure開発周辺の知識も得ることができた．まあ出来なかったものは仕方がないので，この開発で出てきた問題点や疑問点をこれから徹底的に潰していって，これからプログラムを洗練させていくしかないという感じだろうか．今後もできれば開発を続けていきたいと思っているので，とにかく一つの区切りのようなところまで持っていけたのは素直に嬉しい．
開発の流れ
合宿前
さすがに準備なしで合宿に挑むのは無謀だと思って，事前に少し練習のようなものをすることに．Suffix Arrayの記事で取り上げている問題は，まさに準備運動にうってつけだった．あとはBWTに関する資料をいくつか読んだり，全文検索周りで転置インデックスの方を調べるなど脇道に逸れたり．
生活
温泉宿は周りにコンビニすらないような立地だったので，お菓子やら飲み物を買い込んでひたすら部屋で開発という感じだった．温泉は1日目は浴衣が無くて入れなかったのだが，2日目には入れるようになった．1回しか入らなかったのだが，非常にリフレッシュ出来て良かった．
ネットに関しては，イーモバイルの電波も入ったし，部屋に設置してあった有線LANがかなり速度が出る感じだったので，全体的にかなり快適に作業出来た．
あと，畳の上で座って作業するのはやはり腰を痛める．例年そうなのだが...
