(. 2.2): ( - ), ; . , . , , .
2.2.1.
, , ZIP, RAR.
80- . .
, n X n X.
, X , ,
ML(X) ³ H X.
( -),
H X ³ M L (X) 1.
X 1 X 2 , .. H X 1 = H X 2, I(X 1, X 2) = 0
H(X 1, H X 2) = 2 H X 1.
X (X 1, X 2). n - H X = n H X 1.
L 1(X) = L (X)/ n X.
M L (X) 1 ≤ H X ≤ M L (X),
M L 1(X) 1/ n ≤ HX1 ≤ M L 1(X).
, n .
:
1) n ;
2) ;
3) , .
4) (. 2.1) .
.
- . .
-. . . 0, , . 2.1. , , .
2.1
X | p(x) | Code(X) | ||
x1 | 1/4 | |||
x2 | 1/4 | |||
x3 | 1/8 | |||
x4 | 1/8 | |||
x5 | 1/16 | |||
x6 | 1/16 | |||
x7 | 1/16 | |||
x8 | 1/16 |
[3] . 2.2.
|
|
2.2
X | p(x) | - | ||||
x1 | 1/4 | I | I | |||
x2 | 1/4 | II | ||||
x3 | 1/8 | II | I | I | ||
x4 | 1/8 | II | ||||
x5 | 1/16 | II | I | I | ||
x6 | 1/16 | II | ||||
x7 | 1/16 | II | I | |||
x8 | 1/16 | II |
. , . 2.3.
2.3
X | p(x) | |||||||
x1 | 0,3 | |||||||
x2 | 0,2 | 0,6 | ||||||
x3 | 0,15 | 0,3 | ||||||
x4 | 0,15 | |||||||
x5 | 0,1 | 0,2 | 0,4 | |||||
x6 | 0,05 | |||||||
x7 | 0,5 | 0,1 |
, . 2.3 . -. .
- . . , . LZZ, . , .
LZZ : ; . LZZ.
LZ , ARJ, PKZIP. , , .
( RAR), .
2.2.2.
, .. .
, , .
.
, .
. 40- .
.
1. . , , , . . , , . , , .
|
|
. .
2. -. , 4
, .
: . , , .
, . , ,
.
, : . .
.
20 6 16 18 10 33 10 15 22 16 18 14 1 24 10 10
12 10 2 6 18 15 6 20 10 12 1 12 10 2 6 18
32 16 18 24 28 15 16 2 32 28 19 26 11 26 16 28
, - . .
, : ; ; .
, .
. p, , (p - 1) a b, . a b .
(a b ) a a º 1(moj(p)), 0 < a < p - 1 b b º 1(modj(p)), 0 < b < p - 1. (p - 1), , (p - 1).
m, m < (p - 1), m 1 = ma (modj(p)). , , m 2 = m 1 b (moj(p)) . m 3 = m 2 a (moj(p)) , , b, .
, m 4 = m 3 a = m a a b b(modj(p)), a a b b º 1 (modj(p)) a a b b = k j(p) +1 k, mk j(p) +1 º (m j(p)) km (modj(p)) º m - m j(p) º 1 (modj(p)) .
2.1. p = 23 (j(23) = 22), a = 5, b = 7. 5a = 1 (mod j(23)) a = 9, 7b = 1 (mod j(23)) b = 19. m = 17.
, . 2.3.
. , .
, , ( ). , , .
. P (y / x) y x. ().
P (y / x) = 1 y = x P (y / x) = 0 y ¹ x, . .
|
|
C = lim(log2 N (T)/ T),
T à ¥
N (T) T.
, , . , .
e, .
( ). X. . u, X, e > 0 u¢ < u u , u¢ e, u = C /HX. .
( ). u¢ > u e > 0, u¢ e e, u¢.
( ). .
. , . 2.4, p ; q - .
(m, n)- , E: Z 2 m à Z 2 n D: Z 2 n à Z 2 m, Z 2 . m < n, m = n . D E H = DTE, T , D E ().
.
d (a, b) a b n , .
w (a) a = { ai, i = 1, n } .
n
w (a) = S ai.
i = 1
a = 1001, b = 0011 d (a, b) = 2, w (a) = w (b) = 2.
Å ( mod2, ). d (a, b) = w (a Å b).
, a n b , pn d ( a , b ) qd ( a , b ). , 1011 0011 p3.
, : .
k, , k +1.
n
S in p n-i q i.
i = 1
k, , 2 k +1.
n
S in p n-i q i,
i = k +1
k
S in p n-i q i.
i = 0
, (n r, n)- 2 k +1 r ,
r ³log2( kn + C k- 1 n + + C1 n + 1).
( -)
|
|
r >log2(2 k- 1 n- 1 + 2 k- 2 n- 1 + + C1 n- 1 + 1),
(n r, n)-, k .
.
, .
, . , . .
, n k
Pn (k) = Cknpn-kqk.
2.1. m = 2 ( E) : 00 à 000; 01 à 011; 10 à 101; 11 à 110.
q 3 + 3 pq 2 + 3 p 2 q. p 3 + 3 p 2 q, q 3 + 3 pq 2.
(m, 3 m) m . .
.
.
() .
.
1. .
2. .
3. .
4. .
.
. . E = (eij) m ´ n. a m, b = aE. m 2 m . , m E . r ³ 2 d 2 log2 d, n ³ 2 d 2=1.
[1] , .
, . . (a 0, a 1,, a m-1) a (x) = a 0 + a 1 x , a m-1 x m-1. . 2: 2. .
. 16 32 . , , .