10周年のSPコンテンツ!
161

 
 
 

※注意事項 かずーさんのツイート(特に後半)は、改行を前提としたツイートがあります。もし改行が反映されていない場合、後半で「 /\ 」とか出てきたらツイート日時の部分をクリックし、Webで見てください。''

4/15 22:20 追記:図を書いて見ました。
図に関しては@lindwurm_に問い合わせてください。

 
 
 
 

Kazuya Gokita @kazoo04
らこらこらこ〜w」この表現、とても冗長ですね。これを「らこx3〜w」と書けば2文字節約できます。これがランレングス法でこれを応用したものがFAXなどで実際に利用されています。
Kazuya Gokita @kazoo04
これだと「らこここ〜w」になるよね
Kazuya Gokita @kazoo04
らこらこらこ〜w」を「らこ[2文字戻って4文字コピー]〜w」という意味で「らこ2:4〜w」と表現しても圧縮できますね。これがLZ77という圧縮アルゴリズムでこれを改良したLZSSを採用したものがみなさんご存知のzipです。
Kazuya Gokita @kazoo04
ところで、""は2進数で表現すると「11100011 10000010 10001001」の24bitもあります(UTF8)。他の文字も24bitなので「らこらこらこ〜w」は192bitも使ってしまいます!ところが、「」の4種類しか文字がないなら最適化できますね
Kazuya Gokita @kazoo04
たとえば、=00, =01, =10, =11 にしたらどうでしょうか。「らこらこらこ〜w」は192bitからまさかの16bitまで減らせます。もちろん、各文字がどんな表記かを記録するぶんファイルサイズは増えてしまいますが、トータルでは大きく減らせます。
Kazuya Gokita @kazoo04
さらに考えてみると、「らこらこらこ〜w」は「」と「」がよく出現します。そこで、=0, =1, =10, =11 としたらどうでしょう?さらに減らせそうですね。これを可変長符号といいます。しかしこの方法では問題があります。どこでしょう?
Kazuya Gokita @kazoo04
先ほどのように、=0, =1, =10, =11 としたときに、 "11101"はどう解凍すればよいでしょうか?「こここらこ」とも解釈出来ますが、「」と解凍することもできます。一意に決定できないのです。先頭から順に見ていって一意に決定できるものを接頭符号といいます。
Kazuya Gokita @kazoo04
たとえば、=0, =10, =110,=111 としたらどうでしょうか。これならどんな表記でも必ず一意に決定できます。最適な接頭符号の表記を探す方法はあるでしょうか?実はハフマン符号という方法を使えば、簡単に最適な表現を見つけることができます。
Laco @laco0416
人の名前使って遊んで飽きたってそりゃないよ・・・
Kazuya Gokita @kazoo04
laco0416 へ 振込先の口座は前回と同じ所でお願いします
Laco @laco0416
この妻子持ち女装プログラマー人の名前使ってふぁぼ稼いだ挙句に金まで要求しやがるのか!!!
Laco @laco0416
kazoo04には賠償を求めたい
Laco @laco0416
三(^o^)ノ かずかずかず~w
Kazuya Gokita @kazoo04
さて、最適な接頭符号をハフマン符号で求めるにはどうしたらいいのでしょうか?実はとても簡単にできます。まずは各文字の出現数をすべて書きだしておきます。 ら 3 こ 3 〜 1 w 1
Kazuya Gokita @kazoo04
最初に、出現回数が少ないものを2つ選びます。そして線で結んで、出現回数を足したものをメモしておきます。今回は「」1回と「」1回なので、これをくっつけて出現回数を合計した「2」とメモしておきます。   2  /\  〜 w
残りを読む(32)

コメント

ふにゃ帽子 @soft_HAT 2013年4月15日
らこらこらこ~w で学ぶ圧縮講座 のまとめを作成しました。
ふにゃ帽子 @soft_HAT 2013年4月15日
まとめを更新しました。
ふにゃ帽子 @soft_HAT 2013年4月15日
後半はそれぞれのTwitterWebのページで見ないと結局わからないので、可読性を持たせたデコレーションは捨ててます。ごめんなさいっヾ(。>﹏<。)ノ゙
らこ @laco0416 2013年4月15日
らこらこらこ~w
M.Aono @aomonoya 2013年4月15日
らこらこらこ~w
ほた @lindwurm 2013年4月15日
図を追加しました。
Kazuya Gokita @kazoo04 2013年4月17日
まとめを更新しました。
Kazuya Gokita @kazoo04 2013年4月17日
6000views超えてて草不可避
ほた @lindwurm 2013年4月17日
7000らこらこおめ
財布 @kagee04 2013年5月21日
8000らこらこおめ
Kazuya Gokita @kazoo04 2014年2月3日
10000らこらこおめ(困惑)
Kazuya Gokita @kazoo04 2015年11月9日
1年ぶりにらこらこしておく
ログインして広告を非表示にする
ログインして広告を非表示にする