BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG……………

LUẬN VĂN

Nghiên cứu lý thuyết
mã nén văn bản dựa theo
mô hình Markov

class="bi xa yb w3 h8"
Đồ án tốt nghiệp Nghiên cứu lý thuyết mã nén văn bản dựa theo mô hình Markov
Lê Hùng Bách – Lớp CT901 1
tin
c
.
.
:
-
.
- .
.
:
Đồ án tốt nghiệp Nghiên cứu lý thuyết mã nén văn bản dựa theo mô hình Markov


.
- ,
64000b. 10%. (trang 22) .
- V ,
640000b. 15%. (trang 25)
.

a
b


5/2

3/1

Đồ án tốt nghiệp Nghiên cứu lý thuyết mã nén văn bản dựa theo mô hình Markov
Lê Hùng Bách – Lớp CT901 4 t
.
"0/
-
.

.
Markov
minh .

.
.
Đồ án tốt nghiệp Nghiên cứu lý thuyết mã nén văn bản dựa theo mô hình Markov
Lê Hùng Bách – Lớp CT901 5



.
1.1:
).
1.2
n
A
1
,a
2
, ,a
m
A
n
(
n
Lp
n
A
)()(
.
( ) - x
ha
.
Đồ án tốt nghiệp Nghiên cứu lý thuyết mã nén văn bản dựa theo mô hình Markov
Lê Hùng Bách – Lớp CT901 7


n
).
.
t
n
Đồ án tốt nghiệp Nghiên cứu lý thuyết mã nén văn bản dựa theo mô hình Markov
Lê Hùng Bách – Lớp CT901 8 n
.

entropy =
i
m
i
i
p
p
1
log
2
1={a
1

1i
i
2i
p
1
logp

m
1i
i
2i
p
1
logp
m
1i
i
2i
p
1
logp
k
1
.
.
).

adbadacbdcbacbdbacbacdcdacbadacbdba
cbacbacdbadacbacbacbadacbacbacbadcd
bacbadbacdbdcbacdacbacbacbacdda

30
(
2222
=1.98

Markov
. A. Markov (1856-1922) đưa ra.
Markov ).
).
.
- , S ={S
1
, S
2
, , S
m
} v
={a
1
,a
2
a
l
}.
Markov ). Markov
1.
Markov sinh ra.
.
Đồ án tốt nghiệp Nghiên cứu lý thuyết mã nén văn bản dựa theo mô hình Markov


1.
.
Markov
)F,P,(
k
Đồ án tốt nghiệp Nghiên cứu lý thuyết mã nén văn bản dựa theo mô hình Markov
Lê Hùng Bách – Lớp CT901 11 )p(P
i
ij
pF
Markov = (1,0,0, ,0).
}i|j{Pp
0k
)k(
ij
k.
:
)l(
j
)k(
i
)lk(
ij
ppp


Lê Hùng Bách – Lớp CT901 12 nh
PF
lim
n
n
=
1
m
1i
i
.
133).
1.2.
5
1i
i
1
.

5
4
3
2
1
5
4

75
.
0
0
25
.
0
0
0
0
75
.
0
0
25
.
0
0 1
=
2
=
3
=
4

{A
1
, A
2
, ,A
m i
ij
c
=1,2, ,
i
m
={
1
,
2
, ,
m
i
ij
w
=1,2, ,
i
m
i
m
1j
ij

n
A
ij
2
m
1i
m
1j
iji
w
1
logw
i
.
hơn entropy.
+

1i
c2i
c3i
c4i

101
19
log
101
19
101
26
log
101
26
101
26
log
101
26
101
30
log
101
30
(
2222
=1.98
, b, c, d”. Tuy nhiên
.
=
75
26
26)12730(
26
; p
21
=
1
26
26
;
a
22
=0
F =
2212
2111
pp
pp
=
49
75
1
26
75
0

- 3. =
2

1
2
1
a, 30
b, 7
d, 12
c, 26
b, 19
d=7

H×nh 1.3
Nguån 2. Entropy=1.55
Đồ án tốt nghiệp Nghiên cứu lý thuyết mã nén văn bản dựa theo mô hình Markov
Lê Hùng Bách – Lớp CT901 16

1
E
1
=
30
2612730

2

E
2
=
19
719
log
719
19
2
+
7
719
log
719
7
2
= 0.84036
- 5
.
E =
1
E
1
+
2
E
2
=

begin
randomize;
a:=0; b:=0; s:=1;
for i:=1 to 10000000 do
begi n
if s=1 then
if random < 26/(30+7+12+26) then
begin
s:=2;
b:=b+1;
end
else a:= a+1;
if s=2 then
begin
a:=a+1;
s:=1;
end;
end;
Pa:= a/(a+b);
Pb:=b/(a+b);
writeln(Pa:10:7,' ',Pb:10:7);
Đồ án tốt nghiệp Nghiên cứu lý thuyết mã nén văn bản dựa theo mô hình Markov
Lê Hùng Bách – Lớp CT901 18 Ea:= -30/(30+7+12+26)*ln(30/(30+7+12+26))/ln(2)
-7/(30+7+12+26)*ln(7/(30+7+12+26))/ln(2)
a, 30
b, 26
c, 26
d, 19
Entropy = 1.98
1
2
1
a, 30
b, 7
d, 12
c, 26
b, 19

(Dynanic Markov
Coding.)
.

1
b 2
entropy 1.11
2
3
d 7
b 22
c 1
c 1
a 2
c 1
b 2
d 8
a 28
d 4
entropy 1.93
2


. - kiêm nhi
.
u
72
c
v
90
a
b
80
82
Entropy = 0.7
H×nh 1.5
Entropy = 0.2
b
1
2
a
2
80

begin
assign(f,'c:\kpt1.txt');rewrite(f);
a:=ord('a');b:=ord('b');
da:=0;
db:=0;
for i:=1 to 640000 do
begin
if random<=2/3 then
begin
write(f,a);
da:=da+1;
end
else
begin
write(f,b);
db:=db+1;
Đồ án tốt nghiệp Nghiên cứu lý thuyết mã nén văn bản dựa theo mô hình Markov
Lê Hùng Bách – Lớp CT901 23 end
end;
close(f);
clrscr;
E:=(da/640000*ln(640000/da)+ db/640000*ln(640000/db))/ln(2);
writeln(' ty le nen con = ',round(E/8*100), '%');
Readln;

ba7/3p
a
7/4p
ba
b
3/2

2/1

2/1

3/1

H×nh 1.7