intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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
681
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

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
8=>2