短単位自動解析用辞書を作る（２）
連接表を圧縮する（その１）
前回書いたモチベーションの１つ目は『UniDic』の単語連接表 matrix.def が大き過ぎるというものでした。
これを最終的に 1/100 の大きさまで圧縮できたのですが、順を追って書いていきます。
/unidic-cwj-202302_full$ head matrix.def
21202 18859
0 0 0
0 1 -1814
0 2 -1814
0 3 -1814
0 4 -1814
0 5 -1814
0 6 -1814
0 7 -1814
0 8 -1814
unidic-cwj-202302_full$ tail matrix.def
21201 18849 -299
21201 18850 -225
21201 18851 -574
21201 18852 -369
21201 18853 -387
21201 18854 -490
21201 18855 110
21201 18856 -237
21201 18857 -50
21201 18858 -153『UniDic』の matrix.def です。サイズが大きすぎるので頭と末尾の10行だけ表示させました。
単語同士の連接表なので、これは行列です。行列としてのサイズは 1行目に書いてあります。21,202（行）x18,859（列） です。
2行目以降が行列の$${i}$$行$${j}$$列における成分: 連接コスト$${e_{ij}}$$です。各行半角スペース区切りで、
$${i}$$ $${j}$$ $${e_{ij}}$$
というふうに記述されています。
単語同士の連接コストを格納した行列ですが、最新版の『UniDic』の語彙ファイルの行数（登録単語数）は 876,803 なので単純に連接表を作ると、876,803 x 876,803 のサイズで、現状の約40倍のサイズです。
unidic-cwj-202302_full$ wc -l lex.csv
876803 lex.csv連接表の爆発が起きないように、『MeCab』は語彙ファイル内の各単語を rewrite.def という定義ファイルに書かれたルールを基に抽象化（まとめあげ）しています。
抽象化された後の状態は right-id.def と left-id.def に記述されています。
unidic-cwj-202302_full$ head right-id.def
0 BOS/EOS,*,*,*,*,*,BOS/EOS,BOS/EOS,BOS/EOS,*,*,*,*,*,*
1 代名詞,*,*,*,*,*,*,*,和,*,*,*,"0,1",*,*
2 代名詞,*,*,*,*,*,*,*,和,*,*,*,"0,2",*,*
3 代名詞,*,*,*,*,*,*,*,和,*,*,*,"1,0",*,*
4 代名詞,*,*,*,*,*,*,*,和,*,*,*,"1,2",*,*
5 代名詞,*,*,*,*,*,*,*,和,*,*,*,"1,2,0",*,*
6 代名詞,*,*,*,*,*,*,*,和,*,*,*,"2,1",*,*
7 代名詞,*,*,*,*,*,*,*,和,*,*,*,"2,3",*,*
8 代名詞,*,*,*,*,*,*,*,和,*,*,*,"3,4",*,*
9 代名詞,*,*,*,*,*,*,*,和,*,*,*,*,*,*
unidic-cwj-202302_full$ tail right-id.def
21192 連体詞,*,*,*,*,*,*,*,和,*,*,*,*,*,*
21193 連体詞,*,*,*,*,*,*,*,和,*,*,*,0,*,*
21194 連体詞,*,*,*,*,*,*,*,和,*,*,*,1,*,*
21195 連体詞,*,*,*,*,*,*,*,和,*,*,*,2,*,*
21196 連体詞,*,*,*,*,*,*,*,和,*,*,*,3,*,*
21197 連体詞,*,*,*,*,*,*,*,和,*,*,*,4,*,*
21198 連体詞,*,*,*,*,*,*,*,混,*,*,*,0,*,*
21199 連体詞,*,*,*,*,*,*,*,混,*,*,*,1,*,*
21200 連体詞,*,*,*,*,*,*,*,混,*,*,*,3,*,*
21201 連体詞,*,*,*,*,*,*,*,混,*,*,*,4,*,*
unidic-cwj-202302_full$ head left-id.def
0 BOS/EOS,*,*,*,*,*,BOS/EOS,BOS/EOS,BOS/EOS,*,*,*,*,*,*
1 代名詞,*,*,*,*,*,*,*,和,*,*,*,"0,1",*,*
2 代名詞,*,*,*,*,*,*,*,和,*,*,*,"0,2",*,*
3 代名詞,*,*,*,*,*,*,*,和,*,*,*,"1,0",*,*
4 代名詞,*,*,*,*,*,*,*,和,*,*,*,"1,2",*,*
5 代名詞,*,*,*,*,*,*,*,和,*,*,*,"1,2,0",*,*
6 代名詞,*,*,*,*,*,*,*,和,*,*,*,"2,1",*,*
7 代名詞,*,*,*,*,*,*,*,和,*,*,*,"2,3",*,*
8 代名詞,*,*,*,*,*,*,*,和,*,*,*,"3,4",*,*
9 代名詞,*,*,*,*,*,*,*,和,*,*,*,*,*,*
unidic-cwj-202302_full$ tail left-id.def
18849 連体詞,*,*,*,*,*,*,*,和,*,*,*,*,*,*
18850 連体詞,*,*,*,*,*,*,*,和,*,*,*,0,*,*
18851 連体詞,*,*,*,*,*,*,*,和,*,*,*,1,*,*
18852 連体詞,*,*,*,*,*,*,*,和,*,*,*,2,*,*
18853 連体詞,*,*,*,*,*,*,*,和,*,*,*,3,*,*
18854 連体詞,*,*,*,*,*,*,*,和,*,*,*,4,*,*
18855 連体詞,*,*,*,*,*,*,*,混,*,*,*,0,*,*
18856 連体詞,*,*,*,*,*,*,*,混,*,*,*,1,*,*
18857 連体詞,*,*,*,*,*,*,*,混,*,*,*,3,*,*
18858 連体詞,*,*,*,*,*,*,*,混,*,*,*,4,*,*
unidic-cwj-202302_full$ wc -l right-id.def
21202 right-id.def
unidic-cwj-202302_full$ wc -l left-id.def
18859 left-id.def大きいファイルなので、こちらも頭と末尾の10行を表示させました。
right-id.def の行数は 21,202、left-id.def の行数は18,859。
つまり matrix.def は right-id.def x left-id.def の行列で、各行の番号$${i}$$が right-id、各列の番号$${j}$$が left-id にそれぞれ対応しています。
本論とは関係ありませんが、ここで左右の概念の逆転が起き、実装上非常にややこしいので詳しくはこちらを見てください。
要は連接の左に来る単語が right-id で、右に来る単語が left-id です。
左文脈素性(その形態素を左側から見た時の素性), 右文脈素性(その形態素を左側から見た時の素性)
ここから matrix.def の圧縮の話に入りますが、単純のため、次のようなごくごく小さい matrix.def、right-id.def、left-id.def で説明していきます。
例なので、品詞とその連接コストは深く考えずに適当に書いています。
$ cat right-id.def
0 BOS/EOS
1 名詞
2 動詞
3 形容詞
$ cat left-id.def
0 BOS/EOS
1 名詞
2 動詞
3 形容詞
$ cat matrix.def
4 4
0 0 0
0 1 1
0 2 0
0 3 1
1 0 1
1 1 0
1 2 1
1 3 0
2 0 1
2 1 1
2 2 1
2 3 1
3 0 1
3 1 1
3 2 1
3 3 1この matrix.def を図にすると以下のようになります。
ここで行、つまり right-id に着目します。
right-id から見るとこの行列は、left-id をインデックスとしたベクトルと見ることができます。
こうして見ると、right-id=2 のベクトルと right-id=3 のベクトルは完全に一致しています。つまり各 left-id に対する振る舞いが完全に同じということです。
ならば、right-id を次のように書き換えても『MeCab』の動作的に何も問題ありません。
（定義ファイル内の id の重複はエラーになりませんし、動作上の問題も起きません）
（ちなみに right-id と left-idは、語彙ファイル(.csv)と未知語処理用ファイル(unk.def)にも記載されているので、idを書き換えた時はこれらのファイルも修正が必要です）
$ cat right-id.def
0 BOS/EOS
1 名詞
2 動詞
2 形容詞こうなると、matrix.def の right-id=3 についての行が不要になります。
なので消します。
$ cat matrix.def
3 4
0 0 0
0 1 1
0 2 0
0 3 1
1 0 1
1 1 0
1 2 1
1 3 0
2 0 1
2 1 1
2 2 1
2 3 11 行目の行列サイズも書き換えていることに注意してください。
4x4 の行列が 3x4 になりました。
続いて 列 left-id に着目します。left-id から見ると今度は行列を、right-id をインデックスとしたベクトルと見ることができます。
left-id=0 のベクトルと left-id=2 のベクトルは完全に一致しています。つまり各 right-id に対する振る舞いが完全に同じということです。
またleft-id=1 のベクトルと left-id=3 のベクトルも完全に一致しています。こちらも各 right-id に対する振る舞いが完全に同じということです。
ならば、right-id とおなじく、left-id を次のように書き換えても『MeCab』の動作的に何も問題ありません。
（id は上からsortされている必要もありません）
$ cat left-id.def
0 BOS/EOS
1 名詞
0 動詞
1 形容詞こうなると、matrix.def の left-id=2, 3 についての列が不要になります。
なので消します。
$ cat matrix.def
3 2
0 0 0
0 1 1
1 0 1
1 1 0
2 0 1
2 1 11 行目の行列サイズも書き換えていることに注意してください。
3x4 の行列が 3x2 まで圧縮できました。
途中でも書きましたが、right-id と left-id は 語彙ファイル（.csv）と未知語処理用のファイル(unk.def)にも記載されているので、上記のような書き換えを行なったときは必ず、その2つのファイルに記載の id も修正が必要です。
また上の例では 0, 1, 2 / 0, 1 と、きれいに id が連番で残りましたが、0, 2, 5 のような残り方をした場合は、0->0, 2->1, 5->2 という修正も必要になります。
では、実際にこの圧縮を最新版の『UniDic』に対して実行します。
(py27) unidic-cwj-202302_full$ python ph5_compression_matrix.py
python ph5_compression_matrix.py work_final_dir
(py27) unidic-cwj-202302_full$ ls unidic-cwj-202302_full/
char.bin feature.def license model.bin rewrite.def unidic-cwj-202302_full.zip
char.def left-id.def matrix.bin model.def right-id.def unk.def
dicrc lex.csv matrix.def README_unidic-cwj_full.txt sys.dic unk.dic
(py27) unidic-cwj-202302_full$ python ph5_compression_matrix.py unidic-cwj-202302_full
Reading *.csv...
unidic-cwj-202302_full/lex.csv
Done!
Reading unk.def... Done!
Reading left-id.def... Done!
Reading right-id.def... Done!
Reading matrix.def... Done!
Making right_id->cost map... Done!
Compressing right_id... Done!
Making left_id->[(new_right_id, cost), ...] map... Done!
Compressing left_id... Done!
Making compressed matrix... Done!
Writing new matrix.def... Done!
Writing new *.csv...
unidic-cwj-202302_full/lex.csv
Done!
Writing new unk.def...
Done!
Writing new left-id.def...
Done!
Writing new right-id.def...
Done!
unidic-cwj-202302_full$ head matrix.def
18157 15572
0 0 2675
0 1 -154
0 2 389
0 3 558
0 4 -97
0 5 2814
0 6 -424
0 7 1108
0 8 -545
unidic-cwj-202302_full$ tail matrix.def
18156 15562 -945
18156 15563 23
18156 15564 -189
18156 15565 -745
18156 15566 -1673
18156 15567 -1015
18156 15568 -649
18156 15569 -118
18156 15570 -28
18156 15571 -73
unidic-cwj-202302_full$ ls -lh
total 12G
257K Jul 13 13:23 char.bin
4.3K Jul 13 13:23 char.def
695 Jul 13 13:23 dicrc
8.6K Jul 13 13:23 feature.def
1.6M Jul 13 15:20 left-id.def
1.6M Jul 13 13:23 left-id.def.old
223M Jul 13 15:20 lex.csv
224M Jul 13 13:23 lex.csv.old
4.0K Jul 13 13:23 license
763M Jul 13 13:23 matrix.bin
4.2G Jul 13 15:20 matrix.def
5.9G Jul 13 13:23 matrix.def.old
79M Jul 13 13:23 model.bin
364M Jul 13 13:23 model.def
766 Jul 13 13:23 README_unidic-cwj_full.txt
4.8K Jul 13 13:23 rewrite.def
1.8M Jul 13 15:20 right-id.def
1.8M Jul 13 13:23 right-id.def.old
232M Jul 13 13:23 sys.dic
2.4K Jul 13 15:20 unk.def
2.4K Jul 13 13:23 unk.def.old
5.7K Jul 13 13:23 unk.dic
これで解析性能に影響なく 21,202x18,859 (5.9GB) が 18,157x15,572 (4.2GB) まで圧縮できました。
ちなみにこの matrix.def の圧縮は『UniDic』のバージョン 3.1.0、3.1.1で私が導入していたのですが、上述の通り複数ファイルにまたがった書き換えがややこしいので、引き継がれませんでした。実装は python2系ですが、ここに置いてあります。
（実行後、BOS/EOS の id を 0 に修正する後処理が必要です）
ちなみに上の操作を『ipadic』に対して実行すると、matrix.def が
1,316x1,316 -> 1,281x1,282
と、こちらもまだ圧縮可能です。
行列サイズは小さくなったものの、4.2GB はまだ大きいです。では次どうするのか、というお話は次回に続きます。