Canonical Huffman Codes での符号長の効率的な計算
週末に参加した Managing Gigabytes の読書会で第2章のハフマン符号を担当しました。この中で Canonical Huffman Codes の解説がありますが、そこにハフマン符号の符号長を効率的に求める手法の説明が含まれています。
輪講では時間切れのためこのアルゴリズムの解説が駆け足になってしまいましたので、改めて解説資料を作ってみました。2009 年の今に Managing Gigabytes を読んでいるという方はあまり多くないかもしれませんが、参考になれば幸いです。
先日 Canonical Huffman Codes の習作を Python で実装しましたが、このコード中の CHC クラスのコンストラクタで行っている配列 codelen の初期化が符号長算出の処理になります。
このアルゴリズムは仕組み的にも実装的にもとても面白いです。
符号化したいシンボルの数の倍のサイズの配列を用意しておいて、その配列の半分の領域にハフマン符号木の構築に必要になる二分木ヒープを構築し、このヒープを利用して配列をインプレイスでハフマン木*1に変えていきます。木構造を構築するにあたっては、計算対象の集合から 2 つとって 1 つ追加という処理を繰り返すことで集合を減らしていくのですが、この効率的なバージョンのアルゴリズムではヒープから値を取り除いて空いた領域やすでに処理済みの要素が保存されていた領域を注意深く上書きしていくことでそれを再利用し、追加のメモリ領域を必要とせずに処理を完了します。実装に妥協がない感じな所が良いですね。
資料は SlideShare にもアップロードしてみたのですが、フォントや図が一部つぶれてしまって、少し見づらいです。SlideShare の URL は http://www.slideshare.net/naoya1977/090518computing-huffman-code-length です。
