Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/s43/math/uroki/2009_2010/9mat_0910/spec/15_Data_Compression_Codes_Information.pdf Дата изменения: Sun Sep 2 21:11:49 2012 Дата индексирования: Tue Feb 5 08:28:43 2013 Кодировка: Поисковые слова: вечный календарь

.
. . . , . , . : , , , . . , ? , ? : * , , . * , , , . , , ( ) , - . . A = { a, b, c, d } 1 1 1 1 P = { /2, /4, /8, /8}. C0. 0 1. , a b c d C0 1000 0100 0010 0001 4 4 4 4

, : ( abd ) = 100001000001. , 0 1. , C0 . , ?



0 1 , . a - 10, b - 101, - 1000, d - 10001 "10101...", "abd". ? a b, . "1010...", , : a, ab, ac ad. , . . , , , . : { 0, 10, 11, 100 } , -- . , 010011 : "0 10 0 11" "0 100 11". , . -- prefix, "" . http://ru.wikipedia.org/wiki/_ : . { 0, 10, 11 } . 01001101110 : 0 10 0 11 0 11 10. . ? C1 = { 0, 101 } - 0 101. . C2 = { 1, 101 } - 1 101. . . C3 = { 0, 10, 110, 111 } - . C4 = { 00, 01, 10, 11 } - .


, - . , , , . A = { a, b, 1 1 P = { /2, /4 C3 = { 0, 10, c, 1 , /8 , 110, d }, 1 /8} = { pa, pb, pc, pd }. 111 } = { C(a), C(b), C(c), C(d) }.


a b c d

P() C3 L3
1 1 1 1

/2 /4 /8 /8

0 10 110 111

1 2 3 3

: L3 = { 1, 2, 3, 3 } = { L(a), L(b), L(c), L(d) }. 0 1, N = 4 . L = ( L(a) * /2 + L(b) * /4 + L(c) * /8 + L(d) * /8 ) * 4 = 1 1 1 1 9 = ( 1 * /2 + 2 * /4 + 3 * /8 + 3 * /8 ) * 4 = /4 * 4 = 1.75 * 4 = 7. , , , - 1.75 . 4 - 7 . : C4 = { 00, 01, 10, 11 }. C5 = { 0, 1, 00, 11 }. 000111000. ? C6 = { 0, 10, 011, 111 } - C3 . , C3: - 1.75 . 4 - 7 . ? , . "0", - . ? - "0". {100, 101, 110, 111}. , , , "100" ( 3) "1000" "1001" ( 4). -( ) 2 : :
1 1 1 1

{ 0, 1 }, . , . 0 1 . ( ).


. , , .


http://algolist.manual.ru/compress/standard/huffman.php . 1. . 0 1. 0, - 1. 2. . 3. 1 2, . . A = { a, 1 P = { /4, C = { 00, b, c, d, e }. 1 3 /4, /5, /20, 3/20 }. 10, 11, 010, 011 }.

1

1.0 4 0| 0.55 3 2 1 P() 0| 0.25 | 0.25 | 0.25 a 00 \1 0.45 _ \1 0.3 | 0.3 0| \ 1 0.15 d 010 0.15 e 011 | 0.2 c 11 0.2 | 0.45 0| \ 1 0.25 | 0.25 b 10

|_ _ _|_ _

N ; , 1 . . , . . , , - ? , . ,


. , . , , . .


. -- .
: , , 15? "" "". , 9 :

1: 2: 3: 4:

?

? ? ?

. ( - 1, - 0), . 13. 0 1 , 2 = 16 . 4 p=1/2 , 4 , . 2 , , 1 5, , , . : p1=p5=0.35, -- pi = 0.3/12 = 3/120 = 1/40 = 0.025. ? , - , . - 4 . , ? "" "", -- , . . , - . : , - . , . , , , , . , .
4


, : : ?


, . . , . : , 2 = 8 , . . ( ), . 3 . , : a - 000, b - 001, c 010, ... g - 110, h - 111. , : . , d = 1/16 , 4 , 2 : a - 00, b - 01, c - 10, d - 11. d - , d. . : 0 1. p0 = 0.9 p1 = 0.1. N = 100. * x = 1011010010...101, k N - k . k N-k P(x) = p1 p0 . , 0. 1. * x N, k N - k ? , k N - k k k N-k CN p1 p0 . k?
3




* k N - k CN p1 N-k p0 k = N p1. *

k

k

. , k, . .

: N = 1000, p1 = 0.1, 1-p = 0.9.

, 150 1000 . . , , 150 . , , 100 1000 , .