ハフマン符号を Rust で実装する
ハフマン符号とは
ハフマン符号 (Huffman Coding) は, 1952年に Huffman 氏によって開発された符号で, データの可逆圧縮 (ZIP や JPEG など) に使用されている. 文字の出現頻度を調べ, 頻度の高い文字に短いビット列を, 低い文字には長いビット列を割り当てることでデータを圧縮する.
ハフマン符号は接頭符号であり, 任意の文字列に対応するビット列が他の文字に対応するビット列の接頭辞になることがない. (例えば, 3つの文字がそれぞれ "1 01 011" と符号化される場合, "01" が "011" の先頭2文字となっているため接頭符号ではない.) すなわち, エンコードされたビット列を先頭から読んでいくだけで, 一意に復号できる (瞬時復号可能, 一意復号可能). このことは後述するハフマン木を見れば分かる.
エンコード
以下の流れでエンコードが行われる.
- 平文における各文字の出現頻度を調べる.
- この出現頻度をもとにハフマン木を作る.
- ハフマン木から各文字に割り当てるビット列を求め, その対応表を作る.
- 平文を探索し, 各文字をビット列へ変換する.
- 変換されたビット列にヘッダーとしてビット列の長さ, 平文の長さ, エンコードしたハフマン木とその長さを含める.
以上の手順では, 平文を2回探索する必要がある. このようなハフマン符号を静的ハフマン符号という. それに対し, 探索と木の構築を同時に行っていくものを動的ハフマン符号という. 本記事では静的ハフマン符号を実装する.
ハフマン木は次の手順で作ることができる. 出現頻度の最も低い2文字を子に持つ節を作り, その出現頻度は2文字の和とする. これを加えた中で最も出現頻度の低い2つに同様の処理を行う. この操作を最後の1つになるまで繰り返す.
例として, 次のように出現頻度が得られた場合を考える.
| a | b | c | d | e | f |
|---|---|---|---|---|---|
| 2 | 8 | 2 | 3 | 3 | 4 |
最も頻度の低い2つを繋げると
| a,c | b | d | e | f |
|---|---|---|---|---|
| 4 | 8 | 3 | 3 | 4 |
この 4 も加えた中で, 最も頻度の低い2つを繋げれば
| a,c | b | d,e | f |
|---|---|---|---|
| 4 | 8 | 6 | 4 |
これを繰り返していけば
のように最終的には1つの木が作られる. これがハフマン木である.
この木を用いて, 各文字に割り当てるビット列を求める. そのためには各ノードから見て左の枝に 0, 右の枝に 1 を割り当て, 根から各文字まで辿ったときに通った枝に振られた数字を繋げればよい.
上図を見れば各符号は接頭符号で, ビット列は出現頻度の高いものほど短くなっていることが分かる.
デコード
以下の流れでデコードが行われる.
- ヘッダーからハフマン木を復元する.
- ハフマン木からビット列と文字の対応表を作る.
- ビット列を探索し, 文字に変換する.
実装
ソースコードは次のリポジトリに置く.
環境
$ rustc --version
rustc 1.64.0 (a55dd71d5 2022-09-19)
エンコード
各文字の出現頻度を調べる
文字列中の全ての文字について出現数を数えてやればよい. 次のハフマン木の構築に使用するため, 出現頻度を要素として持つ BinaryHeap を作っている.
ハフマン木を作る
前述の通り BinaryHeap を用いる.
各文字とビット列の対応表を作る
ハフマン木を前置順で深さ優先探索し, 文字をキー, ビット列を値とする HashMap を作ればよい. 再帰を使うと短く書ける.
平文をビット列へ変換する
単純に1文字ずつ対応表にかけ, ビット列に変換している.
ハフマン木をエンコードする
ハフマン木を後置順で深さ優先探索し, 以下のルールに従ってビット列へ変換する.
- 葉ノードの場合, 1 とそれに続けてデータを書き込む.
- 枝ノードの場合, 0 を書き込む.
- 最後には, 木の終端を示す 0 を書き込む.
ヘッダーを作る
ヘッダーは次のように定義する.
- u32 compressed_char_count : 符号化したビット列の長さ
- u32 original_char_count : 符号化前の平文の長さ
- u32 tree_topology_size : エンコードしたハフマン木の長さ
- BitArray tree_topology : エンコードしたハフマン木
この定義は Purdue 大学の講義資料を参考にした. なお, エンコードされたハフマン木はそれ単体で復号可能であるため, 他の3つはなくてもよい.
デコード
ハフマン木を復元する
ビット列の先頭から見ていき, 1 ならばデータを基に葉ノードを生成し, スタックに追加する. 0 ならばスタックから2つノードを取り出し枝ノードを生成, 同様にスタックに追加する. そして 0 を見つけたときに, スタックの長さが1ならば, 木の終端に達しているため, 完了となる. 詳細は以下の記事を参照のこと.
ビット列と文字の対応表を作る
エンコード時に作った対応表のキーと値を入れ替えたものを作るため, 処理は同様である.
ビット列を平文へ変換する
ハフマン符号は瞬時復号可能であるから, 先頭から見ていくだけでよい.
結果
以下の文章で試してみる.
Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod
tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim
veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea
commodo consequat. Duis aute irure dolor in reprehenderit in voluptate
velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat
cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id
est laborum.
エンコードした結果は
Elapsed Time: 7570 μs
Compressibility: 62 %
Code: 000000000000000000000111001101110000000000000000000000011011110100000000000000000000000100011000100101100101110001010111000001011011000101101001010111001010110111001010011001010001010101111000010111011010110011100101100110101100010010100010010110100010101010100100101110000101110101000101101111101100001010111010010110001110110110100010010000010111001110110010001011001010000001100000100001001111101111100010000111100011110111110111011000000110000100110111000011010110100110111111110100000001101011010000101111001111101101010111110100111010011010011110100100001001111001011000101010110011110111100010011010000000110111001111111011101110110001101111001011111100101111000111011101010111110111000011000010011000101011011000111101001111010111010110101100111101011000011001011010110000100111111011111010110111011000000110000100111111010111100101100110101100111010010001001000001011110010110111110011011011101011011110101001101111101001111011101011100101010011011111001100101111010100110011011100000011000000101110011110011001011000111001010010001111110111011110110001111101001011000110101001101000110000101110011100010001100110111101101000110000110010110101100001000011110011001010011110000111001111010110100100010010000010111001000011101111011000111011111001110101101000101111011110001110110001101011010000101111001111000001011110011010011011111001101100011100111100110100101111010111111000101000111010011111101110110000001100001001100010101110010011110000101001111011011010111101011110111110100001101011000101011100110010100000010111000011010100110101111110011001011110001001101011011111110011100111111010110001000100010111101111101110110000001100001001111110111101111100110100011101100110011001101011001010111000100011001110000011001010000110011010011101000110111110011000010110001101101111000011010111101110100110111000010101101011010001011010110100111111011010011010110101100111000010011110110011010100110101100101100001011100000101001000001111011111010110100000001101110001110101101011000101011101011001110001000011001110000001011100111010000110100011010000110110001100111011101111111100111101000111010110101101011110000001000100110101101001010100110111110001111011101111111001010110000110010110101100001000111101110110111
このビット列に対してデコードすれば
Elapsed Time: 9024 μs
Plain Text: Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.
となった. そこそこの圧縮率だが成功している.
参考文献
Purdue 大学の講義資料.
Jeff Erickson 著 Algorithms の電子版.
4章 Greedy Algorithms 内にハフマン符号の説明がある.
TypeScript での実装記事.
Discussion