THUẬT TOÁN NÉN HUFFMAN TĨNH
Data: ADDAABBCCBAAABBCCCBBBCDAADDEEAA
Số bit cần mã hóa: Len * 8 = 31 * 8 = 248 bit
I.
Lập bảng tần số:
|
Ký tự
|
Tần số
|
|
A
|
10
|
|
B
|
8
|
|
C
|
6
|
|
D
|
5
|
|
E
|
2
|
II.
Xây dựng cây:
Nhóm
2 chuỗi ký tự có tần số nhỏ nhất trước thành 1 chuỗi mới vì chuỗi ký tự được
nhóm trước sẽ có đã dài mà Huffman dài hơn, chuỗi nhóm sau có độ dài mã Huffman
ngắn hơn, nên chuỗi có tần số lớn nhất sẽ có mã Huffman ngắn nhất. Từ đó ta có
chuỗi được nén được nén hiệu quả nhất.
Để tiện cho việc tạo
cây ta có những quy ước sau:
·
Luôn nhóm 2 chuỗi ký tự có trọng số
(tổng tần số các ký tự) nhỏ nhất.
·
Chuỗi có trọng số lớn hơn sẽ là nút
phải
·
Nếu trọng số bằng nhau, chuỗi có ký
tự nhỏ nhất lớn hơn sẽ là nút phải
(VD: TCXB và KSAM thì TCXB là nút phải vì ‘C’ > ‘A’)
(VD: TCXB và KSAM thì TCXB là nút phải vì ‘C’ > ‘A’)
|
Chuỗi ký tự
|
Tần số
|
|
A
|
10
|
|
B
|
8
|
|
C
|
6
|
|
D
|
5
|
|
E
|
2
|
Ø E + D
|
Chuỗi ký tự
|
Tần số
|
|
A
|
10
|
|
B
|
8
|
|
ED
|
7
|
|
C
|
6
|
Ø C + ED
|
Chuỗi ký tự
|
Tần số
|
|
CED
|
13
|
|
A
|
10
|
|
B
|
8
|
Ø A + B
|
Chuỗi ký tự
|
Tần số
|
|
BA
|
18
|
|
CED
|
13
|
Ø CED + BA
|
Chuỗi ký tự
|
Tần số
|
|
CEDBA
|
31
|
III.
Xây dựng bảng mã Huffman
Ta duyệt từ gốc đến ký tự, theo chiều duyệt cây
cứ theo nút trái là 0, nút phải là 1 thì ta nhận được mã Huffman tương ứng với
ký tự đó.
|
Ký tự
|
Mã Huffman
|
|
A
|
11
|
|
B
|
10
|
|
C
|
00
|
|
D
|
011
|
|
E
|
010
|
IV.
Nén chuỗi
Duyệt chuỗi Data, mỗi ký
tự ta thay bằng mã Huffman
è Data nén: 110110111111101000001011111110100000001010100001111110110110100101111
Số bit mã hóa: 2 * 10 + 2 * 8 + 2 * 6 + 3 * 2 + 3 * 5 = 69
Hiệu suất nén: 1 – 69
/ 248 * 100 = 72.18%
V.
Giải nén
Sau
khi nén dữ liệu, dữ liệu được nén được lưu trữ hoặc gửi đến điểm đích và được
giải nén để xem nội dung. Để giải nén được nội dung này thì dữ liệu đã nén phải
luôn đi kèm với bảng mã Huffman, ta có thể xem bảng mã Huffman là chìa khóa để
giải mã dữ liệu nén và mỗi dữ liệu nén sẽ có 1 bảng mã Huffman đặc trưng riêng.
Để giải được
dữ liệu đã nén, ta duyệt chuỗi nhị phân theo cây được tạo bởi bảng mã huffman,
‘0’ để duyệt bên nhánh trái, ‘1’ để duyệt bên nhánh phải khi tới điểm nút lá ta
có được ký tự tương ứng, sau đó ta trả về điểm gốc cây, và duyệt dữ liệu nén
còn lại tương tự như trên.
