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

Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 4: Nén dữ liệu" trình bày các nội dung: Các thuật ngữ nén dữ liệu, khái niệm nén dữ liệu, thuật toán nén - Tạo cây Huffman, thuật toán nén - Phát sinh mã bit, thuật toán nén - Lưu lại thông tin, thuật toán giải nén, phần giới thiệu một số thuật toán nén đơn giản. Mời các bạn cùng tham khảo nội dung chi tiết.
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 - Chương 4: Nén dữ liệuGiảng viên:Văn Chí Nam – Nguyễn Thị Hồng Nhung – Đặng Nguyễn Đức Tiến2 Giới thiệu Một số khái niệm Giải thuật nén Huffman tĩnh Cấu trúc dữ liệu và giải thuật - HCMUS 20123  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 20124  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ữ  Truyền dữ liệu Cấu trúc dữ liệu và giải thuật - HCMUS 20125  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 20126  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ữ liệu sau khi nén.  Tỷ lệ nén R: N R N1  Ví dụ:  Dữ liệu ban đầu 8KB, nén còn 2 KB. Tỷ lệ nén: 4-1 Cấu trúc dữ liệu và giải thuật - HCMUS 20127  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ữ liệu sau khi nén.  Tỷ lệ nén R: N1 R  1 N  Ví dụ:  Dữ liệu ban đầu 8KB, nén còn 2 KB. Tỷ lệ nén: 75% Cấu trúc dữ liệu và giải thuật - HCMUS 20128  Nén dữ liệu không mất mát (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 PCX, GIF, PNG,..  Tập tin *. ZIP  Ứng dụng gzip (Unix) Cấu trúc dữ liệu và giải thuật - HCMUS 20129  Nén dữ liệu có mất mát (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;  Âm thanh: AAC, MP2, MP3;  Video: MPEG-2, MPEG-4 Cấu trúc dữ liệu và giải thuật - HCMUS 201210 Cấu trúc dữ liệu và giải thuật - HCMUS 201211  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 201212  Tư tưởng chính:  Phương pháp cũ: dùng 1 dãy cố định để biểu diễn 1 byte dữ liệu.  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;  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) Cấu trúc dữ liệu và giải thuật - HCMUS 201213  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 3 bit/ký tự cần: (10 + 8 + 6 + 5 + 2) * 3 = 93 bit Cấu trúc dữ liệu và giải thuật - HCMUS 201214  Dữ liệu: ADDAABBCCBAAABBCCCBBBCDAADDEEAA  Biểu diễn bằng chiều dài thay đổi: Ký tự Tần số Mã A 10 11 ...