Microsoft Word 宗像データ圧縮（Ｗｏｒｄ）.doc

Transcription

1 Lempel-Ziv のデータ圧縮法 参考文献 1) Ziv, J. and Lempel, A.: An Universal Algorithm for Sequential Data Compression, IEEE Trans, Vol. IT-23, No. 3, pp (1977). 2) Ziv, J. and Lempel, A.: Compression of Individual Sequences via Variable-Rate Coding, IEEE Trans, Vol. IT-24, No. 5, pp (1978). 3) 山田真市 : Kolmogorov-Chaitin の計算論的情報量と Lempel-Zivの万能データ圧縮法, 日本ユニバック技報, 第 1 号, pp (1981). 4) 宗像清治 : Ziv-Lempelのデータ圧縮法, 情報処理, Vol. 26, No. 1, pp. 2-6 (1985). 5) 昌達 K's: 圧縮アルゴリズム符号化の原理とC 言語による実装, ソフトバンクパブリッシング株式会社 (2003). 文献 1),2) のデータ圧縮法はLZ77,LZ78と略称されており ( 動的 ) 辞書式データ圧縮法とも言われている LZ77は記号列内のパターンを識別して圧縮し LZ78はブロック化された記号列を個々に圧縮する方法である 3),4) は日本ユニバックとSperry Research Centerとの合意に基づき進められたデータ圧縮法の共同研究成果の一部である 共同研究では ファイルの圧縮 / 復元プログラムを作成し Lempel-Zivの種々のデータ圧縮性能を調査した M. Cohn, W. L. Eastman, ならびに山田真市, 森俊治, J. Speroniの各氏に感謝する 5) は雑誌 Cマガジン に連載された画像圧縮アルゴリズムの記事をまとめたものである LZ77,LZ78の符号化原理の説明はかなり粗雑である

2 米 Unisys 特許 ( 日本国内でも成立 ) 画像圧縮アルゴリズムLZW(Lempel Ziv Welch) の特許取得 同特許が失効 現在 LZW.Cのソースがインターネットで公開 IBM 研究員が Huffmanコードの米国特許を2 件取得している 圧縮ソフト LZ77 系の LHA(Windows) や gzip(linux) のフリーソフトが広く使われている LZ78 系には ZIP(Unix) があるが gzipの方が圧縮効率が良いので使われなくなっている これらの圧縮ソフトは ディレクトリの下にあるプログラムやデータをまとめて圧縮する機能を持ってり 復元 展開プログラム付で圧縮ファイルを配布することにより システムの保守が簡便に行われるようになった 1. Lempel-Ziv のデータ圧縮法 1 Lempel-Zivは 記号列の複製 ( コピー ) と生成 の操作で記号列の情報量を考察し 操作に必要な情報を符号化するデータ圧縮法を導いた Huffmanコードが記号を符号化するのに対して LZ77,LZ78は記号列を符号化するので 圧縮効率はより良くなる また LZ77,LZ78はデータ源の性質を予め調査する必要がなく 直接データに適用できる簡便性を持つ 文献 4) にある下表は小さい PL/1 プログラムを実験的に圧縮した結果である 数字は平均符号長 ( ビット / 記号 ) である 記号数 Huffman LZ77 LZ78

3 Sample Sample Sample , Sample Sample 記号列 P の複製を P [ p,l] と表す p は複製の始点 l は複製の長さである 複製の長さ l が P の末尾を超えるときは 始点に戻り複製を続ける 複製例 P=aab とする P [ 1,1] =a, P [ 2,1] =a, P [ 2,2] =ab, P [ 3,3] =bbb, P [ 2,4] =abab 記号列 P,Q の連結 P.Q に対して Q が P の複製である場合 Q は P から再生可能であるという 再生例 P=aab, Q=abab とすると Q は P から再生可能である P.Q=aab.abab の P の末尾までの複製を P の末尾に連結した記号列の複製を考えるのである P から再生可能な記号列 P.Q に対して Q に1 記号を連結した記号列 Qa が P の複製ではない場合 Qa は P から生成可能であるといい P P.Qa と書く 生成例 aab aab.ababb: abab は aab から再生可能であるが ababb は aab の複製ではない 生成を反復して 空列 λ から任意の記号列を生成することができる 生成により分解された各部分列を成分と呼ぶ 生成例 記号列 aabababb の生成 :λ a a.ab

4 a.ab.ababb 2

5 2. ユニバーサル データ圧縮法 (LZ77) LZ77は空列 λから出発して 最長の複製を用いて入力記号列 x の各成分 X i を生成し 生成情報 ( 複製の始点 長さ 右端の記号 ) を固定長の符号に変換する λ X 1 X 1.X2 X 1.X2.X3... x 圧縮算法はバッファ B=PQ を使用する P は複製に参照する記号列 Q は未圧縮の記号列を記憶する バッファ P, Q の長さを p, q とする 1)P を p 個の NULL( _ ) 記号 Q を q 個の入力記号で初期化する B 1 =PQ, P=, Q=x1x 2...xq 以下の 2)~3) を入力記号列が空になるまで繰り返す 2)Bi =PQ 上で P から Q の頭部への最長の複製 Q(1,li-1) = P [ p i,li-1] と右端の記号 Q ( l i ) から生成される成分 X i を求め その符号を c i にする q ) X i =P[ p i,li -1] Q ( l i ), c i=( p i -1,li -1,Q( l i )) ( p i p, li 3)Bi =PQ の内容を長さ l i だけ左にシフトし 同時に Q の右側に l i 個の入力記号を補充してバッファ B i+1 にする P からシフトアウトした記号列は失われる 圧縮例バッファ長を p=q=8 8 ビット記号とすると符号長

6 は 3+3+8=14 ビットになる 記号列 aabababb の 64 ビットが符号列 42 ビットに圧縮される B 1 : P=, Q=aabababb X1 =P[ 0,0] a=a, c 1 = ( 0,0,a) B 2 : P= a, Q=abababb_ X2 =P[ 8,1] b=ab, c 2 = ( 7,1,b) B 3 : P= aab, Q=ababb X3 =P[ 7,4] b=ababb, c 3 = ( 6,4,b) B 4 : P=aabababb, Q= 終了 復元算法もバッファ B=PQ を使用する P に圧縮時と同じ記号列を再現し Q に符号 c i の成分 X i を生成する 1)P を p 個の NULL( _ ) 記号で初期化する B 1 =PQ, P= 以下の2)~3) を符号列が空になるまで繰り返す 2) 符号 c i = ( p i -1,li-1,di) を取り出し Q 上に c i の成分 Q=Xi =P[ p i,li-1] d i を生成する d i は X i の右端の記号である 3 3)B i =PQ の内容を長さ l i だけ左にシフトしてバッファ B i+1 とする LZ77の圧縮効率は バッファ構成のパラメタ ( p, q ) に影響される 先の表の LZ77は p=1024, q=16 で行った 文献 5) は p=2048 か p=4096 が適切としている 複製の長さの上限を q>16 とすると バッファが大きすぎ圧縮効率は悪くなる バッファ B=PQ のシフトは長さ p+n* q 以上の配列を用意す

7 ることで避けられる シフトする代わりに配列上のバッファ位置を右に移動するのである LZ77 は P のことをスライド辞書と呼んでいる LZ77 は以下の弱点を持つ 1) 長さ0,1の複製の符号表現が元のデータよりも長くなる 2) 最長の複製を求める計算量が大きい 3) スライド辞書が最近の記号列に限定される これは辞書として不要の記号列を捨てる効果もあり 必ずしも弱点とはいえない LZSS 符号化 LZSS 符号化は1) の弱点を改良するものである 複製情報の有無を表す1ビットのフラッグを設け 有のときは複製情報と右端の記号を出力し 無の場合は右端の記号だけを出力する LZ77よりも符号長が1ビット長くなるが 短い複製が多くなる場合は有効であろう 場合によっては LZSS 符号化のことをLZ77 符号化と呼ぶこともある 複製情報の項目を入れ替え 長さが0,1の場合は始点を出力しない方法も考えられる 圧縮ソフト LHA 圧縮ソフトLHA は LZ77 符号化の後 Huffman 符号化を行って圧縮の効率を高めている ( LZH 符号化 ) 複製の始点は Huffman 符号になじまないが 複製の長さと右端の記号には有効であろう 2パスの圧縮を行う価値はあると思われる 文献 5) には 複製の長さを可変長符号にする LZB 符号化 複製の長さの代わりに最大一致長と第 2 一致長の差を使用する LZBW 符号化 高速探索法としてツリー探索とハッシュ探索が言及されているが詳細は不明である 最長複製の高速探索アルゴリズムには かなりの数の特許が認められている 3. インクリメンタル データ圧縮法 (LZ78) 4

8 LZ78 は複製を成分複製に限定するものである 成分 X j は既成分 X 0,...,Xj-1 の中の最長の成分複製と右端の記号から生成される X 0 は空列 λ である 成分複製による分解例記号列 aabababb は成分列 a.ab.aba.b.b_ に分解される _ は記号列の終わりを示す 分解の過程は成分木で表すことができる 木の根は空列 X 0 節は分解済みの成分であり 枝に子節を生成するときの右端の記号をつける 表は成分木の実装モデルである 成分木は LZ78 の辞書に相当する X 0 成分子節のリスト X 1 =X0a=a a /\ b 0 ( a, 1 ), ( b, 4 ) X 2 =X1b=ab X 1 X 4 1 ( b, 2 ) X 3 =X2a=aba \ b \ _ 2 ( a, 3 ) X 4 =X0b=b X 2 X 5 3 X 5 =X4 _=b_ a / 4 ( _, 5 ) X 3 5 圧縮算法入力記号列と一致する根 X 0 からの枝記号列をたどって最長の成分複製 X i を見つけ 次の入力記号を右端の記号 r j として成分 X j =Xi r j を生成し 成分木の表 [i ] の子節リストに ( r j, j ) を追加する 入力アルファベット A={ 0,1,...,d-1} の記号数を d とすると 成分 X j の符号

9 c j は次式で与えられる c j =i* d+rj ( i < j, rj < d ) ( j=1,2,...) 符号 c j の符号長 L j は c j (j-1) * d+( d-1) =j* d-1 から L j = [log( j * d )] になる [] は天井関数である LZ78の符号は 成分数が 2 の n 乗になる毎に段階的に符号長を増分するインクリメンタル符号である 圧縮例記号列 aabababb は 記号を ASCII とすると d=128, L j = [log( j )]+7 から以下のように符号化され 入力列 56 ビットは符号列 43 ビットに圧縮される X 1 =X0a, c 1 =0* , L 1 =0+7=7 X 2 =X1b, c 2 =1* , L 2 =1+7=8 X 3 =X2a, c 3 =2* , L 3 =2+7=9 X 4 =X0b, c 4 =0* , L 4 =2+7=9 X 5 =X4_, c 5 =4* , L 5 =3+7=10 5 復元算法は 圧縮算法とは逆に 成分 X j から根 X 0 までの枝記号をたどって X j の記号列を復元する 符号列から符号長 Lj=[log(j* d)] の符号 c j =i* d+rj ( i < j, rj< d ) を取り出し 除算 c j /d の商と余で親節の成分番号 i と枝記号 r j 得 これを復号表 [ j ] に登録する j から 0 まで復号表の親節をたどって逆順の枝記号列 r m,...,r1 を得 これを正順にして X j =r1...rm を復元する 復号表例上記の圧縮例の復号表は以下のように作られる 成分親節枝記号 1 0 a

10 2 1 b 3 2 a 4 0 b 5 4 _ LZ78 は 成分数が多くなると符号長が増分しすぎ 符号表現の効率が落ちてくる弱点をもつ 実験的に最良の圧縮をするまでの符号長を求めると 14 ビット ( 成分数 16000) ほどになることが多い この段階に達したときは 成分木を再初期化し既成分を空列 X 0 だけに戻して圧縮を続けた方が良い結果が得られる LZ78 は何らかの時点で辞書の再初期化を必要とする圧縮法である LZW 文献 5) によると LZW は全ての記号の長さ1の記号列を開始辞書にし 記号コードでこれを参照する 実際に生成する成分は 開始辞書内の記号から始まる長さ2 以上の記号列であり これに最大記号コード+1からの番号を付ける 言い換えれば 成分木の表の初めに記号数分の領域を確保し これらを長さ1の成分の根とするのである LZW は長さ1の成分を生成しないだけなので 効率向上は僅かである 文献 5) は LZW を開発を容易にするための実装上の技法と位置づけている 不思議なのはLZW が画像圧縮アルゴリズムの特許と限定されている点である LZ78 自体は画像圧縮に向いているとしても 画像に限定されるものではない ( 圧縮の比較表を参照 ) LZW には LZ78 の他に画像データを記号化する何らかの手法が隠されているのではないかとも思われる

11 参考 Huffman コード 6 Huffmanコードは 記号の使用頻度を反映させた可変長 2 進 Prefix 符号 ( どの符号も他の符号のPrefixになることはない ) である 下表の左端の記号と頻度のリストを例にしてコードの割付法を説明する リストは頻度の降順にしておく リスト最下位のペアをマージして頻度の和をとり 和のノードをリストの降順位置に置く (1*) 和と同じ頻度のものがある場合は その上位に置く (2*) 和が次のペアの上位の頻度よりも大きい場合は 続けてマージしても良い (3*,4*) A 0.30 A 0.30 A * 0.4 5* 0.6 6* 1.0 E 0.25 E 0.25 E * 0.3 4* 0.4 B 0.15 B * 0.15 A 0.3 D 0.15 D 0.15 B 0.15 C 0.10 C 0.10 D 0.15 F * 0.05 G 0.01 ノード表 N L R 1* 2* 3* 4* F C B E 3* 5* G 1* D 2* A 4* 5* 6* マージの過程はノード表にまとめられ 2 分木で表すことができる 2 分木の左枝に 0 右枝に 1 を割り付け 根から記号までの 0/1 の列が Huffman コードになる ( 符号 1 を参照 ) 復元を簡便にするためには 2 分木の左から右に沿って符号長が増大し 同じ符号長の記号が記号リスト順に並んでいる符号の方がよい 図の場合 (3*,A,E) のノードを (A,E,3*) に入れ替えるのである ( 符号 2 を参照 ) 6* 記号頻度符号 1 符号 2

12 /\ A * 4* E /\ /\ B * A E 2* D /\ /\ C B D C 1* F /\ G F G 実際のコード割付は記号リストを符号長で区切ることから始める ノード表を下から上にサーチしてノードを符号長でグループ化してゆく 結果は区切り目の記号を用いて 1,0;2,E;3,C;4,G; と出力する 0 は記号が無いことを示す この後 記号リストの順に次のコードを割付ける 1) 最初の記号は 符号長だけ0を続けたコードにする 2) 次の記号は 前のコードに1を加算し 更に次の符号長の最初の記号の場合は符号長の増大分だけ0を追加したコードにする 7