mots quotidiens. | |
Daichi Mochihashi (持橋大地) daichi <at> ism.ac.jp | by hns, version 2.10-pl1. |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||
% ./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
にあります。凄すぎる..。
"\1\2\3\010\6\4\011__\7\5"[n*0x5300000>>28];はslashdot.jpでも8月頭に 話題になっていたらしい。
今, 問題は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系列を ビットシフトすれば, 完全ハッシュが得られる, という流れのようです。
最近たまたま, これの Windows 版の
「Win書道」
が出ているのを知りました。
Mac版が18000円くらいだったのに対して, なんと1980円!。
当然, 即座にオンラインで購入しました。
Mac版と基本的な機能は同じで, 違うのはMac版にある「筆休め」がついて
いないことや
(Mac版では, 上のメニューから「筆休め」を選択すると,
「カコーン」と鹿おどしの鳴るわびさびの世界が全画面で展開されるという,
超絶イカス機能がついていた。),
筆, 硯, 墨, 紙等の選択が限定されているということです。
墨を硯の上でドラッグして墨を摺って色を調節して, マウスで書きます。
もちろん色は黒だけではなくて, カラーが全部使えます。
やっぱり, タブレットを買った方がいいかも。
ちなみに X には豊橋技科大で開発された
Xshodo
[RPM]
というソフト(前の名前はX莫山)があって, 前に隣の席の森川君に紹介したら,
遊び心のある彼は色々面白い/可愛い絵を描いていたのだった。
というわけで, 僕は演算星組/ソースネクストの回し者ではありませんが,
この
Win書道
はかなりおすすめです。送料を入れても2500円くらいなので, もう買うしか!(笑)
という感じです。
なお, Plusでも動くMac書道の元祖については, 名作ソフトとして このあたり に色々解説があるようです。
タイトル一覧 |