編集可能

らこらこらこ~w で学ぶ圧縮講座

かずーさん、圧縮技術についての本でも書くの!?Σ
162

 
 
 

※注意事項

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

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

 
 
 
 

Kazuya Gokita @kazoo04

らこらこらこ〜w」この表現、とても冗長ですね。これを「らこx3〜w」と書けば2文字節約できます。これがランレングス法でこれを応用したものがFAXなどで実際に利用されています。

2013-04-15 17:24:38
Kazuya Gokita @kazoo04

これだと「らこここ〜w」になるよね

2013-04-15 17:25:29
Kazuya Gokita @kazoo04

らこらこらこ〜w」を「らこ[2文字戻って4文字コピー]〜w」という意味で「らこ2:4〜w」と表現しても圧縮できますね。これがLZ77という圧縮アルゴリズムでこれを改良したLZSSを採用したものがみなさんご存知のzipです。

2013-04-15 17:28:18
Kazuya Gokita @kazoo04

ところで、""は2進数で表現すると「11100011 10000010 10001001」の24bitもあります(UTF8)。他の文字も24bitなので「らこらこらこ〜w」は192bitも使ってしまいます!ところが、「」の4種類しか文字がないなら最適化できますね

2013-04-15 17:35:56
Kazuya Gokita @kazoo04

たとえば、=00, =01, =10, =11 にしたらどうでしょうか。「らこらこらこ〜w」は192bitからまさかの16bitまで減らせます。もちろん、各文字がどんな表記かを記録するぶんファイルサイズは増えてしまいますが、トータルでは大きく減らせます。

2013-04-15 17:37:23
Kazuya Gokita @kazoo04

さらに考えてみると、「らこらこらこ〜w」は「」と「」がよく出現します。そこで、=0, =1, =10, =11 としたらどうでしょう?さらに減らせそうですね。これを可変長符号といいます。しかしこの方法では問題があります。どこでしょう?

2013-04-15 17:39:10
Kazuya Gokita @kazoo04

先ほどのように、=0, =1, =10, =11 としたときに、 "11101"はどう解凍すればよいでしょうか?「こここらこ」とも解釈出来ますが、「」と解凍することもできます。一意に決定できないのです。先頭から順に見ていって一意に決定できるものを接頭符号といいます。

2013-04-15 17:43:13
Kazuya Gokita @kazoo04

たとえば、=0, =10, =110,=111 としたらどうでしょうか。これならどんな表記でも必ず一意に決定できます。最適な接頭符号の表記を探す方法はあるでしょうか?実はハフマン符号という方法を使えば、簡単に最適な表現を見つけることができます。

2013-04-15 17:46:48
Laco @laco0416

人の名前使って遊んで飽きたってそりゃないよ・・・

2013-04-15 17:47:37
Kazuya Gokita @kazoo04

laco0416 へ 振込先の口座は前回と同じ所でお願いします

2013-04-15 17:49:04
Laco @laco0416

この妻子持ち女装プログラマー人の名前使ってふぁぼ稼いだ挙句に金まで要求しやがるのか!!!

2013-04-15 17:49:57
Laco @laco0416

kazoo04には賠償を求めたい

2013-04-15 17:53:53
Laco @laco0416

三(^o^)ノ かずかずかず~w

2013-04-15 17:54:05
Kazuya Gokita @kazoo04

さて、最適な接頭符号をハフマン符号で求めるにはどうしたらいいのでしょうか?実はとても簡単にできます。まずは各文字の出現数をすべて書きだしておきます。 ら 3 こ 3 〜 1 w 1

2013-04-15 18:03:21
Kazuya Gokita @kazoo04

最初に、出現回数が少ないものを2つ選びます。そして線で結んで、出現回数を足したものをメモしておきます。今回は「」1回と「」1回なので、これをくっつけて出現回数を合計した「2」とメモしておきます。   2  /\  〜 w

2013-04-15 18:04:49
残りを読む(32)

コメント

ふにゃ帽子 @soft_HAT 2013年4月15日
らこらこらこ~w で学ぶ圧縮講座 のまとめを作成しました。
0
ふにゃ帽子 @soft_HAT 2013年4月15日
後半はそれぞれのTwitterWebのページで見ないと結局わからないので、可読性を持たせたデコレーションは捨ててます。ごめんなさいっヾ(。>﹏<。)ノ゙
0
Kazuya Gokita @kazoo04 2013年4月17日
まとめを更新しました。
0
Kazuya Gokita @kazoo04 2013年4月17日
6000views超えてて草不可避
3
Kazuya Gokita @kazoo04 2014年2月3日
10000らこらこおめ(困惑)
0
Kazuya Gokita @kazoo04 2015年11月9日
1年ぶりにらこらこしておく
0