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

Bài giảng "Cấu trúc dữ liệu và giải thuật: Nén dữ liệu" trình bày về các nội dung: tổng quan nén giới thiệu, giải thuật nén Huffman tĩnh, thuật toán nén, thuật toán giải nén. Để biết rõ hơn về nội dung chi tiết, . | 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 Giải thuật nén Huffman tĩnh Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©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 2011 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 2011 ©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 2011 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 Ví N1 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 2011 ©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 Ví N 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 2011 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 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 2011 ©FIT-HCMUS 4 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 gần Ứng hoàn toàn với dữ liệu .

• Cơ sở dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Nén dữ liệu
• Giải thuật nén Huffman tĩnh
• Thuật toán nén
• Thuật toán giải nén
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• Cấu trúc dữ liệu và giải thuật
• tài liệu Cấu trúc dữ liệu và giải thuật
• giáo trình Cấu trúc dữ liệu và giải thuật
• bài tập Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu
• Ngôn ngữ diễn đạt giải thuật
• Thiết kế và phân tích giải thuật
• Giải thuật đệ quy
• Bài giảng Cấu trúc dữ liệu
• Cấu trúc dữ liệu cơ bản
• Kiểu dữ liệu trừu tượng
• Tổng quan về giải thuật
• Kiểu dữ liệu
• Các tiêu chuẩn đánh giá dữ liệu
• Cách diễn đạt giải thuật
• Phân tích giải thuật
• phân tích thiết kế
• thiết kế hướng đối tượng
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cây nhị phân tìm kiếm