soft_HAT
※注意事項
かずーさんのツイート（特に後半）は、改行を前提としたツイートがあります。もし改行が反映されていない場合、後半で「 ／＼ 」とか出てきたらツイート日時の部分をクリックし、Webで見てください。''
4/15 22:20 追記:図を書いて見ました。
図に関しては@lindwurm_に問い合わせてください。
Kazuya Gokita
@kazoo04
「らこらこらこ〜ｗ」この表現、とても冗長ですね。これを「らこx3〜ｗ」と書けば2文字節約できます。これがランレングス法でこれを応用したものがFAXなどで実際に利用されています。
Kazuya Gokita
@kazoo04
「らこらこらこ〜ｗ」を「らこ[2文字戻って4文字コピー]〜ｗ」という意味で「らこ2:4〜ｗ」と表現しても圧縮できますね。これがLZ77という圧縮アルゴリズムでこれを改良したLZSSを採用したものがみなさんご存知のzipです。
Kazuya Gokita
@kazoo04
ところで、"ら"は2進数で表現すると「11100011 10000010 10001001」の24bitもあります(UTF8)。他の文字も24bitなので「らこらこらこ〜ｗ」は192bitも使ってしまいます！ところが、「ら、こ、〜、ｗ」の4種類しか文字がないなら最適化できますね
Kazuya Gokita
@kazoo04
たとえば、ら=00, こ=01, 〜=10, ｗ=11 にしたらどうでしょうか。「らこらこらこ〜ｗ」は192bitからまさかの16bitまで減らせます。もちろん、各文字がどんな表記かを記録するぶんファイルサイズは増えてしまいますが、トータルでは大きく減らせます。
Kazuya Gokita
@kazoo04
さらに考えてみると、「らこらこらこ〜ｗ」は「ら」と「こ」がよく出現します。そこで、ら=0, こ=1, 〜=10, ｗ=11 としたらどうでしょう？さらに減らせそうですね。これを可変長符号といいます。しかしこの方法では問題があります。どこでしょう？
Kazuya Gokita
@kazoo04
先ほどのように、ら=0, こ=1, 〜=10, ｗ=11 としたときに、
"11101"はどう解凍すればよいでしょうか？「こここらこ」とも解釈出来ますが、「ｗ〜ら」と解凍することもできます。一意に決定できないのです。先頭から順に見ていって一意に決定できるものを接頭符号といいます。
Kazuya Gokita
@kazoo04
たとえば、ら=0, こ=10, 〜=110, ｗ=111 としたらどうでしょうか。これならどんな表記でも必ず一意に決定できます。最適な接頭符号の表記を探す方法はあるでしょうか？実はハフマン符号という方法を使えば、簡単に最適な表現を見つけることができます。
Kazuya Gokita
@kazoo04
さて、最適な接頭符号をハフマン符号で求めるにはどうしたらいいのでしょうか？実はとても簡単にできます。まずは各文字の出現数をすべて書きだしておきます。
ら 3
こ 3
〜 1
ｗ 1
Kazuya Gokita
@kazoo04
最初に、出現回数が少ないものを2つ選びます。そして線で結んで、出現回数を足したものをメモしておきます。今回は「〜」1回と「ｗ」1回なので、これをくっつけて出現回数を合計した「2」とメモしておきます。
2
／＼
〜 ｗ
