mots quotidiens.
Daichi Mochihashi (持橋大地) daichi <at> ism.ac.jp by hns, version 2.10-pl1.

先月 2024年03月 来月
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31

2009年08月29日() [n年日記]

#1 SVM 2009終了

今年も SVM 2009 が終了。発表も面白かったし, その後で普段話せない人と色々話すことができて, 楽しかったです。
僕は Gaussian Process とGPLVM, GPDMの話をしました。スライドがまだ荒削りなのと, 本来書きたくて時間切れになってしまったものもあるのでまだ公開は控えますが, Gaussian process と Dirichlet process の関係は知りたい人が他にもいるかも 知れないので, そこだけ1ページのPDFにして公開しておきます。 ご興味のある方はどうぞ。
Poisson processなんかも考えてみると同じ構造を持っているので, 本当はそれらを 含めて統一的に説明すべきなのだと思いますが, そこまで僕の準備が整っていない ので, 今後ということで..。
M1が結構多かったようなので, M1あたりから見るとポカーン, なのかなあ, と 思ったり。 *1


*1: M1でも一瞬で理解できるような話をしているようでは駄目だ, という気もしますが..。

2008年08月29日(金) [n年日記]

#1 DNA

任意のファイルの"DNA"を求めるコード
% ./dna < /etc/fstab
TTGAACGCCCGCGCTCTTGAGCCCTTGCATGCTCACGATCTTGCCCTCAATCAATAAATATTGAATACTTGCTCG\
CGCCCTTGCATGCAATAAATAAAGATTGAAAGAAAGAAAGAAAGAAAGAAAGAAAGAAAGAAAGAAAGAAAGAAA\
GAAAGAAAGAAAGAAAGAAAGAAAGAAAGAAAGAAAGAAAGAAAGACCGCAGTCACTCTATAAAGAAAGAAAGAA\
AGAACGCCCGCGCGCCAGCCCTCATGCACTCTATCAAGAAAGAAAGAAAGAAAGAAAGAAAGAAAGACATAAAGA\
CATAGGAAATACCAACGAACCCACATACCTTATTGAGAGCTTGCTTGCACTCAAGAAAGAAAGAAAGAAAGAAAG\
AAAGAAAGAAAGAAAGAAAGAAAGAAAGATTGAGAGCTTGCTTGCACTCAAGAAAGAAAGAAAGAAAGAAAGAAA\
GAAAGAAAGAAAGAAAGAAAGAAAGAAAGAAAGAAAGAAAGAAAGAAAGACCGCAGTCACTCTATAAAGAAAGAA
(以下略)
は以下のように書けるという話を前に聞いて, 面白いなと思っていた。
#include <stdio.h>
int main() {
  char*s="ACGT",c,i;
  while((c=getchar())!=EOF)
    for(i=0;i<4;i++,c>>=2)
      printf("%c",s[c&3]);
}
1バイトは8ビットで"ACGT" *1 は2bitの情報量なので, これは単純に1バイトを順番に2ビットずつ ずらしながらDNAにエンコードしている。
こういうのを見ると当然デコーダーを書きたくなるわけで, 書いてみたものを 実習生で来ている神戸大の 泉谷君 に相談して一箇所直して, 一番素直には, 以下のプログラムでデコードできる。
% cat and.c
#include <stdio.h>
main(){
  int c,i,d[256];
  d['A']=0; d['C']=1; d['G']=2; d['T']=3;
  while ((c=getchar())!=EOF){
    c=d[c];
    for(i=1;i<4;i++)
      c |= d[getchar()] << i*2;
    putchar(c);
  }
}
% cat /tmp/dna
AGGCTTGCTCTCAAGACAGCGATCCCGCAAGACGTCTTGCCCTCAAGATCGCCCGCGTGCACTCATGCCCGCCTGCCCGCGTGCGGAA
% ./and < /tmp/dna
how are you gentlemen
ただ, これはいかにもd['A']=0; d['C']=1; d['G']=2; d['T']=3;の部分が冗長。

これは'ACGT'(文字コード65,67,71,84)をそれぞれ0,1,2,3にマップしているだけ なので, 2進表現を考えると, 朝少し計算して, (c*3>>3)&3 で書けることに気づいた。 こうすると, 上のプログラムは Short coding的なテクニックを使って短くして, 2行で書ける。

main(){char c,i;while(c=getchar(),~c){c=(c*3>>3)&3;
for(i=1;i<4;i++)c|=((getchar()*3>>3)&3)<<i*2;putchar(c);}}
泉谷君が, さらにゴルフして1行にしてくれた。
i,b,c;main(){while(c=getchar(i/4?putchar(b),b=i=0:0),~c)b|=(c*3>>3&3)<<i++*2;}

-1は二進表現で111..11なので, ~cにすると-1のときだけ全部0(false)になる模様。 なるほど。
なお, 上のようなハッシュを計算するさらに一般的な超絶コードが, "ビット演算 0x02"スレ762-763 にあります。凄すぎる..。

・ 補足: M系列

これで終わりにするはずがないわけで, もう少し追及してみた。
入力 n = 2^a に対してaを一瞬で返す
"\1\2\3\010\6\4\011__\7\5"[n*0x5300000>>28];
はslashdot.jpでも8月頭に 話題になっていたらしい。
M系列を使っているとのことだが, 上のリンク等を見ても, どこがM系列?と 全然わからなかった。
ようやく理解できたので, 以下簡単なまとめ。もう知っている人やわかっている人は 飛ばして下さい。

今, 問題は512→9, 256→8, 16→4 のような数を返すこと。
実は, 必ずしも上の通りに値を返さなくても, 入力nに対してそれぞれ違う整数を マップできれば, "...." の文字列の形をしたテーブルの対応する添字をアクセスすれば 所望の結果が得られる。 *2 よって上のコードの中心は "\1\2\3\010\6\4\011__\7\5" ではなくて, 掛けてある 0x5300000 (や0xCA030FF) をどうやって求めたか, ということ。

まずM系列とは, 一番簡単には, p個のビット列xを初期値として, x[n] = x[n-p] ^ x[n-q] (p>qとする) の形でXORを取ることで生成される 1111000010011010111 のようなビット数列のことらしい。 [説明] これをpビット毎に切り出すと, 周期2^p-1ですべて違ったビット列 1..2^p が現れる。 (自然言語処理では全く使わないので, 僕は聞いたことがなかった。)
ここで, 入力nは常に512や32のように 2^a の形をしているので, n*■(謎の定数)は■をaビット左にシフトするという意味。
これが各a=1,2,..,9について常に異なった値になる→■にはM系列を使えばいい!
ということのようだ。
実際にはM系列は一意ではない&&問題は1<=a<=9を対象にしているため, a>=10ビット 以上シフトすることはないため, うまくM系列を選ぶと引くテーブル(文字列)を短く することができる, というのが最後のコツの模様。

というわけでまとめると, 今回は与えられたキー集合に対する完全ハッシュ関数を 作ればよく(順番はテーブルを引くことで吸収する), 一般にはgperfのようなものを 使えばよいが, 今回入力nは常に2の巾乗→nを掛けることはビットシフト→M系列を ビットシフトすれば, 完全ハッシュが得られる, という流れのようです。


*1: "ICFP" にしてもOKです。:-)
*2: だからDNAの場合も, "ACGT"でなく"CATG"でエンコードされていれば, b|=("\1\0\3\2"[c*3>>3&3])<<i++*2; のように適切に変換すればok。

2005年08月29日(月) [n年日記]

#1 Win書道

漢字Talk 7が出たころからのMacユーザーとして, 演算星組の Mac書道 Pro はとても気に入っている, 名作ソフトです。
( Mac書道 山水 も持っています。が, これはG3くらいの速度がないとまともに動かなくて, 前に持っていた8100/80AVでは使えなかった。)
何が素晴らしいと言って, 上のページの真ん中から下あたりにある, 「Macは「気」のメディアになった。..」で始まる アオリ文句が素晴らしいのです。(笑) ちなみに, パッケージもいかしまくってます (特に Mac書道 山水)。

最近たまたま, これの Windows 版の 「Win書道」 が出ているのを知りました。 Mac版が18000円くらいだったのに対して, なんと1980円!。
当然, 即座にオンラインで購入しました。
Mac版と基本的な機能は同じで, 違うのはMac版にある「筆休め」がついて いないことや (Mac版では, 上のメニューから「筆休め」を選択すると, 「カコーン」と鹿おどしの鳴るわびさびの世界が全画面で展開されるという, 超絶イカス機能がついていた。), 筆, 硯, 墨, 紙等の選択が限定されているということです。

で, 買ったので, とりあえず何かお習字してみました。(ぉ

墨を硯の上でドラッグして墨を摺って色を調節して, マウスで書きます。 もちろん色は黒だけではなくて, カラーが全部使えます。
やっぱり, タブレットを買った方がいいかも。
ちなみに X には豊橋技科大で開発された Xshodo [RPM] というソフト(前の名前はX莫山)があって, 前に隣の席の森川君に紹介したら, 遊び心のある彼は色々面白い/可愛い絵を描いていたのだった。
というわけで, 僕は演算星組/ソースネクストの回し者ではありませんが, この Win書道 はかなりおすすめです。送料を入れても2500円くらいなので, もう買うしか!(笑) という感じです。

・ Mac書道

なお, Plusでも動くMac書道の元祖については, 名作ソフトとして このあたり に色々解説があるようです。


3 days displayed.
タイトル一覧
カテゴリ分類
 なかのひと
Powered by hns-2.10-pl1, HyperNikkiSystem Project