ハフマン符号化のJavaでの実装

突然ですが、皆さんはモールス信号をご存知でしょうか？

有名なものは「SOS」ですね。S「・・・」とO「－－－」を組み合わせて「・・・－－－・・・」（トントントンツーツーツートントントン）と打ちます。

以下のリンクを辿ってアルファベットのモールス信号の一覧を見てください。（https://www.jrc.co.jp/casestudy/column/04）

例えば、eは短く、zは長いですが、これは英文の文字の出現頻度と相関しています。つまり、出現頻度の高い文字は短く、出現頻度の低い文字は長くなっています。これと同じ考え方をするのがハフマン符号化です。

ハフマン符号化は、可逆圧縮アルゴリズムの一種です。

ハフマン符号化は、ランレングス符号化とは異なり、頻繁に出現する文字やシンボルに短いビットパターンを割り当て、まれに出現する文字やシンボルに長いビットパターンを割り当てることにより、圧縮率を向上させます。なお、符号化とはデータを0,1のビットで表現することをいいます。

ハフマン符号化では、まずデータの出現頻度を調べ、その情報を使用してハフマン木を構築します。ハフマン木は、出現頻度が高いデータほど木の根に近く配置され、出現頻度が低いデータほど木の葉に近く配置されます。次に、ハフマン木の左側に0を、右側に1を割り当てて、各データに対応する符号を生成します。この符号は、木の根から各葉に至るまでの0と1の組み合わせで表されます。

ハフマン符号化は、圧縮アルゴリズムの中でも効率的なものの一つです。ハフマン符号化は、音声、画像、ビデオ、テキストなど、様々な種類のデータの圧縮に利用されています。

ハフマン符号化は以下の分野で活用されています。

1. データ圧縮: ハフマン符号化は、元のデータを効率的に圧縮するために使用されます。特に、テキストや画像、音声、ビデオなど、大量のデータを扱う場合によく使われます。zipやLHZ圧縮でも使われているアルゴリズムです。
2. 通信システム: ハフマン符号化は、通信システムにおいて、データ転送の効率化や誤り検出・訂正などに利用されます。例えば、音声圧縮の規格であるMP3やAAC、画像圧縮の規格であるJPEGやPNG、さらには通信規格のLTEや5Gなど、様々な通信技術においてハフマン符号化が使用されています。

講師が実際にハフマン木を書いて説明します。

基本情報技術者試験の過去問を解いてみましょう。

練習問題1

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

＜サンプルプログラム＞

＜出力結果＞

Original text: baggage Encoded text: 110 10 0 0 10 0 111