• 作成:

haskellによるLZ78の実装

背景

2015年07月の大学の講義｢情報理論｣で｢Ziv Lempel符号について調べて解説せよ｣という課題が出ました.

情報理論という名前の講義ですが, プログラミングは直接は関係していない, 数学寄りの講義でした. しかし私はプログラミングで理解したほうが楽なため, LZ78 - Wikipediaによるデータ圧縮プログラムを実装してみることにしました.

なぜLZ78なのか. それは適当にググってる時に出てきたwikipediaの記事の解説が丁寧でわかりやすくて, これなら自分でも実装できそうだと思ったからです.

ソースコード

コード解説

標準入出力を使って, オプションが-eならエンコード, -dならデコードを行う.

簡単のため, 符号はAscii範囲の文字しか想定していません.

評価

実用性はありません.

シリアライズが非効率

今回の目的は実用性のある圧縮ソフトウェアを作ることではなく, LZ78アルゴリズムを理解することなので, その範囲外であるデータシリアライズには全くやる気を出しておらず, haskell標準関数であるshowを使っています. これの効率は論外であり, 大抵の場合LZ78を使ったのにも関らず, データ量は大抵増加します.

参考にしたWikipediaの記事のHTMLを圧縮すると, シリアライズが非効率的すぎてサイズは81KB -> 195KBに増大します.

まともな速度が出ない

この効率の悪さからは信じられないほどの圧縮時間がかかります. このプログラムは固定で128文字(｢文字｣のカウントはあまり考えていない)を最大探索数とします. 浮動小数点の誤差をカウントするプログラムの出力(要するに規則性のある膨大な出力)を圧縮すると, 26MB -> 14MBになりましたがとても遅いです.

デコードが二度手間になっている

デコードの手順が辞書を作る → 辞書を使って伸長になっていますが, LZ78の特性上, 辞書を作りながら伸長が出来るはずで, これは二度手間です. 理解が浅い.

標準ライブラリの選定がイマイチ

バイナリを扱うならData.ByteStringをただただ使うべきであり, Char8を使うべきではありませんでした.

講義の学習の自己評価

情報理論の学習はそれなりに出来たと考えています. これのおかげてhttp/2のヘッダ圧縮にハフマン符号が出てきても, すぐにわかることが出来ました(本当にわかっているのだろうか).

また既存の圧縮手法とその実装の偉大さを知り, プログラムの効率を重視することの大切さを改めて実感することが出来ました.