bzip2を読む ハフマン符号1

こんにちは、junkawaです。

本記事では、bzip2で使われるハフマン符号について紹介します。

これまでのあらすじ

bzip2ではブロックソート、MTFを使って、下記方針のもとに入力データを変換します。

　・データに含まれるシンボルの出現頻度に偏りがでる
　・元のシンボルに戻すことが簡単な方式
　　(簡単とは、戻すための付加データが少ない、高速に復号できる、など)

この段階ではbzip2の目的である、データサイズの圧縮は実現できていません。

これから説明する、「ハフマン符号化」によって、データの圧縮を行います。

ハフマン符号化とは

出現頻度の高いシンボルに短い符号を割り当て、出現頻度の低いシンボルに長い符号を割り当てます。

　「aaaaaaaaaaabcde」
　出現頻度 a=11回、b=1回、c=1回、d=1回、e=1回
　ハフマン符号化 a=0、b=100、c=101、d=110、e=111
　符号化後 00000000000100101110111 → 23ビット

15文字のアルファベットは15バイト(120ビット)ですが、ハフマン符号化後は23ビットになります。

備考
a,b,c,d,e の5種類のシンボルなので、それぞれに均等な長さの符号を割り当てる場合を考えます。2^3が8なので、3ビットあれば足ります。
a=000、b=001、c=010、d=011、e=100 などで割り当てます。
このとき、15シンボル * 3ビット = 45ビットとなります。
よって、ハフマン符号の方が短いビット数になります。

よく出るシンボルを短くして、あまり出ないシンボルを長くして、全体を短くするという考えは理にかなっていると思います。

このようにして、入力データの出現頻度の偏りを利用して、データ長を短くしてデータサイズを圧縮します。

ハフマン符号では、シンボルと符号の対応を記したテーブル(Huffman code table)が必要となります。

上記の例では、a=0、b=100、c=101、d=110、e=111 がテーブルになります。

復号時には符号からシンボルへの変換を行います。これにはテーブルが必要です。したがって、圧縮データにはハフマンテーブルを含めます。

ハフマン符号の構成方法

1. シンボルに符号長を割り当てる
2. シンボルに符号を割り当てる

1. シンボルに符号長を割り当てる

シンボルの出現頻度に応じて、シンボルに符号長を割り当てます。

すなわち、出現頻度が高いシンボルには短い符号長(2,3ビット)を割り当て、出現頻度が低いシンボルには長い符号長(最大17ビット)を割り当てます。

具体的な方法は別の記事で紹介します。ここでは、簡単な方針だけ紹介します。

前提条件として、符号は2進数で割り当てるとします。

2進数で符号を割り当てるので、データ構造として二分木を利用します。
二分木の左右の枝に2進数の0,1を割り当てます。二分木の葉をシンボルとすると、根から葉までの枝をたどって得られた0,1のパターンを符号とします。

また、根から葉までの深さが符号長となります。

二分木の構成方法は別の記事で紹介しますが、方針として、
出現頻度の高いシンボルに対応する葉が根に近い場所に配置されるようにします。

2. シンボルに符号を割り当てる

bzip2 で行うハフマン符号は、カノニカルハフマン符号(Canonical Huffman Code)と呼ばれるものです。

一般的なハフマン符号では、符号の割当(枝への0,1の割当)は自由なのですが、カノニカルハフマンでは、「符号長が同じシンボルは、符号の辞書式順とシンボルの順序が同じ」になるように符号を割り当てる、という制約があります。

この制約のおかげで、シンボルの符号長が決まれば、一意にシンボルに符号を割り当てることができます。

カノニカルハフマン符号の実現方法については別記事で紹介します。

参考
https://en.wikipedia.org/wiki/Bzip2
https://en.wikipedia.org/wiki/Canonical_Huffman_code

カノニカルハフマンでは、シンボルと符号長から、符号が一意に割り当てられるので、ハフマンテーブルとして圧縮データに保存する情報は、「シンボルと符号長の組」になります。

まとめ

ハフマン符号の概略について紹介しました。

次回は、シンボルの出現頻度から符号長を割り当てる関数BZ2_hbMakeCodeLengths()について紹介します。