LZ78

出典: フリー百科事典『ウィキペディア(Wikipedia)』

出典: フリー百科事典『ウィキペディア(Wikipedia)』

LZ78は、1978年にジェイコブ・ジヴ (Jacob Ziv) とエイブラハム・レンペル (Abraham Lempel) によって開発されたデータ圧縮アルゴリズム。 ジヴ、レンペルらによるLZ77が発表当時ユニバーサル性を証明できていなかったため、完全なユニバーサル性が証明できる本手法が提案された。 1984年に、実用的な改良となるLZWが提案された。

読み込んだ記号列から動的に辞書を作成して、それをもとに入力記号列を置き換えていく。そのため、動的辞書法とも呼ばれる。 また、記号列の長さを増して部分列に分解していくことから、増分分解法とも呼ばれる。 LZ77と同様にすでに符号化が終わっている過去の記号列を参照するが、明示的に破棄しない限り、登録した単語をすべて使用する。

符号化[編集]

記号列

ababaabaaab

をもとに、符号化の手順を説明する。

まず、単語を登録するための辞書を次のように初期化する。ここで、辞書番号0は、未出記号を意味する空列となる。

番号 単語
0 (空列)

符号化は、対象となる記号列の prefix (先頭から見た部分列)に最長一致する辞書の単語を見つけることから始まる。 符号化対象の先頭は a... だが、a から始まる単語は辞書に登録されていない単語である。 そこで、未出を表す 0 がまず得られる。 符号語は、得られた辞書番号と次の記号列の先頭記号とを組み合わせて、 (0,a) として出力する。

a babaabaaab
(0,a)

続いて辞書の更新を行う。 得られた辞書番号 0 の単語の末尾に、次の記号列の先頭記号である a を加えたものを辞書番号 1 に登録する。 ここで、辞書の番号は現在までの最大値に +1 したものとなる。 上記の場合は 0 の単語が空列であるため、 a を辞書の 1 番に登録する。

番号 単語
0 (空列)
1 a

次の b も未出なので、(0,b) を出力して、 b を登録する。

a b abaabaaab
(0,a)(0,b)
番号 単語
0 (空列)
1 a
2 b

次の ab... は、a が辞書に登録されているため、その番号 1 と続く1記号 b を符号語として出力する。

a b ab aabaaab
(0,a)(0,b)(1,b)

辞書には、a と b を連接した ab を登録する。

番号 単語
0 (空列)
1 a
2 b
3 ab

同様に、次の aa... は、a が辞書に登録されているため、その番号 1 と続く1記号 a を符号語として出力する。

a b ab aa baaab
(0,a)(0,b)(1,b)(1,a)

辞書には、a と a を連接した aa を登録する。

番号 単語
0 (空列)
1 a
2 b
3 ab
4 aa

残りは、ba と aab がそれぞれ切り出されて、最終的に次のような符号語の列が得られる。

(0,a)(0,b)(1,b)(1,a)(2,a)(4,b)

またこの時点での辞書は、次のようになる。

番号 単語
0 (空列)
1 a
2 b
3 ab
4 aa
5 ba
6 aab

符号語の列を別の何らかの符号で符号化したものが、最終的な出力となる。 辞書は、符号語の列から再構成できるため、特に保存する必要はない。

復号[編集]

LZ78の復号は符号化と逆に、符号語の列から辞書を構成することで行われる。

符号化時と同一の辞書が得られるが、符号化時とは異なり、辞書の探索を行わずに辞書番号だけで単語を参照するため、符号化時より復号時の方が高速である。