忍者ブログ
[PR]
×

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

【2024年03月29日21:01 】 |
LZ77符号・・・
LZ77符号・・・

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

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

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

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

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

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

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

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

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

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

でも処理速度を考えるといちいち計算させるよりは・・・
辞書の先頭、データの先頭と末尾くらいは記憶していた方がいいのかな
PR
【2007年03月15日07:26 】 | 圧縮 | コメント(0) | トラックバック()
<<たんじょうび・・・ | ホーム |は~~~ぃ>>
コメント
コメントの投稿













トラックバック
トラックバックURL

前ページ| ホーム |次ページ

忍者ブログ [PR]