Các thuật toán nén dữ liệu (Data Compression Algorithms) Cấu trúc dữ liệu & Giải thuật (Data Structures and Algorithms) 09/2013 Data Structures & Algorithms Data Compression Nguyen Tri Tuan, DH KHTN T[.]
Cấu trúc liệu & Giải thuật (Data Structures and Algorithms) Các thuật toán nén 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 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 Giới thiệu (tt) Mục đích nén liệu: Giảm kích thước liệu: Khi lưu trữ Khi truyền liệu Tăng tính bảo mật 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM Giới thiệu (tt) Có hình thức nén: Nén bảo tồn thơng tin (Lossless Compression): Không 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 tồn thơng tin (Lossy Compression): Thơng tin ngun thủy bị 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 Giới thiệu (tt) Hiệu suất nén (%): Tỉ lệ % kích thước liệu giảm sau á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 nén M: kích thước data sau nén Hiệu suất nén tùy thuộc Phương pháp nén Đặc trưng liệu 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM Giới thiệu (tt) Nén tập tin: Dùng cần Backup, Restore,… liệu Dùng thuật tốn nén bảo tồn thông tin Không quan tâm đến định dạng (format) 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 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 Giải thuật nén RLE RLE = Run Length Encoding: mã hoá theo độ dài lặp lại 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 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) – dãy ký tự lặp lại liên tiếp “đường chạy” biểu diễn ngắn gọn: 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 ... thước liệu giảm sau á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 nén M: kích thước data sau nén Hiệu suất nén tùy thuộc Phương pháp nén Đặc trưng liệu. .. thức nén: Nén bảo tồn thơng tin (Lossless Compression): Không 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. .. 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 Giới thiệu Các thuật ngữ thường dùng: Data