FC2ブログ
ひそかにぐあんをめぐらして
スポンサーサイト
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
ハフマン符号・その3
 これまで説明してきたハフマン符号は、まず最初にデータ全体から各文字の出現頻度を求め、それに基づいてハフマン木を作成し、各文字を符号化していきました。このような方法を「静的符号化」と呼びますが、これには、以下のような欠点があります。

・各文字の出現頻度に関する情報を符号化データに格納することが必要不可欠であり、これがオーバヘッドの原因になることがある
・符号化の際、2度読みをしなければならない(1回目で出現頻度を調べ、2回目で符号化処理を行う)

 特に、オンラインでのストリームデータを処理する場合に問題となります。大容量のデータを処理する場合、全データを一時的に読み込んでメモリに格納しなければ、圧縮処理を開始することができません。データをブロック単位に区切ればそのメモリ領域を節約できますが、各文字の出現頻度に関する情報がブロック分割数のぶん増加してしまいます。

 これを解消する方法として、「適応型符号化」というものがあり、これを利用したハフマン符号を「適応型ハフマン符号」といいます。これは、簡単に言えば、ハフマン木の初期状態をある決められた形にしておき、文字1バイトを入力し符号化するたびに一定の法則でハフマン木を更新させていくというものです。これにより、前述の2点の問題を解消することができます。しかし、1バイト読むたびにハフマン木の更新処理があるため、処理速度が遅いという欠点があります。

 適応型ハフマン符号の詳しい解説は、『圧縮アルゴリズム―符号化の原理とC言語による実装(*)』に載っています。ハフマン木の更新処理は、FGKアルゴリズムというものを利用しているそうです。これを参考にして作って試してみましたが、処理速度は、静的ハフマン符号と比べかなり遅くなったという印象を持ちます。しかも、ソースコードも長くなり、圧縮率も改善するどころかむしろ少し悪くなるといった結果になってしまいました(この原因がよくわかりません)。残念な結果になりましたが、ハフマン木の更新処理を工夫すれば、もう少し良くなるのかもしれません。

(*) http://www.amazon.co.jp/exec/obidos/ASIN/4797325526/ewords-22


スポンサーサイト

テーマ:プログラミング - ジャンル:コンピュータ

コメント
この記事へのコメント
コメントを投稿する
URL:
Comment:
Pass:
秘密: 管理者にだけ表示を許可する
 
トラックバック
この記事のトラックバックURL
この記事へのトラックバック
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。