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

かずーさん、圧縮技術についての本でも書くの!?Σ
圧縮 かずー氏 技術 らこらこらこ〜w
soft_HAT 30622view 23コメント
155
ログインして広告を非表示にする
  •  
     
     

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

  •  
     
     
     

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

コメント

カテゴリーからまとめを探す

「ネタ」に関連するカテゴリー

ログインして広告を非表示にする
ログインして広告を非表示にする