忍者ブログ

Infoseek検索 Infoseek検索

[PR]
×

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

【2018年12月16日01:44 】 |
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)
<<今君は・・・ | ホーム |LZ78符号・・・>>
コメント
コメントの投稿













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

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

忍者ブログ [PR]