これまで説明してきたハフマン符号は、まず最初にデータ全体から各文字の出現頻度を求め、それに基づいてハフマン木を作成し、各文字を符号化していきました。このような方法を「静的符号化」と呼びますが、これには、以下のような欠点があります。

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

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

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

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

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