パソコンでファイルの圧縮などしたことはありますか？
zipファイルだったり、lzhだったりする拡張子を持っていて、
5MBのファイルを3MBにしてくれたりします。
なのでパソコンの中身を圧縮します。
みなさんzipなどいろいろ使ったことがあるでしょう！
現実世界だったら、布団を圧縮袋で圧縮しますが、
パソコンの中身はそんなことができません。
ではパソコンはどうやってデータを圧縮しているのでしょうか？
データは0101の連続で表されるって聞きませんか？
例えばです。
Aを00
Bを01
Cを10
Dを11
と表すとしましょう。
AABBAABBCCDD~~~~~~~~~~~~~みたいな文字列は0000010100101011~~~~と表されると思います。
でも待て待てと…
このAを00 Bを01 Cを10 Dを11に置き換えようって言う発想はA、B、C、Dのそれぞれの出現頻度を考慮しておらず…
とりあえずAを1、Bを01、Cを001、Dを000って決めればいいんじゃね？
という発想です。
ピアノの楽譜だって同じ部分の小節を楽譜にもう一度書きません。
こういう反復記号で省略します。
コンピュータの世界でも何度も登場するビットは省略してしまおうという考えがあります。
ここで登場するのが「ハフマン符号」ってやつです。
入力 DAEBCBACBBBC に対して上記のアルゴリズムを適用すると…
純粋にA~Dを2進法で書くより…
文字の出現回数で
0,10,110,1110,1111を割り当てれば文字数＝スペースを省略できます。
例えば…
「11111110」という文字列があったとしましょう…
0=A B=10=B 110=C 1110=D 1111=Eを左から当てはめていき迷う。
11111110を見ます。
↓
いきなり1が7連続やんけ！
↓
ってことは11111110 の最初の1111は
Eで確定です。
11111110→E+1110
あとはこの1110のハフマン符号を解けば解決です。
1110=Dなので、 1111110=「DE」を表していたことがわかります。
0を区切りにすることで圧縮が可能になる。
010を見たら…「0」「10」
でも01101→ハフマン記号のルールに則っていないのでこのデータは壊れています。
01101のデータがなぜ壊れているとわかるのでしょう？
0=A B=10=B 110=C 1110=D 1111=E
まず01101の一番左の0はA以外にありません。
01101=A1101
次にA1101はAB1 になるはずです。
0が出てきたらしれは文字の区切りです。
そうすると最後の1は？
これがファイルを正しく回答できなかったり、文字化けの原因です。
ハフマン符号などの一定のルールに基づいてファイルを圧縮したけれど、配送途中でハフマン符号のルールを満たす文字列ではなくなり、ハフマン符号で圧縮した文字列をもとに戻せなくなったことを意味しています。
最後に1で終わるのは1111=Eしかないはずなのに、この文字列はどんなに上手に区切っても元に戻せない01の羅列になっています。
これがハフマン符号による文字列の圧縮の仕組みです。
