15.

-, . . , . , .

LZ77 1977 . (Ziv) (Lempel). LZ77. LZ .

LZ77 , .

LZ77 . , .

LZ77 " " , . , , . , , , . ,

. ( ) , .

LZ77 , :

- , ;

- ;

- , .

. 20 , 12 , 8. " Э MICROSOFT". .

" ", " ". , , " ", 0 , " ". , (0,3,''). +1 . " ",

" ". (0,0,''), . " -", " ". ..

LZ77 , . . .

1^77:

1) - ;

2) . ,

. , 1^77 .

. 1^77 " ".

(8)

(5)

 

""

<0,0,''>

"......."

""

<0,0,''>

......

""

<0,0,''>

" "

<0,0,''>

" "

<0,0,''>

"..."

" "

<5,1,''>

."

" "

<0,0,' '>

" "

""

<0,4,''>

" "

"____"

<0,0,''>

, "" , . . .

: , 1. , 1^2( ), 1g2 ( +1). 8 (, 8+).

9 * (3 + 3 + 8) = 126 , 14 * 8 = 112 .

1982 . (81) (82181) 1^77 1^88, 1^77 .

, 1^88, , . : , 1^77. 1^88 1, . 1^88 , .

. 1^88 " ".

(8)

(5)

0''

9

"......."

0''

9

......

0''

9

0''

9

0''

9

..."

1<5,1>

7

.."

■■

0''

9

.

0' '

9

1<0,4>

7

...

1<4,1>

7

____

1<0,1>

7

7 * 9 + 4 * 7 = 91 . 1^77 1^88 :

1) , , ;

2) , , .

, , . . , . , -.

1978 . 1^77 1^78, .

178 "" , . ( ). , . , , , , , . . , .

, 1^78 . , , +8 ( - ASCII).

. LZ78 " ", 1 .

 

( )

 

0

<0,''>

1

<0,''>

2

<0,''>

3

<0,''>

4

<0,''>

<3,''>

<0,' '>

<1,''>

<3,''>

9

<1,''>

10

0 15, .

10 * (4 + 8) = 120 .

LZ77, LZ78 LZSS .

1984 . (Welch) LZ78 LZW.

-. 1. ( 256 ASCII). w . 2. K . 3. w

wK

wK

2

w

wK

K

2.

1^78 \JZWf : 1^"\¥- , .

. "

". 500 .

, wK ( )

w

ASCII+

 

0-255

""

0''

256

""

0''

257

""

0''

258

""

0''

259

""

0''

260

" "

0''

261

" "

0''

262

" "

0' '

263

" "

<256>

264

" "

<258>

265

" "

0''

266

" "

0''

 

12 * 9 = 108 .

, . . , , , .

LZW , , . .

LZW. LZW IBM Unisys, Unisys, . , LZW Unix compress.

► 30

"AABCDAACCCCDBB", "" " ", , ,

LZ77 ( 12 , 4 ),

1^78 ( 16 ), 1^88 ( 12 , 4 ), ( 811+ 16 ).

► 31

1^78 \JZWf ? . 1^"\¥ 811+.