📑LZ77 - Sereinme

1696781354749

引言#

LZ77 は、辞書を用いてデータ圧縮を行う古典的な圧縮アルゴリズムであり、1977 年にイスラエルのエンジニア Jacob Ziv と Abraham Lempel によって発表された論文「A Universal Algorithm for Sequential Data Compression」において提案されました。

従来の統計に基づく圧縮符号化（例えば Huffman 符号化）は、事前情報 — 信号源の文字頻度を取得する必要があり、その後に圧縮を行います。しかし、ほとんどの場合、この事前情報を事前に取得することは非常に困難です。したがって、より一般的なデータ圧縮符号化を設計することが特に重要であり、LZ77 データ圧縮アルゴリズムが登場しました。その核心的な考え方は、データの繰り返し構造情報を利用してデータ圧縮を行うことです。つまり、文字列内の情報が以前に出現した場合、その以前に出現した位置を指摘するだけで、相対インデックスを用いてこれらの単語を表現することができます。

原理#

ここでは LZ77 アルゴリズムの圧縮と解凍プロセスについてのみ議論します。LZ77 アルゴリズムの唯一の可訳で無損圧縮の特性については、元の論文を参照してください。

スライディングウィンドウ#

まず、文字列 $S$ の長さを $N$ と定義し、文字列 $S$ の部分文字列 $S_{ij},1\leq i,j \leq N$ とします。接頭辞部分文字列 $S_{1,j}$ に対して、 $L_i^j$ を最初の文字 $S_i$ の部分文字列と最初の文字 $S_{j+1}$ の部分文字列の最大一致長と定義します。すなわち：

L_i^j=\max\{l|S_{i,i+l-1}=S_{j+1,j+l}\},\quad l\leq N-j

文字列 $S_{j+1,j+l}$ が文字列 $S_{i,i+l-1}$ と一致し、かつ一致長が $l$ であると呼びます。図に示すように、2 つのケースがあります。

string_match

$p^j$ をすべてのケースにおける最長一致の開始位置 $i$ の値と定義します。すなわち

p^i = \mathop{\arg\max}\limits_i\{L_i^j\}, \quad 1\leq i \leq j

例えば、文字列 $S=00101011,j=3$ の場合、次のようになります。

$L_1^j=1\rightarrow S_{j+1,j+1}=S_{1,1},S_{j+1,j+2}\neq S_{1,2}$
$L_2^j=4\rightarrow S_{j+1,j+1}=S_{2,2},S_{j+1,j+2}=S_{2,3},S_{j+1,j+3}=S_{2,4},S_{j+1,j+4}=S_{2,5},S_{j+1,j+5}\neq S_{2,6}$
$L_3^j=0\rightarrow S_{j+1,j+1}\neq S_{3,3}$

したがって、 $p^j=2$ かつ最長一致の長さ $l^j=4$ です。これにより、部分文字列 $S_{j+1,j+p}$ は $S_{1,j}$ によって生成できることがわかります。したがって、これを $S_{1,j}$ の再生拡張（Reproducible Extension）と呼びます。LZ77 アルゴリズムの核心的な考え方はここから生まれます —— 過去に出現した文字列を辞書として使用し、将来出現する文字を符号化してデータ圧縮を達成します。具体的な実装では、スライディングウィンドウ（Sliding Window）辞書を使用して過去の文字を保存し、Lookahead-Buffer を使用して圧縮待ちの文字を保存し、カーソルが両者の間の区切りとして機能します。図に示すように

lz77

辞書と Lookahead Buffer の長さは固定されています。

圧縮#

$(p,l,c)$ を Lookahead Buffer 内の文字列の最長一致結果として表します。ここで

$p$ は最長一致時の辞書内の文字の開始位置（カーソル位置に対して）
$l$ は最長一致文字列の長さ
$c$ は Lookahead Buffer の最長一致終了時の次の文字を指します

圧縮のプロセスは、 $(p,l,c)$ を繰り返し出力し、カーソルを $l+1$ に移動させることです。アルゴリズムは次のようになります。

Repeat:
	Output (p,l,c),
	Cursor --> l+1
Until to end of string

圧縮の例は図に示されています。

lz77-compression

解凍#

正しくデコードするためには、解凍時のスライディングウィンドウは圧縮時と同じでなければなりません。解凍時に $(p,l,c)$ に遭遇した場合、大きく分けて三つのケースに分かれます：

$p==0$ かつ $l==0$ 、すなわち初期状態で、この場合は直接 $c$ をデコードします
$p\geq l$ 、辞書 dict[p:p+l+1] としてデコードします
$p<l$ 、すなわちループ符号化が発生した場合、左から右にループして結合する必要があります。擬似コードは次のようになります。

for (i = p, k = 0; k < length; i++, k++)
	out[cursor+k] = dict[i%cursor]

例えば、dict=abcd、符号化が (2,9,e) の場合、解凍結果は output=abcdcdcdcdcdce となります。

実装#

Matlab を用いて簡単な LZ77 圧縮アルゴリズムを実装しました。私の目的は主に配列を圧縮することなので、配列を用いて圧縮設計とテストを行いました。具体的な実装は以下の通りです。

classdef LZ77
% A simple implementation of LZ77 compression algorithm

    properties (SetAccess = private)
        window_size % dictionary
        buffer_size % lookahead buffer
    end

    methods
        function self = LZ77(d, h)
            if nargin == 2
                self.window_size = d;
                self.buffer_size = h;
            elseif nargin == 1
                self.window_size = d;
                self.buffer_size = 4;
            elseif nargin == 0
                self.window_size = 6;
                self.buffer_size = 4;
            end
        end

        function [p, l, c] = longest_match(self, data, cursor)
        % Find the longest match between dictionary and
        % lookahead-buffer.
        % 
        % arguments: (input)
        %   data    - data used to find longest match
        %   cursor  - position of data that seperate dictionary and 
        %             lookahead-buffer, from 0 to data length, value of
        %             cursor should be equal to its left item's index
        % arguments: (output)
        %   p - start point of longest match based on cursor
        %   l - length of longest match
        %   c - next character of longest match

            end_buffer = min(cursor + self.buffer_size, length(data)-1);

            p = -1;
            l = -1;
            c = '';

            for i = cursor+1:end_buffer
                start_index = max(1, cursor - self.window_size + 1);
                sub_string = data(cursor+1:i);
                subs_len = length(sub_string);

                for j = start_index:cursor
                    repetition = floor(subs_len / (cursor - j + 1));
                    last = rem(subs_len, (cursor - j + 1));
                    matched_string = [repmat(data(j:cursor), ...
                        [1 repetition]), data(j:j+last-1)];

                    % if match, update p, l, c
                    if isequal(matched_string, sub_string) && subs_len > l
                        p = cursor - j + 1;
                        l = subs_len;
                        c = data(i+1);
                    end
                end
            end

            % if not match, return next character of cursor
            if p == -1 && l == -1
                p = 0;
                l = 0;
                c = data(cursor + 1);
            end
        end

        function cm = compress(self, message)
        % Compress message
        % 
        % arguments: (input)
        %   message - data ready to compress
        % arguments: (output)
        %   cm      - compressed message
            
            i = 0;
            while i < length(message)
                [p, l, c] = self.longest_match(message, i);
                if exist('cm', 'var')
                    cm = [cm;[p,l,c]];
                else
                    cm = [p,l,c];
                end
                i = i + l + 1;
            end
        end

        function dm = decompress(self, cm)
        % Decompress the compressed message
        % 
        % arguments: (input)
        %   cm - compressed message
        % arguments: (output)
        %   dm - decompressed message

            cursor = 0;
            [n, ~] = size(cm);
            dm = [];

            for i = 1:n
                p = cm(i,1);
                l = cm(i,2);
                c = cm(i,3);
                if p == 0 && l == 0
                    dm = [dm, c];
                elseif p >= l
                    dm = [dm, dm(cursor - p + 1: cursor - p + l), c];
                elseif p < l
                    repetition = floor(l / p);
                    last = rem(l, p);
                    dm = [dm, repmat(dm(cursor-p+1:cursor), ...
                        [1 repetition]), dm(cursor-p+1:cursor-p+last), c];
                end
                cursor = cursor + l + 1;
            end
        end
    end
end

全体の符号化解凍ロジックは明確で、解凍プロセス中のループ一致も比較的簡単です。最大一致部分文字列を探す際、前置部分文字列はループ一致と同じ生成方法を採用していますが、実際には他の方法でも同様です。この生成方法は本質的ではありません。

最大一致部分文字列を探す際に、Lookahead-Buffer はデータの最後の位置を取得できないことに注意が必要です。すなわち、length(data)-1 である必要があります。これは、カーソルの後のデータがすべて一致した場合、一致後の次の文字インデックスが境界を超えてしまうためです。Lookahead-Buffer が最大で倒数第二の文字までしか到達しないようにすることで、すべて一致した後でも $(p,l,c)$ の $c$ の位置に 1 文字を残すことができ、配列の越境を効果的に回避できます。同時に圧縮効率も低下しません。

end_buffer = min(cursor + self.buffer_size, length(data)-1);

性能#

辞書と Lookahead-Buffer の長さが小さい場合、LZ77 の圧縮速度は非常に速いですが、圧縮率は非常に低く、重複データが少ない場合、圧縮後のデータが圧縮前よりも大きくなることさえあります。辞書と Lookahead-Buffer の長さが小さい場合、圧縮効果は良好ですが、圧縮速度は非常に遅く、長さが大きくなるほど圧縮効果が良くなり、圧縮速度が遅くなります。

辞書と Lookahead-Buffer の長さが共に 80 の場合、小型アンテナのブルーボックスでデータを収集した結果、圧縮比は約 1.29:1 で、圧縮率は 22% です。ウィンドウの長さを 200 に拡大した場合、同じデータで圧縮比は約 1.49:1、圧縮率は 33% です。

解凍については、辞書と Lookahead-Buffer の長さに依存しないため、解凍速度は非常に速いです。

直接 zip を使用して 2.29G の原始収集データを圧縮した場合、圧縮比は約 3.35:1 で、LZ77 アルゴリズムの変種に基づいているため、直接の圧縮に比べて性能が向上していますが、全体のデータ量が大きいことも圧縮率の向上に寄与しています。

参考#

Ziv, Jacob, and Abraham Lempel. "A universal algorithm for sequential data compression." IEEE Transactions on information theory 23.3 (1977): 337-343.
LZ77 アルゴリズム原理及び実装