ユニバーサル符号化

データにおいて値が無秩序に並んでいることは少なく、なんらかの関連性があるものである。
データ値の並び方のパターンを抽出し、そこに元よりも短いコードを振って出力することで
データの情報量を減らすことができます。ここでデータのパターンと対応するコード値を管理
するテーブルを辞書と呼び、代表的な圧縮アルゴリズムとして、LZ符号化を取り上げる.

辞書の構築方法

過去に現れたパターンに対してコードを割り振っていくという考え方で圧縮を行う
アルゴリズムが「LZ符号化」である。
LZ符号化の特徴として、

• • 記号の出現率などの事前データを必要としない
  • データ長が長くなれば長くなるほど圧縮効率は高くなる

LZ77符号化

スライド辞書と呼ばれる辞書を用いる方法である。
LZ77符号化の辞書=これまで圧縮したデータ列
この中に処理しようとするデータ列が存在するか調べ、「存在する位置」「一致するデータ長」を記録

辞書:[ABCDEFGHI]

パターン[BCDEF] コード値:1.4

辞書の末尾には処理しようとしているデータそのものが繋がる

スライド辞書の末尾
[ABCDE DEDEX]
コード値:3,4

DEDEX:符号化するデータパターン
ABCDEDEDEX:辞書データ

パターン・データ長に上限を設ける

辞書から一致するデータパターンを探す際にあるところで打ち切る
辞書のデータ長に上限を定めるにはある程度蓄積すると過去のデータを削除する。

LZ77符号化の処理の流れ

[データパターンが現れる位置][一致長の情報][次に来るパターン]
をセットにして出力する。
4,4'X'

処理の例:
ABAAABABC:処理したいデータ列
辞書 / データパターン/出力
/A/0,0,A
A/B/0,0,B
AB/AA/2,1,A
ABAA/ABA/0,2,A (最大長は2まで)
AABA/BC/2,1,C

• スライド辞書の初期化
• 処理したいデータ列のデータパターンと一致するデータパターンを検索
• 一致長が最も長いデータパターンにおける辞書中の位置と長さを求める(まったくない場合は0,0)
• 続くデータを一つ出力
• 処理を行ったデータ列を辞書の末尾に追加(ただし、辞書のデータ長を越える場合はデータ長の範囲内に収まるようにする。
• 処理したいデータがなくなるまで繰り返す

復号化の方法

• 圧縮データを読み込む
• 辞書より、開始時から一致長の長さだけデータパターンを出力する
• 次の一文字を読み込み、そのまま出力する、そして出力したデータを辞書に追加する
• 圧縮データがなくなるまで繰り返す

LZSS符号化

LZ77符号化のバリエーション
先ほどの0,0,Aのような場合には本来のデータ以上にデータが長くなってしまう。
よってこのような場合にはそのままデータを出力することにする.
ポイント情報を出力する場合と元データを出力する場合をフラグビットで区別する。

また、一致長が短い場合、圧縮データが圧縮前よりも大きくなってしまうことがある。
そのような場合には元データをそのまま出力する。

0/A/1/2,4/1/2,4/0/S
フラグ0の後=データ値そのもの
フラグ1の後=ポイント情報

アルゴリズム

圧縮

• 辞書を初期化
• 処理したいデータ列と一致するパターンを検索する
• 検索の結果、一致長が最も長いデータパターンにおける辞書中の位置と長さを出力する
• 一致長が最小値以下の場合はフラグ"0"と元のデータを出力する。
• 一致長が１よりも大きい場合はフラグ１とポイント情報を出力する。

展開

• 圧縮データより1文字読み込む
• 値が0であればそのまま出力
• 値が1の場合にはポイント開始情報を読み込み、データパターンを一致長だけ出力する。

出力したデータ値を逐次辞書に追加

• 圧縮データがなくなるまで繰り返す