Chương 5: Tổng quan các thuật toán nén dữ liệu (RLE, Huffman)

Chuyên khảo toán học phân tích Các thuật toán nén dữ liệu chuong 5 cac thuat toan nen compatibility mode, đánh giá các khía cạnh quan trọng, đề xuất hướng nghiên cứu tiếp theo.

• Đề tài: Các Thuật Toán Nén Dữ Liệu Chương 5 Các Thuật Toán Nén Compatibility Mode

Mục lục chi tiết

• 1. Giới thiệu
• 1.1. Các thuật ngữ thường dùng
• 1.2. Mục đích của nén dữ liệu
• 1.3. Các hình thức nén
• 1.4. Hiệu suất nén
• 1.5. Nén tập tin
• 2. Giải thuật nén RLE
• 2.1. Ý tưởng
• 2.2. Dạng 1: RLE với file *.PCX
• 2.3. Dạng 2: RLE với file *.BMP
• 2.4. Nhận xét
• 3. Giải thuật nén Huffman
• 3.1. Giới thiệu
• 3.2. Huffman tĩnh (Static Huffman)
• 3.2.1. Thuật toán nén
• 3.2.2. Tạo cây Huffman
• 3.2.3. Phát sinh bảng mã bit
• 3.2.4. Lưu trữ thông tin dùng để giải nén
• 3.2.5. Thuật toán giải nén
• 3.3. Huffman động (Adaptive Huffman)
• 3.3.1. Giới thiệu
• 3.3.2. Thuật toán tổng quát
• 3.3.3. Cây Huffman động
• 3.3.4. Thuật toán nén (Encoding)
• 3.3.5. Thuật toán giải nén (Decoding)

Tóm tắt

I. Tổng quan các thuật toán nén dữ liệu và vai trò cốt lõi

Các thuật toán nén dữ liệu đóng vai trò nền tảng trong khoa học máy tính, giúp giảm kích thước lưu trữ và tăng tốc độ truyền tải thông tin. Về cơ bản, nén dữ liệu là quá trình mã hóa thông tin sử dụng ít bit hơn so với biểu diễn gốc. Theo giáo trình Cấu trúc dữ liệu và Giải thuật, mục đích chính của việc này bao gồm: giảm dung lượng khi lưu trữ (backup, restore) và khi truyền dữ liệu qua mạng, đồng thời có thể tăng tính bảo mật. Có hai hình thức nén chính cần phân biệt rõ ràng: nén không mất dữ liệu (lossless) và nén mất mát dữ liệu (lossy). Mỗi hình thức có ưu nhược điểm và ứng dụng riêng, quyết định đến hiệu suất và chất lượng dữ liệu sau khi giải nén dữ liệu (decompression). Hiệu suất nén, hay tỷ lệ nén (compression ratio), được tính bằng phần trăm kích thước giảm được so với bản gốc. Hiệu suất này phụ thuộc lớn vào phương pháp nén và đặc trưng của chính dữ liệu đó. Việc hiểu rõ các khái niệm này là bước đầu tiên để nắm vững các kỹ thuật phức tạp hơn.

1.1. Phân biệt nén không mất dữ liệu và nén mất mát dữ liệu

Hai phương pháp nén dữ liệu cơ bản là nén không mất dữ liệu (lossless) và nén mất mát dữ liệu (lossy). Với nén lossless, dữ liệu sau khi giải nén hoàn toàn giống hệt dữ liệu gốc, không có bất kỳ thông tin nào bị mất đi. Phương pháp này cực kỳ quan trọng đối với các loại dữ liệu yêu cầu sự toàn vẹn tuyệt đối như văn bản, mã nguồn chương trình, hay các file thực thi. Các thuật toán tiêu biểu cho hình thức này bao gồm mã hoá Run-Length (RLE), thuật toán Huffman, và họ thuật toán Lempel-Ziv (LZW, LZ77, LZ78). Hiệu suất nén của lossless thường dao động từ 10% đến 60%. Ngược lại, nén lossy chấp nhận loại bỏ một số thông tin được cho là 'không quan trọng' để đạt được tỷ lệ nén cao hơn nhiều, từ 40% đến 90%. Dữ liệu sau giải nén sẽ gần giống với bản gốc nhưng không hoàn toàn chính xác. Kỹ thuật này phù hợp với dữ liệu đa phương tiện như hình ảnh, âm thanh, video, nơi mà sự mất mát nhỏ thường khó nhận ra bởi giác quan con người. Các định dạng file nén phổ biến như JPEG, MP3, MP4 là ví dụ điển hình của nén lossy.

1.2. Các thuật ngữ cơ bản Encoding Decoding và Compression Ratio

Để hiểu sâu về các thuật toán nén dữ liệu, cần nắm vững một số thuật ngữ cốt lõi. Encoding (Mã hóa) là quá trình chuyển đổi dữ liệu từ dạng gốc sang một định dạng khác, thường là nhỏ gọn hơn, dựa trên một thuật toán cụ thể. Decoding (Giải mã) hay giải nén dữ liệu là quá trình ngược lại, biến đổi dữ liệu đã mã hóa trở về dạng ban đầu (hoặc gần giống ban đầu trong trường hợp nén lossy). Compression Ratio (Tỷ lệ nén) là chỉ số đo lường hiệu quả của một thuật toán. Theo tài liệu của Nguyễn Trí Tuấn (ĐH KHTN Tp.HCM), công thức tính hiệu suất nén D(%) là (N – M)/N*100, trong đó N là kích thước trước khi nén và M là kích thước sau khi nén. Một khái niệm quan trọng khác là entropy thông tin, đại diện cho mức độ 'ngẫu nhiên' hoặc 'bất ngờ' của dữ liệu. Các thuật toán nén hiệu quả thường khai thác tính dự đoán được và sự dư thừa thông tin (entropy thấp) để giảm kích thước file.

II. Thách thức chính khi lựa chọn thuật toán nén dữ liệu tối ưu

Việc lựa chọn một thuật toán nén không phải lúc nào cũng đơn giản. Thách thức lớn nhất nằm ở sự đánh đổi giữa ba yếu tố: tỷ lệ nén, tốc độ xử lý (bao gồm cả nén và giải nén), và mức độ toàn vẹn dữ liệu. Một thuật toán có thể cho tỷ lệ nén rất cao nhưng lại yêu cầu tài nguyên tính toán lớn, làm chậm hệ thống. Ví dụ, mã hóa số học (Arithmetic Coding) thường cho kết quả nén tốt hơn Huffman nhưng lại có độ phức tạp thuật toán cao hơn. Một thách thức khác là đặc tính của dữ liệu đầu vào. Một thuật toán hoạt động cực kỳ hiệu quả trên dữ liệu ảnh có nhiều vùng màu đồng nhất (như RLE) có thể 'phản tác dụng' và làm tăng kích thước file khi áp dụng cho dữ liệu văn bản ngẫu nhiên. Do đó, không có một thuật toán 'tốt nhất' cho mọi trường hợp. Người phát triển cần phân tích bản chất dữ liệu và yêu cầu của ứng dụng để chọn ra phương pháp phù hợp, cân bằng giữa hiệu suất, tốc độ và chi phí tài nguyên.

2.1. Đánh đổi giữa tỷ lệ nén và độ phức tạp thuật toán

Sự cân bằng giữa tỷ lệ nén và độ phức tạp thuật toán là yếu tố quyết định. Các thuật toán đơn giản như mã hoá Run-Length (RLE) rất nhanh và dễ cài đặt nhưng chỉ hiệu quả với dữ liệu có các chuỗi ký tự lặp lại dài. Ngược lại, các phương pháp nén thống kê như thuật toán Huffman hay mã hóa số học (Arithmetic Coding) phân tích tần suất xuất hiện của các ký tự để tạo ra mã bit có độ dài thay đổi, đạt tỷ lệ nén tốt hơn trên nhiều loại dữ liệu. Tuy nhiên, chúng đòi hỏi các bước xử lý phức tạp hơn, chẳng hạn như xây dựng bảng tần suất và cây Huffman. Các thuật toán nén dựa trên từ điển như họ Lempel-Ziv (LZ77, LZW) còn phức tạp hơn nữa, tìm kiếm các chuỗi lặp lại trong toàn bộ dữ liệu thay vì chỉ các ký tự đơn lẻ, nhưng đổi lại là hiệu suất nén vượt trội và là nền tảng cho các định dạng file nén như ZIP và GZIP.

2.2. Ảnh hưởng của đặc trưng dữ liệu đến hiệu quả nén

Hiệu quả của một thuật toán nén phụ thuộc mật thiết vào đặc trưng của dữ liệu. Dữ liệu có tính dự đoán cao, độ dư thừa lớn (low entropy thông tin) sẽ dễ nén hơn. Ví dụ, một file ảnh bitmap đơn sắc với nhiều mảng trắng đen lớn sẽ được nén rất tốt bằng RLE. Một file văn bản tiếng Anh, nơi ký tự 'e' và 'space' xuất hiện rất thường xuyên, là ứng cử viên lý tưởng cho thuật toán Huffman. Ngược lại, một file đã được mã hóa hoặc đã được nén trước đó sẽ có entropy rất cao, gần như ngẫu nhiên, và việc áp dụng thêm một thuật toán nén không mất dữ liệu lên nó thường không mang lại hiệu quả, thậm chí có thể làm tăng kích thước. Đây là lý do tại sao các file JPEG hay MP3 (đã được nén lossy) không thể được nén thêm nhiều bằng WinZip hay WinRar. Việc phân tích dữ liệu trước khi nén là một bước quan trọng để tối ưu hóa quá trình.

III. Phương pháp mã hoá Run Length RLE và ứng dụng thực tế

Mã hoá Run-Length (RLE) là một trong những thuật toán nén đơn giản và trực quan nhất. Tư tưởng cốt lõi của RLE là thay thế các chuỗi ký tự lặp lại liên tiếp (gọi là một 'run') bằng một cặp giá trị: số lần lặp và ký tự lặp. Ví dụ, chuỗi AAAAABBB sẽ được mã hóa thành 5A3B, giảm đáng kể số byte cần lưu trữ. Đây là một kỹ thuật nén không mất dữ liệu vì quá trình giải nén có thể tái tạo lại chính xác chuỗi ban đầu. Mặc dù đơn giản, RLE lại cực kỳ hiệu quả cho các loại dữ liệu có nhiều vùng đồng nhất, chẳng hạn như hình ảnh đồ họa đơn giản, icon, hoặc các file ảnh y tế. Tuy nhiên, thuật toán này có một nhược điểm lớn: nó có thể gây 'phản tác dụng' với dữ liệu không có chuỗi lặp, làm tăng kích thước file. Ví dụ, chuỗi ABCDE có thể bị mã hóa thành 1A1B1C1D1E, tăng gấp đôi kích thước. Để giải quyết vấn đề này, các biến thể của RLE đã được phát triển.

3.1. Nguyên tắc hoạt động và ví dụ minh họa của thuật toán RLE

Nguyên tắc của mã hoá Run-Length (RLE) là tìm kiếm các 'run' - dãy ký tự giống hệt nhau và liên tiếp. Thay vì lưu trữ toàn bộ dãy, thuật toán chỉ lưu một bộ đếm và ký tự đại diện. Ví dụ được đưa ra trong bài giảng nén dữ liệu là: chuỗi AAAABBBBBBBBCCCCCCCCCCDEE (25 bytes) được nén thành 4A8B10C1D2E (10 bytes). Tuy nhiên, một vấn đề phát sinh với các 'run đặc biệt' chỉ có một ký tự. Chuỗi X (1 byte) nếu mã hóa theo cách trên sẽ thành 1X (2 bytes), làm tăng kích thước. Các triển khai thực tế của RLE phải có cơ chế để xử lý trường hợp này. Ví dụ, các định dạng file PCX và BMP sử dụng các 'cờ hiệu' (flag) hoặc 'mã thoát' (escape code) để phân biệt giữa dữ liệu được nén và dữ liệu không được nén, giúp tối ưu hóa kích thước cuối cùng.

3.2. So sánh hai biến thể RLE trong định dạng file PCX và BMP

Tài liệu gốc đã trình bày chi tiết hai biến thể của RLE trong các định dạng file nén hình ảnh là PCX và BMP. Trong file PCX, RLE sử dụng 2 bit cao của một byte làm cờ hiệu. Nếu 2 bit này được bật (11), 6 bit còn lại sẽ biểu thị số lần lặp (tối đa 63 lần) của byte dữ liệu tiếp theo. Nếu không, byte đó được hiểu là một ký tự đơn lẻ. Cách này giải quyết được phần lớn trường hợp phản tác dụng, nhưng vẫn có điểm yếu với các ký tự có mã ASCII >= 192. Ngược lại, RLE trong file BMP sử dụng một phương pháp linh hoạt hơn. Dữ liệu được chia thành hai dạng: dạng nén và dạng không nén. Dạng nén được biểu diễn bằng cặp <Số lần lặp> <Ký tự>, tương tự RLE cơ bản. Dạng không nén được bắt đầu bằng một mã đặc biệt (escape code 0x00), theo sau là số lượng byte không nén và chuỗi byte đó. Cách tiếp cận này giúp BMP xử lý hiệu quả cả những vùng ảnh có nhiều chi tiết phức tạp (không lặp) và những vùng có màu đồng nhất.

IV. Hướng dẫn chi tiết thuật toán Huffman và cách xây dựng cây

Thuật toán Huffman, do David Huffman đề xuất vào năm 1952, là một phương pháp nén thống kê kinh điển và hiệu quả. Đây là một thuật toán nén không mất dữ liệu, hoạt động dựa trên nguyên tắc mã hóa có độ dài thay đổi (Variable Length Encoding). Thay vì dùng một số bit cố định (như 8 bit trong mã ASCII) để biểu diễn mỗi ký tự, Huffman gán các mã bit ngắn cho các ký tự xuất hiện thường xuyên và các mã bit dài hơn cho các ký tự ít xuất hiện. Điều này giúp giảm tổng số bit cần thiết để biểu diễn toàn bộ dữ liệu. Nền tảng của thuật toán là việc xây dựng một cấu trúc dữ liệu đặc biệt gọi là cây Huffman. Đây là một cây nhị phân tối ưu, nơi mỗi ký tự là một nút lá và đường đi từ gốc đến lá xác định mã bit cho ký tự đó. Quá trình này đảm bảo không có mã bit nào là tiền tố của một mã bit khác, giúp việc giải nén dữ liệu trở nên eindeutig (đơn nhất) và chính xác.

4.1. Các bước xây dựng cây Huffman từ bảng tần suất ký tự

Quá trình nén bằng Huffman tĩnh (Static Huffman) bao gồm các bước chính sau. Đầu tiên, duyệt qua toàn bộ dữ liệu để lập một bảng thống kê tần suất xuất hiện của mỗi ký tự. Từ bảng này, quá trình xây dựng cây Huffman bắt đầu. Mỗi ký tự được xem là một nút lá với trọng số bằng tần suất của nó. Thuật toán lặp đi lặp lại việc chọn hai nút có trọng số thấp nhất trong tập hợp các nút hiện có, kết hợp chúng thành một nút cha mới. Nút cha này có trọng số bằng tổng trọng số của hai nút con. Quá trình này tiếp tục cho đến khi chỉ còn lại một nút duy nhất, đó chính là gốc của cây. Theo quy ước, khi duyệt cây, nhánh trái tương ứng với bit '0' và nhánh phải tương ứng với bit '1'. Mã bit của một ký tự được xác định bằng cách đi từ gốc đến nút lá chứa ký tự đó. Các ký tự có tần suất cao sẽ tự động nằm gần gốc hơn, do đó có mã bit ngắn hơn.

4.2. Mã hóa và giải nén dữ liệu sử dụng cây Huffman đã tạo

Sau khi cây Huffman được xây dựng và bảng mã bit được tạo ra, quá trình mã hóa bắt đầu. Thuật toán duyệt lại dữ liệu gốc một lần nữa, thay thế mỗi ký tự bằng mã bit tương ứng đã được phát sinh. Chuỗi bit kết quả này chính là dữ liệu đã nén. Để có thể giải nén dữ liệu, thông tin về cấu trúc cây Huffman (hoặc bảng tần suất/bảng mã bit) phải được lưu lại cùng với dữ liệu nén. Quá trình giải nén bắt đầu bằng việc tái tạo lại cây Huffman từ thông tin đã lưu. Sau đó, thuật toán đọc chuỗi bit nén từng bit một. Bắt đầu từ gốc cây, nó di chuyển sang trái nếu đọc được bit '0' và sang phải nếu đọc được bit '1'. Khi đến một nút lá, ký tự tại nút lá đó được ghi ra, và quá trình quay trở lại gốc cây để giải mã ký tự tiếp theo. Thuật toán kết thúc khi toàn bộ chuỗi bit đã được đọc.

4.3. Hạn chế của Huffman tĩnh và giới thiệu về Huffman động

Mặc dù hiệu quả, Huffman tĩnh có một số hạn chế. Nó đòi hỏi phải duyệt file hai lần: một lần để xây dựng bảng tần suất và một lần để mã hóa. Điều này làm tăng chi phí và không phù hợp cho việc nén dữ liệu theo thời gian thực (streaming). Thêm vào đó, việc phải lưu trữ thông tin về cây hoặc bảng tần suất làm tăng kích thước của file nén cuối cùng. Để khắc phục những nhược điểm này, Huffman động (Adaptive Huffman) đã được phát triển. Thuật toán này chỉ cần duyệt file một lần. Nó bắt đầu với một cây rỗng hoặc cây mặc định và cập nhật cây Huffman một cách linh hoạt ngay khi đọc từng ký tự. Cả bộ nén và bộ giải nén đều tuân theo cùng một quy tắc cập nhật cây, do đó không cần phải lưu trữ thông tin cây. Điều này làm cho Huffman động trở nên lý tưởng cho các ứng dụng truyền dữ liệu trực tuyến.

V. Ứng dụng thực tiễn của các thuật toán nén dữ liệu phổ biến

Các thuật toán nén dữ liệu không chỉ là lý thuyết trong giáo trình cấu trúc dữ liệu và giải thuật mà còn có ứng dụng sâu rộng trong mọi khía cạnh của công nghệ hiện đại. Từ việc gửi một email, duyệt web, xem video trực tuyến đến lưu trữ tài liệu trên đám mây, tất cả đều dựa vào các kỹ thuật nén để hoạt động hiệu quả. Các định dạng file nén quen thuộc như ZIP, GZIP, RAR sử dụng các biến thể của thuật toán Lempel-Ziv (LZ77, LZW), thuộc loại nén dựa trên từ điển. Các định dạng ảnh như PNG sử dụng kết hợp giữa bộ lọc dự đoán và thuật toán Deflate (một biến thể của LZ77 và thuật toán Huffman), mang lại khả năng nén không mất dữ liệu hiệu quả. Trong khi đó, định dạng JPEG cho hình ảnh và MP3 cho âm thanh lại là ví dụ điển hình của nén mất mát dữ liệu, giúp giảm kích thước file một cách ngoạn mục mà vẫn giữ được chất lượng chấp nhận được.

5.1. Vai trò của Huffman và Lempel Ziv trong định dạng ZIP GZIP

Các định dạng nén file phổ biến như ZIP và GZIP chủ yếu dựa trên một thuật toán mạnh mẽ có tên là DEFLATE. DEFLATE là sự kết hợp thông minh của hai phương pháp: thuật toán Lempel-Ziv (LZ77) và thuật toán Huffman. Đầu tiên, LZ77 quét qua dữ liệu để tìm các chuỗi byte lặp lại. Thay vì lưu trữ lại chuỗi đó, nó tạo ra một tham chiếu ngược (một cặp con trỏ khoảng cách và độ dài) đến lần xuất hiện trước đó của chuỗi. Kết quả của giai đoạn này là một chuỗi các ký tự và các tham chiếu. Sau đó, chuỗi kết quả này được đưa qua bộ mã hóa Huffman. Bằng cách gán mã bit ngắn cho các ký tự và tham chiếu thường xuyên xuất hiện nhất, Huffman nén dữ liệu thêm một lần nữa. Sự kết hợp này tận dụng cả sự dư thừa cục bộ (LZ77) và sự dư thừa thống kê (Huffman), tạo ra một tỷ lệ nén rất cao cho nhiều loại dữ liệu khác nhau.

5.2. Ứng dụng RLE và Huffman trong nén hình ảnh PNG BMP

Nén hình ảnh là một lĩnh vực ứng dụng quan trọng. Mã hoá Run-Length (RLE) được sử dụng trong định dạng BMP (Bitmap) để nén các vùng màu đồng nhất, đặc biệt hiệu quả với các ảnh có độ sâu màu thấp (16 màu, 256 màu). Đối với định dạng PNG, một phương pháp nén không mất dữ liệu tiên tiến hơn được sử dụng. PNG đầu tiên áp dụng một bước 'lọc' (filtering) để biến đổi dữ liệu điểm ảnh, làm tăng khả năng nén. Dữ liệu sau khi lọc sau đó được nén bằng thuật toán DEFLATE, chính là sự kết hợp của LZ77 và thuật toán Huffman. Điều này cho phép PNG đạt được tỷ lệ nén tốt hơn đáng kể so với các định dạng cũ như GIF, trong khi vẫn bảo toàn 100% chất lượng hình ảnh. Ngay cả trong định dạng JPEG (nén lossy), sau khi các hệ số tần số được lượng tử hóa, thuật toán Huffman cũng thường được sử dụng ở bước cuối cùng để mã hóa các hệ số này, giúp giảm thêm kích thước file.

VI. Tóm tắt lý thuyết và định hướng phát triển trong tương lai

Tổng kết lại, các thuật toán nén dữ liệu là một lĩnh vực đa dạng, từ các phương pháp đơn giản như RLE đến các kỹ thuật phức tạp hơn như Huffman, Lempel-Ziv, và mã hóa số học. Lựa chọn thuật toán phụ thuộc vào sự cân bằng giữa tỷ lệ nén, tốc độ, tài nguyên yêu cầu và bản chất của dữ liệu. Nén không mất dữ liệu là bắt buộc đối với dữ liệu cần toàn vẹn, trong khi nén mất mát dữ liệu thống trị trong lĩnh vực đa phương tiện. Việc nghiên cứu và phát triển các thuật toán nén mới vẫn đang tiếp tục, đặc biệt trong bối cảnh bùng nổ dữ liệu lớn (Big Data), Internet vạn vật (IoT) và học máy. Các thuật toán trong tương lai không chỉ tập trung vào việc cải thiện tỷ lệ nén mà còn hướng đến việc tối ưu hóa cho các kiến trúc phần cứng cụ thể (như GPU), giảm độ trễ cho các ứng dụng thời gian thực và phát triển các kỹ thuật nén chuyên biệt cho các loại dữ liệu mới như mô hình học sâu hoặc dữ liệu gen.

6.1. So sánh tổng quan hiệu quả các thuật toán nén đã học

Để đưa ra tóm tắt lý thuyết cô đọng, có thể so sánh các thuật toán đã trình bày. RLE là nhanh nhất, đơn giản nhất nhưng có phạm vi ứng dụng hẹp, chỉ hiệu quả với dữ liệu có độ lặp cao. Thuật toán Huffman cung cấp khả năng nén tốt hơn RLE trên nhiều loại dữ liệu hơn, dựa trên tần suất thống kê, nhưng yêu cầu chi phí tính toán để xây dựng cây. Thuật toán Lempel-Ziv (LZW, LZ77, LZ78) vượt trội hơn cả hai bằng cách sử dụng phương pháp nén dựa trên từ điển, hiệu quả với các chuỗi dữ liệu lặp lại. Mã hóa số học (Arithmetic Coding) thường đạt tỷ lệ nén cao nhất về mặt lý thuyết, gần với giới hạn entropy thông tin, nhưng lại có độ phức tạp thuật toán cao nhất và chậm hơn. Sự lựa chọn cuối cùng luôn là một sự đánh đổi, và trong thực tế, các hệ thống thường kết hợp nhiều thuật toán để đạt được kết quả tối ưu như trong định dạng ZIP hay PNG.

6.2. Hướng đi mới và các thuật toán nén dữ liệu hiện đại

Tương lai của lĩnh vực nén dữ liệu đang hướng tới việc xử lý các tập dữ liệu khổng lồ và đa dạng. Các thuật toán hiện đại như Zstandard (Zstd) của Facebook hay Brotli của Google đang ngày càng phổ biến. Chúng thường kết hợp các kỹ thuật tốt nhất từ các thuật toán trước đó (như LZ77, Huffman, và mã hóa số học bất đối xứng) và được tối ưu hóa ở mức độ thấp để tận dụng tối đa kiến trúc vi xử lý hiện đại. Một hướng đi khác là nén dữ liệu dựa trên học máy (machine learning), nơi các mô hình neural network học cách biểu diễn dữ liệu một cách hiệu quả nhất. Các kỹ thuật này hứa hẹn sẽ tạo ra một cuộc cách mạng trong việc nén các loại dữ liệu phi cấu trúc như hình ảnh và video, đạt được tỷ lệ nén cao hơn trong khi vẫn duy trì chất lượng hình ảnh tốt hơn so với các tiêu chuẩn hiện tại như JPEG.

Trích đoạn nội dung tài liệu

Cấu trúc dữ liệu & Giải thuật (Data Structures and Algorithms) Các thuật toán nén dữ liệu (Data Compression Algorithms) Data Compression Giới thiệu Giải thuật nén RLE Giải thuật nén Huffman 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 2 Giới thiệu  Các thuật ngữ thường dùng: Data Compression Lossless Compression Lossy Compression Encoding Decoding Run / Run Length RLE, Huffman, LZW 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 3 Giới thiệu (tt) Mục đích của nén dữ liệu: Giảm kích thước dữ liệu: Khi lưu trữ Khi truyền dữ liệu Tăng tính bảo mật 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 4 Giới thiệu (tt) Có 2 hình thức nén: Nén bảo toàn thông tin (Lossless Compression): Không mất mát thông tin nguyên thuỷ Hiệu suất nén không cao: 10% - 60% Các giải thuật tiêu biểu: RLE, Arithmetic, Huffman, LZ77, LZ78,… Nén không bảo toàn thông tin (Lossy Compression): Thông tin nguyên thủy bị mất mát Hiệu suất nén cao 40% - 90% Các giải thuật tiêu biểu: JPEG, MP3, MP4,… 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 5 Giới thiệu (tt) Hiệu suất nén (%): Tỉ lệ % kích thước dữ liệu giảm được sau khi áp dụng thuật toán nén D (%) = (N – M)/N*100 D: Hiệu suất nén N: kích thước data trước khi nén M: kích thước data sau khi nén Hiệu suất nén tùy thuộc Phương pháp nén Đặc trưng của dữ liệu 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 6 Giới thiệu (tt) Nén tập tin: Dùng khi cần Backup, Restore,… dữ liệu Dùng các thuật toán nén bảo toàn thông tin Không quan tâm đến định dạng (format) của tập tin Các phần mềm: PKzip, WinZip, WinRar,… 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 7 Data Compression Giới thiệu Giải thuật nén RLE Giải thuật nén Huffman 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 8 Giải thuật nén RLE RLE = Run Length Encoding: mã hoá theo độ dài lặp lại của dữ liệu Ý tưởng Dạng 1: RLE với file *.PCX Dạng 2: RLE với file *.BMP Nhận xét 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 9 Giải thuật nén RLE (tt) Tư tưởng: Hình thức biểu diễn thông tin dư thừa đơn giản: “đường chạy” (run) – là dãy các ký tự lặp lại liên tiếp “đường chạy” được biểu diễn ngắn gọn: <Số lần lặp> <Ký tự> Khi độ dài đường chạy lớn  Tiết kiệm đáng kể Ví dụ: Data = AAAABBBBBBBBCCCCCCCCCCDEE (# 25 bytes) Datanén = 4A8B10C1D2E (# 10 bytes) 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 10 Giải thuật nén RLE (tt) Tư tưởng: (tt) Khi vận dụng thực tế, cần có biện pháp xử lý để tránh trường hợp “phản tác dụng” đối với các “run đặc biệt – 1 ký tự” X (# 1 bytes)  1X (# 2 bytes) 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 11 Giải thuật nén RLE (tt) Dạng 1: RLE với file *.PCX 1 1 0 0 1 1 0 1 0 1 0 0 0 0 0 1 Hai bit n = 6 bit thaáp d = byte döõ cao baät cho bieát soá lieäu keá tieáp “11” laàn laëp… ñöôïc laëp Trường hợp “run bình thường”: AAAAAAAAAAAAA  13 A (biểu diễn 2 bytes)  0xCD 0x41 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 12 Giải thuật nén RLE (tt) RLE trong cấu trúc file *.PCX (tt) 0 1 0 0 0 0 0 1 Hai bit cao Ñaây laø byte khoâng baät döõ lieäu (soá laàn laëp = 1) Trường hợp “run đặc biệt”: A  A (biểu diễn 1 byte)  0x41 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 13 Giải thuật nén RLE (tt) RLE trong cấu trúc file *.PCX (tt) 1 1 0 0 0 0 0 1 1 1 0 1 1 0 0 1 Hai bit n = 6 bit thaáp d = byte döõ cao baät cho bieát soá lieäu keá tieáp “11” laàn laëp (= 1) ñöôïc laëp Trường hợp “run đặc biệt”: 0xD9(217 d)  1 0xD9 (biểu diễn 2 bytes)  0xC1 0xD9 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 14 Giải thuật nén RLE (tt) RLE trong cấu trúc file *.PCX (tt) Ưu điểm: Cài đặt đơn giản Giảm các trường hợp “phản tác dụng” của những run đặc biệt Khuyết điểm: Dùng 6 bit biểu diễn số lần lặp  chỉ thể hiện được chiều dài max = 63  Các đoạn lặp dài sẽ phải lưu trữ lặp lại Không giải quyết được trường hợp “phản tác dụng” với run đặc biệt có mã ASCII >= 192d 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 15 Giải thuật nén RLE (tt) RLE trong cấu trúc file *.PCX (tt) Vì sao dùng 2 bits làm cờ hiệu, mà không dùng 1 bit ? 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 16 Giải thuật nén RLE (tt) #define MAX_RUNLENGTH 63 int PCXEncode_a_String(char *aString, int nLen, FILE *fEncode) { unsigned char cThis, cLast; int i; int nTotal = 0; // Tổng số byte sau khi mã hoá int nRunCount = 1; // Chiều dài của 1 run cLast = *(aString); for (i=0; i<nLen; i++) { cThis = *(++aString); if (cThis == cLast) { // Tồn tại 1 run nRunCount++; if (nRunCount == MAX_RUNLENGTH) { nTotal += PCXEncode_a_Run(cLast,nRunCount,fEncode); nRunCount = 0; } } Continued… 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 17 Giải thuật nén RLE (tt) else // Hết 1 run, chuyển sang run kế tiếp { if (nRunCount) nTotal += PCXEncode_a_Run(cLast,nRunCount,fEncode); cLast = cThis; nRunCount = 1; } } // end for if (nRunCount) // Ghi run cuối cùng lên file nTotal += PCXEncode_a_Run(cLast, nRunCount, fEncode); return (nTotal); } // end function 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 18 Giải thuật nén RLE (tt) int PCXEncode_a_Run(unsigned char c, int nRunCount, FILE *fEncode) { if (nRunCount) { if ((nRunCount == 1) && (c < 192)) { putc(c, fEncode); return 1; } else { putc(0xC0 | nRunCount, fEncode); putc(c, fEncode); return 2; } } 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 19 Giải thuật nén RLE (tt) int PCXDecode_a_File(FILE *fEncode, FILE *fDecode) { unsigned char c, n; while (!feof(fEncode)) { c = (unsigned char) getc(fEncode); if (c == EOF) break; if ((c & 0xC0) == 0xC0) // 2 bit cao bật { n = c & 0x3f; // Lấy 6 bit thấp  số lần lặp… c = (unsigned char) getc(fEncode); } else n = 1; // Ghi dữ liệu đã giải mã lên file fDecode for (int i=0; i<n; i++) putc(c, fDecode); } fclose(fDecode); } 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 20 Giải thuật nén RLE (tt) Dạng 2: RLE với file *.BMP Định dạng file chuẩn của Windows dùng để lưu ảnh bitmap Có khả năng lưu trữ ảnh B&W, 16 màu, 256 màu, 24bits màu Có sử dụng thuật toán nén RLE khi lưu trữ dữ liệu điểm ảnh 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 21 Giải thuật nén RLE (tt) RLE trong cấu trúc file *.BMP (tt) AAA………………………………………A lặp 255 lần Neùn PCX Dữ liệu lưu lặp lại vì số lần lặp chỉ sử dụng có 6 bits 0xFF’A’0xFF’A’ 0xFF’A’0xFF’A’ 0xC3’A’ 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 22 Giải thuật nén RLE (tt) RLE trong cấu trúc file *.BMP (tt) Ý tưởng: Dữ liệu có 2 dạng Dạng 1: Run với độ dài > 1. AAAAAAAAAAAA Dạng 2: Dãy các ký tự đơn lẻ. BCDEFG Biểu diễn: phân biệt 2 dạng bằng cách dùng “mã nhận dạng” (ESCAPE 0x00) Dạng 1: <Số lần lặp> <Ký tự lặp> VD. 0x0C ‘A’ Dạng 2: <ESCAPE> <n> <Dãy ký tự> VD.

0x00 0x06 ‘B’’C’’D’’E’’F’’G’ 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 23 Giải thuật nén RLE (tt) RLE trong cấu trúc file *.BMP (tt) AAA………………………………………ABCDEFG lặp 255 lần Neùn BMP 0xFF ‘A’ 0x00 0x06 “BCDEFG” 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 24 Giải thuật nén RLE (tt) So sánh giữa PCX RLE và BMP RLE ? 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 25 Giải thuật nén RLE (tt) int BMPDecode_a_File(FILE *fEncode, FILE *fDecode) { unsigned char cMode, cData; int i, n; while (!feof(fEncode)) { cMode = (unsigned char) getc(fEncode); if (cMode==EOF) break; if (cMode==0) { // Dạng 2 n = (unsigned char) getc(fEncode); for (i=0; i<n; i++) { cData = (unsigned char) getc(fEncode); putc(cData, fDecode); } } Continued… 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 26 Giải thuật nén RLE (tt) else // Dạng 1 { n = cMode; // Số lần lặp cData = (unsigned char) getc(fEncode); for (i=0; i<n; i++) putc(cData, fDecode); } } // end while } // end 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 27 Giải thuật nén RLE (tt) Nhận xét / Ứng dụng: Dùng để nén các dữ liệu có nhiều đoạn lặp lại (run) Thích hợp cho dữ liệu ảnh  ứng dụng hẹp Chưa phải là một thuật toán nén có hiệu suất cao Đơn giản, dễ cài đặt 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 28 Data Compression Giới thiệu Giải thuật nén RLE Giải thuật nén Huffman 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 29 Giải thuật nén Huffman Giới thiệu Huffman tĩnh (Static Huffman) Huffman động (Adaptive Huffman) 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 30 Giải thuật nén Huffman – Giới thiệu  Hình thành Vấn đề: Một giải thuật nén bảo toàn thông tin; Không phụ thuộc vào tính chất của dữ liệu; Ứng dụng rộng rãi trên bất kỳ dữ liệu nào, với hiệu suất tốt Tư tưởng chính: Phương pháp cũ: dùng 1 dãy cố định (8 bits) để biểu diễn 1 ký tự Huffman: Sử dụng vài bits để biểu diễn 1 ký tự (gọi là “mã bit” – bits code) Độ dài “mã bit” cho các ký tự không giống nhau: Ký tự xuất hiện nhiều lần  biểu diễn bằng mã ngắn; Ký tự xuất hiện ít  biểu diễn bằng mã dài  Mã hóa bằng mã có độ dài thay đổi (Variable Length Encoding) David Huffman – 1952: tìm ra phương pháp xác định mã tối ưu trên dữ liệu tĩnh 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.