LZ符号化 森田 岳史
文書データなど局所的に、法則性が 存在する。(データパターン) データパターンを符号化。 データパターンを登録するために 辞書を用いる。 元データに含まれる記号の出現率な どの事前情報を必要としない。 元データの種類にかかわらず、デー タ長が長くなればなるほど、より高 い圧縮効果が期待できる。
イメージ They will come soon 辞書 辞書とは英単語と対応する コードが記録されたデータ come 210 600 ・ come 210 ・ 600 1300 210 500 soon 500 ・ they 600 ・ 辞書に記録されたデータパターンに 従ってデータ値をコード化する will 1300 ・
LZ77符号化 (スライド辞書法)
コード化 スライド辞書による (A)辞書データ (B)符号化する データパターン 0 1 2 3 4 5 6 7 8 A B C D E F 0 1 2 3 4 5 6 7 8 A B C D E F G H I (A)辞書データ (B)符号化する データパターン コード値 B B C D E 1,4 1番目から4つが一致する
スライド辞書へのデータ追加 元の辞書データ 追加後の 辞書データ 先頭のデータを消去して 追加分を末尾に加える 0 1 2 3 4 A B 0 1 2 3 4 A B C D E 追加 F G 元の辞書データ 0 1 2 3 4 追加後の 辞書データ C D E F G 先頭のデータを消去して 追加分を末尾に加える
が複数ある場合 一致するデータパターン 辞書データ 符号化する データパターン “0,2”と”2,4”の2つのコード 0 1 2 3 4 5 6 7 8 A B A B C D E F G 辞書データ “0,2”と”2,4”の2つのコード が考えられるが、”2,4”の方 が一致長が長いため、こちら を用いる。 符号化する データパターン A B C D
4,4'X' LZ77符号化での出力方法 辞書データ 符号化する データパターン 一致するデータパターン 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 A B C D E F G H I 辞書データ 符号化する データパターン E F G H X コード値 “4,4” 次に続く1データは そのまま出力 出力 4,4'X'
LZ77符号化の流れ １、空のスライド辞書を用意する 2、処理したいデータ列のデータパターンと一致するデータパターンを辞書中から検索する。 一致するデータパターンが複数ある場合は、それらを全て求める。 3、検索の結果、一致長が最も長いデータパターンにおける辞書中の位置と長さを求め、その 値を出力する。一致するパターンまったくない場合はポイント情報を”0,0”として出力する。 4、次に続くデータ1つ、そのまま出力する。 5、辞書データの更新。 6、処理したいデータ列がなくなるまで2〜5を繰り返す。
0 1 2 3 4 5 6 7 8 A B A A A B A B C 処理したいデータ 辞書 処理するデータパターン 出力値 0 1 2 3 A 0,0 'A' 0 1 2 3 0,0 'B' A B 0 1 2 3 A B A A 2,1 'A' A B 0 1 2 3 0,2 'A' 0 1 2 3 最大一致長が 2なのでここまで A A B A B C 2,1 'C'