Tài liệu Kỹ thuật nén dữ liệu burrow wheeler và các cải tiến

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐH CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN THỊ PHƯỢNG KỸ THUẬT NÉN DỮ LIỆU BURROW WHEELER VÀ CÁC CẢI TIẾN LUẬN VĂN THẠC SỸ: KHOA HỌC MÁY TÍNH Thái Nguyên - 2011 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐH CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN THỊ PHƯỢNG KỸ THUẬT NÉN DỮ LIỆU BURROW WHEELER VÀ CÁC CẢI TIẾN CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH MÃ SỐ CHUYÊN NGÀNH: 60 80 01 LUẬN VĂN THẠC SĨ: KHOA HỌC MÁY TÍNH HƯỚNG DẪN KHOA HỌC: PGS TSKH NGUYỄN XUÂN HUY Thái Nguyên - 2011 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn LỜI CAM ĐOAN Tôi xin cam đoan: Luận văn “Kỹ thuật nén dữ liệu Burrow Wheeler và các cải tiến” là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả nghiên cứu trong luận văn được sử dụng trung thực và có nguồn trích dẫn. ----------------------------------------LỜI CẢM ƠN Em xin gửi lời cảm ơn sâu sắc tới thầy PGS TSKH Nguyễn Xuân Huy - Viện Công nghệ thông tin, người đã gợi mở và định hướng cho em tìm hiểu về lĩnh vực giấu tin trong ảnh. Thầy đã hết lòng giúp đỡ, tạo điều kiện cho em nghiên cứu và hoàn thành luận văn này. Em xin cảm ơn các thầy cô trong Viện Công nghệ thông tin, các thầy cô giáo khoa Công nghệ thông tin ĐH Thái nguyên, đã giảng dạy và giúp đỡ em trong hai năm học qua. Cuối cùng tôi xin cảm ơn tới gia đình, các bạn cùng lớp và các bạn đồng nghiệp đã giúp đỡ, động viên, cùng nghiên cứu, đóng góp ý kiến, chia sẻ kinh nghiệmvới tôi trong suốt quá trình học tập và làm luận văn! Thái Nguyên - 2011 Nguyễn Thị Phượng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn i MỤC LỤC .................................................................................................................. i DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT........................................ iii DANH SÁCH BẢNG BIỂU.................................................................................... iv DANH SÁCH HÌNH ẢNH .......................................................................................v MỞ ĐẦU ....................................................................................................................1 1. Lý do chọn đề tài................................................................................................1 2. Mục tiêu của đề tài ............................................................................................2 3. Đối tƣợng và phạm vi nghiên cứu ....................................................................2 4. Hƣớng nghiên cứu của đề tài ............................................................................3 5. Những nội dung nghiên cứu chính ...................................................................3 6. Phƣơng pháp nghiên cứu ..................................................................................3 7. Ý nghĩa khoa học của đề tài ..............................................................................3 CHƢƠNG 1: TỔNG QUAN VỀ NÉN DỮ LIỆU ...................................................4 1.1. Nén dữ liệu .....................................................................................................4 1.1.1. Khái niệm về dữ liệu .................................................................................4 1.1.2. Sự trùng lặp dữ liệu ...................................................................................4 1.1.3. Nén dữ liệu.................................................................................................5 1.2 Các phƣơng pháp nén dữ liệu cơ bản ............................................................5 1.2.1. Nén không tổn hao .....................................................................................5 1.2.2. Nén tổn hao ................................................................................................6 1.3. Dữ liệu ký hiệu và các mã ..............................................................................7 1.3.1. Dữ liệu kí hiệu .........................................................................................12 1.3.2. Mã chiều dài thay đổi ................................................................................7 1.3.3. Mã tiền tố và các cây nhị phân ..................................................................8 1.4. Cơ bản về lý thuyết thông tin ......................................................................11 1.5. Đơn vị đo đặc tính nén .................................................................................12 CHƢƠNG 2: KỸ THUẬT NÉN DỮ LIỆU BURROWS WHEELER VÀ CÁC CẢI TIẾN .................................................................................................................14 2.1. Chuyển đổi Burrows – Wheeler ..................................................................14 2.1.1. Giới thiệu .................................................................................................14 2.1.2. Chuyển đổi Burrows-Wheeler thuận .......................................................14 2.1.3. Chuyển đổi Burrows-Wheeler nghị ch. ....................................................16 2.2. Kỹ thuật nén dữ liệu Burrows-Wheeler .....................................................23 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ii 2.3. Các cải tiến với kỹ thuật nén dữ liệu Burrows-Wheeler ..........................27 2.3.1. Các định nghĩa .........................................................................................35 2.3.2. Sự đảo ngược tần số (IF) .........................................................................30 2.3.3. Mã hóa khoảng cách (DC). ......................................................................32 2.3.4. Phương pháp đếm trọng số tần số (WFC)……….……………………..35 2.3.5. Những thay thế MTF khác .......................................................................34 2.3.6. Mã hoá Run Length 2.3.7. Các cải tiến với mã hóa RLE ...................................................................36 2.3.7.1. Hoạt động chung ..............................................................................36 2.3.7.2. Vị trí mới cho giai đoạn RLE ............................................................37 2.3.7.3. Thuật toán RLE-EXP ........................................................................38 2.3.7.4. Thuật toán RLE-BIT .........................................................................39 2.3.8. Các cải tiến với đảo ngược tần số ............................................................41 2.3.8.1. Sắp xếp biểu tượng bằng phân phối tần số .......................................41 2.3.8.2. Thứ tự sắp xếp ...................................................................................42 2.3.8.3. Giai đoạn EC .....................................................................................43 2.3.9. Các cải tiến với đếm tần số trọng số ........................................................44 2.3.9.1. Phân cấp mịn hơn (Finer Graduation)...............................................44 2.3.9.2. Tính toán các trọng số .......................................................................44 2.3.9.3. Giai đoạn EC .....................................................................................46 2.3.10. Một thuật toán nén Burrows-Wheeler được cải tiến .............................47 2.3.10.1. Lựa chọn giai đoạn GST .................................................................47 2.3.10.2. So sánh tỉ lệ nén và thời gian nén ..................................................49 Kết luận .............................................................................................................51 CHƢƠNG 3: CÀI ĐẶT THỬ NGHIỆM ..............................................................52 3.1. Sơ đồ nén số học kết hợp với BWT và MTF ..............................................52 3.1.1. Thuật toán nén .........................................................................................52 3.1.2. Thuật toán giải nén ..................................................................................52 3.2. Cài đặt thử nghiệm .......................................................................................53 3.3. Kết luận……...…………………………………………………………………….54 KẾT LUẬN VÀ DỰ KIẾN .....................................................................................55 TÀI LIỆU THAM KHẢO ......................................................................................56 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn iii DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT Chữ viết Diễn giải tắt AWFC BWCA Advanced Weighted Frenquency Count Burrows-Wheeler Compression Algorithm Ý nghĩa Đếm trọng số tần số cao cấp Thuật toán nén Burrows-Wheeler BWT Burrows Wheeler Transform Chuyển đổi Burrows Wheeler DC Distance Coding Mã hóa khoảng cách EC Entropy Coding Mã hóa Entropy GST Global Structure Transformation Chuyển đổi cấu trúc tổng thể IF Inversion Frequencies Sự đảo ngược tần số IFC Inversion Frequencies Count Đếm gia tăng tần số LUA List Update Algorithm Thuật toán cập nhật danh sách MTF Move To Front Di chuyển lên phía trước RLE Run Length Encoding Mã hóa loạt dài RLE – BIT Run Length Encoding - BIT Thuật toán RLE – BIT RLE – EXP Run Length Encoding - EXP Thuật toán RLE – EXPBIT RLE0 Run Length Encoding 0 Mã hóa chuyển đổi run 0 RMB RLE Mantissia Buffer Luồng dữ liệu riêng biệt SIF Sort Inversion Frequencies Sự đảo ngược tần số có sắp xếp WFC Weighted Frequency Count Đếm trọng số tần số Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn iv DANH SÁCH BẢNG BIỂU Bảng 2.1- 2.2: Mã hóa Move-To-Front Bảng 2.3: Sự đảo ngược tần số Bảng 2.4.: Mã hóa khoảng cách Bảng 2.5: Những giá trị xếp hạng trung bì nh rx và thời gian Bảng 2.6: Tỉ lệ nén với giai đoạn RLE trước và sau giai đoạn WFC trong bps. Bảng 2.7: Các run ngưỡng với t=2 Bảng 2.8: Mã hóa RLE-BIT của chiều dài run Bảng 2.9: Tỉ lệ nén theo bps cho các giai đoạn IF và SIF. Bảng 2.10: Biểu thị S với mỗi file của Calgary Corpus với f a  2Favg Bảng 2.11: Tỉ lệ nén theo bpc với w p , p ,S (t ) . Bảng 2.12: Tỉ lệ nén theo bpc với lược đồ SIF và AWFC. Bảng 2.13: Tỷ lệ nén với Calgary Corpus theo bpc Bảng 2.14: Thời gian nén và giải nén với Cagary Corpus theo giây 0 1 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn v DANH SÁCH HÌNH ẢNH Hình 1.1: Minh họa việc trùng lặp dữ liệu của các frame hoạt hình Hình 1.2 Máy nén và máy giải nén. Hình 1.3: Bộ mã hóa và bộ giải mã Hình 1.4: Những thuật toán nén không tổn hao Hình 1.5: Những thuật toán nén tổn hao Hình 1.6: Mã và dữ liệu nguồn Hình 1.7: Đặc tính tiền tố và các cây nhị phân Hình 1.8: Không phải mã tiền tố nhưng có thể giải mã duy nhất Hình 2.1: Minh họa chuyển đổi BWT thuận Hình 2.2: Mảng R được sử dụng để sắp xếp file Hình 2.3: Minh họa chuyển đổi BWT nghịch Hình 2.4: Sử dụng thứ tự ký tự để thực hiện chuyển đổi ngược Hình 2.5: Mảng (As) mặc nhiên được khôi phục để giải mã Hình 2.6: Các mảng phụ trợ V và W có thể được sử dụng để giải mã xâu mẫu Hình 2.7: Lược đồ nén Burrows-Wheeler cơ bản Hình 2.8a,b: Minh họa về Mã hóa Huffman Hình 2.9 – 2.10: Minh họa mã hóa số học Hình 2.11: Lược đồ nén BWT Hình 2.12: Sự chia sẻ các Book1 Hình 2.13: Thuật toán nén Burrows-Wheeler sử dụng giai đoạn RLE0 Hình 2.14: Minh họa chuyển đổi RLE0 Hình 2.15: Thuật toán RLE-EXP Hình 2.16: Thuật toán RLE-BIT Hình 2.17: BWCA với giai đoạn GST hỗn hợp Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1 MỞ ĐẦU 1. Lý do chọn đề tài Một trong các chức năng chính của máy tính là xử lý và lưu trữ dữ liệu. Bên cạnh việc xử lý nhanh người ta còn quan tâm đến việc lưu trữ được nhiều dữ liệu nhưng lại tiết kiệm được vùng nhớ và giảm chi phí lưu trữ. Về mặt lý thuyết thì các thiết bị lưu trữ là không có giới hạn, nhưng ngày nay do nhu cầu xử lý nhiều tập tin, nhiều loại dữ liệu trong cùng một tệp do vậy mà kích thước tập tin trở nên khá lớn. Trong nhiều năm gần đây, mạng máy tính đã trở nên khá phổ biến trên thế giới. Sự ra đời của mạng đã thực hiện ước mơ chinh phục khoảng cách của con người. Những lợi ích mà mạng cung cấp rất đa dạng và phong phú trên các lĩnh vực khác nhau của toàn xã hội như cung cấp, trao đổi thông tin giữa các máy tính, giữa máy chủ với server hoặc giữa các server với nhau. Điều này dẫn đến phải làm thế nào để giảm thiểu thời gian, chi phí sử dụng để trao đổi dữ liệu trên mạng. Nó đồng nghĩa với việc bên cạnh nâng cao chất lượng của các thiết bị truyền dữ liệu trên mạng thì mặt khác chúng ta phải nghĩ ra một phương pháp để sao cho việc truyền dữ liệu có hiệu quả hơn. Tất cả những vấn đề trên nảy sinh ra nhu cầu nén dữ liệu với mong muốn thu gọn kích thước các tập tin làm cho thông tin chiếm không gian trên đĩa là ít nhất. Nó là một trong những kỹ thuật quyết định đến cuộc cách mạng đa phương tiện kỹ th uật số đang diễn ra trong nhiều thập kỷ. Trong một quá trình phát triển lâu dài, nhiều kỹ thuật nén dữ liệu đã ra đời và được chia làm 2 nhóm kỹ thuật chính là nén tổn hao và nén không tổn hao. Nén không tổn hao là kỹ thuật nén mà sau đó ta có thể khôi phục lại chính xác dữ liệu ban đầu. Nén tổn hao là kỹ thuật nén mà sau khi nén ta không thể khôi phục lại chính xác dữ liệu ban đầu của nó. Nén không tổn hao rất được mong đợi vì tỉ lệ nén cũng như tốc độ nén cao của nó. Tuy nhiên, kỹ thuật này chỉ được dùng cho nén âm thanh, hình ảnh bởi cách thức mà các hệ thống thị giác và thính giác của con người làm việc có thể chấp nhận được. Với dữ liệu gốc của nguồn là rất quan trọng mà ta không thể để mất bất kỳ chi tiết nào dụ như hình ảnh y tế , văn bản, các hình ảnh được bảo vệ vì lý do Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 2 pháp lý, một số file khả thi của máy tính … thì ta không thể sử dụng kỹ thuật nén tổn hao. Nhiều kỹ thuật nén không tổn hao đã ra đời như: Phương pháp mã hóa Entropy bao gồm mã số học và mã Huffman. Sau đó, hàng loạt các kỹ thuật mới ra đời để cải tiến các kỹ thuật trên như: Mã hóa RLE, CD, MTF, LZW... Và gần đây là kỹ thuật nén dữ liệu Burrows Wheeler được công bố bởi Burrows và Wheerler năm 1994. Trong vòng hơn một thập kỷ qua, thuật toán nén Burrows Wheeler [6] đã trở thành một trong những công cụ then chốt trong lĩnh vực nén dữ liệu nói chung. Lý do thành công của nó là tốc độ nén cao kết hợp với tỷ lệ nén tốt. Nhiều cải tiến của kỹ thuật này cũng đã được trình bày. Hiện nay, nén dữ liệu đặc biệt là kỹ thuật nén không tổn hao Burrows Wheeler đang là vấn đề quan tâm rất lớn của các cá nhân, tổ chức, trường học, viện nghiên cứu... trên thế giới. Chính vì vậy, tôi đã chọn đề tài “Kỹ thuật nén dữ liệu Burrows Wheeler và các cải tiến”. Cấu trúc của luận văn được chia làm 3 chương. Chƣơng 1: Tổng quan về nén dữ liệu. Trình bày các khái niệm cơ bản như “dữ liệu”, “Nén dữ liệu”... Các phương pháp nén dữ liệu...Chƣơng 2: Kỹ thuật nén dữ liệu Burrows Wheeler và các cải tiến. Trong chương này trình bày cách làm việc của chuyển đổi Burrows Wheeler, kỹ thuật nén dữ liệu Burrows Wheeler và các cải tiến với kỹ thuật nén này. Chƣơng 3: Cài đặt thử nghiệm. Áp dụng chuyển đổi BWT tiến hành một kỹ thuật nén số học kết hợp với BWT và MTF trên đối tượng là tệp văn bản. Xây dựng chương trình thử nghiệm áp dụng thuật toán nén số học kết hợp với BWT và MTF. 2. Mục tiêu của đề tài Luận văn tập trung tìm hiểu kỹ thuật nén BWT và các cải tiến của kỹ thuật. Cuối cùng là cài đặt thử nghiệm chương trình nén số học kết hợp với BWT và MTF. 3. Đối tƣợng và phạm vi nghiên cứu Đối tượng và phạm vi nghiên cứu của luận văn tập trung vào kỹ thuật nén dữ liệu Burrows Wheeler và các cải tiến. Từ đó xây dựng chương trình ứng dụng nén số học kết hợp với Burrows Wheeler và MTF, sử dụng phương pháp Quicksort để sắp xếp và áp dụng trên đối tượng dữ liệu là tệp văn bản. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 3 4. Hƣớng nghiên cứu của đề tài - Tìm hiểu các phương pháp nén dữ liệu. - Tìm hiểu kỹ thuật nén dữ liệu Burrows Wheeler. - Tìm hiểu các cải tiến của kỹ thuật nén dữ liệu Burrows Wheeler. - Cài đặt thử nghiệm chương trình nén số học kết hợp với BWT và MTF. 5. Những nội dung nghiên cứu chính Đề tài tập trung nghiên cứu kỹ thuật nén dữ liệu Burrows Wheeler và các cải tiến. Xây dựng chương trình thử nghiệm nén Burrows Wheeler kết hợp với MTF và nén số học. 6. Phƣơng pháp nghiên cứu  Về lý thuyết: - Tìm hiểu tổng quan về nén dữ liệu. - Tìm hiểu kỹ thuật nén dữ liệu Burrows Wheeler và các cải tiến.. - Tìm hiểu ngôn ngữ lập trình Dev C++, VB.Net...vv.  Về thực nghiệm: - Sử dụng ngôn ngữ lập trình Dev C++ xây dựng và cài đặt thử nghiệm chương trình nén dữ liệu theo kỹ thuật Burrows Wheeler kết hợp với MTF và mã số học. 7. Ý nghĩa khoa học của đề tài Một vấn đề nén liên quan đến việc tìm một thuật toán nén hiệu quả để loại bỏ dư thừa khác nhau từ một kiểu dữ liệu nhất định. Vậy số lượng bit it hơn là bao nhiêu? Điều đó phụ thuộc vào những thuật toán nhưng nó cũng phụ thuộc vào sự dư thừa có thể chiết ra từ dữ liệu gốc là bao nhiêu. Dữ liệu khác nhau có thể yêu cầu những kỹ thuật khác nhau để xác định dư thừa và loại bỏ dư thừa trong dữ liệu Không có giải pháp nào phù hợp cho tất cả các vấn đề nén dữ liệu. Theo các nghiên cứu về nén dữ liệu, ta chú ý phải phân tích các đặc tính của dữ liệu đã được nén và hy vọng đưa ra một số mô hình để đạt được sự biểu diễn ngắn gọn hơn. Điều này làm gia tăng sự đa dạng của mô hình dữ liệu và những kỹ thuật biểu diễn, đó là điểm quan trọng của kỹ thuật nén. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 4 CHƢƠNG 1: TỔNG QUAN VỀ NÉN DỮ LIỆU 1.1. Nén dữ liệu 1.1.1. Khái niệm về dữ liệu Dữ liệu là phương tiện truyền thông logic thường được mang bởi một số phương tiện truyền thông vật lý như CD hay kênh truyền thông. Vì vậy, dữ liệu có thể được xem như dạng cơ bản của một số thông tin xác thực. Từ dữ liệu trong ngữ cảnh của nén dữ liệu bao gồm bất kỳ dạng kỹ thuật số nào c ủa thông tin xác thực như : văn bản, âm thanh, hình ảnh và video… được xử lý bởi chương trình máy tính. 1.1.2. Sự trùng lặp dữ liệu. Dữ liệu trùng lặp có thể là một số thông tin được che dấu , một số cơ sở dữ liệu chung, một số các ký tự giống nhau, một số cấu trúc tương đương trong tự nhiên… Ta xét một số ví dụ đơn giản sau đây: Ví dụ 1.1: Xâu BAAAAAAAC có 7 biểu tượng A được lặp lại liên tục Ví dụ 1.2: Xem xét một văn bản với các từ được lặp lại như sau: the red, the green and the blue colour, and the paint in red, green Ở đây có các từ được lặp lại đó là các xâu như red, green, và blue. Ví dụ 1.3: Xem xét một vectơ gồm các số nguyên: (6, 428, 32, 67, 125). Dữ liệu thuộc đoạn lớn [6, 428]. Do đó, mỗi dữ kiện d trong vectơ yêu cầu 9 bit để biểu diễn vì 0 < d < 512 và 29=512. Ta có thể sử dụng phương pháp chia tỷ lệ đơn giản như sau: Lấy phần dư của d chia 32, ta có (0, 13, 1, 2, 4) gồm đoạn nhỏ hơn nhiều [0, 13]. Bây giờ chỉ cần 4 bit để biểu diễn mỗi dữ kiện d‟ được chia tỷ lệ vì 4 0  d '  16 và 2 =16. Ví dụ 1.4: Sự trùng lặp temple. Hình 1.1 cho thấy một dãy các ảnh hoạt hình (được gọi là các frame). Các frame sẽ được hiển thị tách rời nhau một vài giây. Để phản ứng của hệ thống giác quan con người, những gì ta thấy là một khuôn mặt khôi hài thay đổi từ ngủ đến thức, và cuối cùng với một trạng thái “cười”. Hình 1.1: Một dãy các frame hoạt hình Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 5 1.1.2. Nén dữ liệu Nén dữ liệu là quá trình loại bỏ sự trùng lặp trong dữ liệu nhằm đưa ra dãy các biểu tượng chứa cà ng í t bit càng tốt. Nói cách khác, nén dữ liệu có nghĩa là đưa ra các kỹ thuật hay cụ thể hơn là thiết kế những thuật toán hiệu quả nhằm để:  Biểu diễn dữ liệu theo dạng mà chứa ít sự trùng lặp dữ liệu.  Loại bỏ trùng lặp trong dữ liệu. Một thuật toán nén thường được gọi là máy nén và thuật toán giải nén được gọi là máy giải nén. Hình 1.2: Máy nén và máy giải nén. Máy nén thường được gọi là bộ mã hóa và máy giải nén được gọi là bộ giải mã. Hình 1.3 cho thấy một flatform dựa trên quan hệ giữa bộ mã hóa và bộ giải mã được kết nối bởi một kênh truyền dẫn. Hình 1.3: Bộ mã hóa và bộ giải mã 1.2 Các phƣơng pháp nén dữ liệu cơ bản 1.2.1 Nén không tổn hao Một phương pháp nén là không tổn hao (nén thuận nghịch ) nếu và chỉ nếu nó có thể khôi phục chính xác dữ liệu gốc từ phiên bản đã được nén. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 6 Ví dụ, trong Hình 1.9, xâu đầu vào AABBBA được khôi phục lại sau khi thực hiện thuật toán nén và được theo sau bởi thuật toán giải nén. . Hình 1.4: Những thuật toán nén không hao tổn Kỹ thuật nén không tổn hao được sử dụng khi dữ liệu gốc của nguồn là rất quan trọng mà ta không thể để mất bất kỳ chi tiết nào. Ví dụ như hình ảnh y tế , văn bản, các hình ảnh được bảo vệ vì lý do pháp lý, một số file khả thi của máy tính … 1.2.2. Nén tổn hao Một phương pháp nén tổn hao (nén không thuận nghịch) nếu nó không thể khôi phục bản gốc chính xác từ các phiên bản đã được nén. Ví dụ: Hình 1.5: Các thuật toán nén tổn hao Khôi phục xấp xỉ có thể đưa đến hiệu quả nén nhiều hơn. Tuy nhiên, nó thường yêu cầu sự cân bằng tốt giữa khả năng trực quan và độ phức tạp trong tính toán. Dữ liệu như hình ảnh, video và âm thanh đa phương tiện được nén dễ dàng hơn bởi kỹ thuật nén tổn hao vì cách thức mà các hệ thống thị giác và thính giác của con người làm việc. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 7 1.3. Dữ liệu ký hiệu và các mã 1.3.1. Dữ liệu kí hiệu. Giả sử bảng chữ cái của dữ liệu nguồn là S=(s1, s2, …, sn). Biểu diễn kỹ thuật số của tập hợp biểu tượng được gọi là mã C=(c1, c2, …, cn) và cj biểu diễn mỗi biểu tượng được gọi là từ mã cho biểu tượng sj, j  1, n . Quá trình gán các từ mã cho mỗi biểu tượng trong dữ liệu nguồn được gọi là mã hóa. Quá trình đảo ngược, tức là khôi phục dãy các biểu tượng trong dữ liệu nguồn, được gọi là giải mã. Ví dụ: BAAAAAAAC là một dữ liệu ký hiệu từ một bảng chữ cái (A, B, C, D, E). Giả sử ta định nghĩa một mã nhị phân (000, 001, 010, 011, 100), các từ mã 000, 001, 010, 011, 100 là biểu diễn nhị phân của A, B, C, D, E tương ứng. Biểu diễn nhị phân của dữ liệu ký hiệu là 001 000 000 000 000 000 000 000 010 (không có các dấu cách). Đây là dữ liệu nguồn theo biểu diễn nhị phân, là đầu vào của thuật toán nén . Điều này có thể được thấy từ Hình 1.12. Hình 1.6: Mã và dữ liệu nguồn Ta có thể biểu diễn một bảng chữ cái bằng một tập các từ mã chiều dài cố đị nh và mã được gọi là mã chiều cố đị nh. Cũng có thể biểu diễn một bảng chữ cái bằng một tập các từ mã chiều dài thay đổi và mã được gọi là mã chiều dài thay đổi. Ví dụ 1.5: Hai mã nhị phân C1=(000, 001, 010, 011, 100) và C2=(0, 100, 101, 110, 111), có thể được sử dụng để biểu diễn bảng chữ cái (A, B, C, D, E). Ở đây C1 là mã chiều dài cố định và C2 là mã chiều dài thay đổi. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 8 1.3.2. Mã chiều dài thay đổi Các mã chiều dài thay đổi rất được mong đợi cho nén dữ liệu bởi vì toàn bộ quá trình tiết kiệm có thể đạt được bằng cách gán các từ mã ngắn cho những biểu tượng xảy ra thường xuyên và các từ mã dài cho những biểu tượng hiếm khi xảy ra . Ví dụ 1.6: Cho bảng chữ cái (A, B, C, D, E). Xét mã chiều dài thay đổi (0, 100, 101, 110, 111) với chiều dài của các từ mã (1, 3, 3, 3, 3), và xâu nguồn BAAAAAAAC với tần số cho mỗi biểu tượng là (7, 1, 1, 0, 0). Số trung bì nh các bit được yêu cầu: l 1 7  3 1  3 1  1.4 bit/biểu tượng 9 Điều này gần như tiết kiệ m được nửa số lượng các bit so với 3 bit/biểu tượng bằng cách sử dụng 3 bit mã chiều dài cố đị nh. Các mã chiều dài thay đổi rất hữu í ch với nén dữ liệu . Tuy nhiên , một mã chiều dài thay đổi sẽ không hữu í ch nếu các từ mã không thể xác định theo một cách duy nhất từ thông điệp được mã hóa. Ví dụ 1.6: Xem xét mã chiều dài thay đổi (0, 10, 010, 101) với bảng chữ cái (A, B, C, D). Một đoạn thông điệp được mã hóa như „ 0100101010‟ có thể được giải mã nhiều hơn một cách . Ví dụ: „0100101010‟ có thể được thể hiện í t nhất theo hai cách : „0 10 010 101 0‟ bằng ABCDA hoặc „010 0 101 010‟ bằng CADC. Mã (0, 10, 010, 101) trong ví dụ 1.9 không thể giải mã duy nhất và vì vậy không được sử dụng cho nén dữ liệu. Mã lý tưởng trong trường hợp này không chỉ là một mã chiều dài thay đổi mà với một số đặc tí nh tự động tách (self-punctuating). Ví dụ, mã (0, 10, 110, 111) có đặc tính tự động tách vì vậy chỉ có một cách giải mã duy nhất . 1.3.3. Mã tiền tố và các cây nhị phân Có một kiểu để kiểm tra một mã có thể giải mã duy nhất hay không được gọi là mã tiền tố. Mã tiền tố có thể được xác định bằng cách kiểm tra n ên nó cũng được gọi là đặc tí nh tiền tố. Một tiền tố là một số bit liên tục đầu tiên của một từ mã . Khi hai từ mã có chiều dài khác nhau , từ mã ngắn giống với một số bit đầu tiên của từ mã dài hơn thì từ mã ngắn hơn được gọi là tiền tố của từ mã dài hơn. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 9 Ví dụ 1.7: Xét hai từ mã nhị phân có chiều dài khác nhau : c1=010 và c2=01011. Từ mã ngắn c1 là tiền tố của từ mã c2=01011. Từ mã c2 có thể thu được bằng cách nối thêm hai bit 11 với c1. Đặc tính tiền tố của mã nhị phân là cơ sở lập luận để kiểm tra một từ mã không phải là tiền tố của một từ mã khác. Ví dụ 1.8: Xét hai mã nhị phân sau: (0, 10, 010, 101) và (0, 10, 110, 111). Trong mã (0, 10, 010, 101) không thể giải mã duy nhất (Xem lại ví dụ 1.9).Ta thấy, từ mã 0 là tiền tố của từ mã 010; từ mã 10 là tiền tố của từ mã 101. Ngược lại, trong mã có thể giải mã duy nhất (0, 10, 110, 111) không có từ mã là tiền tố c ủa một từ mã khác trong mã . Đặc tính tiền tố trở thành đặc điểm ưa thích khi tìm kiếm mã có thể giải mã duy nhất. Mã với đặc tính tiền tố được gọi là mã tiền tố . Nói cách khác , mã tiền tố là mã mà không có từ mã là tiền tố của từ mã khác. Để kiểm tra xem mã nhị phân là mã tiền tố bằng cách vẽ một cây nhị phân . Mỗi mã nhị phân có thể tương ứng với một cây nhị phân mà mỗi từ mã tương ứng với một đường đi từ gốc đến một nút với tên từ mã được đánh dấu tại cuối đường đi . Mỗi bit 0 trong một từ mã tương ứng với cạnh trái và bit 1 tương ứng với cạnh phải. Các bước để vẽ cây nhị phân: Bƣớc 1: Xây dƣ̣ng cây nhị phân - Tạo một nút là gốc của cây nhị phân. - Với mỗi từ mã , ta đọc một bit một lần từ đầu đến cuối . Bắt đầu từ gốc, vẽ nhánh mới hoặc di chuyển xuống mỗi cạnh dọc theo nhánh tương ứng với giá trị của bit. - Khi bit 0 được đọc, nếu chưa có nhánh ta vẽ nhánh trái và nút mới tại cuối nhánh. Di chuyển xuống một cạnh theo nhánh trái ngược lại và đến nút cuối của cạnh . Tương tự , khi bit 1 được đọc , nếu chưa có nhánh, ta vẽ nhánh phải, hoặc di chuyển xuống một cạnh nhánh phải - Lặp lại quá trì nh từ nút đến nút trong khi đọc từng bit cho đến khi kết thúc từ mã. Ta đánh dấu từ mã sau khi kết thúc toàn bộ từ mã . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 10 Bƣớc 2: Kiểm tra vị trí tƣ̀ mã Nếu tất cả các nhãn từ mã được kết hợp với c ác lá, thì từ mã là mã tiền tố . Ngược lại, không phải mã tiền tố . Ví dụ 1.9: Xét các mã (1, 01, 001, 0000) và (0, 10, 110, 1011) với bảng chữ cái (A, B, C, D) xem mã nào là mã tiền tố. Bước 1: Vẽ cây nhị phân như trong Hình 1.13 (a) và (b) với mỗi mã ở trên. Bước 2: Với một mã tiền tố , các từ mã được kết hợp với các lá. Vì tất cả các mã trong (1, 01, 001, 0000) là các lá (Hình 1.10 (a)), ta có thể dễ dàng kết luận rằng (1, 01, 001, 0000) là mã tiền tố. Vì từ mã 10 (B) được kết hợp với nút bên trong của cây nhị phân (Hình 1.10 (b)), ta kết luận rằng (0, 10, 110, 1011) không phải mã tiền tố . Các mã tiền tố là tập con của các mã có thể giải mã được duy nhất. Điều này có nghĩa nếu một mã là mã tiền tố, thì mã đó có thể giải mã duy nhất . Hình 1.7: Đặc tính tiền tố và các cây nhị phân Tuy nhiên, nếu mã không phải là mã tiền tố , ta không thể kết luận rằng mã đó không có thể giải mã duy nhất. Ví dụ 1.10: Xét mã (0, 01, 11) với (A, B, C). Đây không phải là mã tiền tố vì từ mã 0 đầu tiên là tiền tố của từ mã thứ hai là 01. Nhưng mã này vẫn có thể giải mã duy nhất. Hình 1.14 cho thấy quá trì nh giải mã từng bước một với thông điệp đã được mã hóa như sau: 011101. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 11 Hình 1.8: Không phải mã tiền tố nhưng có thể giải mã duy nhất Như đã thấy, quá trình giải mã không đơn giản . Nó bao gồm quá trình học “thử và sai” và đòi hỏi “sự lần tì m ngược” . Một số từ mã có thể giải mã duy nhất nhưng yêu cầu tì m kiếm trong suốt quá trì nh giải mã . Điều này làm cho chúng không hiệu quả bằng mã tiền tố. 1.4. Cơ bản về lý thuyết thông tin Một trong số các đặc tí nh quan trọng trong lĩ nh vực lý thuyết thông tin là entropy được giới thiệu bởi C . E. Shannon vào năm 1948 trong bài báo “ A Mathematical Theory of Communication”. Theo lý thuyết của Shannon , entropy là độ đo lượng thông tin không chắc chắn . Giả sử một tập tin có chứa các biểu tượng s0, s1, …, sk và mỗi biểu tượng có một xác suất xuất hiện là p(s0), p(s1), …, p(sk). Lượng thông tin với mỗi biểu tượng được xác đị nh bằng –log2p(sk) và thường được biểu diễn theo bit. Entropy - H(S) được đị nh nghĩ a là lượng thông tin trung bì nh , (số bit trung bì nh ) cần thiết để mã hóa một biểu tượng: L 1 H ( S )   p( sk ) log2 p( sk ) k 0 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 12 1.5. Đơn vị đo đặc tính nén Việc thực hiện một thuật toán nén có thể được đo bằng các tiêu chuẩn khác nhau phụ thuộc vào tí nh chất của ứng dụng. Ta sẽ thảo luận đơn vị đo theo hai trường hợp cụ thể là nén không tổn hao và nén tổn hao. Nén không tổn hao: Đối với các thuật toán nén không tổn hao, ta đo hiệu quả nén bằng số lượng hao hụt của file nguồn so với kích thước của phiên bản đã được nén.  Tỉ lệ nén: Là tỉ lệ đầu ra với kích thước file đầu vào của một thuật toán nén, tức là kích thước file sau khi nén với kích thước file nguồn trước khi nén.  Hệ số nén: Ngược với tỉ lệ nén.  Tỷ lệ phần trăm tiết kiệm được: Ngoài ra, hiệu quả của một thuật toán chỉ là một khía cạnh về đơn vị đo của thuật toán. Trong thực tế, tiêu chuẩn sau đây thường là mối quan tâm với các lập trình viên: Độ phức tạp trong tính toán, Thời gian nén, Entropy, Sự dư thừa, Độ phức tạp Kolmogorov, Kiểm tra cài đặt, Chi phí phụ (Overhead) Nén tổn hao: Đối với nén tổn hao, ta phải đo đặc tính của dữ liệu đã được giải nén cũng như hiệu quả nén. Từ “độ tin cậy ” thường được sử dụng để mô tả độ chính xác giữa file dữ nguồn và file được giải nén. Sự khác biệt giữa dữ liệu nguồn trước khi nén và file sau khi giải nén, được gọi là độ biến dạng. Thường độ biến dạng xấp xỉ được sử dụng trong thực tế. Tóm lại: Nén dữ liệu là một lĩnh v ực nghiên cứu tích cực và đang được quan tâm. Có nhiều lí do thú vị để nghiên cứu những thuật toán nén . Những thuật toán nén có thể được phân loại theo hai lớp đại cương sau : Nén không tổn hao và nén tổn hao . Đặc tính nén có thể được đo bằng nhiều cách khác nhau. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn