Bài giảng Nén Huffman tĩnh

Nội dung text: Bài giảng Nén Huffman tĩnh

1. Thuật tốn nén Huffman tĩnh
2. Nội dung: • Giới thiệu • Thuật toán giải nén: • Dẫn nhập – Các bước thực hiện – VD – VD • Thuật toán nén: • Đánh giá cây – Ý tưởng Huffman – Cây Huffman • Hạn chế của Huffman – Phát sinh bảng mã tĩnh bit • Mã bit dài??? – Nén – Cấu trúc file nén
3. Giới thiệu: • ASCII ( 256 ký tự 8 bit ) • rút ngắn số bit cho 1 ký tự ??? • Dùng tư tưởng của giải thuật nén huffman. vSử dụng 1 vài bit (mã/code) để biểu diễn 1 ký tự vKý tự xuất hiện nhiều: biểu diễn bằng mã ngắn vKý tự xuất hiện ít: biểu diễn bằng mã dài ÞTiết kiệm dược số bit lưu trữ • Sử dụng bảng thống kê số lần xuất hiện các kí tự.
4. Dẫn nhập: • Việc mã hóa các kí tự bằng những chuỗi bit có độ dài khác nhau khó khăn • Có thể dùng dấu phẩy “,” chiếm thêm 1 không gian đáng kể để lưu trữ • bộ các từ mã tập hợp các kí hiệu phải thoả điều kiện: từ mã của mỗi ký tự khơng là tiền tố (phần đầu) của từ mã một ký tự khác trong bộ mã ấy(mã tiền tố).
5. Ví dụ: • Ví dụ, muốn mã hĩa từ "PETE", với 3 ký tự “E”, “P”, “T”. Ta cĩ: - Nếu mã hĩa bằng các từ mã cĩ độ dài bằng nhau, ta dùng ít nhất 2 bit cho một ký tự. Chẳng hạn “E”=00, “P”=01, “T”=10. Khi đĩ mã hĩa của cả từ là 01001000. - Nếu mã hĩa “E”=0, “P”=01, “T”=11 thì bộ từ mã này khơng là mã tiền tố. Vì từ mã của “E” là tiền tố của từ mã của “P”. - Nếu mã hĩa “E”=0, “P”=10, “T”=11 thì bộ mã này là mã tiền tố. Khi đĩ, để mã hĩa xâu “PETE” ta cĩ 100110. người ta dùng biểu đồ cây (thường gọi là cây Huffman)
6. Thuật toán nén : Tư tưởng chính v [b1] Duyệt file  Lập bảng thống kê số lần xuất hiện của mỗi ký tự v [b2] Phát sinh cây Huffman dựa vào bảng thống kê số lần xuất hiện v [b3] Cây Huffman  Phát sinh bảng mã bit ứng với từng ký tự v [b4] Duyệt file  Thay thế các ký tự bằng mã bit tương ứng v [b5] Lưu lại thông tin của cây Huffman (dùng để giải nén)
7. Thuật toán nén -minh họa ý tưởng: B1 Ký Số lần xuất f = “ADDAABBCCBAAABBCCCBBBCDAADDEEAA” tự hiện A 10 B 8 C 6 B2 D 5 E 2 Ký tự Mã A 11 B3 B 10 C 00 B4 D 011 E 010 fnén =110110111111101000001011111110100000001010100001111110110110100101111
8. Thuật toán nén - cây Huffman: • Nút Huffman : • Cây Huffman : • Ký tự • Trọng số • Cây con trái • Cây con phải • Nút lá chứa 1 ký tự • Nút không phải nút lá chứa tất cả ký tự các nút lá bên dưới • Trọng số : •Nút lá có trọng số bằng số lần xuất hiện của ký tự tương ứng trong file •Nút không phải là lá có trọng số bằng tổng của tất cả các nút là bên dưới
9. Thuật toán nén - cây Huffman: – Cấu trúc dữ liệu để mô tả cây: #define MAX_NODES 511 typedef struct HuffNode { char c; //ký tự long lFreq; //trọng số int iLeft; //cây con trái int iRight; //cây con phải } HuffNode; HuffNode HuffTree[MAX_NODES]; int iStart = 0; // trỏ vào phần tử đầu tiên của cây int iEnd = 0; // trỏ vào phần tử null sau phần tử cuối của mảng ( phần tử cuối của mảng là gốc )
10. Thuật toán nén - cây Huffman: • Phát sinh cây Huffman – Thuật toán phát sinh cây: v[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 1 nút mới z: v[b2] Loại bỏ nút x và y khỏi bảng; thêm nút z vào bảng v[b3] Lặp lại bước [b1] và [b2] cho đến khi trong bảng chỉ còn 1 nút duy nhất
11. Thuật toán nén - cây Huffman: ví dụ minh họa Ký tự SLXH Ký tự SLXH A 10 A 10 B 8 B 8 C 6 ED 7 D 5 C 6 E 2 Ký tự SLXH Ký tự SLXH CED 13 A 10 BA 18 B 8 CED 13
12. Thuật toán nén - cây Huffman: ví dụ minh họa
13. Code: void CreateTree() { while ( iEnd > iStart + 1 ) //cây còn nút { sort( iStart, iEnd ); //sắp xếp các nút theo thứ tự tăng dần theo trọng số từ iStart -> iEnd //các nút trước đó đã có cha rời ( đã loại ra khỏi bảng ) HuffTree[iEnd].iLeft = iStart; //nút con trái của nút cha HuffTree[iEnd].iRight = iStart + 1; //nút con phải của nút cha HuffTree[iEnd].lFreq = HuffTree[iStart].lFreq + HuffTree[iStart + 1].lFreq; //trọng sớ của nút cha bằng tởng trọng sớ của 2 nút con iEnd++; iStart += 2; } }
14. Thuật toán nén – phát sinh bảng mã bit • Duyệt cây mã bit của 1 ký tự • Duyệt sang trái 0, duyệt sang phải 1 0 1 Ký tự Mã A 11 B 10 C 00 D 011 E 010
15. Thuật toán nén – Phát sinh bảng mã bit - Cấu trúc bảng mã: typedef struct Ele { char c; // ký tự int code; // mã của ký tự int length; // đợ dài của code }Ele; Ele HuffTable[256]; // bảng mã ký tự và mã bit tương ứng int iN = 0; sớ phần tử của bảng mã
16. Thuật toán nén – Phát sinh bảng mã bit - Code: void CreateTable( int pos, int code, int length ) // pos: vị trí nút hiện tại, code: mã bit đạt được tới thời điểm hiện tại, length: chiều dài của mã bit hiện tại { if ( HuffTree[pos].iLeft == -1 && HuffTree[pos].iRight == -1 ) // tới nút lá { HuffTable[iN].c = HuffTree[pos].c; HuffTable[iN].code = code; HuffTable[iN].length = length; iN++; } else { CreateTable( HuffTree[pos].iLeft, code << 1, length + 1 ); CreateTable( HuffTree[pos].iRight, ( code << 1 ) | 1, length + 1 ); } }
17. Thuật toán nén - nén: v [b1] Đọc từng ký tự trong tập tin cần nén vào v [b2] Tìm trong bảng mã bit mã bit tương ứng ký tự đó v [b3] Ghi ra file nén đoạn mã bit đó v [b4] Nếu file còn ký tự thì quay lại bước 1, nếu khơng thì kết thúc thuật toán
18. Cấu trúc file nén: • Lưu bảng thống kê số ký tự: – Byte đầu lưu số N ký tự – N phần tử kế tiếp lưu loại ký tự và số lần xuất hiện – 4 byte kế lưu số ký tự đã được nén – Phần cịn lại lưu mã bit của các ký tự của file được nén • Lưu bảng mã bit: – Byte đầu lưu số N ký tự – N phần tử kế tiếp lưu loại ký tự, mã bit và chiều dài mã bit – 4 byte kế lưu số ký tự đã được nén – Phần cịn lại lưu mã bit của các ký tự của file được nén
19. Thuật toán giải nén – các bước thực hiện v [b1] Xây dựng lại cây Huffman (từ thông tin được lưu) v [b2] Bắt đầu từ nút gốc v [b3] Đọc 1 bit b từ file nén fn v [b4] Nếu (b==0) thì qua nút trái ngược lại qua nút phải v [b5] Nếu tới nút lá thì: - Xuất ký tự tại nút lá ra file - Nếu đã đọc hết file thì kết thúc thuật tốn - Quay lại bước [b2] ngược lại không phải là nút lá - Quay lại bước [b3]
20. Thuật toán giải nén – Ví dụ: • Cho bảng mã huffman như sau: Ký tự Mã A 111 • Cho đoạn mã 1111001. Ta có sơ đồ giải mã như sau: C 10 E 01 H 110 I 00
21. Thuật toán giải nén – Ví dụ: • Phát sinh cây huffman từ bảng mã: root 0 1 Ký tự Mã 1 1 A 111 0 0 C 10 I E C E 01 0 1 H 110 H A I 00
22. Thuật toán giải nén – Ví dụ: • Tiến hành các bước giải mã dựa vào cây huffman đã có root 1111001 0 1 1 1 0 0 I E C 0 1 H A
23. Thuật toán giải nén – Ví dụ: root 1111001 0 1 1 1 0 0 I E C 0 1 H A
24. Thuật toán giải nén – Ví dụ: 1111001 root => 0 1 1 1 0 0 A I E C 0 1 H A
25. Thuật toán giải nén – Ví dụ: 1111001 root => 0 1 1 1 0 0 A I E C 0 1 H A
26. Thuật toán giải nén – Ví dụ: 1111001 root => 0 1 1 1 0 0 AC I E C 0 1 H A
27. Thuật toán giải nén – Ví dụ: 1111001 root => 0 1 1 1 0 0 AC I E C 0 1 H A
28. Thuật toán giải nén – Ví dụ: 1111001 root => 0 1 1 1 0 0 ACE I E C 0 1 H A
29. Đánh giá cây Huffman • Đánh giá cây Huffman: v 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 có mã bit dài; và ngược lại, các nút có tần số cao nằm gần gốc có mã bit ngắn – Độ dài dữ liệu được mã hoá =  dx*x.Frequency x.Frequency : trọng số của nút lá thuộc cây Huffman dx : độ dài đường đi (tính từ gốc) đến nút x ( độ dài mã bit ) – Nếu có n loại ký tự trong file thì: • số nút của cây Huffman là (2n-1) • số mức tối thiểu là log2(2n-1+1) = log2(2n) • số mức tối đa là (2n-1+1)/2 = n – Số mức trong cây Huffman xác định chiều dài tối đa của mã bit cần thiết để biểu diễn cho 1 ký tự – Cây Huffman là cách thức tối ưu nhất để xác định mã bit
30. Hạn chế của huffman tĩnh: • [Nén] Cần 2 lần duyệt file  Chi phí cao • Cần lưu trữ thông tin giải nén (bảng mã bit/bảng thống kê tần suất của các ký tự)  Tăng kích thước dữ liệu nén • Không thể nén “on-line” • => giải quyết bằng cách dùng thuật toán nén huffman động (sẽ đươc nhóm sau trình bày)
31. Mã bit dài??? § Độ dài tối đa một mã ký tự ? § Sau khi nén Huffman, 1 ký tự > 8 bit N ký tự khác nhau N bậc của cây Bậc 1 ABCD Độ dài mã bit lớn nhất là N- 1 bit ( ký tự a, b) 255 bit (256 ký tự khác Bậc 2 ABC D nhau) 32byte để lưu 1 ký tự Bậc 3 AB C Bậc 4 A B
32. Mã bit dài??? • Trọng số các nút ??? Nhận xét : ABCD A(1) ABCD BậcBậc 1 1 (7) B(1) C(2) D(3) ABC D BậcBậc 2 2 ABC D (4) (3) Dãy Fibonanci BậcBậc 3 3 AB C AB C (2) (2) A B BậcBậc 4 4 A B (1) (1)
33. Mã bit dài??? = • Giả sử Maxbit code 32 bits 33 ký tự khác nhau Ký tự 1 - (1) Ký tự 2 - (1) Ký tự 3 - (2) Ký tự 4 - (3) . Ký tự 34 – (5702287) Min kích thước = 14,930,351 byte ≈ 14MB !!!
34. Giải đáp thắc mắc ???
35. CẢM ƠN CÁC BẠN ĐÃ CHÚ Ý LẮNG NGHE