›
›

Bài giảng Cấu trúc dữ liệu và giải thuật: Nén dữ liệu (Data Compression) - Nguyễn Tri Tuấn

pdf 40 trang phuongnguyen 6830
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và giải thuật: Nén dữ liệu (Data Compression) - Nguyễn Tri Tuấn", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_cau_truc_du_lieu_va_giai_thuat_nen_du_lieu_data_co.pdf

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật: Nén dữ liệu (Data Compression) - Nguyễn Tri Tuấn

  1. Data Structure & Algorithm Nén dữ liệu (Data Compression) Nguyễn Tri Tuấn Khoa CNTT – ĐH.KHTN.Tp.HCM Email: nttuan@ fit.hcmuns.edu.vn Data Compression Giới thiệu Giải thuật nén RLE Giải thuật nén Huffman Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM2 1
  2. Giới thiệu ª Các thuật ngữ thường dùng: Data Compression Lossless Compression Lossy Compression Encoding Decoding Run / Run Length RLE, Arithmetic, Huffman, LZ77, LZ78 Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM3 Giới thiệu (tt) ªMục đích của nén dữ liệu: Giảm kích thước dữ liệu: Khi lưu trữ Khi truyền dữ liệu Tăng tính bảo mật Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM4 2
  3. Giới thiệu (tt) ªCĩ2 hình thức nén: Nén bảo tồn thơng tin (Lossless Compression): Khơng mất mát thơng tin nguyên thuỷ Hiệu suất nén khơng cao: 10% -60% Các giải thuật tiêu biểu: RLE, Arithmetic, Huffman, LZ77, LZ78, Nén khơng bảo tồn thơng tin (Lossy Compression): Thơng tin nguyên thủy bị mất mát Hiệu suất nén cao 40% -90% Các giải thuật tiêu biểu: JPEG, MP3, MP4, Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM5 Giới thiệu (tt) ªHiệu suất nén (%): Tỉ lệ % kích thước dữ liệu giảm được sau khi áp dụng thuật tốn nén D (%) = (N –M)/N*100 D: Hiệu suất nén N: kích thước data trước khi nén M: kích thước data sau khi nén ªHiệu suất nén tùy thuộc Phương pháp nén Đặc trưng của dữ liệu Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM6 3
  4. Giới thiệu (tt) ªNén tập tin: Dùng khi cần Backup, Restore, dữliệu Dùng các thuật tốn nén bảo tồn thơng tin Khơng quan tâm đến định dạng (format) của tập tin Các phần mềm: PKzip, WinZip, WinRar, Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM7 Data Compression Giới thiệu Giải thuật nén RLE Giải thuật nén Huffman Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM8 4
  5. Giải thuật nén RLE ªRLE = Run Length Encoding: mã hố theo độ dài lặp lại của dữ liệu ªTư tưởng ªRLE trong cấu trúc file *.PCX ªRLE trong cấu trúc file *.BMP ªNhận xét Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM9 Giải thuật nén RLE (tt) ªTư tưởng: Hình thức biểu diễn thơng tin dư thừa đơn giản: “đường chạy”(run) –làdãy các ký tự lặp lại liên tiếp “đường chạy” được biểu diễn ngắn gọn: Khi độ dài đường chạy lớn à Tiết kiệm đáng kể Vídụ: Data = AAAABBBBBBBBCCCCCCCCCCDEE (# 25 bytes) Datanén = 4A8B10C1D2E (# 10 bytes) Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM10 5
  6. Giải thuật nén RLE (tt) ªTư tưởng: (tt) Khi vận dụng thực tế, cần cĩbiện pháp xử lý để tránh trường hợp “phản tác dụng” đối với các “run đặc biệt –1 ký tự” X (# 1 bytes) à 1X (# 2 bytes) Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM11 Giải thuật nén RLE (tt) ªRLE trong cấu trúc file *.PCX 11001101010 0 0 001 Haibit n = 6 bit thấp d = byte dữ caobật chobiếtsốlần liệukếtiếp “11” lặp đượclặp Trường hợp “run bình thường”: AAAAAAAAAAAAA à 13 A (biểu diễn 2 bytes) à 0xCD 0x41 Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM12 6
  7. Giải thuật nén RLE (tt) ªRLE trong cấu trúc file *.PCX (tt) 0 1 0 0 0 0 0 1 Haibit cao Đâylàbyte dữ khôngbật liệu(sốlầnlặp = 1) Trường hợp “run đặc biệt”: A à A (biểu diễn 1 byte) à 0x41 Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM13 Giải thuật nén RLE (tt) ªRLE trong cấu trúc file *.PCX (tt) 11000001110 1 1 001 Haibit n = 6 bit thấp d = byte dữ caobật chobiếtsốlần liệukếtiếp “11” lặp (= 1) đượclặp Trường hợp “run đặc biệt”: 0xD9(217 d) à 1 0xD9 (biểu diễn 2 bytes) à 0xC1 0xD9 Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM14 7
  8. Giải thuật nén RLE (tt) ªRLE trong cấu trúc file *.PCX (tt) Ưu điểm: Cài đặt đơn giản Giảm các trường hợp “phản tác dụng”của những run đặc biệt Khuyết điểm: Dùng 6 bit biểu diễn số lần lặp à chỉ thể hiện được chiều dài max = 63 à Các đoạn lặp dài sẽ phải lưu trữ lặp lại Khơng giải quyết được trường hợp “phản tác dụng” với run đặc biệt cĩmã ASCII >= 192d Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM15 Giải thuật nén RLE (tt) ªRLE trong cấu trúc file *.PCX (tt) Vìsao dùng 2 bits làm cờ hiệu, màkhơng dùng 1 bit ? Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM16 8
  9. Giải thuật nén RLE (tt) #define MAX_RUNLENGTH63 int PCXEncode_a_String(char *aString, int nLen, FILE *fEncode) { unsigned char cThis, cLast; int i; int nTotal = 0;// Tổng số byte sau khi mã hố int nRunCount = 1; // Chiều dài của 1 run cLast = *(aString); for (i=0; i<nLen; i++) { cThis = *(++aString); if (cThis == cLast) {// Tồn tại 1 run nRunCount++; if (nRunCount == MAX_RUNLENGTH) { nTotal += PCXEncode_a_Run(cLast,nRunCount,fEncode); nRunCount = 0; } } Continued Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM17 Giải thuật nén RLE (tt) else// Hết 1 run, chuyển sang run kế tiếp { if (nRunCount) nTotal += PCXEncode_a_Run(cLast,nRunCount,fEncode); cLast = cThis; nRunCount = 1; } } // end for if (nRunCount) // Ghi run cuối cùng lên file nTotal += PCXEncode_a_Run(cLast, nRunCount, fEncode); return (nTotal); }// end function Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM18 9
  10. Giải thuật nén RLE (tt) int PCXEncode_a_Run(unsigned char c, int nRunCount, FILE *fEncode) { if (nRunCount) { if ((nRunCount == 1) && (c < 192)) { putc(c, fEncode); return 1; } else { putc(0xC0 | nRunCount, fEncode); putc(c, fEncode); return 2; } } Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM19 Giải thuật nén RLE (tt) int PCXDecode_a_File(FILE *fEncode, FILE *fDecode) { unsigned char c, n; while (!feof(fEncode)) { c = (unsigned char) getc(fEncode); if (c == EOF) break; if ((c & 0xC0) == 0xC0)// 2 bit cao bật { n = c & 0x3f;// Lấy 6 bit thấp à số lần lặp c = (unsigned char) getc(fEncode); } else n = 1; // Ghi dữ liệu đã giải mã lên file fDecode for (int i=0; i<n; i++)putc(c, fDecode); } fclose(fDecode); } Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM20 10
  11. Giải thuật nén RLE (tt) ªRLE trong cấu trúc file *.BMP File *.BMP Định dạng file chuẩn của Windows dùng để lưu ảnh bitmap Cĩkhả năng lưu trữảnh B&W, 16 màu, 256 màu, 24bits màu Cĩsửdụng thuật tốn nén RLE khi lưu trữ dữ liệu điểm ảnh Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM21 Giải thuật nén RLE (tt) ªRLE trong cấu trúc file *.BMP (tt) AAA A lặp 255 lần N e ù n P C X Dữ liệu lưu lặp lại vì số lần lặp chỉ sử dụng cĩ6 bits 0xFF’A’0xFF’A’ 0xFF’A’0xFF’A’ 0xC3’A’ Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM22 11
  12. Giải thuật nén RLE (tt) ªRLE trong cấu trúc file *.BMP (tt) Ý tưởng: Dữ liệu cĩ2 dạng Dạng 1: Run với độ dài > 1. VD. AAAAAAAAAAAA Dạng 2: Dãy các ký tự đơn lẻ. VD. BCDEFG Biểu diễn: phân biệt 2 dạng bằng cách dùng “mã nhận dạng” (ESCAPE 0x00) Dạng 1: VD. 0x0C ‘A’ Dạng 2: VD. 0x00 0x06 ‘B’’C’’D’’E’’F’’G’ Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM23 Giải thuật nén RLE (tt) ªRLE trong cấu trúc file *.BMP (tt) AAA ABCDEFG lặp 255 lần N e ù n B M P 0xFF ‘A’0x00 0x06 “BCDEFG” Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM24 12
  13. Giải thuật nén RLE (tt) So sánh giữa PCX RLE vàBMP RLE ? Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM25 Giải thuật nén RLE (tt) int BMPDecode_a_File(FILE *fEncode, FILE *fDecode) { unsigned char cMode, cData; int i, n; while (!feof(fEncode)) { cMode = (unsigned char) getc(fEncode); if (cMode==EOF) break; if (cMode==0) {// Dạng 2 n = (unsigned char) getc(fEncode); for (i=0; i<n; i++) { cData = (unsigned char) getc(fEncode); putc(cData, fDecode); } } Continued Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM26 13
  14. Giải thuật nén RLE (tt) else// Dạng 1 { n = cMode;// Số lần lặp cData = (unsigned char) getc(fEncode); for (i=0; i<n; i++) putc(cData, fDecode); } }// end while }// end Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM27 Giải thuật nén RLE (tt) ªNhận xét / Ứng dụng: Dùng để nén các dữ liệu cĩnhiều đoạn lặp lại (run) Thích hợp cho dữ liệu ảnh à ứng dụng hẹp Chưa phải làmột thuật tốn nén cĩhiệu suất cao Đơn giản, dễ cài đặt Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM28 14
  15. Data Compression Giới thiệu Giải thuật nén RLE Giải thuật nén Huffman Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM29 Giải thuật nén Huffman ªGiới thiệu ªHuffman tĩnh (Static Huffman) ªHuffman động (Adaptive Huffman) Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM30 15
  16. 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 tồ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 Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM31 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 Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM32 16
  17. 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 Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM33 Static Huffman ªThuật tố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 tốn giải nén Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM34 17
  18. Static Huffman (tt) ª Thuật tố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ự [b4] Duyệt file à Thay thế các ký tự bằng mã bit tương ứng [b5] Lưu lại thơng tin của cây Huffman dùng để giải nén Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM35 Static Huffman (tt) [b1] Ký Số lần xuất 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 Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM36 18
  19. 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 Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM37 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ã hốbit ‘0’; nhánh phải tương ứng với mã hố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) Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM38 19
  20. 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 intnRight;// cây con phải } HUFFNode; HUFFNode HuffTree[MAX_NODES]; Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM39 Static Huffman (tt) ª Tạo cây Huffman: (tt) Thuật tố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 Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM40 20
  21. Static Huffman (tt) Ký SLXH tự Ký SLXH A 10 tự B 8 A 10 C 6 B 8 D 5 ED 7 E 2 C 6 Ký SLXH tự Ký SLXH tự CED 13 BA 18 A 10 CED 13 B 8 Minh họa quátrình tạo cây Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM41 Static Huffman (tt) Cây Huffman sau khi tạo Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM42 21
  22. 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 Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM43 Static Huffman (tt) ªLưu trữ thơng tin dùng để giải nén: P.Pháp1: lưu bảng mã bit P.Pháp2: lưu số lần xuất hiện Ký Mã Ký Số lần xuất tự tự hiện A 11 A 10 B 10 B 8 C 00 C 6 D 011 D 5 E 010 E 2 Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM44 22
  23. Static Huffman (tt) ª Thuật tố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 tốn sẽ dừng khi hết file fn Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM45 Static Huffman (tt) Cây Huffman vàqui trình giải nén cho chuỗi được mã hố“1000110” Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM46 23
  24. Adaptive Huffman ªGiới thiệu ªThuật tốn tổng quát ªCây Huffman động ªThuật tốn nén (Encoding) ªThuật tốn giải nén (Decoding) Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM47 Adaptive Huffman (tt) ªGiới thiệu: Hạn chế của Huffman tĩnh: Cần 2 lần duyệt file (quátrình nén) à chi phícao Cần phải lưu trữ thơng tin để giải nén à tăng kích thước dữ liệu nén Dữ liệu cần nén phải cĩsẵn à khơng nén được trên dữ liệu phát sinh theo thời gian thực Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM48 24
  25. Adaptive Huffman (tt) ªGiới thiệu: (tt) Lịch sử hình thành: Được đề xuất bởi Faller (1973) và Gallager (1978) Knuth (1985) đưa ra một số cải tiến vàhồn chỉnh thuật tốn à thuật tốn cịn cĩtên “thuật tốn FGK” Vitter (1987): trình bày các cải tiến liên quan đến việc tối ưu cây Huffman Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM49 Adaptive Huffman (tt) ªGiới thiệu: (tt) Ưu điểm: Khơng cần tính trước số lần xuất hiện của các ký tự Quátrình nén: chỉ cần 1 lần duyệt file Khơng cần lưu thơng tin phục vụ cho việc giải nén Nén “on-line”: trên dữ liệu phát sinh theo thời gian thực Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM50 25
  26. Adaptive Huffman (tt) ªThuật tốn tổng quát: Huffman tĩnh: cây Huffman được tạo thành từ bảng thống kê số lần xuất hiện của các ký tự Huffman động: Nén “on-line” à khơng cĩ trước bảng thống kê Tạo cây như thế nào ? Phương pháp: khởi tạo cây “tối thiểu” ban đầu; cây sẽ được “cập nhật dần dần”(~ thích nghi –Adaptive) dựa trên dữ liệu phát sinh trong quátrình nén/giải nén Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM51 Adaptive Huffman (tt) Dữ liệu phát sinh Khởi tạo cây Cây Nén / Giải nén “tối thiểu” Huffman Dữ liệu Cập nhật cây nén / Giải nén Sự phối hợp giữa việc dùng cây (cho thuật tốn nén/giải nén) vàcập nhật cây Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM52 26
  27. Adaptive Huffman (tt) Y e s Thuật tốn nén Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM53 Adaptive Huffman (tt) Y e s Thuật tốn giải nén Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM54 27
  28. Adaptive Huffman (tt) ªCây Huffman (động): Một cây nhị phân cĩ n nút lá được gọi làcây Huffman nếu thỏa: Các nút lácĩtrọng số Wi >= 0, i  [1 n] Các nút nhánh cĩtrọng số bằng tổng trọng số các nút con của nĩ Tính chất Anh/Em (Sibling Property): Mỗi nút, ngoại trừ nút gốc, đều tồn tại 1 nút anh/em (cĩcùng nút cha) Khi sắp xếp các nút trong cây theo thứ tự tăng dần của trọng số thìmỗi nút luơn ở kề với nút anh/em của nĩ Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM55 Adaptive Huffman (tt) Thứ tự #1 #2 #3 #4 #5 #6 #7 #8 #9 Wi 1 2 2 2 3 4 7 10 17 Giátrị A B C D E Root Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM56 28
  29. Adaptive Huffman (tt) ªCách thức tạo cây: Khởi tạo cây “tối thiểu”, chỉ cĩnút Escape (0-node) Cập nhật 1 ký tự c vào cây: Nếu c chưa cĩtrong cây à thêm mới nút lác Nếu c đã cĩtrong cây à tăng trọng số nút c lên 1 (+1) Cập nhật trọng số của các nút liên quan trong cây Escape Cây “tối thiểu”chỉ cĩ1 nút Escape Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM57 Adaptive Huffman (tt) W = 2 # 5 W = 1 # 3 a W = 1 W = 1 # 3 # 4 ESCAPE a W = 0 W = 1 ESCAPE b # 1 # 2 W = 0 W = 1 # 1 # 2 Thêmnút ‘a’ Thêmnút ‘b’ Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM58 29
  30. Adaptive Huffman (tt) W = 3 W = 3 # 7 # 7 a a W = 2 W = 2 W = 1 W = 1 # 5 # 6 # 6 # 5 b b W = 1 W = 1 W = 1 W = 1 # 3 # 3 # 4 # 4 ESCAPE c ESCAPE c Hiệuchỉnhcây W = 0 W = 1 W = 0 W = 1 # 1 # 2 # 1 # 2 Thêmnút ‘c’ Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM59 Adaptive Huffman (tt) ªCách thức tạo cây: (tt) Khi thêm 1 nút mới hoặc tăng trọng số: Vi phạm tính chất anh/em Tràn số Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM60 30
  31. Adaptive Huffman (tt) Cập nhật trọng số các nút trên cây ROOT W = 1817 # = 9 W = 78 E # = 7 W = 10 # = 8 W = 43 W = 4 # = 5 # = 6 A B C D Tăngtrọngsố(1) W = 21 W = 2 W = 2 W = 2 ## == 11 # = 2 # = 3 # = 4 Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM61 Adaptive Huffman (tt) ªCách thức tạo cây: (tt) Thuật tốn “Cập nhật trọng số”: Tăng trọng số của nút lá lên 1 Đi từ nút là à nút gốc: tăng trọng số của các nút lên 1 Kiểm tra tính chất anh/em vàhiệu chỉnh lại cây (nếu vi phạm) Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM62 31
  32. Adaptive Huffman (tt) Vi phạm tính chất anh/em ROOT W = 18 # = 9 E W = 8 W = 10 # = 7 # = 8 W = 4 W = 4 # = 5 # = 6 A B C D Tăngtrọngsố(1) W = 32 W = 2 W = 2 W = 2 # = 1 # = 2 # = 3 # = 4 Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM63 Adaptive Huffman (tt) ROOT W = 1918 Điều chỉnh cây để thoả tính chất # = 9 anh/em E W = 89 W = 10 # = 7 # = 8 W = 4 W = 45 # = 5 # = 6 DA B C AD WW == 23 W = 2 W = 2 W = 32 ## == 11 # = 2 # = 3 # = 4 Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM64 32
  33. Adaptive Huffman (tt) ROOT W = 20 # = 9 E W = 10 W = 10 # = 7 # = 8 W = 4 W = 6 # = 5 # = 6 D B C AA W = 2 W = 2 W = 2 WW == 54 Tăngtrọngsố # = 1 # = 2 # = 3 ## == 44 Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM65 Adaptive Huffman (tt) ROOT W = 21 # = 9 E W = 10 W = 11 # = 7 # = 8 A W = 6 W = 5 # = 6 # = 5 Điều chỉnh cây C W = 4 W = 2 # = 4 # = 3 D B W = 2 W = 2 # = 1 # = 2 Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM66 33
  34. Adaptive Huffman (tt) ªCách thức tạo cây: (tt) Thuật tốn “Xác định nút vi phạm”: Gọi x lànút hiện hành So sánh x với các nút tiếp theo sau (từ trái à phải, từ dưới à trên) Nếu ∃y sao cho: y.Weight < x.Weight à x là nút bị vi phạm Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM67 Adaptive Huffman (tt) ªCách thức tạo cây: (tt) Thuật tốn “Điều chỉnh cây thỏa tính chất anh/em”: Gọi x lànút vi phạm Tìm nút y xa nhất, cĩ trọng số cao nhất, thoả: y.Weight < x.Weight Hốn đổi nút x vànút y trên cây Cập nhật lại các nút cha tương ứng Lặp lại bước [1] cho đến khi khơng cịn nút vi phạm Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM68 34
  35. Adaptive Huffman (tt) ªCách thức tạo cây: (tt) Vấn đề “tràn số” Quátrình cập nhật cây à tăng trọng số của các nút Trọng số của nút gốc tăng rất nhanh à giátrị trọng số vượt quákhả năng lưu trữ của kiểu dữ liệu VD. unsigned int Weight; // Giátrị max 65535 Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM69 Adaptive Huffman (tt) ROOT W = 255 # = 7 W = 126 W = 129 # = 5 # = 6 A B C D W = 63 W = 63 W = 64 W = 65 # = 1 # = 2 # = 3 # = 4 Nút gốc sẽ bị tràn số khi ta tăng trọng số của bất kỳ nút nào Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM70 35
  36. Adaptive Huffman (tt) ªCách thức tạo cây: (tt) Thuật tốn “Xử lý trường hợp tràn số”: Khi cập nhật trọng số, kiểm tra trọng số của nút gốc Nếu trọng số của nút gốc > MAX_VALUE Giảm trọng số các nút látrong cây (chia cho 2) Cập nhật trọng số các nút nhánh Kiểm tra tính chất anh/em và điều chỉnh lại cây (*) (*) do phép chia cho 2 làm mất phần dư của số nguyên Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM71 Adaptive Huffman (tt) ROOT ROOT W = 18 W = 8 # = 7 # = 7 W = 6 W = 12 W = 2 W = 6 # = 5 # = 6 # = 5 # = 6 A B C D A B C D W = 3 W = 3 W = 6 W = 6 W = 1 W = 1 W = 3 W = 3 # = 1 # = 2 # = 3 # = 4 # = 1 # = 2 # = 3 # = 4 Câysaukhichia trọng số các nút lácho 2 Cây bị tràn số vàcập nhật lại trọng số các nút nhánh à viphạmtínhchất anh/em Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM72 36
  37. Adaptive Huffman (tt) ROOT W = 8 # = 7 C W = 5 W = 3 # = 6 # = 5 W = 2 D # = 3 W = 3 # = 4 A B W = 1 W = 1 # = 1 # = 2 Cây sau khi điều chỉnh Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM73 Adaptive Huffman (tt) ªThuật tốn nén (Encoding): initialize_Tree(); // khởi tạo cây “tối thiểu” while(c != EOF) { c = getchar(inputfile); // đọc 1 byte dữ liệu encode(c, outputfile); // mã hố(nén) c update_Tree(c); // cập nhật c vào cây } Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM74 37
  38. Adaptive Huffman (tt) ªThuật tốn nén (Encoding): (tt) // Mã hốký tự c vàghi lên outputfile encode(c, outputfile) Nếu c chưa cĩtrong cây Phát sinh mã bit của Escape, vàghi lên file outputfile Ghi 8 bits mã ASCII của c lên file outputfile Nếu c đã cĩtrong cây Phát sinh mã bit của c, vàghi lên file outputfile Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM75 Adaptive Huffman (tt) ªThuật tốn giải nén (Decoding) initialize_Tree(); // khởi tạo cây “tối thiểu” while((c = decode(inputfile)) != EOF) { putchar(c, outputfile); // ghi c lên outputfile update_Tree(c); // cập nhật c vào cây } Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM76 38
  39. Adaptive Huffman (tt) ªThuật tốn giải nén (Decoding): (tt) // Giải mã 1 ký tự c từ inputfile decode(inputfile) § b = getchar(inputfile); § Lấy từng bit của b, duyệt trên cây w Nếu đi đến 1 nút lá x à return (x.char) w Nếu đi đến nút Escape: Øc = 8 bit tiếp theo từ inputfile Øreturn c Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM77 Thank you for your attention Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM78 39
  40. QQ && AA Sprint 2006Data Structure & Algorithm -Data Compression -Nguyen Tri Tuan, DH.KHTN Tp.HCM79 40