tailieunhanh - Giải thuật nén Huffman

Trong khoa học máy tính và lý thuyết thông tin, mã hóa Huffman là một thuật toán mã hóa dùng để nén dữ liệu. Nó dựa trên bảng tần suất xuất hiện các kí tự cần mã hóa để xây dựng một bộ mã nhị phân cho các kí tự đó sao cho dung lượng (số bít) sau khi mã hóa là nhỏ nhất. | Data Compression Giới thiệu Giải thuật nén RLE Giải thuật nén Huffman Winter 2006 Data Structure Algorithm - Data Compression - Nguyen Tri Tuan Giải thuật nén Huffman Giới thiệu Huffman tĩnh Static Huffman Huffman động Adaptive Huffman Winter 2006 Data Structure Algorithm - Data Compression - Nguyen Tri Tuan 30 15 Giải thuật nén Huffman - Giới thiệu Hình thành Vấ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 Tư tưởng chính Phương pháp cũ dùng 1 dãy cố định 8 bits để biểu diễn 1 ký tự Huffman 2 Sử dụng vài bits để biểu diễn 1 ký tự gọi là mã bit - bits code n Độ 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 David Huffman - 1952 tìm ra phương pháp xác định mã tối ưu trên dữ liệu tĩnh Winter 2006 Data Structure Algorithm - Data Compression - Nguyen Tri Tuan 31 Giải thuật nén Huffman - Giới thiệu tt Giả sử có dữ liệu như sau f ADDAABBCCBAAABBCCCBBBCDAADDEEAA Biểu diễn bình thường 8 bits ký tự Sizeof f 10 8 8 8 6 8 5 8 2 8 248 bits Ký tự Số lần xuất hiện trong file f A 10 B 8 C 6 D 5 E 2 Winter 2006 Data Structure Algorithm - Data Compression - Nguyen Tri Tuan 32 16 Giải thuật nén Huffman - Giới thiệu tt Biểu diễn bằng mã có độ dài thay đổi theo bảng Sizeof f 10 2 8 2 6 2 5 3 2 3 69 bits Ký tự Mã A 11 B 10 C 00 D 011 E 010 Winter 2006 Data Structure Algorithm - Data Compression - Nguyen Tri Tuan 33 Thuật toán nén Tạo cây Huffman Phát sinh bảng mã bit Lưu trữ thông tin dùng để giải nén Thuật toán giải nén Winter 2006 Data Structure Algorithm - Data Compression - Nguyen Tri Tuan 34 .