intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE

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

Chia sẻ: Nguyen Lan | Ngày: | Loại File: PDF | Số trang:91

82
lượt xem
19
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục tiêu của luận văn này nhằm hệ thống các kiến thức về nén văn bản thông qua minh họa cụ thể và lý thuyết xác suất, từ đó đưa ra giới hạn nén của một văn bản.

Chủ đề:
Lưu

Nội dung Text: 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

  1. 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
  2. Đồ á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 tin c . . : - . - . . : Lê Hùng Bách – Lớp CT901 1
  3. Đồ á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 - . - ,c . - . 4 chương: . : - 1 = 2/3, p2 = 1/3 = 2/3 log2(3/2)+ 1/3 log2(3) 0.918. Sau kh . (trang 19) - , 64000b. 12%. (trang 20) Lê Hùng Bách – Lớp CT901 2
  4. Đồ á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 2/3 1/ 2 b a 1/ 3 1/ 2 . - , 64000b. 10%. (trang 22) 3/ 5 1/ 7 b a 2/5 6/7 . - V , 640000b. 15%. (trang 25) 2/5 2/5 b a 1/ 5 3/ 5 2/5 c 1/ 3 2/3 . Lê Hùng Bách – Lớp CT901 3
  5. Đồ á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 t . "0/ - . . Markov minh . . . Lê Hùng Bách – Lớp CT901 4
  6. Đồ á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 trong khoa CNTT ,đ . Hải Phòng 7 năm 2009 ={a1,a2,....,am i 0/1. . . :A - . . .) . V . Lê Hùng Bách – Lớp CT901 5
  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 . 1.1: ). 1.2 An 1,a2,...,am An p ( ) L( ) An ( . n ( )-x ha . Lê Hùng Bách – Lớp CT901 6
  8. Đồ á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 Markov. ={a1,a2,....,am 1=p(a1), p2=p(a2),..., pm=p(am). = 1 2... n ( )= p( 1) p( 2)... p( n). . t n Lê Hùng Bách – Lớp CT901 7
  9. Đồ á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 n . m 1 entropy = p i log2 i 1 pi ={a1, a2, ..., am p1 p2 ... pm > 0. 1 m 1 p ( )L ( ) p i log2 n An i 1 pi (c m 1 p i log 2 i 1 pi m 1 1 m 1 p i log2 p i log2 . i 1 pi k i 1 pi . ). adbadacbdcbacbdbacbacdcdacbadacbdba cbacbacdbadacbacbacbadacbacbacbadcd bacbadbacdbdcbacdacbacbacbacdda Lê Hùng Bách – Lớp CT901 8
  10. Đồ á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 . Entropy=1.98 30 30 26 26 26 26 19 19 entropy= ( log2 log2 log2 log2 ) =1.98 101 101 101 101 101 101 101 101 Markov . A. Markov (1856-1922) đưa ra. Markov ). ). . - , S ={S1, S2, ..., Sm} v ={a1,a2...al}. Markov ). Markov 1. Markov sinh ra. . Lê Hùng Bách – Lớp CT901 9
  11. Đồ á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 - . - . ij i nh Aj i j ij i j ij : : pij 0 m m 1: p ij 1 . Do p ij j 1 j 1 1. . Markov ( k , P, F) Lê Hùng Bách – Lớp CT901 10
  12. Đồ á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 P (p i ) F p ij Markov = (1,0,0,..,0). p ij( k ) P{ k j| 0 i} k. : p ij( k l) p i( k ) p ( lj) . . Markov 0. Tro 0 sao cho min p ijn 0 0. i, j . Markov n n . Markov ergodic. 1.1. P={pi , F2P, F3 - Lê Hùng Bách – Lớp CT901 11
  13. Đồ á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 n nh lim F P = n m i 1. i 1 133). 5 1.2. i 1. i 1 5 0 0.25 0 0.75 0 1 1 1/4 1/4 0 0 0.25 0 0.75 2 2 0.75 0 0 0.25 0 3 3 1 4 0 0.75 0 0 0.25 4 4 3/4 0.25 0 0.75 0 0 5 5 1/4 1/4 3 2 1/4 H×nh 1.1 1 1= 2= 3= 4= 5= . 5 Lê Hùng Bách – Lớp CT901 12
  14. Đồ á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.3.3. Entropy. ci4 c i3 H×nh 1.2 c i2 c i1 {A1, A2,...,Am i c ij =1,2,.., m i ={ 1, 2,..., m mi 1 i w ij =1,2,.., m i Ei w ij log 2 j 1 w ij m m mi 1 i = iEi = i w ij log 2 i 1 i 1 j 1 w ij . 1.2 Markov. . p( ) L( ) m mi An 1 i w ij log 2 . n i 1 j 1 w ij hơn entropy. + Lê Hùng Bách – Lớp CT901 13
  15. Đồ á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 146). log2 p( ) 1.3. lim entropy . n n . . adbadacbdcbacbdbacbacdcdacbadacbdba cbacbacdbadacbacbacbadacbacbacbadcd bacbadbacdbdcbacdacbacbacbacdda . 1. Entropy=1.98 30 30 26 26 26 26 19 19 entropy= ( log2 log2 log2 log2 ) =1.98 101 101 101 101 101 101 101 101 , b, c, d”. Tuy nhiên . Lê Hùng Bách – Lớp CT901 14
  16. Đồ á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 a, 30 a, 30 b, 26 b, 7 c, 26 d, 12 d, 19 c, 26 1 1 2 b, 19 Nguån 1 d=7 Nguån 2. Entropy=1.55 H×nh 1.3 : . - 1. X 2. - 2. 30 7 12 49 26 26 26 p11= ; p12 = ; p21= 1; (30 7 12) 26 75 (30 7 12) 26 75 26 a22=0 49 p11 p 21 1 F= 75 = 26 p12 p 22 0 75 - 3. = 49 1 75 1 1 26 1 + 2= 1. 0 2 2 75 75 26 1= ; 2= . 101 101 - 4. Lê Hùng Bách – Lớp CT901 15
  17. Đồ á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 a=30 b=7 d=12 c=2 1 6 1 30 30 7 12 26 E1 = log2 + 30 7 12 26 30 7 30 7 12 26 + log2 + 30 7 12 26 7 12 30 7 12 26 + log2 + 30 7 12 26 12 26 30 7 12 26 + log2 = 1.80096 30 7 12 26 26 2 2 19 19 7 7 19 7 b=1 E2 = log2 + log2 = 0.84036 19 7 19 19 7 7 9 d=7 - 5 . 75 26 E= 1E1 + 2E2 = 1.80096 + 0.84036 = 1.55368. 101 101 1.55368 : 1 2 Lê Hùng Bách – Lớp CT901 16
  18. Đồ á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 n . var a, b, Ea, Eb, Pa, Pb: extended; i, s: longint; 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); Lê Hùng Bách – Lớp CT901 17
  19. Đồ á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 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) -12/(30+7+12+26)*ln(12/(30+7+12+26))/ln(2) -26/(30+7+12+26)*ln(26/(30+7+12+26))/ln(2); Eb:= -19/(19+7)*ln(19/(19+7))/ln(2) -7/(19+7)*ln(7/(19+7))/ln(2); writeln(Ea*Pa+Eb*Pb:10:5); end. . . c .N . adbadacbdcbacbdbacbacdcdacbadacbdba cbacbacdbadacbacbacbadacbacbacbadcd bacbadbacdbdcbacdacbacbacbacdda Lê Hùng Bách – Lớp CT901 18
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
3=>0