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

Thêm vào BST

Báo xấu

81
lượt xem 19
download

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

Mục tiêu của luận văn này nhằm hệ thống các kiến thức về nén văn bản thông qua minh họa cụ thể và lý thuyết xác suất, từ đó đưa ra giới hạn nén của một văn bản.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

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

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
Đồ á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
Đồ á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
Đồ á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
Đồ á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
Đồ á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
Đồ á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
Đồ á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
Đồ á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
Đồ á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
Đồ á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
Đồ á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
Đồ á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
Đồ á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
Đồ á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
Đồ á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
Đồ á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
Đồ á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
Đồ á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