[表示 : 全て 最新50 1-99 101- 201- 301- 401- 501- 2chのread.cgiへ]
Update time : 05/09 11:59 / Filesize : 137 KB / Number-of Response : 557
[このスレッドの書き込みを削除する]
[+板 最近立ったスレ&熱いスレ一覧 : +板 最近立ったスレ/記者別一覧] [類似スレッド一覧]


↑キャッシュ検索、類似スレ動作を修正しました、ご迷惑をお掛けしました

最強の圧縮アルゴリズムを語ろう



268 名前:デフォルトの名無しさん mailto:sage [2006/06/09(金) 08:47:12 ]
FAという訳ではないんだが一応答えらしきものを示しておこうか。

一般に辞書との一致で置き換えるアルゴリズムは圧縮率が悪い。
何故か?
今、abc...bcd...abcdという文字列があったとする。
3つ目のabcdを符号化したい。
選択肢としてabc|dとすることも出来るし、
またはa|bcdとすることも出来る。
場合によってはa|b|c|dとしてもいい。
そしてこれらの選択肢は全て結果が等しい、つまり等価なわけだ。
同じ結果に対して別の選択肢が存在するという事は、
それはつまり冗長だということになる。
等価であるならば一つに纏めて確率を上げなければならない。

極端な例を挙げるとすると、纏め(られ)ないということは、
aaaabbbcという文字列があって、これの確率を求めた時に、
1. a 3/8
2. a 1/8
3. b 3/8
4. c 1/8
このような状態になってしまうことを意味するわけだ。
'a'を符号化する時に1,2のどちらを選んでも結果は等しい。
しかしこの時、'a'の確率は4/8でなくてはいけない。
しかし実際には分かれてしまっているため、1の'a'を選んで符号化しなければならず、
'a'一文字につき1/8ずつ無駄を増やしているということになる。

じゃあどうすればいいのか?
書くのが疲れたので終わり。ごめん。






[ 続きを読む ] / [ 携帯版 ]

全部読む 前100 次100 最新50 [ このスレをブックマーク! 携帯に送る ] 2chのread.cgiへ
[+板 最近立ったスレ&熱いスレ一覧 : +板 最近立ったスレ/記者別一覧]( ´∀`)<137KB

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef