2013年4月15日
編集可能

らこらこらこ～ｗ で学ぶ圧縮講座

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

まとめ

メニュー

  • 　
    　
    　

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

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

  • 　
    　
    　
    　

  • かずー @kazoo04 2013-04-15 17:24:38
    「らこらこらこ〜ｗ」この表現、とても冗長ですね。これを「らこx3〜ｗ」と書けば2文字節約できます。これがランレングス法でこれを応用したものがFAXなどで実際に利用されています。
  • かずー @kazoo04 2013-04-15 17:25:29
    これだと「らこここ〜ｗ」になるよね
  • かずー @kazoo04 2013-04-15 17:28:18
    「らこらこらこ〜ｗ」を「らこ[2文字戻って4文字コピー]〜ｗ」という意味で「らこ2:4〜ｗ」と表現しても圧縮できますね。これがLZ77という圧縮アルゴリズムでこれを改良したLZSSを採用したものがみなさんご存知のzipです。
  • かずー @kazoo04 2013-04-15 17:35:56
    ところで、"ら"は2進数で表現すると「11100011 10000010 10001001」の24bitもあります(UTF8)。他の文字も24bitなので「らこらこらこ〜ｗ」は192bitも使ってしまいます！ところが、「ら、こ、〜、ｗ」の4種類しか文字がないなら最適化できますね
  • かずー @kazoo04 2013-04-15 17:37:23
    たとえば、ら=00, こ=01, 〜=10, ｗ=11 にしたらどうでしょうか。「らこらこらこ〜ｗ」は192bitからまさかの16bitまで減らせます。もちろん、各文字がどんな表記かを記録するぶんファイルサイズは増えてしまいますが、トータルでは大きく減らせます。
  • かずー @kazoo04 2013-04-15 17:39:10
    さらに考えてみると、「らこらこらこ〜ｗ」は「ら」と「こ」がよく出現します。そこで、ら=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^)ノ かずかずかず～ｗ
  • かずー @kazoo04 2013-04-15 18:03:21
    さて、最適な接頭符号をハフマン符号で求めるにはどうしたらいいのでしょうか？実はとても簡単にできます。まずは各文字の出現数をすべて書きだしておきます。 ら 3 こ 3 〜 1 ｗ 1
  • かずー @kazoo04 2013-04-15 18:04:49
    最初に、出現回数が少ないものを2つ選びます。そして線で結んで、出現回数を足したものをメモしておきます。今回は「〜」1回と「ｗ」1回なので、これをくっつけて出現回数を合計した「2」とメモしておきます。 　 2 　／＼ 　〜 ｗ
残りを読む(32)

あわせて読みたい

作者のオススメ

いま話題のおすすめまとめ

コメント

「ネタ」の人気まとめ

「ネタ」の新着まとめ

まとめマイスター

公式アカウント

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

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

ログインして広告を非表示にする
今月は33462はてブされました!あなたはもうチェックした?
soft_HAT
ふにゃ帽子 @soft_HAT
A.はい、たぶん帽子ですっ♪(੭ु⁾⁾＞ω＜)੭ु⁾⁾ /高専/プログラミング/その他ツイプロ(URL)へどうぞ！
ログインして広告を非表示にする

ツイッターの話題をいち早くお届け！

トゥギャッチ

「その他」の注目キュレーター

カテゴリーを見る
携帯ショップで「新しいスマホは今の1.5倍の処理能力があ.. 1 user
2017-09-19のまとめ用のメモ
9/17(日) Tokyo HoloLens ミートアッ.. 1 user
最近のエンジニアの退職エントリまとめ
NaITE24 テストカタマリー勉強会