Bài giảng "Cấu trúc dữ liệu và giải thuật: Các thuật toán nén dữ liệu" cung cấp cho người đọc các kiến thức về nén dữ liệu, giải thuật nén RLE, giải thuật nén Huffman. nội dung chi tiết. | Bài giảng Cấu trúc dữ liệu và giải thuật: Các thuật toán nén dữ liệu - Nguyễn Tri Tuấn Data Structures & Algorithms Các thuật toán nén dữ liệu (Data Compression Algorithms) Nguyễn Tri Tuấn Khoa CNTT – Email: nttuan@ Data Compression Giới thiệu Giải thuật nén RLE Giải thuật nén Huffman Winter 2015 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, 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 Winter 2015 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, 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 Winter 2015 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, 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, Winter 2015 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, 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 .