【基本情報技術者試験】ハフマン符号化

本日のテーマは「ハフマン符号化」です。

聞いたことがない言葉ですね。

基本情報技術者試験や応用情報技術者試験で出題される問題である ハフマン符号化、過去問だけをみると難しく感じる問題です。

ただ、ハフマン符号化の動きを理解してしまえば、そこまで難しい問題ではありません。

本記事では、ハフマン符号化について図解で分かりやすく解説しています。

符号化とは

符号化とは、データを"0"と"1"の2進数に置き換えることです。

コンピュータは"0"と"1"の集まりしか理解できません。そのため、コンピュータに処理をさせるにはデータを2進数に変換する必要があります。この作業が符号化です。

スポンサーリンク

例えば「A」を「00」、「B」を「01」、「C」を「10」、「D」を「11」というように置き換えるものとします。

この場合、文字列「ABCD」は「000101」に置き換えることができます。この作業が符号化です。

符号化は、処理効率の側面からできるだけ少ないビット数で2進数へ変換することが求められています。

例えば「AAA」を「000000」の6ビットに変換するよりも「000」の3ビットに変換できた方が、データ量が少なくなり、メモリの使用量が減り処理の高速化に繋がります。

このデータをできるだけ少ないビット数で2進数へ変換する方法の1つが「ハフマン符号化」です。

ハフマン符号化とは

ハフマン符号化とは、データの出現頻度に着目した圧縮方法です。出現確率が高いデータには短い符号を、低いデータには長い符号を与えることで圧縮を効率よく行う方法です。

例えば「ABAAACBDBA」という文字列を以下のルールで符号化すると「00010000001001110100」となり、長さは20ビットです。

この「ABAAACBDBA」をハフマン符号化で符号化すると「01000011010111100」となり、長さは17ビットです。（85%の圧縮率 ※圧縮率は文字の出現頻度により変わる）

このようにハフマン符号化を使うことで、データをできるだけ少ないビット数で2進数へ変換することができます。

ハフマン符号化でデータを圧縮するまでの流れ

ハフマン符号化では、ハフマン木と呼ばれる木構造を用いて符号化します。今回の例では「ABAAACBDBA」のデータをハフマン符号化で符号化します。

スポンサーリンク

ハフマン木（木構造）の作り方

ハフマン木は次の3つの手順で作成します。

【手順1】各データを出現確率の高い順に並べる

各データを出現確率の高い順に並べます。

今回の例では「ABAAACBDBA」のデータをハフマン符号化で符号化します。出現確率はAが50%(5回)、Bが30%(3回)、CとDが10%(1回)なので、出現確率の高い順（A、B、C、D）に並べます。

【手順2】最も出現確率の低い2つを1つにする

出現確率の高い順に並べた後は、最も出現確率の低い2つをつなぐ「親」を作り1つにします。今回の例では「C」と「D」が最も出現確率が低いので、2つを繋ぐ「親CD」を作ります。

【手順3】手順2を繰り返して木構造を完成させる

次に最も出現確率が低い2つは「B」と「CD」なので、「B」と「CD」をつなぐ「親BCD」を作ります。

最後に「A」と「BCD」をつないで木構造（ハフマン木）の完成です。

ハフマン木（木構造）に「0」と「1」を割り振る

作成したハフマン木（木構造）に「0」と「1」を割り振ります。今回の例では左に「0」、右に「1」を割り振っています。（左に「1」、右に「0」でも可）

ハフマン木（木構造）から符号表を作る

ハフマン木（木構造）を上から順にたどり符号表（文字と符号の対応表）を作ります。

[符号表]

この符号表どおりに符号化すると「ABAAACBDBA」を「01000011010111100」に変換できます。

平均ビット長の求め方

各文字を表すビット数とその出現確率をかけたものを足し合わせて平均ビット数を求めることができます。

例えば、上記の符号表の平均ビット長は1.7ビットです。

基本情報技術者試験 過去問の解説

スポンサーリンク

基本情報技術者平成30年秋期 午前問4

ハフマン符号化は出現率の高い文字は短い符号に変換し、出現率の低い文字は長い符号に変換します。

この際に符号は重複しないようする必要があります。（設問の表を見ると"00"、"01"、"10"、"111"は既に割当て済なので、Dにはこれ以外のビット列から開始する必要がある）

また下記のように、符号表からハフマン木を作成して考えることもできます。ハフマン木を作成した結果、Dの符号が「110」になることがわかります。

基本情報技術者平成23年特別 午前問3

平均ビット数は、各文字を表すビット数とその出現確率をかけたものを足し合わせて平均ビット数を求めることができます。

計算結果より平均ビット数は「1.8」となり「イ」が正解です。