忍者ブログ

Infoseek検索 Infoseek検索

[PR]
×

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

【2018年06月25日14:37 】 |
LZ77符号・・・
LZ77符号・・・

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

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

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

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

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

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

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

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

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

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

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













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

[データ圧縮] LZ系(LZ77, LZ78, LZWなど)の特許について
LZWは米国ユニシス社の特許です。しかし、 2004年6月20日に特許期限が切れたそうです。 モノノフの声 : 【祝】UNISYS/LZW 特許期限切れ LZ77については特許はありません。 Previo (旧Stac Software) 社が持つ特許は、 ハッシュを使ってLZ77圧縮をする方法です。 つまり、デ
【2007/04/01 12:11】 | drill256の日記
前ページ| ホーム |次ページ
PR

忍者ブログ [PR]