Bài giảng Cấu trúc dữ liệu và giải thuật: Nén dữ liệu

Bài giảng "Cấu trúc dữ liệu và giải thuật: Nén dữ liệu" được biên soạn với các nội dung chính sau đây: Giới thiệu chung về nén dữ liệu; Thuật toán nén; Nén RLE trên PCX; Nén RLE trên BMP; Tính chất cây Huffman động;... Mời các bạn cùng tham khảo bài giảng!
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Nén dữ liệu Cấu trúc dữ liệu và giải thuật NÉN DỮ LiỆU Giảng viên: Văn Chí Nam Nội dung trình bày 2 Cấu trúc dữ liệu và giải thuật ­ HCMUS 2011 Giới thiệu 3  Thuật ngữ:  Data compression  Encoding  Decoding  Lossless data compression  Lossy data compression  … Cấu trúc dữ liệu và giải thuật ­ HCMUS 2011 Giới thiệu 4  Nén dữ liệu  Nhu cầu xuất hiện ngay sau khi hệ thống máy tính đầu tiên ra đời.  Hiện nay, phục vụ cho các dạng dữ liệu đa phương tiện  Tăng tính bảo mật.  Ứng dụng:  Lưu trữ Cấu trúc d ữ liệu và giải thuật ­ HCMUS 2011  Truyền dữ liệu Giới thiệu 5  Nguyên tắc:  Encode và decode sử dụng cùng một scheme. encode decode Cấu trúc dữ liệu và giải thuật ­ HCMUS 2011 Khái niệm 6  Tỷ lệ nén (Data compression ratio)  Tỷ lệ giữa kích thước của dữ liệu nguyên thủy và của dữ liệu sau khi áp dụng thuật toán nén.  Gọi: N là kích thước của dữ liệu nguyên thủy,  N1 là kích thước của dữNliệu sau khi nén. R  Tỷ lệ nén R: N1  Ví dụ: Cấu trúc d ữ liệu và giải thuật ­ HCMUS 2011  Dữ liệu ban đầu 8KB, nén còn 2 KB. Tỷ lệ nén: 4-1 Khái niệm 7  Tỷ lệ nén (Data compression ratio)  Về khả năng tiết kiệm không gian: Tỷ lệ của việc giảm kích thước dữ liệu sau khi áp dụng thuật toán nén.  Gọi: N là kích thước của dữ liệu nguyên thủy,  N1 là kích thước của dữ N liệu sau khi nén. R 1 1  Tỷ lệ nén R: N  Ví dụ: Cấu trúc d ữ liệu và giải thuật ­ HCMUS 2011  Dữ liệu ban đầu 8KB, nén còn 2 KB. Tỷ lệ nén: 75% Khái niệm 8  Nén dữ liệu không mất mát thông tin (Lossless  data compression)  Cho phép dữ liệu nén được phục hồi nguyên vẹn như dữ liệu nguyên thủy (lúc chưa được nén).  Ví dụ:  Run-length encoding  LZW …  Ứng dụng:  Ảnh Cấu trúc d PCX,ải thu ữ liệu và gi GIF, PNG,.. ật ­ HCMUS 2011 Khái niệm 9  Nén dữ liệu mất mát thông tin (Lossy data  compression)  Dữ liệu nén được phục hồi  không giống hoàn toàn với dữ liệu nguyên thủy;  gần đủ giống để có thể sử dụng được.  Ứng dụng:  Dùng để nén dữ liệu đa phương tiện (hình ảnh, âm thanh, video):  Ảnh: JPEG, DjVu; Cấu trúc dữ liệÂm thanh: ải thuAAC, MP2, MP3;  u và gi ật ­ HCMUS 2011 10 Nén Huffman tĩnh Cấu trúc dữ liệu và giải thuật ­ HCMUS 2011 Giới thiệu 11  Mong muố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. Cấu trúc dữ liệu và giải thuật ­ HCMUS 2011 Giới thiệu 12  Tư tưởng chính:  Phương pháp cũ: dùng 1 dãy bit cố định để biểu diễn 1 ký tự  David Huffman (1952): tìm ra phương pháp xác định mã tối ưu trên dữ liệu tĩnh :  Sử dụng vài bit để biểu diễn 1 ký tự (gọi là “mã bit” – bit 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; Cấu trúc dữ liệu và giải thuật ­ HCMUS 2011  Ký tự xuất hiện ít : biểu diễn bằng mã dài Giới thiệu 13  Giả sử có dữ liệu sau đây: ADDAABBCCBAAABBCCCBBBCDAADDEEAA Ký tự Tần số xuất hiện A 10 B 8 C 6 D 5 E 2  Biểu diễn 8 bit/ký tự cần: Cấu trúc dữ liệu và giải thuật ­ HCMUS 2011 (10 + 8 + 6 + 5 + 2) * 8 = 248 bit Giới thiệu 14  Dữ liệu: ADDAABBCCBAAABBCCCBBBCDAADDEEAA  Biểu diễn bKý tự ằng chiều dài thay đ Tần số i: ổMã A 10 11 B 8 10 C 6 00 D 5 011 E 2 010 Cấu trúc dữ liệu và giải thuật ­ HCMUS 2011 Thuật toán nén 15 [B1]: Duyệt tập tin ­> Lập bảng thống kê tần số  xuất hiện của các ký tự. [B2]: Xây dựng cây Huffman dựa vào bảng thống  kê tần số xuất hiện [B3]: Phát sinh bảng mã bit cho từng ký tự tương  ứng Cấu trúc dữ liệu và giải thuật ­ HCMUS 2011 Thuật toán nén 16 ADDAABBCCBAAABBCCCBBBCDAADDEEAA 1101101111111010000010111111101000 0000101010000111111011011010010111 1 Cấu trúc dữ liệu và giải thuật ­ HCMUS 2011 Thuật toán nén – Thống kê tần số 17  Dữ liệu: ADDAABBCCBAAABBCCCBBBCDAADDEEAA Ký tự Tần số xuất hiện ...