Canonical Huffman Codes - naoyaのはてなダイアリー
1999年出版と少し古い書籍ですが Managing Gigabytes を読んでいます。理解のために 2.3 で出て来る Canonical Huffman Codes の習作を作りました。 ハフマン符号は情報圧縮で利用される古典的なアルゴリズムで、圧縮対象データに出現するシンボルの出現確率が分かっているときに、その各シンボルに最適な符号長の接頭語符号を求めるものです。 通常のハフマン符号はポインタで結ばれたハフマン木を構築して、ツリーを辿りながら各シンボルに対する接頭語符号を計算します。このハフマン木には曖昧な箇所が残されています。ハフマン木は木の辺を右に辿るか左に辿るかで符号のビットが決まりますが、右が 0 で左が 1 などというのはどちらでも良いという点です。(曖昧だから駄目、という話ではありません。) 従って、ハフマン木から生成される符号は一意には決まりません。 ここで各シンボル
高速に符号／復号を行える最小冗長符号「Canonical Huffman Code」
対象読者 C++の利用者を対象としています。データ圧縮の基礎を知っていることが望ましいです。 必要な環境 C++、32bit環境を想定しています。Windows XP上のVisual Studio C++ 2005、gcc 3.2.2で動作確認済みです。 Huffman Codeの概要 初めに、Huffman Code（以下、HC）について簡単に説明します。データ中に出現する各文字の出現確率が既に分かっている、もしくは予測できる場合に、多く出現する文字に対し短い符号を割り当て、あまり出現しない文字に対し長い符号を割り当てることで、データ全体の符号長を短くすることができます。このように各文字の符号の長さが違う符号（可変長符号）は、元のデータに間違いなく復元できる条件は必要ですが、HCはさらに次の条件を満たした符号を決定します。 瞬時復元可能である データ全体の符号長が最小である 「瞬時復元可
Canonical Huffman Codes での符号長の効率的な計算 - naoyaのはてなダイアリー
週末に参加した Managing Gigabytes の読書会で第2章のハフマン符号を担当しました。この中で Canonical Huffman Codes の解説がありますが、そこにハフマン符号の符号長を効率的に求める手法の説明が含まれています。 輪講では時間切れのためこのアルゴリズムの解説が駆け足になってしまいましたので、改めて解説資料を作ってみました。2009 年の今に Managing Gigabytes を読んでいるという方はあまり多くないかもしれませんが、参考になれば幸いです。 https://www.dropbox.com/s/539fhyc7rf6b9ik/090518computing_huffman_code_length.ppt?dl=0 (PPT, 258K) 先日 Canonical Huffman Codes の習作を Python で実装しましたが、このコード
Canonical Huffman Code
Daisuke Okanohara (VZV05226@nifty.com) 2003/12/9 公開 2003/12/11 誤植、chc.zipのmain.cppを修正 2003/12/13 multidecodeを実装 main.cppもそれに伴い変更 Canonical Huffman Code (以下CHC）は、Huffman法と同様に、最小冗長符号をHuffman木を作成、保持することなく、表引きで、符号化、復号化できる符号法です。 CHCは突然現れたアルゴリズムではなく、1950年代にHuffman法が登場して以来（Huffman法は、Fano符号で有名なFanoが出した最終試験免除の課題を学生だったHuffmanが試験直前に解決して発明された）、表向きにしろ、そうでないにしろさまざまな改良が、実装面、理論面でも行われてきました。その変種はいろいろありますが、その中で最も
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
