15.

-, . , .

1^77 1977 . ^) (1). 1^77. 1 .

\JL77 , .

1^77 . , .

1^77 "" , . , , . , , , .

,

. ( ) , .

LZ77 , :

- , ;

- ;

- , .

. 2G , l2 , 8. " Э MICROSOFT". .

" ", " ". , , " ", G , " ". , ^,,''). +1 . " ",

" ". (G,G,'y), . " -", " ". ..

LZ77 , . . . LZ77:

1) - ;

2) . . LZ77 "

".

()

()

<0,0,''>

<0,0,''>

<0,0,''>

'

<0,0,''>

<0,0,''>

■■...11

<,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 . LZ77 LZ78, .

LZ78 "" , . ( ). , . , , , , , . . , .

, LZ78 . , , +8 ( - ASCII).

. LZ78 " ", 16 .

 

( )

 

0

""

<0,''>

1

<0,''>

2

" "

<0,''>

3

" "

<0,''>

4

" "

<0,''>

5

" "

<3,''>

6

 

<0,' '>

7

" "

<1,''>

8

" "

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

LZ78 LZW : LZW- , .

. LZW " ". 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 = 1G8 .

, . . , , , .

LZW , , . .

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

► 29

"AABCDAACCCCDBB", " "

" ", , ,

LZ77 ( 12 , 4 ),

LZ78 ( 16 ),

LZSS ( l2 , 4 ),

LZW ( ASCII+ l6 ).

LZ78 LZW ? . LZW ASCII+.