Xem mẫu
- Giải thuật nén Huffman
om
.c
Nén tĩnh (Static Huffman)
ng
co
an
Nén động (Adaptive Huffman)
th
o ng
du
u
cu
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Nén tĩnh (Static Huffman)
om
.c
ng
co
an
th
o ng
du
u
cu
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Giới thiệu
om
• Mã hóa Huffman (David A. Huffman)là một
.c
thuật toán mã hóa dùng để nén dữ liệu.
ng
co
• Dựa trên bảng tần suất xuất hiện các kí tự
an
cần mã hóa để xây dựng một bộ mã nhị
th
phân cho các kí tự đó sao cho dung lượng
o ng
(số bit) sau khi mã hóa là nhỏ nhất.
du
u
cu
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Trong bản mã ASCII, mỗi ký tự được biểu diễn bằng chuỗi 8 bit.
Ký tự Mã bit
om
Ý tưởng A 01000001
Giảm số bit để biểu diễn 1 ký tự
.c
B 01000010
ng
Dùng chuỗi bit ngắn hơn để biểu diễn ký tự xuất hiện nhiều C 01000011
D 01000100
co
Sử dụng mã tiền tố để phân cách các ký tự E 01000101
an
th
o ng
du
Ký tự Mã bit Ký tự Tần suất Ký tự Mã bit Ký tự Mã tiền tố
A 000 A 9 A 000 A 00
u
cu
B 001 B 15 B 1 B 11
C 010 C 10 C 01 C 01
D 011 D 6 D 011 D 100
E 100 E 7 E 100 E 101
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Cây Huffman
om
.c
Là cây nhị phân, mỗi nút chứa ký tự và trọng số (tần suất của ký tự đó).
ng
co
Mỗi ký tự được biểu diễn bằng 1 nút lá (tính tiền tố).
an
th
Nút cha có tổng ký tự, tổng trọng số của 2 nút con.
o ng
du
Các nút có trọng số, ký tự tăng dần từ trái sang phải.
u
cu
Các nút có trọng số lớn nằm gần nút gốc.
Các nút có trọng số nhỏ nằm xa nút gốc hơn.
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Mã Huffman
om
Là chuỗi nhị phân được sinh ra dựa trên cây Huffman.
.c
ng
Mã Huffman của ký tự là đường dẫn từ nút gốc đến nút lá đó.
co
• Sang trái ta được bit 0
an
• Sang phải ta được bit 1
th
ng
Có độ dài biến đổi (tối ưu bảng mã).
o
du
• Các ký tự có tần suất lớn có độ dài ngắn.
u
cu
• Các ký tự có tần suất nhỏ có độ dài dài hơn.
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Thuật toán nén tĩnh (Static Huffman)
om
B1: Duyệt file, lập bảng thống kê tuần suất xuất hiện của mỗi ký tự. B1
.c
ng
B2: Xây dựng cây Huffman dựa vào bảng thống kê. B2
co
an
B3: Sinh mã Huffman cho mỗi ký tự dựa vào cây Huffman. B3
th
ng
B4: Duyệt file, thay toàn bộ ký tự bằng mã Huffman tương ứng. B4
o
du
u
B5: Lưu lại cây Huffman (bảng mã) dùng cho việc giải nén. Xuất file đã nén. B5
cu
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Chuỗi ký tự cần nén
om
.c
F = “ABABBCBBDEEEABABBAEEDDCCABBBCDEEDCBCCCCDBBBCAAA” N = 47
ng
co
an
Bảng tần suất xuất hiện
th
ng
Ký tự Tần suất
o
A 9
du
B 15
u
C 10
cu
D 6
E 7
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Xây dựng cây Huffman
Thuật toán tham lam
om
.c
B1: Tạo N cây, mỗi cây chỉ có một nút gốc, mỗi nút gốc chỉ
ng
chứa một kí tự và trọng số (tần suất của ký tự đó). (N = số ký tự)
co
an
th
B2: Lặp lại thao tác sau cho đến khi chỉ còn 1 cây duy nhất:
ng
+ Ghép 2 cây con có trọng số gốc nhỏ nhất thành 1 nút cha, có
o
du
tổng ký tự, tổng trọng số trọng số của 2 nút con.
u
+ Xóa các cây đã duyệt.
cu
+ Điều chỉnh lại cây nếu vi phạm tính chất.
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Xây dựng cây Huffman
Ký tự Tần suất
om
DE | 13
B 15
.c
C 10
A 9
ng
E 7
co
D 6
D|6 E|7
an
th
ng
Ký tự Tần suất Ký tự Tần suất Ký tự Tần suất Ký tự Tần suất
o
B 15 AC 19 BDE 28 ABCDE 47
du
DE 13 B 15 AC 19
u
C 10 DE 13
cu
A 9
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Bảng mã Huffman
ABCDE | 47 Ký tự Mã Huffman
A 00
0 1
om
B 11
.c
C 01
ng
AC | 19 BDE | 28 D 100
co
0 1 E 101
0 1
an
th
A |9 C | 10 DE | 13 B | 15
o ng
0 1
du
u
00
cu
D|6 E|7
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Ký tự Mã Huffman Chuỗi ký tự cần nén
A 00
F = “ABABBCBBDEEEABABBAEEDDCCABBBCDEEDCBCCCCDBBBCAAA”
om
B 11
C 01
.c
D 100
ng
E 101
co
an
Chuỗi đã được nén
th
ng
FOutput =
o
“001100111101111110010110110100110011110010110110010001
du
01001111110110010110110001110101010110011111101000000”
u
cu
Tiết kiệm: 8*47 - (2*9 + 2*15 + 2*10 + 3*6 + 3*7) = 376 - 107 = 269 bit
Tỷ lệ nén: (1 - 107/376)*100 = 72.54 %
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Thuật toán giải nén
om
B1: Xây dựng lại cây Huffman từ thông tin giải mã đã lưu.
.c
ng
B2: Duyệt file, đọc lần lượt từng bit trong file nén và duyệt cây.
co
an
th
B3: Xuất ký tự tương ứng khi duyệt hết nút lá.
ng
o
du
B4: Thực hiện B2, B3 cho đến khi duyệt hết file.
u
cu
B5: Xuất file đã giải nén.
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Bài tập: Nén chuỗi sau bằng giải thuật nén tĩnh – Static Huffman
F=
“CNTT10110CLCCNNTTT10000CCCCLLLLCCCTTTT11000
om
NTNNN000TNT” N = 54
.c
ng
Ký tự Tần suất Ký tự Mã Huffman
co
0 12 0 01
1 6
an
1 1111
th
C 11 ng C 00
L 5 L 1110
o
N 8 N 110
du
T 12 T 10
u
cu
Kết quả
FOutput =
“001101010111101111111110100111000001101101010101111010101010000000011
101110111011100000001010101011111111010101110101101101100101011011010”
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Ưu - Nhược điểm
om
• Hệ số nén tương đối cao.
.c
• Phương pháp thực hiện tương đối đơn giản.
ng
Ưu điểm • Đòi hỏi ít bộ nhớ.
co
an
th
ng
• Mất 2 lần duyệt file khi nén.
o
du
• Phải lưu trữ thông tin giải mã vào file nén.
Nhược
u
• Phải xây dựng lại cây Huffman khi giải nén.
cu
điểm
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Nén động (Adaptive Huffman)
om
.c
ng
• Khắc phục nhược điểm của Static Huffman.
co
• Đầu đọc vừa duyệt, vừa cập nhật cây Huffman,
an
vừa xuất kết quả ra file nén theo thời gian thực.
Ưu điểm
th
• (Ngược lại). ng
o
du
u
cu
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Cây Huffman
om
Tính chất anh em:
.c
Trọng số của nút bên trái phải nhỏ hơn nút bên phải, nhỏ hơn nút
ng
cha
co
an
th
Nút NYT (not yet transmitted) có trọng số luôn = 0, dùng dể nhận
ng
biết ký tự đã xuất hiện trong cây hay chưa.
o
du
u
cu
Trọng số nút cha bằng tổng trọng số 2 nút con.
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Thuật toán nén động (Adaptive Huffman)
B1: Duyệt tuần tự từng ký tự có trong file nhập.
om
TH1: Nếu ký tự chưa tồn tại:
.c
+ Chuỗi bit: đường dẫn đến NYT + Mã bit của ký tự.
ng
+ Chèn nút mới (Ký tự | trọng số = 1) vào NYT. Đánh lại số thứ tự.
co
an
TH2: Nếu ký tự đã tồn tại:
th
+ Chuỗi bit: đường dẫn đến ký tự đó.
ng
+ Tăng trọng số của ký tự đó. (+1)
o
du
u
cu
B2: + Tăng trọng số của các nút cha. (+1)
+ Nếu vi phạm tính anh em điều chỉnh cho đến khi hết vi phạm.
B3: Lưu chuỗi bit vào file xuất. Lặp lại B1, B2 đến khi duyệt hết file.
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Thuật toán điều chỉnh
om
.c
+ Nếu trọng số nút hiện hành > nút lân cận
ng
từ phải sang trái, từ dưới lên trên Vi phạm.
co
an
th
+ Tìm nút xa nhất có trọng số cao nhất <
ng
trọng số nút vi phạm Hoán đổi vị trí.
o
du
u
cu
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- TH1: Ký tự chưa tồn tại F = “AABBB”
NYT | 01 #0
#2
om
0 1
.c
ng
NYT A|1
co
(new)
an
#0 #1
th
o ng
du
u
cu
FOutput = 01000011
CuuDuongThanCong.com https://fb.com/tailieudientucntt
nguon tai.lieu . vn
