yusuk****@cheru*****
yusuk****@cheru*****
2005年 7月 29日 (金) 01:31:34 JST
田畑です。
データ構造の説明その2という感じで、疎行列を1次元配列に
詰める方法を説明してみます。Johnsonのアルゴリズムなどと
呼ばれていたと思います。
先日説明したDouble Array Trieよりは簡単に理解できる
はずです。
正方行列でなくても利用可能で、変換エンジンに使うとすると
行方向に各単語、列方向に雑多な属性をならべ、行列の成分を
true or falseにするといった使いかたができると思います。
例えば、次のような行列を作ることによって、変換精度を上げる
ことができるかもしれません。
|武蔵中原 住宅 蛍光灯 猫 友人 ケーキ
--------------------+------------------------------
「〜駅」と言う | 1 0 0 0 0 0
垂直方向の高さを持つ| 0 1 0 0 0 1
値段がある | 0 1 1 0 0 1
食べれる | 0 0 0 0 0 1
鳴く | 0 0 0 1 0 0
人である | 0 0 0 0 1 0
このような行列をそのまま2次元で扱うと、単語の数*属性の数
の領域を用意する必要があって、ほとんど0しか詰めてないのに
メモリの無駄遣いが悲惨なことになりますが、以下に説明する方法で
1次元配列に詰め込むことで、メモリ消費を少なく抑えながら、
M(鳴く、猫)は0か1かというような検索を高速に行なえるように
なります。
まず、運の良い場合のアルゴリズムを説明します。
次のような行列を圧縮してみます。
|1 2 3 4 5
-+----------
1|0 0 d 0 0
2|a 0 0 0 0
3|0 0 0 0 0
4|0 0 0 0 c
5|0 b 0 0 0
0の入っている所は無視して、行列を縦につぶします。
|a b d 0 c
何行目の成分かわからなくならないように、どの行から来た成分かを
書く配列を用意します。
|2 5 1 0 4
これで、二つの配列が作れます。
index| 0 1 2 3 4
-----+-----------
data | a b d 0 c
row | 2 5 1 0 4
行列の成分M(i,j)を取得する時は
(a) row[j]==iの場合 M(i,j)=data[j]
(b) row[j]!=iの場合 M(i,j)=0
というように計算します。
このやり方では、次のように同じ列に複数の非0があった時に明らかにダメです。
|1 2 3 4 5
-+----------
1|0 e d 0 0
2|a 0 0 0 0
3|0 0 0 f 0
4|0 0 g 0 c
5|0 b 0 0 0
この場合は同じ列に来る非0が一つになるようにずらします。
|1 2 3 4 5
-+----------
1|0 e d 0 0
2|a 0 0 0 0
3|0 0 0 f 0
4| 0 0 g 0 c
5| 0 b 0 0 0
行をどれだけずらしたかを配列に記録します。
index| 1 2 3 4 5
-----+----------
shift| 0 0 0 2 4
最初のやり方と同様に縦に圧縮します。
index| 1 2 3 4 5 6 7 8 9
-----+------------------
data | a e d f g b c 0 0
row | 2 1 1 3 4 5 4 0 0
この場合も行列の成分M(i,j)を取得する時は
(a) row[shift[i]+j]==iの場合 M(i,j)=data[j]
(b) row[shift[i]+j]!=iの場合 M(i,j)=0
というように簡単にアクセスができます。
どの行からずらしていくかを決めるのに少し
実験が必要かもしれません。
--
そこそこプログラミングの経験を持った人がこの方法と、
Double Array Trieの(仕組みではなく)動作と、あと
ビタビアルゴリズムを理解できれば変換エンジンを
作れると感じるのではないかと思います。
実際に作れるかどうかは別として、この手の説明によって変換エンジン
開発への敷居を下げることができれば良いなと願ってます。
--
CHAOS AND CHANCE!
Yusuke TABATA (yusuk****@cheru*****)