Yusuke TABATA
yusuk****@w5*****
2005年 9月 11日 (日) 17:21:56 JST
田畑です。 Yusuke TABATA wrote: > anthyで実験的に実装中の機能を説明してみます。 > (1)疎行列 > (2)逆変換を利用して実現したchasen or kakasi的機能(形態素解析器) このうち、疎行列のコードの説明をしてみます。 先日、Johnsonのアルゴリズムについて説明を書いたのですが、 #http://lists.sourceforge.jp/mailman/archives/anthy-dev/2005-July/002170.html これよりももっと基礎的な技術でコードを書いてます。 まず、行列の各行を見て非0要素を含む行だけをハッシュで 小さな配列に詰めなおします。詰めるときには元の行番号も いっしょに記録します。 (いわゆるオープンアドレス法を使います。構成する時に衝突が 一定回数を超えたらmを大きくしてやり直ります。) 行番号(h):非0要素の有無 もとの行番号:非0要素の有無 0:0 1:1 1:1 ---->> 3:1 2:0 hash(h)%m 7:1 3:1 / 4:0 / 5:0 / 6:0 7:1 8:0 上のように行を圧縮する(というか詰める)と、次のように横方向に 疎な行列になります。 1:1 . . 3:1 . . 7:1 . . . これを同じ方法で詰めます。右側の点は列番号と行列内の値が 入っていることになります。 1:1 . . -> .. 3:1 . . -> .. 7:1 . . . -> ... 各行内の成分をずらして、どれだけずらしたかを記録した上で 一つの配列に詰めます。 1:1 .. -> .. shift 0 3:1 .. -> .. shift 2 7:1 ... -> ... shift 4 | \|/ ....... (一つの配列) 説明するほどの事でも無いのかもしれませんけど、一応、書いてみました。
