experimentalマラソンというか edit distance

そういえば微妙に参加していたので感想を書いてみよう。

AGCT を構成要素とする文字列の群 A, B, C があって、要は DNA やね、A の中から a 、 B の中から b 、 C の中から c 、と取り出して、それらを適当に先頭をランダムにカットして、適当に先頭と末尾にランダムなゴミを付加して、a' + b' + c' を作る。でその後にさらに 10% の確率だったかで起きるランダムな変異を加えて入力 q を作る。

で、この入力がたくさん与えられるから、それぞれ A,B,C の中のどこから来たものかを当てるというもの。評価は a+b+c と q の edit distance で行なわれる。

ただし今回は前半後半に分けて、グループAは最初から最後までコードを公開しあい、掲示板で議論しながら、グループBは前半は個人戦で、後半はグループで協力、
グループCは最初から最後まで個人戦、という設定だった。

まず前半は、成田以外で書いた記憶がない。基本的には何も考えず、高速に edit distance を近似できる関数を書けばいいんだろう、ということでそういうことでやっていた。でまぁそれを使ってもイマイチ成績が良くならないのでやる気が起きず、そして edit distance の最適化ばかりやっていた。

なんてこと。

後半はなんかトップの人のコードの edit distance が遅そうなので高速化とかしてみた。これもやる気が足りなくて中途半端にしかやらなかったけど。

でまぁわかったことは、 3 つあって、

  • Cell challenge でやられていたという、 edit distance の bit 演算を用いた高速化の方法
  • edit distance ってのは似たような文字列相手だと適当な近似でかなりいい感じの結果が出る
  • そんな最適化よりアルゴリズム的に工夫した方がはるかに良い

ということだった。いや最後の一つは知ってたけど。

でまぁ最初の方は、言うべきことは一つで

http://mono.kmc.gr.jp/~oxy/d/?date=20090323#p01

oxyさんのスライドの式間違ってるよ! ということだった。この式かなり難しいのでデバッグ大変なのだった。結局どっかにあった論文を見た。たしかこれ

http://www.cs.uta.fi/~helmu/pubs/psc02.pdf

間違ってるところだけを書くと24枚目、

 d0 = (((pm & vp) + vp)) ^ vp | pm | vn;

が正しい、らしい。

2つ目も、まぁ当たり前なんだろうけど、基本的な話としては edit distance はDP テーブルのうち斜めに切った部分しか計算しなくて良い、という話が基本としてあって、

 ooooxxx
 oooooxx
 oooooox
 ooooooo
 xoooooo
 xxooooo
 xxxoooo

具体的にはこんな形で x の部分は調べる必要がない。でさらに、近似値でいいんなら x の近傍の o は別に計算しなくても最終結果にはそんなに関わってこないわけで、そのへん使うとそうとうに計算をはしょれるわけだけど、ただ bit 並列な形で計算するとこれ実装するの結構めんどくさいんですよね。特に x 軸が y 軸より結構長い場合なんかに、微妙な形の平行四辺形みたいな何かを書くことになって、これがめんどくさいと思いました。実装したかったけどしませんでした。

 ooooxxxxxxxxxxxx
 ooooxxxxxxxxxxxx
 xooooxxxxxxxxxxx
 xxxooooxxxxxxxxx
 xxxxxooooxxxxxxx
 xxxxxxxooooxxxxx
 xxxxxxxxxooooxxx
 xxxxxxxxxxxoooox
 xxxxxxxxxxxxoooo
 xxxxxxxxxxxxoooo

こんな感じの歪んだ形で計算するのが近似精度良さそうですよね…

というわけで誰か速い edit distance ライブラリとか作っておくといいんじゃないかなぁとか。

なにかあれば下記メールアドレスへ。
shinichiro.hamaji _at_ gmail.com
shinichiro.h