忍者ブログ

Infoseek検索 Infoseek検索

[PR]
×

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。

【2018年09月21日21:33 】 |
ログ・・・
二値レンジコーダでは正常なのに・・・
多値レンジコーダでは・・・;;

多分頻度表の部分だと思うのだが・・・
なかなか特定できない・・・

ログとして頻度表を出力・・・
でもログの容量が大きくなりすぎないか心配だなぁ・・・^^;

これくらいなら大丈夫かな?と・・・
あれっ・・・処理が終わらない・・・TT

強制終了だぁ~~~
ログがギガを超えてるぅ~~~orz

もっと小さいファイルで検証・・・
やっぱり頻度表の更新で・・・

でもそこは何度も見ていた箇所なのに・・・^^;
どこかであっているはずだ・・・
と思い込んでいたからだろうか???
【2008年06月02日07:30 】 | 圧縮 | コメント(0) | トラックバック(0)
二値から多値へ・・・
レンジコーダ・・・

複数の頻度表を切り替えながら
圧縮率を向上させようと試みたが・・・

切り替えのタイミングや合成の仕方が良くないのか
複雑にしただけで結果は良くない・・・TT

今度は二値レンジコーダから多値レンジコーダへ・・・
でも多分二値の方が良い結果になると思うのだが・・・
どれくらい違うのか試してみよう^^

あれっ???
コンパイルはできたのに・・・
圧縮して展開すると別物に・・・orz

二値では正常に動作するのに・・・
もぅいちどElias(エライアス)符号
算術符号の原理を・・・

適応型では下限値と下限値+幅の上位ビットが
同じになったらコードを出力するから・・・

展開時もコードと下限値は同じ符合になるんだぁwww
今までの謎が解けたぁ~~~^^
でもまだバグが残ってる・・・^^;
【2008年05月15日07:30 】 | 圧縮 | コメント(0) | トラックバック(0)
夢の圧縮・・・
以前データを1/100に圧縮できるという話題があったが・・・
今は昔、私もそれ以上のものを作っちゃった^^
あらゆるデータを0バイトに圧縮する夢の圧縮ソフト

分かり易い(かもしれない)解説

仲良し夫婦が・・・
「あれ」取ってくれ・・・と言われ
状況に応じ必要なものが手渡されるとき

全てのものは「あれ」に圧縮できる^^
さらには・・・

何かしようとしたとき
スッと必要なものが差し出されるなら・・・
「あれ」さえ不要になる
つまり情報量0にまで圧縮できる^^

しかし大多数においては・・・

「あれ」取ってくれ・・・
「それ」じゃない「あれ」だ
「あれ」と言ったら「これ」だろ・・・

となり犬も食わぬ何とかが・・・^^;
結論、夢の圧縮は不可能である

もう少し詳しい解説

ある平文を圧縮する場合
平文が決まれば圧縮すべき文字列が決まる

1文字ずつ圧縮していくと
次に圧縮すべき文字は決まっており出現確率は1である
(文字列が決まっているため次に決まった文字以外がくる事はない)

出現確率が1ならば情報量は0である
各文字の情報量が0ならばトータルも0である

つまり圧縮文の情報量は0である
よって夢の圧縮ソフトは0バイトに圧縮可能である^^

ただし前提条件がある^^;
平文が決まれば・・・
つまり平文と一緒にある場合のみ成立する・・・TT
【2007年06月06日07:30 】 | 圧縮 | コメント(0) | トラックバック(0)
頻度表と圧縮率
AAAABBCDDDDCCCBBの文字列を圧縮する場合

全体的にはA、B,C,Dの各文字が4回ずつ出現するため
各文字の出現確立は1/4であり
平均情報量Hは

H = 4×(-(1/4)log(1/4)) = 2 [ shannon / symbol ]

である(対数の底は2)
よって各文字2bitの符号長で最適に表現できる

しかし・・・
最初8文字を見るならば
各文字の出現確立は1/2,1/4,1/8,1/8であり
平均情報量Hは

H = (-(1/2)log(1/2))+(-(1/4)log(1/4))+2×(-(1/8)log(1/8))
= 1.75 [ shannon / symbol ]

である(対数の底は2)
ということは・・・
1.75(shannon/symbol)の情報量に対して
2(bit/symbol)の符号長を与えると無駄が生じる

この時各文字の符号を0,10,110,111とすると
各文字の符号長は1,2,3,3bitであるから平均符号長は

1/2×1bit + 1/4×2bit + 1/8×3bit + 1/8×3bit
= 1.75 [ bit / symbol ]

であり最適な符号長となる
つまり最適な頻度表に切り替えながら圧縮することにより
高圧縮率にすることが可能である

でも現実は・・・

ほど甘くないです・・・^^;
【2007年05月31日05:30 】 | 圧縮 | コメント(0) | トラックバック(0)
LZW符号・・・
LZW符号・・・

1984年にT.Welchにより開発された
基本的にはLZ78と同じだが・・・
LZW符号化は最初から辞書内に
出現する可能性のある一文字を全て登録されている点が異なる

初期設定・・・
辞書に出現する可能性のある一文字を全て登録する

符号化は・・・
辞書の中から一致する文字列を探し
一致長が最大のものを選ぶ

次に選択した辞書番号を出力する
この辞書番号の文字列に不一致文字を追加した新しい文字列を
辞書の最後に追加する

この不一致文字から始まる文字列に対して同様に繰り返す
(最低一文字は一致するため・・・辞書内にないことはない)

出力データは
(辞書番号)・・・(辞書番号)
のようになる

復号化は・・・
1番目の辞書番号を読み込み対応する文字列を出力する

2番目の辞書番号を読み込み対応する文字列の最初の文字を
1番目の文字列の末尾に追加し・・・
辞書の最後に追加する

2番目の辞書番号を1番目として同様に繰り返す

最後に・・・
辞書に文字列を追加し続けると・・・
辞書サイズが大きくなるにつれ辞書番号も大きくなり・・・
圧縮効率が悪くなる

そこで辞書サイズを決めておき・・・
超えた場合は・・・

・辞書更新を停止する
・辞書を初期化する
・辞書を再構築する(削除後追加)

等がある

辞書再構築の主な方法として・・・

・FIFO(First In First Out):追加順に削除(ところてん方式)
・LRU(Least Recently Used):最長時間未使用から削除(最後に参照後最も時間経過)
・LFU(Least Frequently Used):最小使用回数から削除(参照回数が最も少ない)

等がある
【2007年03月22日07:12 】 | 圧縮 | コメント(0) | トラックバック(0)
| ホーム |次ページ
PR

忍者ブログ [PR]