LZ符号化 森田 岳史.

Presentation on theme: "LZ符号化 森田 岳史."— Presentation transcript:

1 LZ符号化 森田 岳史

2 文書データなど局所的に、法則性が 存在する。(データパターン) データパターンを符号化。 データパターンを登録するために 辞書を用いる。 元データに含まれる記号の出現率な どの事前情報を必要としない。 元データの種類にかかわらず、デー タ長が長くなればなるほど、より高 い圧縮効果が期待できる。

3 イメージ They will come soon 辞書 辞書とは英単語と対応する コードが記録されたデータ come 210 600
・ come 210 ・ 600 1300 210 500 soon 500 ・ they 600 ・ 辞書に記録されたデータパターンに 従ってデータ値をコード化する will 1300 ・

4 LZ77符号化 (スライド辞書法)

5 コード化 スライド辞書による (A)辞書データ (B)符号化する データパターン 0 1 2 3 4 5 6 7 8 A B C D E F
A B C D E F G H I (A)辞書データ (B)符号化する データパターン コード値 B B C D E 1,4 1番目から4つが一致する

6 スライド辞書へのデータ追加 元の辞書データ 追加後の 辞書データ 先頭のデータを消去して 追加分を末尾に加える 0 1 2 3 4 A B
A B C D E 追加 F G 元の辞書データ 追加後の 辞書データ C D E F G 先頭のデータを消去して 追加分を末尾に加える

7 が複数ある場合 一致するデータパターン 辞書データ 符号化する データパターン “0,2”と”2,4”の2つのコード
A B A B C D E F G 辞書データ “0,2”と”2,4”の2つのコード が考えられるが、”2,4”の方 が一致長が長いため、こちら を用いる。 符号化する データパターン A B C D

8 4,4'X' LZ77符号化での出力方法 辞書データ 符号化する データパターン 一致するデータパターン 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'

9 LZ77符号化の流れ １、空のスライド辞書を用意する 2、処理したいデータ列のデータパターンと一致するデータパターンを辞書中から検索する。
一致するデータパターンが複数ある場合は、それらを全て求める。 3、検索の結果、一致長が最も長いデータパターンにおける辞書中の位置と長さを求め、その 値を出力する。一致するパターンまったくない場合はポイント情報を”0,0”として出力する。 4、次に続くデータ1つ、そのまま出力する。 5、辞書データの更新。 6、処理したいデータ列がなくなるまで2〜5を繰り返す。

10 A B A A A B A B C 処理したいデータ 辞書 処理するデータパターン 出力値 A 0,0 'A' 0,0 'B' A B A B A A 2,1 'A' A B 0,2 'A' 最大一致長が 2なのでここまで A A B A B C 2,1 'C'