Mã Huffman tối ưu và Cây nhị phân Huffman

Giới thiệu
Trong khoa học máy tính và lý thuyết thông tin, mã hóa Huffman là một thuật toán mã hóa dùng để nén dữ liệu. Nó dựa trên bảng tần suất xuất hiện các kí tự cần mã hóa để xây dựng một bộ mã nhị phân cho các kí tự đó sao cho dung lượng (số bít) sau khi mã hóa là nhỏ nhất. Nói chung dạng mã này chủ yếu phục vụ cho mục đích nén thông tin là chính còn khả năng che dấu thông tin thì không được đánh giá cao.

Thuật toán được đề xuất bởi David A. Huffman khi ông còn là sinh viên Ph.D. tại MIT, và công bố năm 1952 trong bài báo "A Method for the Construction of Minimum-Redundancy Codes". Sau này Huffman đã trở thành một giảng viên ở MIT và sau đó ở khoa Khoa học máy tính của Đại học California, Santa Cruz, Trường Kỹ nghệ Baskin (Baskin School of Engineering).

Mã tiền tố (prefix-free binary code)

Để mã hóa các kí hiệu (kí tự, chữ số, ...) ta thay chúng bằng các xâu nhị phân, được gọi là từ mã của kí hiệu đó. Chẳng hạn bộ mã ASCII, mã hóa cho 256 kí hiệu là biểu diễn nhị phân của các số từ 0 đến 255, mỗi từ mã gồm 8 bít. Trong ASCII từ mã của kí tự "a" là 1100001, của kí tự "A" là 1000001. Trong cách mã hóa này các từ mã của tất cả 256 kí hiệu có độ dài bằng nhau (mỗi từ mã 8 bít). Nó được gọi là mã hóa với độ dài không đổi.

Khi mã hóa một tài liệu có thể không sử dụng đến tất cả 256 kí hiệu. Hơn nữa trong tài liệu chữ cái "a" chỉ có thể xuất hiện 1000000 lần còn chữ cái "A" có thể chỉ xuất hiện 2, 3 lần. Như vậy ta có thể không cần dùng đủ 8 bít để mã hóa cho một ký hiệu, hơn nữa độ dài (số bít) dành cho mỗi kí hiệu có thể khác nhau, kí hiệu nào xuất hiện nhiều lần thì nên dùng số bít ít, ký hiệu nào xuất hiện ít thì có thể mã hóa bằng từ mã dài hơn. Như vậy ta có việc mã hóa với độ dài thay đổi. Tuy nhiên, nếu mã hóa với độ dài thay đổi, khi giải mã ta làm thế nào phân biệt được xâu bít nào là mã hóa của ký hiệu nào. Một trong các giải pháp là dùng các dấu phẩy (",") hoặc một kí hiệu quy ước nào đó để tách từ mã của các kí tự đứng cạnh nhau. Nhưng như thế số các dấu phẩy sẽ chiếm một không gian đáng kể trong bảng mã. Một cách giải quyết khác dẫn đến khái niệm mã tiền tố.

Mã tiền tố là bộ các từ mã của một tập hợp các kí hiệu sao cho từ mã của mỗi ký hiệu không là tiền tố (phần đầu) của từ mã một ký hiệu khác trong bộ mã ấy.
Đương nhiên mã hóa với độ dài không đổi là mã tiền tố.

Ví dụ:
Giả sử mã hóa từ "ARRAY", tập các ký hiệu cần mã hóa gồm 3 chữ cái "A","R","Y".
- 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 chữ cái chẳng hạn "A"=00, "R"=01, "Y"=10. Khi đó mã hóa của cả từ là 0001010010. Để giải mã ta đọc hai bit một và đối chiếu với bảng mã.
- Nếu mã hóa "A"=0, "R"=01, "Y"=11 thì bộ từ mã này không là mã tiền tố ví từ mã của "A" là tiền tố của từ mã của "R". Để mã hóa cả từ ARRAY phải đặt dấu ngăn cách vào giữa các từ mã 0,01,01,0,11
- Nếu mã hóa "A"=0, "R"=10, "Y"=11 thì bộ mã này là mã tiền tố. Với bộ mã tiền tố này khi mã hóa xâu "ARRAY" ta có 01010011.

Biểu diễn mã tiền tố trên cây nhị phân

Nếu có một cây nhị phân n lá ta có thể tạo một bộ mã tiền tố cho n ký hiệu bằng cách đặt mỗi ký hiệu vào một lá. Từ mã của mỗi kí hiệu được được tạo ra khi đi từ gốc tới lá chứa ký hiệu đó, nếu đi qua cạnh trái thì ta thêm số 0, đi qua cạnh phải thì thêm số 1.
Ví dụ: Cây 3 lá sau đây biểu diễn bộ mã của A,R,Y trong ví dụ trên

Code:

                            *
                          0/  \1
                          A    *
                            0/  \1
                            R    Y

Từ mã của "A" là 0, của "R" là 10, của "Y" là 11.

Mã tiền tố tối ưu

Từ ví dụ trên thấy mã hóa của xâu "ARRAY" bằng mã độ dài cố định mất 10 bít, bằng mã tiền tố đã đưa ra mất 8 bít, tiết kiệm được 20%. Bài toán đặt ra là bộ mã tiền tố đã tối ưu chưa?

(Nguồn: wikipedia.org)

a. Giới thiệu
Sở dĩ gọi là "giải thuật tham lam" bởi trong thuật giải bài toán xây dựng cây mã tiền tố tối ưu của Huffman, ở mỗi bước ta chọn hai chữ cái có tần số thấp nhất để mã hóa bằng từ mã dài nhất.

b. Ý tưởng
Giả sử có tập A gồm n ký hiệu và hàm trọng số tương ứng W(i), với (i=1,2,3...n).
Khởi tạo: Tạo một rừng gồm n cây, mỗi cây chỉ có một nút gốc, mỗi nút gốc tương ứng với một kí tự và có trọng số là tần số/tần suất của kí tự đó.
Thủ tục lặp:
Mỗi bước sau thực hiện cho đến khi rừng chỉ còn một cây:
- Chọn hai cây có trọng số ở gốc nhỏ nhất hợp thành một cây bằng cách thêm một gốc mới nối với hai gốc đã chọn. Trọng số của gốc mới bằng tổng trọng số của hai gốc tạo thành nó. Như vậy ở mỗi bước số cây bớt đi một.
- Khi rừng chỉ còn một cây thì dừng lại, cây đó biểu diễn mã tiền tố tối ưu với các ký tự đặt ở các lá tương ứng.

c. Giải thuật

Cấu trúc cây nhị phân Huffman

Code:

Cây = ^ Node;
Node = Record
      c: Ký tự
        s: Số lần xuất hiện
        L, R: Cây;
end;

Giải thuật xây dựng cây nhị phân Huffman

Code:

PROC Tạo_Cây (T: KT; VAR P: Cây)
1)PhầnTử := ARRAY (1..n) of Cây;
2) FOR i := 1 TO n DO
          NEW (PhầnTử (i)); // Tạo n cây, mỗi cây có đúng một nút.
          PhầnTử (i). c = T (i). c;
          PhầnTử (i). s = T (i). s;
          PhầnTử (i). L = Nil;
          PhầnTử (i). R = Nil;
3) FOR m := n DOWNTO 2 DO // Lần lượt kết hợp từng cặp hai cây với nhau thành một cây mới cho đến khi chỉ còn một cây duy nhất
          a) Sắp xếp m phần tử đầu tiên của PhầnTử theo thứ tự giảm dần của s.
          b) NEW (X);
          X. s = PhầnTử (m). s + PhầnTử (m - 1). s;
          X. L = PhầnTử (m - 1);
          X. R = PhầnTử (m);
          PhầnTử (m-1) := X;

(Nguồn: Copy từ link gốc của lớp Cao học CNTT K23, Học viện KTQS: http://khmt.123.st/t89-topic#ixzz2TFSzrA7Q)

1. Ví dụ 1
Cho bảng tần suất của 5 chữ cái A,B,C,D,E như sau tương ứng là 0.10; 0.15; 0.30; 0.16; 0.29

Quá trình xây dựng cây Huffman diễn ra như sau




Như vậy bộ mã tối ưu tương ứng là

Code:

A   B   C   D   E
010   011   11   00   10

(Nguồn: http://vi.wikipedia.org/wiki/M%C3%A3_h%C3%B3a_Huffman)

Câu 2. Đề thi năm 2008

a. Danh sách D lưu trữ các ký tự và tần suất xuất hiện của chúng trong văn bản T có n ký tự:
List = ^Words;
Words = Record;
w: Char;
t: Integer;
End;
D[1..n] of List;
Viết giải thuật xây dựng cây nhị phân Huffman mã hoá văn bản T.

b. Văn bản T chỉ gồm các ký tự a, b, c, d, e, f, g, h với số lần xuất hiện như sau:

Ký tự	a	b	c	d	e	f	g	h
Tần suất	30	20	20	13	7	5	3	2

Xây dựng bộ mã Huffman tối ưu và vẽ cây nhị phân Huffman tương ứng. Cho biết số bit của văn bản mã hoá và hiệu suất mã hoá.

Giải đề 2008:
1) Đầu tiên phải sắp xếp lại theo thứ tự giảm dần về tần suất, nhưng ở đây đã sắp xếp rồi, chỉ việc viết lại, nếu đề mà chưa sắp xếp, chúng ta cần sắp xếp lại.


b1) Ta thấy g và h là 2 ký tự có tần suất ít nhất nên:


b2) Làm tiếp f và M1 do lớn hơn e nên xếp lên trên:


b3)Làm tiếp cứ theo nguyên tắc tần suất lớn hơn xếp lên trên để được:


b4)Tiếp tục:


b5)Tiếp tục:


b6)Tiếp tục:


b7)Tiếp tục:


Điền các giá trị theo cây, nhánh bên trái là 0, nhánh bên phải là 1:


Ta có bảng mã hóa Huffman, lấy từ gốc xuống:
a = 00
b = 10
c = 11
d = 011
e = 0101
f = 01000
g = 010010
h = 010011

Số bit mã hóa văn bản là:
2.30 + 2.20 + 2.20 + 3.13 + 4.7 + 5.5 + 6.3 + 6.2
= 60 + 40 + 40 + 39 + 28 + 25 + 18 + 12 = 262
Hiệu suất mã hóa văn bản là:
= 0,3275

(Nguồn: Copy từ link gốc của lớp Cao học CNTT, Học viện KTQS: http://khmt.123.st/t89-topic#ixzz2TFXShj1H)