CHƯƠNG 1: TỔNG QUAN VỀ NÉN DỮ LIỆU 1. Vấn đề về nén dữ liệu Nén là một quá trình giảm lượng không gian cần thiết để biểu diễn cùng một lượng thông tin cho trước. Người ta còn gọi nén là biến đổi một luồng ký hiệu vào thành một luồng các từ mã. Quá trình nén như sau: Hình 1.
1: Quy trình nén dữ liệ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ụ thể Nén dữ liệu là quy trình mã hóa từ một file nguồn f thành một file đích f’, đáp ứng được dung lượng file đích f’ nhỏ hơn file nguồn f, file đích càng nhỏ hơn file nguồn càng tốt, từ file đích f’ khôi phục được file nguồn f, với thời gian í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ể.
Ta kí hiệu F là thuật toán nén dữ liệu D để thu được bản nén V khi đó ta có F(D) = V. Học viên: Hoàng Văn Sáng – Lớp CHK12I 5 Các yêu cầu của một thuật toán nén dữ liệu: + Dữ liệu ra nhỏ hơn dữ liệu vào. - Có |D|là dung lượng của dữ liệu vào khi đó F(D) < |D| + Khôi phục V -> D - Gọi F-1 là thuật toán giải nén khi đó F-1(V) = D + Thời gian thực hiện càng ít càng tốt. + Tỉ lệ nén.
- Gọi k là tỉ lệ nén khi đó 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, truyền hình kỹ thuật số, các kỹ thuật truyề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 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 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 Học viên: Hoàng Văn Sáng – Lớp CHK12I 6 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. Nén dữ liệu là 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ố mô hình để đạt được sự biểu 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.
Học viên: Hoàng Văn Sáng – Lớp CHK12I 7 1. Bài toán nén dữ liệu 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 tiếp cận với những bài toán về 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. Phân loại chương trình nén Trên thực tế những phần mềm nén hoặc hệ điều hành thường được hợp thành bởi nhiều kiểu nén. Dựa vào dữ liệu sau khi được giải nén, so sánh với dữ liệu đầu vào của quá trình nén, có thể chia thành nén bảo toàn và nén không bảo toàn.
Một chương trình được gọi là nén bảo toàn khi nó có thể dựng lại được dữ liệu nguyên gốc từ dữ liệu đã được nén. Trong thực tế, nén bảo toàn được dùng đối với các loại dữ liệu quan trọng: các bức ảnh thuộc về ngành sinh học, y tế như bức ảnh tế bào bệnh, văn bản chữ viết, những phần mềm,. Một chương trình được gọi là nén không bảo toàn khi nó không có khả năng dựng lại nguyên mẫu dữ liệu ban đầu từ dữ liệu đã qua quá trình nén. Nén không bảo toàn thường được áp dụng để nén ảnh, đoạn băng.
Dựa vào khả năng cập nhật thông số cho thuật toán trong quá trình mã hóa và giải mã, có thể chia ra 2 loại: nén tĩnh (static compression) và nén động (adaptive compression). Nén tĩnh: các quy luật dữ liệu vào của thuật toán không bị thay đổi trong suốt quá trình nén và Học viên: Hoàng Văn Sáng – Lớp CHK12I 8 giải nén. Nén động: các quy luật hoặc dữ liệu vào của thuật toán được cập nhật thường xuyên, có thể lại được cập nhật bằng chính những dữ liệu vừa mới ra. (Một số chương trình nén động được xây dựng từ những dữ liệu khởi đầu là trắng) Nếu như một chương trình nén và giải nén được thực hiện với các thao tác đồng nhất như nhau, thì thuật toán mã hóa được gọi là cân đối và ngược lại thì được gọi là không cân đối.
Căn cứ độ dài ký tự trước và sau nén, cũng có thể chia thuật toán dùng để nén dữ liệu ra các kiểu sau: Fixed to fixed: độ dài biểu diễn trên máy tính của từng ký tự phải đều bằng nhau, và khi được nén, độ dài biểu diễn mã của các ký tự cũng phải bằng nhau; Fixed to variable: những ký tự trước khi nén thì đều có độ dài như nhau, nhưng những ký tự đã được nén sẽ có độ dài không cân đối tương đồng nhau nữa; Variable to fixed: những dãy ký tự có độ dài khác nhau sau khi được nén, trở thành những dãy ký tự có độ dài bằng nhau; Variable to variable: các chuỗi ký tự trước khi nén và sau khi nén có độ dài khác nhau, không nhất thiết phải tương ứng theo đúng tỷ lệ. Chất lượng của thuật toán nén dữ liệu Hiệu quả của một thuật toán nén được đánh giá thông qua lượng dữ liệu mà nó có thể giúp tiết kiệm được không gian lưu trữ của bộ nhớ. Không nên đánh giá hiệu quả một thuật toán bằng cách công nghiệp dập khuôn, bởi khả năng của một chương trình nén còn phụ thuộc rất nhiều vào dữ liệu ban đầu, dữ liệu ấy có thể chứa hay không chứa những kiểu dư thừa mà thuật toán đào sâu xử lý. Trong nén bảo toàn, có thể đo hiệu quả của chương trình nén bằng sự hao hụt giữa kích thước dữ liệu đầu vào và kích thước dữ liệu đầu ra.
Từ đó, có thể xét tới một vài thông số được định nghĩa sau: - Tỷ lệ nén (k): Là tỷ lệ của kích thước sau nén và kích thước trước nén. Học viên: Hoàng Văn Sáng – Lớp CHK12I 9 - Thừa số nén: Là nghịch đảo của tỷ lệ nén. - Mức độ hao hụt: Là tỷ lệ của độ chênh lệch 2 kích thước với kích thước ban đầu. Ngoài ra còn một số tiêu chí cần đánh giá trên thuật toán: độ phức tạp của thuật toán, thời gian thực hiện nén và giải nén, số lượng bit nhị phân trung bình ít nhất biểu diễn ký tự mã hóa trung bình, sự dư thừa của dữ liệu sau khi được mã hóa… 1.
Vấn đề 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ó 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.
