tailieunhanh - Bài giảng Cấu trúc dữ liệu và giải thuật: Nén dữ liệu - Văn Chí Nam, Nguyễn Thị Hồng Nhung, Đặng Nguyễn Đức Tiến

Bài giảng "Cấu trúc dữ liệu và giải thuật: Nén dữ liệu" cung cấp cho người học các kiến thức cơ bản về nén dữ liệu, một số khái niệm, nén Huffman tĩnh, nén Run-Length Encoding, nén LZW. nội dung chi tiết. | Bài giảng Cấu trúc dữ liệu và giải thuật: Nén dữ liệu - Văn Chí Nam, Nguyễn Thị Hồng Nhung, Đặng Nguyễn Đức Tiến Giảng viên: Văn Chí Nam – Nguyễn Thị Hồng Nhung – Đặng Nguyễn Đức Tiến 2 Giới thiệu Một số khái niệm Nén Huffman tĩnh Nén Run-Length Encoding Nén LZW Cấu trúc dữ liệu và giải thuật - HCMUS 2015 ©FIT-HCMUS 1 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 2015 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ữ Truyền dữ liệu Cấu trúc dữ liệu và giải thuật - HCMUS 2015 ©FIT-HCMUS 2 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 2015 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ữ 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 2015 ©FIT-HCMUS 3 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ữ 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 2015 8 Nén dữ liệu không mất mát (Lossless data compression) Cho phép dữ liệu