導入
最近、応用情報の勉強を始めたため、アウトプットとして自分なりの理解をまとめて投稿しています。誤りなどがあればご指摘いただけると助かります。この記事で3本目です。
１．LZ77符号化
LZ77符号化は過去に読み込んだ文字列を参照して、部分文字列が一致する箇所の「出現位置」と「長さ」、および「次の1文字」で表現する、圧縮技法の１つである。
LZ77符号化の特徴
- 辞書式圧縮：過去の文字列を疑似的な辞書として利用する
- 可逆圧縮：圧縮データから元のデータを一意に復元可能な圧縮
- 適応型辞書：入力をしながら、過去の出現パターンを動的に利用する
LZ77符号化の流れ
今回は「出現位置」と「長さ」を2ビットで表す。
- 初めの１文字目を読み込んで（00, 00, 一文字目の文字）を出力する
- 読み込んだ文字列の中に部分文字列があれば
（一致している場所の先頭, 一致している長さ, 次の文字）を出力 - 文字列の最後の文字にたどり着くまで2を続ける
LZ77符号化の例
T = ababaababbについてLZ77符号化を行う。符号化済みの所を水色にしている。
2．LZ78符号化
LZ78符号化は過去に読み込んだ文字列を辞書として、「辞書の登録位置」と「次の1文字」で表現する、圧縮技法の１つである。LZ78符号化もLZ77符号化と同様に以下の性質を持つ。
LZ78符号化の特徴
- 辞書式圧縮：過去の出現パターンを辞書のように利用する
- 可逆圧縮：圧縮データから元のデータを一意に復元可能な圧縮
- 適応型辞書：入力をしながら、過去の出現パターンを動的に利用する
LZ78符号化の流れ
今回は「辞書の登録位置」を3ビットで表す。
- 初めの１文字目を読み込んで（000, 一文字目の文字）を出力して、一文字目の文字を辞書に登録する
- 読み込んだ文字列と辞書の最長一致を探索
（一致している辞書の登録位置, 次の文字）を出力して、新たに読み込んだ文字列を辞書に登録する - 文字列の最後の文字にたどり着くまで2を続ける
LZ78符号化の例
T = ababaababbについてLZ78符号化を行う。符号化済みの所を水色にしている。
まとめ
- LZ77符号化は過去に読み込んだ文字列の部分文字列（スライド窓）を参照する
- LZ78符号化は過去に読み込んだ文字列を辞書として利用する
- LZ77・LZ78符号化は共に、可逆圧縮・辞書式圧縮である
次回は、Re-pairについてまとめたい。
参考
以下のサイトが分かりやすく、参考にさせていただきました。
https://ja.wikipedia.org/wiki/LZ77
https://ja.wikipedia.org/wiki/LZ78