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.
Nội dung trích xuất từ tài liệu:
Giải thuật nén Huffman Data Compression Gi i thi u Giải thuật nén RLE Giải thuật nén HuffmanWinter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 29 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, DH.KHTN Tp.HCM 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: S d ng vài bits đ bi u di n 1 ký t (g i là “mã bit” – bits code) Đ 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ĩnhWinter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 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 2Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 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 010Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 33 Static Huffman 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énWinter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 34 17 Static Huffman (tt) Thu t toán nén: [b1] Duy t file L p b ng th ng kê s l n xu t hi n c a m i lo i k ý t [b2] Phát sinh cây Huffman d a vào b ng th ng kê [b3] T cây Huffman phát sinh b ng mã bit cho các ký t Thay th các ký t b ng mã bit tương ng [b4] Duy t file [b5] Lưu l i thông tin c a cây Huffman dùng đ gi i nénWinter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 35 Static Huffman (tt) Ký S l n xu t [b1] f = “ADDAABBCCBAAABBCCCBBBCDAADDEEAA” t hi n A 10 B 8 C ...