Giải thuật nén Huffman

Chia sẻ: Nguyễn Tấn Hưng | Ngày: | Loại File: PDF | Số trang:9

Thêm vào BST

Báo xấu

683
lượt xem 363
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 Huffman Winter 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ĩnh Winter 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 2 Winter 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 010 Winter 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én Winter 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én Winter 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 6 [b2] D 5 E 2 Ký Mã bit t [b3] A 11 B 10 [b4] C 00 D 011 E 010 fnén = 11011011111110100000101111111010000000 1010100001111110110110100101111 Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 36 18
Static Huffman (tt) T o cây Huffman: Mô t cây Huffman: mã Huffman đư c bi u di n b ng 1 cây nh phân M i nút lá ch a 1 k ý t Nút cha s ch a các ký t c a nh ng nút con M i nút đư c gán m t tr ng s: Nút lá có tr ng s b ng s l n xu t hi n c a ký t trong file Nút cha có tr ng s b ng t ng tr ng s c a các nút con Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 37 Static Huffman (tt) T o cây Huffman: (tt) Tính ch t cây Huffman: Nhánh trái tương ng v i mã hoá bit ‘0’; nhánh ph i tương ng v i mã hoá bit ‘1’ Các nút có t n s th p n m xa g c mã bit dài Các nút có t n s cao n m g n g c mã bit ng n S nút c a cây: (2n-1) Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 38 19
Static Huffman (tt) // C u trúc d li u lưu tr cây Huffman #define MAX_NODES 511 // 2*256 - 1 typedef struct { char c; // ký t long nFreq; // tr ng s int nLeft; // cây con trái int nRight; // cây con ph i } HUFFNode; HUFFNode HuffTree[MAX_NODES]; Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 39 Static Huffman (tt) T o cây Huffman: (tt) Thu t toán phát sinh cây: [b1] Ch n trong b ng th ng kê 2 ph n t x,y có tr ng s th p nh t t o thành nút cha z: z.c = min(x.c + y.c); z.nFreq = x.nFreq + y.nFreq; z.nLeft = x (*) z.nRight = y (*) [b2] Lo i b nút x và y kh i b ng; [b3] Thêm nút z vào b ng; [b4] L p l i bư c [b1] - [b3] cho đ n khi ch còn l i 1 nút duy nh t trong b ng (*) Qui ư c: - nút có tr ng s nh n m bên nhánh trái; nút có tr ng s l n n m bên nhánh ph i; - n u tr ng s b ng nhau, nút có ký t nh n m bên nhánh trái; nút có ký t l n n m bên nhánh ph i - n u có các node có tr ng s b ng nhau ưu tiên x lý các node có ký t ASCII nh trư c Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 40 20
Static Huffman (tt) Ký SLXH t Ký SLXH t A 10 A 10 B 8 B 8 C 6 ED 7 D 5 C 6 E 2 Ký SLXH t Ký SLXH CED 13 t A 10 BA 18 B 8 CED 13 Minh h a quá trình t o cây Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 41 Static Huffman (tt) Cây Huffman sau khi t o Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 42 21
Static Huffman (tt) Phát sinh mã bit cho các ký t : Mã c a m i ký t đư c t o b ng cách duy t t nút g c đ n nút lá ch a k ý t đó; Khi duy t sang trái, t o ra 1 bit 0; Khi duy t sang ph i, t o ra 1 bit 1; Ký Mã t A 11 B 10 C 00 D 011 E 010 Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 43 Static Huffman (tt) Lưu tr thông tin dùng đ gi i nén: P.Pháp 2: lưu s l n xu t hi n P.Pháp 1: lưu b ng mã bit Ký Mã Ký S l n xu t t t hi n A 11 A 10 B 8 B 10 C 6 C 00 D 5 D 011 E 2 E 010 Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 44 22
Static Huffman (tt) Thu t toán gi i nén: [b1] Xây d ng l i cây Huffman (t thông tin đư c lưu) [b2] Kh i t o nút hi n hành pCurr = pRoot [b3] Đ c 1 bit b t file nén fn [b4] N u (b==0) thì pCurr = pCurr.nLeft ngư c l i pCurr = pCurr.nRight [b5] N u pCurr là nút lá thì: - Xu t ký t t i pCurr ra file - Quay l i bư c [b2] ngư c l i - Quay l i bư c [b3] [b6] Thu t toán s d ng khi h t file fn Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 45 Static Huffman (tt) Cây Huffman và qui trình gi i nén cho chu i đư c mã hoá “1000110” Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 46 23