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
lượt xem 19
download
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.
Bình luận(0) Đăng nhập để gửi bình luận!
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
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Luận văn: Nghiên cứu ứng dụng công nghệ điện thoại trên Internet ( Internet Telephony VOIP)
117 p | 498 | 313
-
Luận văn nghiên cứu vấn đề an ninh mạng internet không dâyvà ứng dụng
114 p | 406 | 137
-
Luận văn:Nghiên cứu luật kết hợp và ứng dụng trong công tác quản lý kho hàng tại siêu thị metro
26 p | 539 | 106
-
Luận văn: Nghiên cứu hoạt động cung ứng thuốc tại bệnh viện đa khoa tỉnh Nam Định giai đoạn 2005 - 2007 - HV Quân Y
41 p | 480 | 101
-
Luận văn: Nghiên cứu áp dụng 5S tạo môi trường làm việc hiệu quả tại các phòng ban chức năng của công ty cổ phần dịch vụ du lịch đường sắt Hà Nội
84 p | 318 | 90
-
Luận văn: NGHIÊN CỨU XẠ KHUẨN THUỘC CHI STREPTOMYCES SINH CHẤT KHÁNG SINH CHỐNG NẤM GÂY BỆNH TRÊN CÂY CHÈ Ở THÁI NGUYÊN
77 p | 335 | 79
-
Luận văn:Nghiên cứu quá trình tạo sản phẩm probiotic nước trái cây từ vi khuẩn lactobacillus
26 p | 285 | 72
-
Tóm tắt luận văn Thạc sĩ: Nghiên cứu về chữ kí số và ứng dụng trong hóa đơn điện tử tại VNPT Hà Nội
23 p | 399 | 69
-
Luận văn nghiên cứu khoa học Hoàn thiện chính sách quản lý của Nhà nước về thương mại của nước Cộng hòa Dân chủ Nhân dân Lào đến 2020
215 p | 523 | 57
-
luận văn:NGHIÊN CỨU, TỔ CHỨC QUÁ TRÌNH DẠY HỌC MỘT SỐ KIẾN THỨC CHƯƠNG "CÁC ĐỊNH LUẬT BẢO TOÀN" (VẬT LÍ LỚP 10-NÂNG CAO) THEO QUAN ĐIỂM KIẾN TẠO
163 p | 138 | 49
-
Luận văn - nghiên cứu sự ảnh hưởng của trình độ học vấn đến mức sinh ở tỉnh Thanh Hoá
78 p | 302 | 48
-
Tóm tắt luận văn Thạc sĩ: Nghiên cứu về đối sánh chuỗi và ứng dụng trong phân phân tích sâu các gói tin
25 p | 209 | 35
-
Luận văn: NGHIÊN CỨU KHẢ NĂNG SINH TRƢỞNG, PHÁT TRIỂN MỘT SỐ DÒNG ĐẬU TƢƠNG NHẬP NỘI TỪ AUSTRALIA NĂM 2005 -2006 TẠI THÁI NGUYÊN
134 p | 142 | 31
-
LUẬN VĂN: Nghiên cứu thị trường với sự phát triển của doanh nghiệp Việt Nam
38 p | 150 | 24
-
Luận văn Nghiên cứu thống kê kết quả hoạt động sản xuất kinh doanh củaLuận văn Nghiên cứu thống kê kết quả hoạt động sản xuất kinh doanh của công ty Quản lý và Sửa chữa Đường bộ 240 công
63 p | 194 | 20
-
Tóm tắt luận văn Thạc sĩ: Nghiên cứu về dịch thống kê dựa vào cụm từ và thử nghiệm với cặp ngôn ngữ Anh – Việt
22 p | 133 | 19
-
LUẬN VĂN: Nghiên cứu máy móc và lao động trong quá trình sản xuất giá trị thặng dư
15 p | 89 | 7
-
Bài giảng Phương pháp nghiên cứu khoa học: Chương 10 - TS. Nguyễn Minh Hà
9 p | 79 | 5
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn