第４回MG勉強会

本日は４回目のMG勉強会でした。今日は２章を一気に終わらせるつもりなので、かなりの長丁場です。

まずは前回積み残しのDynamic Markov Compressionです。この手法では有限状態機械を適応的に作りつつ、符号語を構成していくという方法で、この有限状態機械により文脈を判断するようになっています。また、有限状態機械を構築していくときに、入出力が多くなってしまうノード(=文脈が判断しづらいノード)はcloneすることにより文脈を分けます。

次はDictionary modelsです。これは今まで出てきた語の辞書を作りつつ、既に前に出てきた語はその辞書の番号で置き換えていくことにより、文章を圧縮していく手法になります。この本ではLZ77とLZ78という手法が紹介されています。

まずはLZ77です。この手法ではある語が何文字前に出現したかとそこから何文字コピーするか、という情報を保持しておくことにより、後ろの語を前に出てきた語の位置で置き換える手法になります。
もう一つのLZ78は前に出てきた単語を辞書に登録しておいて、後で出てきた単語はその辞書の番号で代替させる方法になります。

次の部分はSynchronizationです。これは今までの手法だと、単語を前から順に復号していかないと中身がとれないのですが、検索のようにランダムアクセスを行いたい場合、どうしても途中から一部分だけ復号したいということがあります。そのときにちょっと工夫して構成することにより、途中からでも復元できるようにする方法がSynchronizationです。

また符号語には、適当な場所から復号を始めても、最初はもちろん一致しないのですが、復号を続けていくうちに、元の語に戻っているというSelf-synchronizationなる性質を持った符号語もあるそうです。まあここら辺はこういうのもありますよ、程度のお話なのでさらっと。

最後は性能比較です。筆者が自分たちで作ったであろうプログラムと、バリバリチューニングされたプログラムを比較してたり、環境によって異なってくるといいつつ、１種類の環境でしか比較してなかったりするので、厳密な結果とはいいがたいですが、参考としては面白い感じです。順当に圧縮率が高いものは符合化復号化に時間がかかる、という感じですね。

次回はIndexingということで、バリバリの検索関連の話題に戻ります。