LZ78
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 |
