, .
, . , , - , , . , , 2 10 .
1). r, . r. r , , r .
:
9 5 7 0 1 2 4
9 5 7 0 1 2 5
9 5 7 0 3 8 6
9 5 7 0 3 9 0
1 2 3 4 5 6 7
1 2 3 4 5 9 1
1 2 3 4 5 9 3
:
9 5 7 0 1 2 4
r 5 r 3 8 6 r
9 0 1 2 3 4 5
6 7 r 9 1 r 3
() . : , r:
9 5 7 0 1 2 4
...... 5
.... 3 8 6
..... 9 0
1 2 3 4 5 6 7
..... 9 1
...... 3
. .
2). , . , r , . . . , . , , .
.
1 2 3 4 5 6 7 1 2 3 4 5 6 7
1 2 1 3 4 8 6 r 8 6 2 1
2 1 3 4 5 2 4 r 2 4 r 9
2 1 3 4 5 2 9 4 2 9 r r
4 2 9 4 5 2 9 r 5 r 1
4 2 9 4 5 2 9
4 2 9 4 5 2 9
5 2 9 4 5 2 1
, , ,
:
1 2 3 4 5 6 7
..... 8 6
2 1... 2 4
4 2 9....
.......
.......
5..... 1
, .
|
|
3). , r , .
, , X - 2, Z - 3, Y - 5,
1 9 7 1 1 3 7 4 3 0 1 9 7 1 1 3 7 4 3 0
1 9 7 1 1 3 7 4 3 1 Z X X 1 Z XX 2 Y2
1 9 7 1 1 3 7 4 3 2 Y X 0 Z X X1 ZXX
1 9 7 2 1 3 7 4 3 0 2
1 9 7 2 1 3 7 4 3 1
1 9 7 2 1 3 7 4 3 2
: , , Y, Z:
1 9 7 2 1 3 7 4 3 0
......... 1
......... 2
... 2..... 0
......... 1
......... 2
. .
LZW
.
. (J.Ziv), . (A. Lempel) 1977 ., . (Terry A.Welch) 1984 .
.
:
4.2.1
-1 -1 -1 -1 |
.
.
: Going, going, gone!
G ( 71) 71 .
o ( 111) 71 111. , 111 . 111 .
i ( 105) . 111 105. , , - . 258 , 71, 11, 105:
4.2.2 258
-1 -1 -1 -1 | Go oi |
, 9 (o going). 264 :
4.2.3 264
-1 -1 -1 -1 | Go oi in ng g, ,# #g go |
111 ( 263) i ( 105) . 111 105 257. :
- 257 n ( 110) .
|
|
257 110, .
:
4.2.4
-1 -1 -1 -1 | -1 | Go oi in ng g, ,# #g go oin ng, ,#g gon ne e! ! |
, 256 .
15 20 .
LZW:
, .