LZ77による数列の符号化

メモ書き

3134313134を2進数に

3134313134
1567156567 0
783578283  1
391789141  1
195894570  1
97947285   0
48973642   1
24486821   0
12243410   1
6121705    0
3060852    1
1530426    0
765213     0
382606     1
191303     0
95651      1
47825      1
23912      1
11956      0
5978       0
2989       0
1494       1
747        0
373        1
186        1
93         0
46         1
23         0
11         1
5          1
2          1
1          0

(3134313134)_10 = (10111010110100011101001010101110)_2

LZ77符号化

スライド窓 k=16, 符号化部 m=8, 参照部 k-m=8

i										1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32
		0	0	0	0	0	0	0	0	1	0	1	1	1	0	1	0	1	1	0	1	0	0	0	1	1	1	0	1	0	0	1	0	1	0	1	0	1	1	1	0
i=1(0,0,1)
i=2(0,1,1)
i=4(5,1,1)
i=6(2,4,1)
i=11(3,3,0)
i=15(1,3,1)
i=19(0,4,1)
i=24(3,3,1)
i=28(2,2,1)
i=31(0,2,#)

1行目は番号

2行目は先頭に0を参照部分並べ、その後に符号化したい数列を並べていく

3行目から計算スタート。左端に参照部の長さ分枠をつける。その右に符号化部の長さ分枠をつける。
符号化部の左端から参照を開始する。まずこの行の符号化部の右端の値は"1"。"1"を参照部の左端から見ていく。この場合は存在しないため、"i=1(0,0,1)"とする。
この文字列の意味は、"i=1"が、符号化部の右端のiの値。
(0,0,1)については後述する。

4行目、スライド窓を右に1個ずらす。符号化部の左端から1つ目の値は"0"。"0"を参照部の右端から見ていく。この場合一番右端から1つ目に"0"が存在する。
見つかった場合は桁数を増やしてみる。符号化部の値を右に1桁増やすと"01"。参照部に"01"はないため、これは放棄する。
i=2とし、(0,1,1)とする。
(0,1,1)について、1つ目は参照部で見つかった値の前に空きがあればその個数を入れる。今回は先頭に見つかったため0。2つ目の数字は見つかった桁数。1桁見つかったため1。最後は符号化部から参照した数字の右の数字。今回は"0"が見つかったため、その右の"1"を入れる。

5行目、スライド窓を"見つかった桁数 + 1"ずらし、同じようにすすめる。

最後まで参照したら最後は#にする。