ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN Vũ Văn Minh ĐỀ TÀI ỨNG DỤNG PHƯƠNG PHÁP MOVE-TO-FRONT TRONG NÉN DỮ LIỆU Chuyên ngành: Bảo đảm tốn học cho máy tính hệ thống tính toán Mã số: 60.46.35 LUẬN VĂN THẠC SĨ KHOA HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC GS.TSKH Nguyễn Xuân Huy Hà Nội, năm 2011 Ứng dụng phương pháp Move to front nén liệu DANH MỤC HÌNH VẼ, BẢNG BIỂU DANH MỤC CÁC TỪ VIẾT TẮT Mở đầu .8 Chương TỔNG QUAN VỀ NÉN DỮ LIỆU .9 1.1 Thông tin, liệu mã hóa 1.2 Dữ liệu ký hiệu 10 1.3 Sự thay đổi độ dài mã 11 1.3.1 Tính để giải mã .11 1.3.2 Mã tiền tố nhị phân 12 1.4 Cơ lý thuyết thông tin 13 1.4.1 Entropy 13 1.4.2 Mã tối ưu 15 1.5 Sự dư thừa liệu 15 1.6 Nén liệu 16 1.6.1 Nén giải nén liệu 16 1.6.2 Nén có thơng tin nén không thông tin .17 1.6.3 Nén theo khối liệu 18 1.7 Mã hóa Entropy 18 1.7.1 Mã hóa Huffman 19 1.7.2 Mã hóa số học 19 Chương NÉN DỮ LIỆU VÀ PHƯƠNG PHÁP MOVE-TO-FRONT 20 2.1 Thuật toán mã hóa độ dài (RLE) 20 2.1.1 Giới thiệu RLE .20 Ứng dụng phương pháp Move to front nén liệu 2.1.2 Mã hóa 21 2.1.3 Giải mã 23 2.2 Thuật tốn mã hóa Huffman 24 2.2.1 Giới thiệu thuật tốn mã hóa Huffman 24 2.2.2 Mã hóa Huffman 28 2.2.3 Giải mã Huffman 29 2.3 Thuật toán nén số học 31 2.3.1 Giới thiệu nén số học 31 2.3.2 Mơ hình nén số học 32 2.3.3 Trường hợp tổng quát nén số học .35 2.3.4 Ví dụ nén số học 37 2.4 Phép biến đổi Burrows-Wheeler (BWT) 39 2.4.1 Giới thiệu BWT 39 2.4.2 Mã hóa 39 2.4.3 Giải mã 42 2.5 Phép biến đổi Move-To-Front (MTF) 45 2.5.1 Giới thiệu MTF 45 2.5.2 Mã hóa 45 2.5.3 Giải mã 47 2.6 Phân tích phương pháp MTF 48 2.6.1 Tổ chức liệu 48 2.6.2 Thực .49 2.7 Lược đồ nén liệu ứng dụng phương pháp MTF 49 2.7.1 Lược đồ nén liệu 49 Ứng dụng phương pháp Move to front nén liệu 2.7.2 Nén liệu 50 2.8 Một số cải tiến phương pháp MTF 51 2.8.1 Một số định nghĩa 51 2.8.2 Cơ sở MTF 52 2.8.3 Một số cải tiến MTF 53 Chương KẾT QUẢ THỰC NGHIỆM .55 3.1 Môi trường thực nghiệm 55 3.2 Dữ liệu mẫu 55 3.3 Phân tích thực nghiệm kết 56 3.3.1 Áp dụng MTF với thuật toán nén Huffman 56 3.3.1 Áp dụng MTF với thuật toán nén số học .58 3.4 Kết luận 59 PHỤ LỤC .62 Ứng dụng phương pháp Move to front nén liệu DANH MỤC HÌNH VẼ, BẢNG BIỂU Hình Cây nhị phân mã Huffman .12 Hình Mã tiền tố 13 Hình Nén liệu khơng thông tin 17 Hình Nén liệu có thơng tin 18 Hình Phương pháp nén RLE (1) .20 Hình Phương pháp nén RLE (2) .21 Hình Minh họa nén theo phương pháp Huffman 27 Hình Cây Huffman nén liệu .27 Hình Mã hóa Arithmetic với hai ký hiệu 31 Hình 10 Minh họa phân đoạn với khối liệu “IOU” .34 Hình 11 Minh họa cách giải mã Burrows - Wheeler 42 Hình 12 Minh họa cách giải mã ví dụ 43 Hình 13 Lược đồ nén liệu Burrows-Wheeler 49 Hình 14 Thể bước nén khối liệu 51 Hình 15 Mơi trường lập trình Dev C++ 55 Bảng Mô tả thông tin với mã Huffman .19 Bảng Mô tả trường hợp xuất ký hiệu nén 21 Bảng Bảng mã nhị phân mở rộng với hai ký hiệu 32 Bảng Bảng xác suất phân đoạn ký hiệu 37 Bảng Mã hóa theo phương pháp số học 38 Bảng Giải mã theo phương pháp số học 38 Bảng Mơ tả q trình mã hóa MTF 46 Bảng Mơ tả q trình giải mã MTF 47 Bảng Các tệp tin mẫu để thực nghiệm 56 Bảng 10 Kết thực nghiệm 57 Bảng 11 So sánh phương pháp nén MTF0, MTF1, MTF2 58 Bảng 12 Số lần xuất ký hiệu tệp tin paper1 ban đầu 63 Bảng 13 Số lần xuất ký hiệu sau sử dụng MTF .64 Ứng dụng phương pháp Move to front nén liệu DANH MỤC CÁC TỪ VIẾT TẮT Từ viết tắt Viết đầy đủ ASCII American Standard Code for Information Interchange BIT BInary digiT BMRH BWT- MTF- RLE- Huffman BRH BWT - RLE- Huffman BWCA Burrow-Wheeler Compression Alogrithm BWT Burrow-Wheeler Transform EC Entropy Coding GIF Graphics Interchange Format JPEG Joint Photographic Experts Group 10 MPEG Moving Picture Experts Group 11 MTF Move-To-Front 12 RLE Run Length Encoding TT Ứng dụng phương pháp Move to front nén liệu Mở đầu Nén liệu sử dụng rộng rãi, lĩnh vực cơng nghệ thơng tin Những hình ảnh mà thấy trang Web hình ảnh nén JPG, GIF phim có định dạng MPEG nén để đảm bảo sử dụng dung lượng xem trực tuyến tải từ internet, số tệp tin hệ thống máy tính tự động nén lưu trữ Vậy nén liệu gì? Có nhiều phần mềm nén liệu công bố zip, gzip winzip (và nhiều nữa) để giảm bớt dung lượng trước lưu trữ truyền Mục đích luận văn nghiên cứu phương pháp Move-To-Front (MTF) nén liệu MTF kỹ thuật biến đổi mã ký hiệu, thường dùng bước thứ hai thuật toán nén liệu Burrow-Wheeler compression algorithm [10] Bước thuật toán nén liệu BWCA phép biến đổi Burrow-Wheeler transform [9] giới thiệu lần vào năm 1994 hai tác giả Burrow Wheeler, BWT biến đổi vị trí ký hiệu cho ký hiệu giống đứng cạnh nhau, bước thuật toán phương pháp MTF, phương pháp xử lý liệu đầu phương pháp BWT để liệu có khả nén cao với mã nén Entropy (một cách khác thuật tốn BWCA có thêm bước mã nén theo độ dài – Run-Length Encoding (RLE)) Ngày nay, phương pháp BWT kết hợp MTF ứng dụng để nén với nhiều loại liệu khác văn bản, hình ảnh, âm phim Luận văn tập trung nghiên cứu phương pháp MTF số cải tiến phương pháp nén văn để đạt hiệu cao Ứng dụng phương pháp Move to front nén liệu Chương TỔNG QUAN VỀ NÉN DỮ LIỆU 1.1 Thông tin, liệu mã hóa Thơng tin thể kiến thức tư người hiểu biết trạng thái hệ thống – thơng tin không chắn Con người cảm nhận tồn thông tin, nhận biết đa dạng phương tiện mang thông tin lúc nhận thấy tác động ngược trở lại thơng tin người – thông tin chắn Thông tin không hữu thiết bị vật lý, tồn liệu logic chứa phương tiện vật lý đĩa CD hay kênh truyền thơng tin Vì liệu xem dạng số thông tin thực Điều tạo nên khác biệt thông tin với văn bản, đồ họa, âm thanh, hình ảnh… Một lượng lớn thông tin cần phải tổ chức, lưu trữ dạng tệp tin thông điệp Ví dụ với liệu “-300C” mang thơng tin thực “Trời lạnh” mẩu tin suy diễn từ đoạn văn “âm ba mươi độ C” mẩu tin thể trang báo, truyền hình cơng cụ đo nhiệt độ Nếu khơng có phương tiện thơng tin khơng thể Thuật ngữ liệu nén liệu dạng số hóa thơng tin thực xử lý chương trình máy tính Dữ liệu trước nén gọi liệu nguồn Một số ví dụ thơng tin thực phân loại rộng rãi văn bản, âm thanh, hình ảnh phim Nhiều chương trình ứng dụng nhận kiểu thơng tin kiểu tệp tin phù hợp với cách xử lý chúng Do liệu phân loại dạng văn bản, hình ảnh, âm phim chương trình xử lý số hóa liệu coi thơng tin chuỗi BIT định dạng nhị phân Ứng dụng phương pháp Move to front nén liệu Văn bản: liệu thường thể dạng BIT mã ASCII Chúng xuất tệp tin có phần mở rộng txt doc sử dụng phần mềm soạn thảo Nhị phân: dạng liệu thường xuất tệp tin liệu, tệp tin thi hành mã chương trình Các tệp tin thường có phần mở rộng bin Hình ảnh: liệu thường thể mảng hai chiều điểm ảnh, điểm ảnh mã màu xác định Phần mở rộng tệp tin bmp chương trình xử lý ảnh bitmap Windows psd chương trình xử lý ảnh Photoshop Đồ họa: liệu dạng vector phương trình tốn học Ví dụ liệu dạng png dạng chuẩn Portable Network Graphics Âm thanh: liệu thể dạng sóng âm Định dạng tệp tin âm wav Mã hóa q trình xử lý chuỗi ký tự (chữ cái, chữ số, ký hiệu …) thành dạng đặc biệt để tốt truyền lưu trữ Mã hóa sử dụng hầu hết máy tính cho tệp tin văn mã hóa ASCII, ký tự mã hóa dạng biểu diễn BIT nhị phân 1.2 Dữ liệu ký hiệu Các ký hiệu ký tự sử dụng đầu vào thuật toán nén liệu cách thể phù hợp cho thuật toán nén mà đề tài đề cập đến Văn bản, hình ảnh, âm hay phim xem xét khối liệu bao gồm mảng chiều ký tự xét đến thuật toán Khối liệu nguồn S=(s1, s2, s3, … , sn) coi chuỗi ký tự s1, s2, s3, … , sn Thể dạng số hóa tập ký tự S C=(c1, c2, c3, …, cn), với ci gọi từ mã đại diện cho ký tự si (i=1,2,3, ,n) Việc biến đổi ký tự si để ci gọi q trình mã hóa, ngược lại biến đổi từ ci 10 Ứng dụng phương pháp Move to front nén liệu thành si gọi giải mã Sự thể ký hiệu mã ASCII có độ dài 8-bit Số bit từ mã gọi độ dài mã 1.3 Sự thay đổi độ dài mã Đối với ký tự thơng thường bảng mã ASCII mã hóa 256 ký tự khác nhau, ký tự có độ dài mã 8-bit Để biểu diễn chuỗi ký tự S=“banana” theo cách thông thường ta cần 48-bit Nhưng nén liệu ta loại bỏ ký hiệu khơng có liệu nguồn, mà ta mô tả ký hiệu xuất liệu nguồn mà Như vậy, với chuỗi ký tự S ta lưu bảng ký hiệu với mã tương ứng cho ký hiệu là a=00, b=01, n=10 Vậy để biểu diễn chuỗi ký tự S lúc ta cần 12-bit Tuy nhiên cịn có cách khác ta giảm bớt số bit ký tự cách thay đổi độ dài từ mã mà đảm bảo liệu xác 1.3.1 Tính để giải mã Thay đổi độ dài từ mã tốt cho việc nén liệu Tuy nhiên thay đổi độ dài từ mã vơ ích khơng xác định tính từ mã thông điệp cần mã hóa Nghĩa ký hiệu phải có từ mã Xét từ mã (0, 10, 010, 101) tương ứng với ký tự (a, b, c, d) Một đoạn mã hóa thơng điệp “0100101010” giải mã với nhiều kết khác “0 10 010 101 0” abcda “010 101 010” cadc Một mã có tính để giải mã có cách để giải mã thơng điệp mã hóa Tất nhiên có cách khác để làm việc này, ví dụ thêm dấu “/” để phân cách từ mã “0/10/010/101/0”, điều phản tác dụng ta nén liệu, làm tăng dung lượng liệu nén khó khăn thao tác nén giải nén Tuy nhiên điều cho ta ý tưởng tự phân cách ký tự thông điệp giải mã cách tổ chức dạng nhị phân Tính chất tự phân cách thể rõ ta biểu diễn dạng nhị phân Hình Mỗi nhánh bên trái ký hiệu nhánh bên phải 11 Ứng dụng phương pháp Move to front nén liệu ký hiệu sử dụng để biến đổi khối liệu thứ tự ban đầu Chỉ số số nguyên có giá trị từ đến n-1 (n số lượng ký tự khối liệu nguồn), đặt vị trí khối liệu mã hóa BWT Giai đoạn thứ hai phương pháp dịch chuyển MTF, sử dụng thuật toán nén liệu BWCA MTF thuật toán cập nhật lại khối liệu cách thay ký hiệu lặp lại thường xuyên ký hiệu có số thứ tự MTF khơng làm thay đổi kích thước khối liệu Điều kỳ diệu trước giai đoạn phương pháp BWT làm biến đổi vị trí ký hiệu, ký hiệu giống đứng cạnh nhau, di chuyển ký hiệu đứng đầu phía trước ký hiệu sau có mã “0” Giai đoạn thứ ba nén số lượng ký hiệu sử dụng thuật toán RLE Thuật toán RLE dồn ký hiệu lặp lặp lại nhiều lần cách thay số lần lặp ký hiệu Như thuật tốn thu nhỏ kích thước khối liệu lại làm tăng số ký hiệu khối liệu RLE phải lưu giữ số lần lặp ký hiệu đó, số lần lặp số nguyên mã ký hiệu có giá trị từ đến 255, số lần lặp lớn 255 ta phải dồn thành hai đoạn Giai đoạn thứ tư phương pháp nén liệu Entropy Entropy Coding phương pháp nén liệu không thơng tin, phụ thuộc vào tần suất xuất ký hiệu Trong phương pháp mã hóa Entropy có thuật tốn Huffman Coding Arithmetic Coding 2.7.2 Nén liệu Để làm rõ giai đoạn nén liệu khác nhau, hình 14 hiển thị dịch chuyển khối liệu đầu vào "abracadabraabracadabra" mã Hexa Khối liệu toán thực tế 64KB, ví dụ ta bỏ qua số ký hiệu phép dịch chuyển BWT 50 Ứng dụng phương pháp Move to front nén liệu BWT input: 61 62 72 61 63 61 64 61 62 72 61 61 62 72 61 63 61 64 61 62 72 61 BWT output: 61 72 72 64 64 61 72 72 63 63 61 61 61 61 61 61 61 61 62 62 62 62 MTF output: 61 72 00 65 00 02 02 00 65 00 02 00 00 00 00 00 00 00 65 00 00 00 RLE output: 61 72 00 65 00 02 02 00 00 65 00 02 00 00 05 65 00 00 01 Huffman: 89 67 EC E5 62 03 Hình 14 Thể bước nén khối liệu "abracadabraabracadabra" Ta nhận thấy giai đoạn BWT kết xuất khối liệu có ký hiệu ngữ cảnh lặp lặp lại liên tiếp Giai đoạn MTF tạo ký hiệu có mã 00 nhiều so với khối liệu ban đầu Giai đoạn thứ ba RLE dồn ký hiệu giống lại với ghi lại số lần lặp ký hiệu Trong ví dụ ta thấy có ký hiệu 00 nén lại thành “00 00 05”, nghĩa có ký hiệu đứng sau ký hiệu 00 Giai đoạn thứ thuật toán Huffman xử lý chuỗi BIT theo cấu trúc Huffman Hai giai đoạn BWT MTF khơng làm thay đổi kích thước khối liệu Trong thuật tốn RLE Huffman làm thay đổi kích thước khối liệu nguồn Trong ví dụ tác giả bỏ qua liệu thêm vào số ký hiệu thuật toán BWT, cấu trúc Huffman thuật toán nén Entropy Tuy nhiên nhiều trường hợp khác, liệu thêm vào không đáng kể so với hệ số nén thuật toán 2.8 Một số cải tiến phương pháp MTF 2.8.1 Một số định nghĩa Để mô tả thuật toán, ta ký hiệu A bảng mã ký hiệu thứ tự với kích thước |A|, ký hiệu X = x0 x1 x2 … xn-1 chuỗi ký hiệu xuất liên tiếp có độ dài n xi A với ≤ i ≤ n-1 Chỉ số chuỗi Mỗi giai đoạn có chuỗi vào Xin chuỗi kết Xout tương ứng với bảng mã ký hiệu vào Ain bảng mã ký hiệu Aout Mỗi giai đoạn xử lý ký hiệu Xin tính tốn ký hiệu tương ứng Xout Sau kết thúc giai 51 Ứng dụng phương pháp Move to front nén liệu đoạn, Xout giai đoạn sử dụng Xin giai đoạn Kích thước tối đa khối Xin bn Đối với hầu hết giai đoạn, Ain Aout có kích thước |Ain| = |Aout| = 256, ký hiệu Ain Aout bit 2.8.2 Cơ sở MTF Giai đoạn MTF biến đổi chuỗi ký hiệu đầu vào trở thành chuỗi số ký hiệu tương ứng Đối với ký hiệu Xin, số đầu đưa Xout Chỉ số nhỏ hơn, gần tương ứng với ký hiệu thường xuyên xuất cuối Để tính tốn giá trị số, danh sách xếp theo thứ tự ký hiệu sử dụng Ban đầu danh sách xếp tăng dần theo bảng chữ Mỗi lần ký hiệu Xin xử lý ký hiệu tương ứng tìm danh sách, số ký hiệu đưa Xout ký hiệu di chuyển tới vị trí danh sách Như vậy, ta có chuỗi ký hiệu xuất liên tiếp Xin có độ dài m ta có m-1 ký hiệu có số Xét chuỗi ký hiệu xuất liên tiếp X1 = “baaaaaacccdddddaaaa” với số lần xuất ký hiệu sau a(10), b(1), c(3), d(5); sau xử lý xong với MTF xét bảng chữ “abcd” ta chuỗi số sau: X2=“1100000200300002000” có số lần xuất số sau 1(2), 0(14), 2(2), 3(1) MTF biến đổi ký hiệu có số lần xuất gần tương đương làm xuất nhiều ký hiệu có số Đối với giai đoạn mã hóa Entropy điều mang lại hiệu nén cao so với chuỗi ban đầu Cụ thể với thuật toán nén Huffman ta có H(X1)=32 bit, H(X2) = 27 bit Một vấn đề giai đoạn MTF di chuyển trực tiếp ký hiệu lên đầu danh sách ký tự xuất khơng có lợi Vì Balkenhol, Kurtz, Shtarkov[1] cải tiến phương pháp MTF gọi MTF-1 Balkenhol and Shtarkov [2] cải tiến phương pháp gọi MTF-2 Các cải tiến MTF trở nên phức tạp hiệu nén cao 52 Ứng dụng phương pháp Move to front nén liệu 2.8.3 Một số cải tiến MTF Trong phần trước tác giả trình bày phương pháp biến đổi MTF hay gọi MTF0 Balkenhol, Kurtz and Shtarkov [1] đề xuất sửa đổi phương pháp MTF nhằm cải thiện tỉ lệ nén, phương pháp gọi MTF-1 Sửa đổi đơn giản sau: ký hiệu có vị trí thứ hai di chuyển vị trí danh sách, cịn ký hiệu có vị trí lớn hai di chuyển vị trí thứ hai danh sách Để so sánh ta xét chuỗi X1 = “baaaaaacccdddddaaaa” danh sách “abcd” sau: baaaaaacccdddddaaaa MTF 1100000200300002000 MTF-1 1100000210310002100 Balkenhol and Shtarkov [2] đề xuất thêm sửa đổi thuật toán MTF-1 để thuật tốn gọi MTF-2, sửa đổi sau: ký hiệu có vị trí thứ hai di chuyển vị trí danh sách ký hiệu di chuyển trước khơng phải vị trí danh sách Sự thay đổi mã nguồn hai phương pháp MTF1 MTF2 đoạn di chuyển ký hiệu sau: Thay đổi phương pháp MTF1 if(i==1){ //Nếu vị trí ký hiệu (vị trí thứ hai) p->prev = NULL; p->next = head; head->prev = p; head = p; }else{ p->prev = head; p->next = head->next; 53 Ứng dụng phương pháp Move to front nén liệu head->next->prev = p; head->next = p; } Thay đổi phương pháp MTF2 if((i==1)&&(last_pos!=0)){ //Nếu vị trí ký hiệu p->prev = NULL; //vị trí ký hiệu trước p->next = head; // khác head->prev = p; head = p; }else{ p->prev = head; p->next = head->next; head->next->prev = p; head->next = p; } last_pos = i; 54 Ứng dụng phương pháp Move to front nén liệu Chương KẾT QUẢ THỰC NGHIỆM 3.1 Môi trường thực nghiệm Các tệp tin tác giả thực nghiệm môn trường Dev-C++ Dev-C++ có đầy đủ đặc Mơi trường phát triển tích hợp (Integrated Development Environment - IDE) ngơn ngữ lập trình C/C++ Hình 15 mơ tả chương trình thực nghiệm Hình 15 Mơi trường lập trình Dev C++ 3.2 Dữ liệu mẫu Để thực nén liệu minh họa phương pháp MTF, tác giả sử dụng tệp tin có cấu trúc liệu thông tin khác nhau, thực theo hai lược đồ nén BMRH BRH Có 16 tệp tin có kích thước kiểu liệu khác thử nghiệm, thông tin tệp tin sau: TT Tệp tin Mơ tả Kích thước (bytes) bib Bibliography 111261 book1 Fiction book 768771 book2 Non-fiction book (troff format) 610856 geo Geophysical data 102400 55 Ứng dụng phương pháp Move to front nén liệu news USENET batch file 377109 obj1 Object code for VAX 21504 obj2 Object code for Apple Mac 246814 paper1 Technical paper 53161 paper2 Technical paper 82199 10 paper3 Technical paper 46256 11 paper4 Technical paper 13286 12 paper5 Technical paper 11954 13 paper6 Technical paper 38105 14 progc Source code in "C" 39611 15 progl Source code in LISP 71646 16 progp Source code in PASCAL 49379 Bảng Các tệp tin mẫu để thực nghiệm 3.3 Phân tích thực nghiệm kết 3.3.1 Áp dụng MTF với thuật toán nén Huffman Trong nghiên cứu tác giả sử dụng phương pháp nén theo lược đồ BWTMTF- RLE- Huffman (BMRH) so sánh với trường hợp khơng có MTF (BRH) Kết thực nghiệm cụ thể sau: TT Tệp tin gốc Kích thước ban đầu BRH Kích thước BMRH (MTF0) Tỉ lệ Kích thước Tỉ lệ bib 111261 48538 56% 34296 69% book1 768771 411887 46% 303084 61% book2 610856 290442 52% 207656 66% geo 102400 67831 34% 66357 35% news 377109 204531 46% 150462 60% obj1 21504 14393 33% 12803 40% obj2 246814 115186 53% 86948 65% 56 Ứng dụng phương pháp Move to front nén liệu paper1 53161 26305 51% 18909 64% paper2 82199 39671 52% 29837 64% 10 paper3 46256 24080 48% 18110 61% 11 paper4 13286 8102 39% 6380 52% 12 paper5 11954 7594 36% 6095 49% 13 paper6 38105 19851 48% 14178 63% 14 progc 39611 20158 49% 14420 64% 15 progl 71646 26558 63% 18611 74% 16 progp 49379 18696 62% 12587 75% Bảng 10 Kết thực nghiệm Kết cho thấy, với nén liệu sử dụng phương pháp MTF0 hiệu so với phương pháp không dùng MTF0 Sau tác giả so sánh phương pháp MTF0 với phương pháp MTF1 MTF2: Tệp tin gốc bib book1 book2 geo news obj1 obj2 paper1 paper2 paper3 paper4 paper5 paper6 progc Kích thước ban đầu 111261 768771 610856 102400 377109 21504 246814 53161 82199 46256 13286 11954 38105 39611 BMRH (MTF0) Kích tỉ lệ thước 34296 69% 303084 61% 207656 66% 66357 35% 150462 60% 12803 40% 86948 65% 18909 64% 29837 64% 18110 61% 6380 52% 6095 49% 14178 63% 14420 64% BMRH (MTF1) Kích tỉ lệ thước 34376 69% 301240 61% 207887 66% 66126 35% 151463 60% 12814 40% 87854 64% 19037 64% 29789 64% 18074 61% 6390 52% 6128 49% 14375 62% 14602 63% 57 BMRH (MTF2) Kích thước tỉ lệ 34386 299237 207225 66095 151500 12815 88252 18999 29680 18037 6374 6131 14376 14652 69% 61% 66% 35% 60% 40% 64% 64% 64% 61% 52% 49% 62% 63% Ứng dụng phương pháp Move to front nén liệu progl progp 71646 49379 18611 74% 19266 73% 19402 12587 75% 13080 74% 13211 Bảng 11 So sánh phương pháp nén MTF0, MTF1, MTF2 73% 73% Theo dõi bảng ta thấy, tỷ lệ phần trăm hai phương pháp MTF1 MTF2 có phần tốt phương pháp MTF0 Tuy nhiên xét kỹ cột kích thước ta thấy có tệp tin áp dụng phương pháp MTF2 cho hiệu cao phương pháp MTF1, dùng phương pháp MTF0 cho hiệu phương pháp MTF1 Như phương pháp MTF0, MTF1, MTF2 có cải tiến định đem lại hiệu nén cao 3.3.1 Áp dụng MTF với thuật toán nén số học Trong lần thực nghiệm này, tác giả áp dụng phương pháp MTF0 với thuật toán nén số học, theo lược đồ BWT-MTF-RLE-ARI (BMRA) trường hợp khơng có MTF (BMA) Kết thực nghiệm sau: TT Tệp tin gốc Kích thước ban đầu BRA Kích thước BMRA (MTF0) tỉ lệ Kích thước tỉ lệ bib 111261 46660 58% 32582 71% book1 768771 402435 48% 298623 61% book2 610856 283711 54% 202928 67% geo 102400 64210 37% 63564 38% news 377109 199921 47% 147285 61% obj1 21504 12375 42% 10816 50% obj2 246814 110306 55% 83597 66% paper1 53161 24959 53% 17618 67% paper2 82199 38087 54% 28180 66% 10 paper3 46256 22941 50% 16911 63% 58 Ứng dụng phương pháp Move to front nén liệu 11 paper4 13286 7309 45% 5479 59% 12 paper5 11954 6740 44% 5077 58% 13 paper6 38105 18802 51% 13040 66% 14 progc 39611 19046 52% 13234 67% 15 progl 71646 25166 65% 17342 76% 16 progp 49379 17558 64% 11524 77% Ta nhận thấy rằng, áp dụng MTF0 với thuật toán nén số học cho hiệu cao 3.4 Kết luận Như áp dụng phương pháp MTF nén liệu mang lại hiệu cao, khơng so với phần mềm có thị trường Winzar Winzip Nếu áp dụng lược đồ nén với phương pháp nén số học cho kết cao phương pháp Huffman Tuy nhiên lược đồ nén liệu theo thuật toán BWCA thời gian phép biến đổi BWT, thuật tốn cần phải xét khối liệu, xếp ký hiệu khối liệu hoán vị số Trong phạm vi luận văn tác giả làm rõ tính hiệu phương pháp MTF việc tạo liệu đầu vào cho thuật toán nén liệu khác Trong phần phụ lục, tác giả thống kê sau sử dụng phương pháp MTF số lần lặp ký hiệu đứng đầu bảng mã tăng lên nhiều Điều có lợi thuật toán mã nén Huffman Tuy nhiên sau sử dụng MTF số ký hiệu tăng lên Trong Bảng 12 số ký hiệu 95, Bảng 13 số ký hiệu tăng lên đến 142 Điều làm ảnh hưởng phần tới chất lượng nén liệu, không đáng kể 59 Ứng dụng phương pháp Move to front nén liệu TÀI LIỆU THAM KHẢO Balkenhol, B, Kurtz, S, Shtarkov, Y M Modifications of the Burrows and Wheeler Data Compression Algorithm Proceedings of the IEEE Data Compression Conference 1999, Snowbird, Utah, J Storer and M Cohn, Eds 188–197, 1999 Balkenhol B, Shtarkov YM One attempt of a compression algorithm using the BWT Preprint 99-133,SFB343: Discrete Structures in Mathematics, Falculty of Mathematics, University of Bielefeld, 1999 http://www.mathematik.uni-bielefeld.de/sfb343/preprints/pr99133.ps.gz Brenton Chapin, Higher compression from the Burrows-Wheeler transform with new algorithms for the list update problem, University of North Texas, 2001 C E Shannon, A Mathematical Theory of Communication, 1948 Guy E Blelloch, Introduction to Data Compression, September 25, 2010 Ida Mengyi Pu, 2006, Fundamental Data Compression Juergen Abel, Improvements to the Burrows-Wheeler Compression Algorithm: After BWT Stages, University Duisburg-Essen Juergen Abel, Post BWT Stages of the Burrows-Wheeler Compression Algorithm, 41469 Neuss – Germany M Burrows and D.J Wheeler, A Block-sorting Lossless Data Compression Algorithm, Research Report 124, System Research Center, Digital System Research Center, Palo Alto, CA, 1994 10 Sebastian Deorowicz, Second step algorithms in the Burrows–Wheeler compression algorithm, November 22, 2001 11 Sebastian Deorowicz, Nov-2001, Second step algorithms in the Burrows– Wheeler compression algorithm 12 Travis Gagie, Giovanni Manzini, Move-to-Front, Distance Coding, and Inversion Frequencies Revisited 60 Ứng dụng phương pháp Move to front nén liệu 13 Vo Si Van, 2009, Image Compression Using Burrows-Wheeler Transform 14 http://sites.google.com/site/datacompressionguide 15 http://michael.dipperstein.com/bwt/index.html 16 http://www.binaryessence.com/dct/en000249.htm 17 http://www.data-compression.info/Algorithms/MTF/index.htm 61 Ứng dụng phương pháp Move to front nén liệu PHỤ LỤC Trong tệp tin thực nghiệm, tác giả thống kê thông tin ký hiệu số lần xuất ký hiệu tệp tin paper1 áp dụng phương pháp MTF Dưới hai bảng thông tin cho biết ký hiệu số lần xuất ký hiệu trước áp dụng MTF sau áp dụng MTF Kết thể theo thứ tự giảm dần số lần xuất ký tự TT Ký hiệu Xuất TT Ký hiệu Xuất TT Ký hiệu Xuất 32 7301 41 243 60 42 101 4698 120 227 83 42 116 3048 39 226 77 39 105 2879 126 224 124 38 111 2568 45 195 122 32 110 2503 73 179 123 30 97 2441 84 157 96 28 115 2374 51 143 125 28 114 2058 57 137 88 27 10 108 1593 10 113 137 10 72 24 11 104 1485 11 82 134 11 79 24 12 99 1476 12 53 128 12 80 22 13 100 1431 13 52 122 13 86 22 14 10 1250 14 91 121 14 87 22 15 109 1154 15 95 102 15 106 22 16 102 1118 16 70 101 16 85 21 17 117 1069 17 43 100 17 42 19 18 112 961 18 56 96 18 58 16 19 92 891 19 107 96 19 33 15 20 46 839 20 54 95 20 37 15 21 103 778 21 65 91 21 38 14 22 98 715 22 93 84 22 68 14 23 48 666 23 67 80 23 71 24 119 540 24 55 75 24 62 62 Ứng dụng phương pháp Move to front nén liệu 25 121 503 25 61 69 25 74 26 36 480 26 34 66 26 75 27 44 431 27 76 60 27 63 28 49 392 28 69 56 28 90 29 118 353 29 78 55 29 94 30 50 314 30 66 49 30 81 31 301 31 59 44 31 89 32 40 277 32 47 43 Bảng 12 Số lần xuất ký hiệu tệp tin paper1 ban đầu TT Ký hiệu Xuất TT Ký hiệu Xuất TT Ký hiệu Xuất 31023 47 20 76 2 5994 53 18 84 2906 57 17 89 1960 65 17 170 1503 48 15 171 1221 51 15 173 970 55 15 178 830 52 14 179 742 58 14 191 10 679 10 56 13 10 206 11 10 595 11 61 12 11 210 12 11 483 12 69 11 12 220 13 12 459 13 50 10 13 222 14 13 380 14 54 10 14 226 15 14 335 15 59 10 15 87 16 15 292 16 64 16 95 17 16 236 17 70 17 136 18 18 210 18 60 18 143 19 17 191 19 67 19 157 20 19 163 20 62 20 161 21 21 123 21 63 21 164 63 Ứng dụng phương pháp Move to front nén liệu 22 23 122 22 66 22 165 23 20 118 23 79 23 166 24 22 107 24 82 24 168 25 24 101 25 215 25 180 26 25 94 26 223 26 181 27 27 85 27 68 27 183 28 26 77 28 72 28 185 29 28 66 29 78 29 186 30 29 65 30 71 30 187 31 30 57 31 214 31 188 32 31 47 32 74 32 190 33 33 44 33 75 33 195 34 32 43 34 81 34 197 35 36 42 35 86 35 201 36 34 40 36 217 36 202 37 38 40 37 219 37 204 38 35 34 38 221 38 205 39 43 33 39 224 39 207 40 37 31 40 73 40 208 41 40 30 41 77 41 209 42 46 24 42 80 42 211 43 42 23 43 83 43 212 44 44 23 44 85 44 246 45 45 23 45 88 45 247 46 39 22 46 213 46 255 47 41 21 47 216 48 49 21 48 225 Bảng 13 Số lần xuất ký hiệu sau sử dụng MTF 64 ... kết kh? ?c “0 10 010 101 0” abcda “010 101 010” cadc Một mã c? ? tính để giải mã c? ? c? ?ch để giải mã thơng điệp mã hóa Tất nhiên c? ? c? ?ch kh? ?c để làm vi? ?c này, ví dụ thêm dấu “/” để phân c? ?ch từ mã... ban đầu, với thuật toán giải nén để khôi ph? ?c chuỗi ký tự g? ?c Vấn đề c? ??n BIT? Điều phụ thu? ?c vào thuật toán dư thừa liệu để suy liệu g? ?c C? ?c liệu kh? ?c đòi hỏi kỹ thuật kh? ?c để x? ?c định dư thừa... mã cho ký tự vào (nén) Để giải vấn đề ta c? ??n tổ ch? ?c liệu vào cho đ? ?c ký tự chuỗi liệu vào, luận văn t? ?c giả định dạng tệp tin dạng byte, mẩu tin đ? ?c vào byte c? ? mã tương ứng bảng mã ASCII 25 Ứng