Bài giảng Cấu trúc dữ liệu & Giải thuật - Chương 5: Các thuật toán nén dữ liệu - Nguyễn Trí Tuấn

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ó 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 56 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 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 57 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 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 58 Adaptive Huffman (tt) Taêng troïng soá (1) A W = 1 # = 1 E W = 10 # = 8 ROOT W = 17 # = 9 W = 7 # = 7 W = 3 # = 5 W = 4 # = 6 B W = 2 # = 2 C W = 2 # = 3 D W = 2 # = 4 4 8 8 2 # = 1 Cập nhật trọng số các nút trên cây 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 59 Adaptive Huffman (tt) Cách thức tạo cây: (tt) Thuật toá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) 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 60 Adaptive Huffman (tt) W = 1 # 3 a W = 1 # 2 ESCAPE W = 0 # 1 W = 2 # 5 a W = 1 # 4 ESCAPE W = 0 # 1 W = 1 # 3 b W = 1 # 2 Theâm nuùt ‘a’ Theâm nuùt ‘b’ 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 61 Adaptive Huffman (tt) W = 3 # 7 a W = 1 # 5 ESCAPE W = 0 # 1 W = 2 # 6 b W = 1 # 4 W = 1 # 3 c W = 1 # 2 W = 3 # 7 a W = 1 # 6 ESCAPE W = 0 # 1 W = 2 # 5 b W = 1 # 4 W = 1 # 3 c W = 1 # 2 Theâm nuùt ‘c’ Hieäu chænh caây 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 62 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ố 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 63 Adaptive Huffman (tt) Taêng troïng soá (1) A W = 2 # = 1 E W = 10 # = 8 ROOT W = 18 # = 9 W = 8 # = 7 W = 4 # = 5 W = 4 # = 6 B W = 2 # = 2 C W = 2 # = 3 D W = 2 # = 4 3 Vi phạm tính chất anh/em 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 64 Adaptive Huffman (tt) A W = 3 # = 1 E W = 10 # = 8 ROOT W = 18 # = 9 W = 8 # = 7 W = 4 # = 5 W = 4 # = 6 B W = 2 # = 2 C W = 2 # = 3 D W = 2 # = 4 D 2 5 9 9 A 3 Điều chỉnh cây để thoả tính chất anh/em 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 65 Adaptive Huffman (tt) E W = 10 # = 8 ROOT W = 20 # = 9 W = 10 # = 7 W = 4 # = 5 W = 6 # = 6 B W = 2 # = 2 C W = 2 # = 3 D W = 2 # = 1 A W = 4 # = 4 5 Taêng troïng soá 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 66 Adaptive Huffman (tt) Điều chỉnh cây D W = 2 # = 1 B W = 2 # = 2 ROOT W = 21 # = 9 W = 11 # = 8 A W = 5 # = 5 W = 6 # = 6 C W = 2 # = 3 W = 4 # = 4 E W = 10 # = 7 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 67 Adaptive Huffman (tt) Cách thức tạo cây: (tt) Thuật toá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 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 68 Adaptive Huffman (tt) Cách thức tạo cây: (tt) Thuật toá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, phía sau x, thoả: y.Weight < x.Weight Hoá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 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 69 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 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 70 Adaptive Huffman (tt) 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 ROOT W = 255 # = 7 W = 126 # = 5 W = 129 # = 6 A W = 63 # = 1 B W = 63 # = 2 C W = 64 # = 3 D W = 65 # = 4 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 71 Adaptive Huffman (tt) Cách thức tạo cây: (tt) Thuật toá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 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 72 Adaptive Huffman (tt) Cây bị tràn số ROOT W = 18 # = 7 W = 6 # = 5 W = 12 # = 6 A W = 3 # = 1 B W = 3 # = 2 C W = 6 # = 3 D W = 6 # = 4 ROOT W = 8 # = 7 W = 2 # = 5 W = 6 # = 6 A W = 1 # = 1 B W = 1 # = 2 D W = 3 # = 4 C W = 3 # = 3 Cây sau khi chia trọng số các nút lá cho 2 và cập nhật lại trọng số các nút nhánh  vi phạm tính chất anh/em 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 73 Adaptive Huffman (tt) Cây sau khi điều chỉnh W = 5 # = 6 W = 2 # = 3 A W = 1 # = 1 B W = 1 # = 2 D W = 3 # = 4 ROOT W = 8 # = 7 C W = 3 # = 5 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 74 Adaptive Huffman (tt) Thuật toán nén (Encoding): // inputfile: dữ liệu cần nén // outputfile: dữ liệu đã nén initialize_Tree(T); // khởi tạo cây “tối thiểu” while(c != EOF) { c = getchar(inputfile); // đọc 1 byte dữ liệu encode(T, c, outputfile);// mã hoá (nén) c update_Tree(T, c); // cập nhật c vào cây } 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 75 Adaptive Huffman (tt) Thuật toán nén (Encoding): (tt) // Mã hoá ký tự c và ghi lên outputfile encode(T, c, outputfile) Nếu c chưa có trong cây T Duyệt cây T tìm mã bit của Escape, và ghi lên file outputfile Ghi tiếp 8 bits mã ASCII của c lên file outputfile Nếu c đã có trong cây Duyệt cây T tìm mã bit của c, và ghi lên file outputfile 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 76 Adaptive Huffman (tt) Thuật toán giải nén (Decoding) // inputfile: dữ liệu ở dạng nén // outputfile: dữ liệu giải nén initialize_Tree(T); // khởi tạo cây “tối thiểu” while((c = decode(T, inputfile)) != EOF) { putchar(c, outputfile); // ghi c lên outputfile update_Tree(T, c); // cập nhật c vào cây } 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 77 Adaptive Huffman (tt) Thuật toán giải nén (Decoding): (tt) // Giải mã 1 ký tự c từ inputfile decode(T, inputfile)  Bắt đầu từ vị trí hiện tại trên inputfile  Lấy từng bit b, duyệt trên cây (b==0: left; b==1: right)  Nếu đi đến 1 nút lá x return (x.char)  Nếu đi đến nút Escape: c = 8 bit tiếp theo từ inputfile return c 09/2013 Data Structures & Algorithms - Data Compression - Nguyen Tri Tuan, DH KHTN Tp.HCM 78 Hỏi & Đáp