こうしてテキストを圧縮する

上段：投稿日

中段：カテゴリ

下段：サブテーマ

ブログナンバー：

６４

　　　　

０８月０６日（日）

ＩＴ関連のカタカナ語と略語ABCに強くなるブログ　(18)

ハフマンの符号化

通信技術が発達して，伝送路も仮想的に広くなり，大量のデータがスピーディーに送られるようになったが，人が読めるデータそのままではデジタル情報の量も多くなり，送信に時間がかかることになる。情報量を少なくする方法が圧縮技術である。画像や音声の場合はよく知られている（JPEG方式やPCM方式）。これらは非可逆圧縮の技術が使われる。しかし，テキストの場合は圧縮できても復元できなければ読むことができない。可逆符号化またはハフマン符号化と呼ばれる技術は復元できる。
	簡単のため，AからFまでの文字だけを使った文をここに書いて，それを圧縮してから元の文に戻す手順をやってみよう。 原文を　Acbd eaf dfebe acedfa cabafe caffee deace a eec efefa cdecaa edacee adecbeb.（文に意味はない） とする。こうした文を圧縮する原理は，文字ごとに８ビット使われている情報量をそれ以下のビット数で表すことである。それだけ情報量が減少することになる。aからfと空白の７種類を頻度の多い順に次のようなコードに変えてしまう。 01，11，000，001，101，1000，1001これらはでたらめに並んでいても特定できる数字の並びになっている（ここが発明の核心だ）。
上の原文の文字数を数えると a=14，b=5，c=10，d=7，e=19，f=8，空白=12　である。 これを表の形に整理してみると以下のようになる。 文字 a b c d e f 空白 合計 個数 14 5 10 7 19 8 12 75 順位 2 7 4 6 1 5 3 コード 11 1001 001 1000 01 101 000 コードビット数 2 4 3 4 2 3 3 使用 ビット数 2*14 4*5 3*10 4*7 2*19 3*8 3*12 204
	こうしてコードに変換すると，文頭のAcbdは"1100110011000"となる。今度はこれを逆に読み替えてみる。始めの11と並ぶコードはa，次の00はないから001を探すとcが見つかる。次の10はない。100もない。1001がbとなる。次の10はない。100もない。1000がdとなる。必ずacbdに復元される。こうした辞書のような情報は圧縮したデータにヘッダとして付加しておく。この圧縮によってどれだけ情報量が減少するか計算してみると，空白を含めて７５文字あったから，75×8（ビット）すなわち６００ビットが２０４ビット＋辞書分に減少する。通常辞書の文字の種類はアルファベット26文字と記号何通りのうち使われたもののみだからそんなに多くはならない。こうしてテキストは１／３くらいに圧縮できる。