忍者ブログ
[PR]
×

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

【2024年03月29日04:26 】 |
LZ78符号・・・
LZ78符号・・・

1978年にJ.ZivとA.Lempelが発表した
LZW符号、LZT符号等の原点

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

次に選択した辞書番号を出力する
辞書内に一致するものがない場合は0を出力する

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

以上を繰り返す

出力データは
(辞書番号,不一致文字)・・・(辞書番号,不一致文字)
のようになる

復号化は・・・
辞書番号を読み取り対応する文字列を出力する
0の場合は何もしない

次の一文字を出力し
先に出力した文字列にこの一文字を追加した新しい文字列を
辞書の最後に追加する

以上を繰り返す

辞書サイズは0から順次増えていくため
辞書番号はその時の辞書サイズに応じて
最適なビット長に調整する
PR
【2007年03月18日21:52 】 | 圧縮 | コメント(0) | トラックバック()
LZ77符号・・・
LZ77符号・・・

1977年にJ.ZivとA.Lempelが発表した
LZSS符号、LZB符号、LZBW符号、LZMA符号等の原点

初期設定・・・
辞書サイズ、最大一致長を決める

符号化は・・・
辞書の中から一致長が最大のものを探す
最大一致長を超えて一致する場合は最大一致長までとする

次に(開始位置,一致長)を出力し、辞書の最後に一致した文字列を追加する
一致するものがない場合は(0,0)を出力する

次に不一致になった文字を出力し、辞書の最後にも追加する
以上をデータの終わりまで繰り返す

出力データは
(開始位置,一致長,不一致文字)・・・(開始位置,一致長,不一致文字)
のようになる

復号化は・・・
(開始位置,一致長)を読み取る
一致文字列を出力し、辞書の最後に一致文字列を追加する
(0,0)の場合は次に進む

次に不一致文字を出力し、辞書の最後に追加する
以上を繰り返す

スライド辞書・・・
リングバッファの実現・・・アナログ時計のように先頭と末尾が連結している
(辞書サイズ+最大一致長)の領域を確保する
辞書の先頭と一致長を記憶していれば・・・

辞書の末尾は辞書の先頭+辞書サイズだし・・・
データの先頭は辞書の末尾の次からだし・・・
一致データの末尾はデータの先頭+一致長だから・・・

でも処理速度を考えるといちいち計算させるよりは・・・
辞書の先頭、データの先頭と末尾くらいは記憶していた方がいいのかな
【2007年03月15日07:26 】 | 圧縮 | コメント(0) | トラックバック()
整数を自然数に・・・
α符号やKZ符号等は可変長であるが・・・
自然数しか表現できない・・・^^;

そこで整数は自然数に変換しなければならない
固定長であれば負の数は2の補数で表現され・・・
最上位ビットが1である・・・

可変長の場合は・・・???

絶対値を2倍し(左シフト)・・・
自然数以外なら1を加算する・・・
つまり最下位ビットを1にする

整数:自然数
-3:7
-2:5
-1:3
 0:1
 1:2
 2:4
 3:6

逆変換は最下位ビットが1であれば・・・
2分の1(右シフト)して(-1)倍・・・
最下位ビットが0であれば右シフトのみで良い^^

これで整数を自然数に変換できた^^
【2007年02月07日22:19 】 | 圧縮 | コメント(0) | トラックバック()
LZSS符号・・・
LZSS符号はLZ77符号を改良したものである。
1982年にStorerとSzymanskiによって考案された。

符号化は・・・
辞書に登録されている場合は1を出力し
続いて開始位置と一致長を出力する。
辞書の最後に一致した文字列を追加する。

辞書に登録されていない場合は0を出力し
続いて文字を出力する。
辞書の最後に出力した文字を追加する。

復号化は・・・
最初に1ビット読み込み
0だった場合、続く1文字を読み込み出力する。
辞書の最後に出力した文字を追加する。

1だった場合、続いて開始位置と一致長を読み込む
辞書から一致長分の文字列を出力する。
辞書の最後に出力した文字列を追加する。

辞書サイズが大きくすると開始位置を表す記号も大きくなるため
辞書サイズが大きくなるほど圧縮率が良くなるという訳ではない。

また一致長が1だった場合(1,開始位置,一致長)と出力するより
(0,文字)と出力した方が圧縮率が良くなる。

さらに一致長が3以下の場合は辞書に登録されていないとみなした場合
つまり(0,文字)(0,文字)(0,文字)のように出力するとした場合
3以下の一致長は現れないため

一致長を符号化時は(一致長 - 3)
復号化時は(一致長 + 3)のように表せる。
要するに最大一致長を増やすことができる。
最大一致長を変えない場合でも、より小さな値で一致長を表現できる。
【2007年01月16日21:58 】 | 圧縮 | コメント(0) | トラックバック()
ZIPのように・・・
ZIPの中には2種類のハフマン木が存在する

1つは文字記号と終端記号、長さをグループとしたハフマン木と
もう1つは長さの次に続く距離のみに適用するハフマン木である

長さの次には必ず距離が来るためハフマン木を切り替えることが可能である
って・・・レンジコーダにはもう組み込んでいたっけ・・・^^;
更に圧縮率を上げるために複数の頻度表を組み合わせたり切り替えたりして・・・
逆に圧縮率を低下させ処理時間も延びたっけ・・・TT

問題は各アルゴリズムを独立させているということだ
独立させることによって単体で動作するし
パラメータの変更による影響も確認できる^^

各アルゴリズムはバイト単位で操作することにより
各ブロックはバイト列として表すことが出来た

しかし可変長符号を用いるとブロックの区切りとバイトの区切りが
必ずしも一致するとは限らない・・・^^;
次のアルゴリズムにもその規則を引き渡せば区別することは可能だが・・・

各アルゴリズムの独立性がなくなる・・・TT
アルゴリズムの組み合わせやパラメータの変更は無限にしたいし・・・
それを次に引き渡すのは・・・^^;

う~~~ん 何か良い方法はないだろうか???
【2006年12月08日00:30 】 | 圧縮 | コメント(0) | トラックバック()
前ページ| ホーム |次ページ

忍者ブログ [PR]