Tài liệu Nén dữ liệu theo kỹ thuật move - to-front

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG LÊ VĂN NINH NÉN DỮ LIỆU THEO KỸ THUẬT MOVE – TO - FRONT Chuyên ngành: KHOA HỌC MÁY TÍNH Mã số: 60 48 01 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 Lêi c¶m ¬n! Em xin chân thành cảm ơn các thầy giáo trong Viện công nghệ thông tin, Viện khoa học và công nghệ Việt Nam; các thầy giáo, cô giáo trường Đại học CNTT & TT - Đại học Thái Nguyên đã tạo điều kiện, giúp đỡ em hoàn thành luận văn này. Đặc biệt, em xin chân thành cảm ơn PGS.TSKH Nguyễn Xuân Huy, thầy giáo đã giảng dạy và trực tiếp hướng dẫn trong suốt quá trình nghiên cứu và hoàn thành luận văn. Dù đã có nhiều cố gắng, nhưng chắc chắn luận văn sẽ không tránh khỏi những thiếu sót và hạn chế. Vì vậy, rất mong được sự góp ý, chỉ dẫn của các thầy, cô giáo, bạn bè và đồng nghiệp. Trân trọng cảm ơn! Thái Nguyên, tháng 11 năm 2011 Lê Văn Ninh 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 DANH MỤC TỪ VIẾT TẮT Move – To – Front (Di chuyển lên phía trước) MTF Borrows – Wheeler Tranform (Chuyển đổi BW) BWT Run length (Mã hóa Run Length) RUL Inversion Frequencies (Sự đảo ngược tần số) IF Distance Coding (Mã hóa khoảng cách) DC Weighted Frequency Count (Đếm trọng số tần số) WFC Increased Frequency Count (Đếm gia tăng tần số) IFC Local to Global Transform (Chuyển đổi từ cục bộ đến tổng thể ) LGT 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 DANH MỤC HÌNH VẼ PAGE Hình 1.1: Máy nén và máy giải nén. Hình 1.2: Bộ mã hóa và bộ giải mã Hình 1.3: Những thuật toán nén không hao tổn Hình 1.4: Các thuật toán nén tổn hao Hình 1.5: Dữ liệu về nén Hình 1.6: Dữ liệu về giải nén Hình 1.7: Dữ liệu ký hiệu về nén Hình 1.8: Mã và dữ liệu nguồn Hình 1.9: Mã tiền tố Hình 1.10: Đặc tính tiền tố và các cây nhị phân Hình 1.11: Không phải mã tiền tố nhưng có thể giải mã duy nhất Hình 1.12: Các điểm ảnh với các màu giống nhau Hình 1.13: Một biểu đồ trong những khoảng xác đị nh Hình 1.14: Một số dữ liệu ma trận được tập hợp dọc theo một dòng Hình 1.15: Một dãy các frame hoạt hình Hình 2.1(a) Mảng A chứa tất cả các phép quay của đầu vào mississippi Hình 2.1(b) As thu được bằng cách sắp xếp A. Cột cuối của As (ký hiệu L) là đầu ra của BWT Hình 2.2 Mảng R được sử dụng để sắp xếp file mẫu mississippi Hình 2.3 Mảng As với mississippi. F và L là các cột đầu và cuối tương ứng 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ã xâu pssmipissii 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 Một số văn bản được chuyển đổi sinh ra từ “Hamlet” của Shakespeare. Hình 2.8: Mã hóa Huffman Hình 2.9: Mã hóa Huffman ngược Hình 2.10: Xác suất và khoảng con khởi tạo của biểu tượng Hình 2.11: Mã hóa số họ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 MỤC LỤC PAGE Lời cảm ơn! Danh mục các ký hiệu, viết tắt Danh mục các hình vẽ Mục lục MỞ ĐẦU 3 Chương I. TỔNG QUAN VỀ NÉN DỮ LIỆU 5 1.1. Giới thiệu 5 1.1.1. Một số vấn đề về Nén dữ liệu 6 1.1.2 Nén không tổn hao và nén tổn hao 9 1.1.2.1 Nén không tổn hao 9 1.1.2.2 Nén tổn hao 9 1.1.3 Đơn vị đo đặc tính nén 11 1.2. Mã hóa dữ liệu ký hiệu 13 1.2.1. Thông tin, dữ liệu và các mã 14 1.2.2 Dữ liệu ký hiệu 17 1.2.3 Mã chiều dài thay đổi 19 1.2.4 Cơ bản về lý thuyết thông tin 26 1.2.5 Sự dư thừa 27 Chương II. KỸ THUẬT NÉN DỮ LIỆU BURROWS WHEELER 31 2.1 Chuyển đổi Burrows-Wheeler (BWT) 31 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.1.1 Cách làm việc của chuyển đổi Burrows-Wheeler 33 2.1.1.1 Chuyển đổi Burrows – Wheeler thuận 33 2.1.1.2 Chuyển đổi Burrows – Wheeler nghịch 35 2.1.2 Các mã với chuyển đổi Burrows-Wheeler 41 2.1.2.1 Mã hóa Entropy 42 2.1.2.2 Mã hóa Huffman 42 2.1.2.3 Mã hóa số học 43 2.1.2.4 Mã hóa khoảng cách 46 2.1.2.5 Mã hóa run length 47 2.1.2.6 Các phương pháp đếm tần số 48 2.2 Mã hóa Move – To – Front 49 2.2.1 Mã hóa MTF với các biểu tượng là tập hợp các số nguyên 52 2.2.2 Hiệu suất mã hóa MTF 54 Chương III. GIẢI THUẬT MOVE – TO – FRONT VÀ DEMO 60 3.1. Thuật toán nén dữ liệu Move – To - Front 60 3.1.1. Thuật toán mã hóa 61 3.1.2. Thuật toán giải mã 62 3.2. Thực hiện giải thuật bằng ngôn ngữ C 62 KẾT LUẬN 72 TÀI LIỆU THAM KHẢO 73 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 MỞ ĐẦU 1. Lý do chọn đề tài Trong các lĩnh vực của công nghệ thông tin và viễn thông hiện nay, việc truyền tải tin tức là công việc xảy ra thường xuyên. Tuy nhiên, thông tin được truyền tải đi thường rất lớn, điều này gây khó khăn cho công việc truyền tải như: gây tốn kém tài nguyên mạng, tiêu phí khả năng của hệ thống,.. Để giải quyết vấn đề đó, các thuật toán nén dữ liệu đã được ra đời. Các kỹ thuật nén được nhúng ngày càng nhiều trong phần mềm và đã trở thành yêu cầu chung cho hầu hết phần mềm ứng dụng như một lĩnh vực nghiên cứu quan trọng và tích cực trong khoa học máy tính. Trong kỹ thuật truyền tin nối tiếp, do các bit dữ liệu được truyền đi nối tiếp, lại bị giới hạn về dải thông của kênh truyền và giới hạn về các chuẩn ghép nối... nên tốc độ truyền tin tương đối chậm. Nén dữ liệu trước khi truyền đi là một trong các phương pháp nhằm tăng tốc độ truyền dữ liệu. Nguyên tắc của nén dữ liệu là quá trình mã hóa thông tin dùng ít bit hơn so với thông tin chưa được mã hóa bằng cách dùng một hoặc kết hợp các phương pháp nào đó. Dựa theo nguyên tắc này giúp tránh các hiện tượng kênh truyền bị quá tải và việc truyền tin trở nên kinh tế hơn. Mặc dù các chương trình nén dữ liệu thường sử dụng kết hợp nhiều thuật toán có độ phức tạp khác nhau nhằm đạt được hiệu quả cao nhất cho dữ liệu được nén để đáp ứng yêu cầu đặt ra. Nhưng nhìn chung không thể có phương pháp nén tổng quát nào cho kết quả tốt đối với tất cả các loại tập tin. Kỹ thuật nén tập tin thường được áp dụng cho các tập tin văn bản (Trong đó có một số kí tự nào đó có xác suất xuất hiện nhiều hơn các kí tự khác), các tập tin ảnh bitmap (Mà có thể có những mảng đồng nhất), các tập tin dùng để biểu diễn âm thanh dưới dạng số hoá và các tín hiệu tương tự khác (các tín hiệu này có thể có các mẫu được lặp lại nhiều lần). Ðối với các tập tin nhị phân như tập tin chương trình thì sau khi nén cũng không tiết kiệm đượ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 1 nhiều. Ngoài ra, trong một số trường hợp để nâng cao hệ số nén người ta có thể bỏ bớt một số thông tin của tập tin (Ví dụ như kỹ thật nén ảnh JPEG). Nén dữ liệu theo kỹ thuật Move-To-Front (MTF) là một trong những kỹ thuật nén dữ liệu được thiết kế để cải tiến hiệu quả của kỹ thuật nén mã hóa entropy. Nó được sử dụng sau kỹ thuật chuyển đổi Burrows -Wheeler để xếp hạng các biểu tượng theo tần số tương quan của chúng. Mục đích là để đạt được một hiệu suất nén tốt hơn cho mã hóa entropy. Xuất phát từ ý tưởng đó, tôi đã lựa chọn đề tài ―Nén dữ liệu theo kỹ thuật Move – To – Front‖. 2. Đối tượng nghiên cứu: - Kỹ thuật nén dữ liệu Move-To-Front 3. Phạm vi nghiên cứu: - Tìm hiểu tổng quan về nén dữ liệu - Nén dữ liệu Burrows-Wheeler - Nén dữ liệu theo kỹ thuật Move – to – front 4. Mục tiêu nghiên cứu Luận văn tập trung nghiên cứu, đánh giá về nén dữ liệu theo kỹ thuật Move-To-Front. Vận dụng nén dữ liệu trong một số lĩnh vực đặc thù. 5. Ý nghĩa khoa học của đề tài - Giúp tìm hiểu, đánh giá khái quát về nén dữ liệu theo kỹ thuật MTF. - Vận dụng được phương pháp nén dữ liệu theo kỹ thuật MTF trong một số lĩnh vực đặc thù. 6. Phương pháp nghiên cứu Sử dụng các phương pháp nghiên cứu chính sau: - Phương pháp nghiên cứu lý thuyết - Phương pháp thực nghiệm - Phương pháp thống kê - Phương pháp trao đổi khoa học, lấy ý kiến chuyên gia. 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 Chương I. TỔNG QUAN VỀ NÉN DỮ LIỆU 1.1. Giới tiệu Nén dữ liệu trong ngữ cảnh khoa học máy tính là khoa học để biểu diễn thông tin dưới dạng thu gọn . Nói cách khác nén dữ liệu là việc thực hiện thu gọn kích thước các tập tin hoặc làm cho thông tin lưu trữ chiếm không gian lưu trữ ít nhất. Có nhiều cách để thực hiện điều này tùy vào từng đối tượng cụ thể. Nén dữ liệu đã trở thành yêu cầu chung cho hầu hết phần mềm ứng dụng như một lĩnh vực nghiên cứu quan trọng và tích cực trong khoa học máy tính. Nếu không có các kỹ thuật nén, Internet sẽ không bao giờ phát triển, TV kỹ thuật số , các kỹ thuật tru yền thông di động hoặc truyền thông video đã được phát triển trên thực tế. Các lĩnh vực ứng dụng có liên quan và được thúc đẩy bởi nén dữ liệu gồm có:  Các hệ thống truyền thông cá nhân: Fax, thư thoại (voice mail) và điện thoại.  Các hệ thống máy tính: Cấu trúc bộ nhớ, đĩa và băng.  Tính toán di động.  Các hệ thống máy tính phân tán.  Mạng máy tính, đặc biệt là Internet.  Sự phát triển đa phương tiện, hình ảnh, xử lý tín hiệu.  Lưu trữ hình ảnh và hội nghị truyền hình.  Ti vi kỹ thuật số và truyền hình vệ tinh.  ... Nhiều vấn đề trên thực tế đã thúc đẩy nhiều nghiên cứu khác nhau về nén dữ liệu. Tương tự , nghiên cứu về nén dữ liệu cũng đã dựa trên hay đượ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 3 kích thích bởi các lĩ nh vực mới khác. Một phần do phạm vi ứng dụng rộng rãi của nó, nén dữ liệu bao trùm nhiều ngành khoa học và có thể được tìm thấy trong nhiều lĩnh vực khác nhau như: Lý thuyết thông tin; Lý thuyết mã hóa; Mạng máy tính và viễn thông; Xử lý tín hiệu kỹ thuật số; Xử lý ảnh; Đa phương tiện; Bảo mật máy tính... Trong nén dữ liệu, từ dữ liệu có nghĩa là thông tin ở dạng kỹ thuật số mà những chương trình máy tính hoạt động và nén, có nghĩa là quá trình loại bỏ dư thừa trong dữ liệu. Cụm từ ―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 dư thừa.  Loại bỏ dư thừa trong dữ liệu.  Cài đặt thuật toán nén và giải nén. 1.1.1. Một số vấn đề về Nén dữ liệu Một vấn đề nén liên quan đến việc tìm một thuật toá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í dụ cho một xâu s, câu hỏi là dãy các biểu tượng có thể thay thế mà chiếm ít không gian lưu trữ là dãy nào? Giải pháp cho vấn đề nén là thuật toán nén nhằm đưa ra dãy các biểu tượng chứa í t số lượng bit hơn , cộng với các thuật toán giải nén để phục hồi xâu gốc. Vậy số lượng bit í t 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ả vấn đề nén dữ liệu . Theo các nghiên cứu về nén dữ liệu , ta chủ yếu phải phân tích những đặc tính của dữ liệu đã được nén và hy vọng đưa ra một Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên số mô hì nh để đạt được sự biểu http://www.lrc-tnu.edu.vn 4 diễn ngắn gọ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. 1.1.1.1 Vấn đề về nén Nén dữ liệu có thể được xem như một phương tiện truyền thông biểu diễn hiệu quả nguồn dữ liệu kỹ thuật số như văn bản , hình ảnh, âm thanh hay bất kỳ sự kết hợp của các kiểu dữ liệu đó như video. Mục đích của nén dữ liệu là biểu diễn dữ liệu nguồn theo dạng kỹ thuật số với càng ít bit càng tốt đáp ứng yêu cầu tối thiểu hóa khi khôi phục lại dữ liệu gốc. Khi làm việc về những vấn đề nén , ta phải xem xét khía cạnh hiệu quả của các thuật toán cũng như hiệu quả nén. Bằng trực quan, tính chất của thuật toán nén sẽ phụ thuộc vào dữ liệu và cấu trúc bên trong của nó. Việc dư thừa càng nhiều của dữ liệu nguồn, càng làm cho một thuật toán nén có thể hiệu quả hơn. 1.1.1.2 Vấn đề về giải nén Bất kỳ thuật toán nén sẽ không làm việc trừ khi một phương tiện giải nén được cung cấp do bản chất của dữ liệu nén. Từ nén ngụ ý là ngữ cảnh của cả nén và giải nén. Trong luận văn này, đôi khi không đề cập những thuật toán giải nén khi quá trình giải nén là hiển nhiên hay có thể dễ dàng được suy ra từ quá trình nén. Trong nhiều trường hợp thực tiễn, hiệu quả của thuật toán giải nén được quan tâm hơn thuật toán nén . Ví dụ như dữ liệu phim ảnh , hình ảnh, và âm thanh thường được nén một lần bởi người lập trì nh và sau đó cùng phiên bản với những file đã nén được giải nén nhiều lần bởi hàng triệu người xem hoặc nghe. Ngoài ra, đôi khi hiệu quả của các thuật toán nén quan trọng hơn . Ví dụ, dữ liệu ghi âm thanh hay video từ một số chương trình thời gian thực 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 5 thể được ghi trực tiếp vào bộ lưu trữ máy tính có giới hạn , hay được truyền đến đí ch từ xa thông qua kênh tín hiệu thu hẹp. Phụ thuộc vào những vấn đề cụ thể , đôi khi ta xem xét vấn đề nén và giải nén như hai quá trình đồng bộ và không đồng bộ riêng biệt. Hình 1.1 Cho thấy một mô hình dựa trên mối quan hệ giữa các thuật toán nén và giải nén. Hình 1.1: Máy nén và máy giải nén. 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. Máy nén và máy giải nén có thể được đặt tại nguồn và đí ch của một kênh truyền thông. Trong trường hợp này, máy nén tại nguồn thường được gọi là bộ mã hóa và máy giải nén tại đích của thông điệp được gọi là bộ giải mã. Hình 1.2 cho thấy một mô hình 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.2: Bộ mã hóa và bộ giải 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 6 1.1.2 Nén không tổn hao và nén tổn hao Có hai hệ thống kỹ thuật nén chủ yếu khi xem xét khả năng khôi phục chính xác dữ liệu nguồn ban đầu . Chúng được gọi là nén không tổn hao và nén tổn hao. 1.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ế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. Đó là không mất bất kỳ thông tin nào trong suốt quá trình nén. Ví dụ, trong Hình 1.3, 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. Nén không tổn hao được gọi là nén thuận nghịch vì dữ liệu gốc có thể được phục hồi hoàn toàn bởi quá trì nh giải nén. Hình 1.3: Những thuật toán nén không hao tổn Những 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 . Các ví dụ về dữ liệu nguồn như các hình ảnh y tế , văn bản và 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.1.2.2 Nén tổn hao Một phương pháp nén tổn hao 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. Có một vài chi tiết không quan trọ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 7 có thể bị mất trong quá trình nén . Từ không quan trọng ở đây hàm ý là những yêu cầu nhất định về đặc tính của dữ liệu được khôi phục. Hình 1.4 cho thấy một ví dụ số thập phân dài trở thành phép xấp xỉ ngắn hơn sau quá trình nén – giải nén. Hình 1.4: Các thuật toán nén tổn hao Nén tổn hao được gọi là nén không thuận nghịch vì nó không thể khôi phục dữ liệu gốc chính xác bởi quá trì nh giải nén. Khôi phục xấp xỉ có thể là một sự mong muốn vì nó 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. Khi xem xét ảnh hưởng của nén tổn hao , có hai dạng bài toán nén cổ điển: Bài toán tỷ lệ biến dạng : Cho một ràng buộc về tỷ lệ dữ l iệu được truyền hoặc dung lượng lưu trữ , bài toán là nén file nguồn bằng hoặc thấp hơn tỷ lệ này nhưng sự chính xác cao nhất có thể. Nén trong các lĩnh vực thư thoại , radio di động chia ô kỹ thuật số và hội nghị truyền hình là các ví dụ cho các bài toán tỷ lệ biến dạ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 8 Bài toán biến dạng tỷ lệ : Cho yêu cầu để đạt được sự chí nh xác được xác định trước nào đó , bài toán là đáp ứng yêu cầu với ít bit trên giây có thể . Nén trong các lĩnh vực âm thanh chất lượng CD và video chất lượng hình ảnh chuyển động là các ví dụ cho các bài toán biến dạng tỷ lệ. 1.1.3 Đơ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 . Khi hiệu quả về thời gian không phải là một vấn đề (mặc dù nó quan trọng như nhau), mối quan tâm chính của ta sẽ là hiệu quả về không gian, tức là hiệu quả một thuật toán nén dữ liệu có thể tiết kiệm được không gian lưu trữ là bao nhiêu? Ví dụ, đo tỷ lệ phần trăm của hiệu giữa kích thước của file đầu vào trước khi nén và kích thước của file đầu ra sau khi nén sẽ cung cấp một dấu hiệu tốt về hiệu quả nén. Nhìn chung rất khó để đo hiệu suất của một thuật toán nén vì tính chất nén của nó phụ thuộc rất nhiều vào dữ liệu chứa dư thừa mà thuật toán tìm kiếm. Tính chất nén cũng phụ thuộc vào việc ta cho phép dữ liệu được khôi phục giống với dữ liệu nguồn. Do đó 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: Đơn giả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 được nén 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. 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 Tỷ lệ phần trăm tiết kiệm được: Điều này cho thấy hao hụt bằng tỷ lệ phần trăm. Ngoài ra, hiệu quả của một thuật toán chỉ là một khía cạnh về đơn vi đ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: Điều này có thể được thông qua từ các kỹ thuật phân tích thuật toán đã có từ lâu. Ví dụ, sử dụng ký hiệu O[CLRS01] với yêu cầu hiệu quả thời gian và lưu trữ . Tuy nhiên, hoạt động của các thuật toán nén có thể không nhất quán . Vì thế nó có thể sử dụng các kết quả thực nghiệm trước đây. Thời gian nén: Ta thường xem xét thời gian mã hóa và giải mã tách biệt nhau. Trong một số ứng dụng, thời gian giải mã quan trọng hơn thời gian mã hóa. Trong các ứng dụng khác, chúng quan trọng như nhau. Entropy: Nếu thuật toán nén dựa trên các kết quả thống kê, thì entropy có thể được sử dụng như một ràng buộc lý thuyết với dữ liệu ngu ồn để giúp thực hiện sự phán đoán đại lượng hữu ích . Vì vậy nó cung cấp sự hướng dẫn lý thuyết để xem nén có thể đạt được bao nhiêu. Sự dư thừa: Trong các lĩnh vực nén nhất định , sự khác biệt giữa chiều dài mã trung bình và entropy của dữ liệu nguồn có thể được xem như là sự dư thừa. Trong một vài lĩnh vực khác, sự khác nhau giữa phân phối xác suất chuẩn và phân phối xác suất đều được xác định bằng sự dư thừa. Độ phức tạp: Đơn vị đo lường này làm việc tốt để ch ứng minh lý thuyết hơn với các cài đặt thực tế . Độ phức tạp của dữ liệu nguồn trong một file có thể được đo bằng chiều dài chương trình ngắn nhất để tạo ra dữ liệu. 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 Kiểm tra cài đặt: Kiểm tra hiệu suất của thuật toán nén bằng cách cài đặt thuật toán và chạy các chương trình với nhiều định dạng dữ liệu kiểm tra. Canterbury Corpus cung cấp thử nghiệm tốt để kiểm tra các chương trình nén. Xem http://corpus.canterbury.ac.nz để biết thêm chi tiết. Chi phí phụ: Đơn vị đo này thường được sử dụng bởi ngành công nghiệp công nghệ thông tin . Chi phí phụ là số lượng dữ liệu bổ sung được thêm vào phiên bản đã được nén của dữ liệu để giải nén sau này . Chi phí phụ đôi khi có thể lớn hơn mặc dù nó nhỏ hơn nhiều không gian được lưu trữ bằng cách nén. 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ữ liệu 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 như sau : Nén tổn hao và không tổn hao. Đặc tính nén có thể được đo bằng nhiều cách khác nhau. 1.2. Mã hóa dữ liệu ký hiệu Nén dữ liệu là khoa học về biểu diễ n thông tin theo một hình thức thu gọn. Tuy nhiên , thông tin là gì ? Thông tin được biểu diễn theo một dạng ―chuẩn‖ như thế nào, tức là dạng bất kỳ trước khi nén ? Ta muốn nói gì về dữ liệu nguồn ? Làm thế nào để biết nếu có bất kỳ dư thừa nào trong dữ liệ u nguồ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 11 Để trả lời các câu hỏi đó, trước hết ta cần làm rõ ý nghĩa của các thuật ngữ như: thông tin, dữ liệu, các mã và mã hóa. 1.2.1. Thông tin, dữ liệu và các mã Thông tin là cái gì đó mà làm tăng thêm kiến thức của con người. Đó là những gì góp phần giảm bớt sự không chắc chắn trong tâm trí con người hay trạng thái của một hệ thống. Mọi người cảm nhận được sự tồn tại của thông tin, xem xét phương tiện truyền th ông mang thông tin và tác động trở lại theo thông tin chắc chắn. Thông tin không hiện hữu nếu không tồn tại một số phương tiện truyền thông sóng mang. 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 . Điều này được phân biệt từ các dạng tương phản của thông tin như : văn bản, đồ họa, âm thanh và hình ảnh . Một số lượng lớn dữ liệu có thể sau đó được tổ chức và được lưu trữ trong những thông điệp ngắn hay những file dài. 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 được xử lý bởi chương trình máy tính . Dữ liệu trước bất kỳ quá trình nén nào được gọi là dữ liệu nguồn, hay nói ngắn gọn là nguồn. Các ví dụ về thông tin xác thực có thể được phân loại rộng rãi như: văn bản, âm thanh, hình ảnh và video. Nhiều chương trình ứng dụng chấp nhận kiểu thông tin như kiểu file dữ liệu của chúng cho thuận tiện. Do đó dữ liệu có thể được phân loại như: văn bản, âm thanh, hình ảnh và video trong khi định dạng dữ liệu kỹ thuật số thực chứa các số 0 và 1 theo định dạng nhị phâ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 12 Dữ liệu văn bản thường được biểu diễn bởi 8 bit mã ASCII mở rộng. Chúng xuất hiện trong các file với phần mở rộng .txt hay .tex (hay các file hệ thống mã hóa có thể đọc được khác như .doc) sử dụng một trình soạn thảo. Các ví dụ của các file văn bản điển hình là các bản thảo, các chương trình trong các ngôn ngữ bậc cao khác nhau (được gọi là các mã nguồn) hay các email văn bản. Dữ liệu nhị phân gồm các file cơ sở dữ liệu, dữ liệu bảng tính, các file thực thi, và các mã chương trình. Các file đó thường có phần mở rộng là .bin. Dữ liệu hình ảnh thường được biểu diễn bằng mảng hai chiều của những điểm ảnh mà mỗi điểm ảnh được kết hợp với mã màu của nó . Phần mở rộng .bmp biểu diễn một kiểu file ảnh bitmap trong Windows và .psd với định dạng file riêng của Adobe Photoshop. Dữ liệu đồ họa được biểu diễn theo dạng các vectơ hay các phương trình toán học. Một ví dụ của định dạng dữ liệu là .png, đây là chuẩn với Portable Network Graphics. Dữ liệu âm thanh được biểu diễn bởi một hàm sóng (tuần hoàn). Một ví dụ phổ biến là các file âm thanh theo định dạng .wav. Ba kiểu cơ bản của dữ liệu nguồn trong máy tính là văn bản, hình ảnh (kỹ thuật số) và âm thanh. Trong các lĩnh vực ứng dụng, dữ liệu nguồn được nén gọi là đa phương tiện và có thể là hỗn hợp của định dạng phương tiện truyền thông tĩnh như: văn bản, hình ảnh và đồ họa, và phương tiện truyền thông động như âm thanh và video . Hình 1.5 giải thích các giai đoạn liên quan đến dữ liệu nguồn trong file được mã hóa thành file nhị phân nguồn trước khi nén . Hình 1.6 cho thấy quá trình ngược lại , trong đó dữ liệu nhị phân được khôi phục sau khi giải nén phải được giải mã thành dữ liệu của một loại nào đó trước khi được nhận ra trong bất kỳ ứng dụng nào. 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 13 Hình 1.5: Dữ liệu về 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 14