Mã hóa Huffman

Mã hóa Huffman

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 (wikipedia.org).

Mã hóa dữ liệu trong máy tính

Để mã hóa các kí hiệu (bao gồm kí tự, chữ số, …) trong máy tính, ta thay chúng bằng các xâu nhị phân, được gọi là từ mã của kí hiệu đó.

Ví dụ bộ mã ASCII ra đời năm 1967, 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 bit. 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 bit để mã hóa cho một ký hiệu, hơn nữa độ dài (số bit) 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ố bit í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. Để 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ản mã. Một cách giải quyết khác dẫn đến khái niệm mã phi tiền tố.

Mã phi tiền tố

Mã phi 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.
Ví dụ có từ “CNTT” gồm 3 chữ cái là C,N,T. Nếu dùng cách mã hóa với độ dài không đổi thì mỗi chữ cái được mã hóa tối thiểu là 2 bit chẳng hạn C=00, N=01, T=10. Khi đó xâu được mã hóa là 00011010.
Nếu mã hóa C=0, N=01, T=11 thì bộ từ mã này không là mã phi tiền tố vì từ mã của chữ C là tiền tố của từ mã của N. Để mã hóa cả từ này ta phải đặt dấu ngăn cách vào giữa các từ mã 0,01,10,10.
Nếu mã hóa C=0, N=10, T=11 thì bộ mã này là mã phi tiền tố. Với bộ mã phi tiền tố này thì xâu được mã hóa là 0101111.

Mã Huffman

Mỗi mã phi tiền tố có thể biểu diễn bởi một cây nhị phân T mà mỗi lá của nó tương ứng với một chữ cái và cạnh của nó được gán cho một trong hai số 0 hoặc 1. Mã của một chữ cái c là một dãy nhị phân gồm các số gán cho các cạnh trên đường đi từ gốc đến lá tương ứng với c.
Bài toán: Tìm cách mã hóa tối ưu, tức là tìm cây nhị phân T làm tối thiểu hóa tổng độ dài có trọng số

B(T) = ∑ f(c) depth(c)

trong đó f(c)depth(c) là tần số và độ dài đường đi từ gốc đến lá tương ứng với ký tự c.
Ý tưởng: Chữ cái có tần suất nhỏ hơn cần được gán cho lá có khoảng cách đến gốc là lớn hơn, chữ cái có tần suất xuất hiện lớn hơn cần được gán cho nút gần gốc hơn.

Thuật toán xây dựng cây mã Huffman

Procedure Huffman(C,f)
Begin
	Duyệt khi đến hết C
		Begin
	   		x, y ← hai chữ cái có tần suất nhỏ nhất trong C;
	   		Tạo nút p với hai con x, y;
	   		f(p):= f(x) + f(y);
	   		C ← C \ {x, y} U {p};
		end;
End;	

Trong đó: C là bảng các chữ cái, n là số chữ cái có trong C, f là bảng tần suất xuất hiện các chữ cái trong C.

Ví dụ: Xây dựng cây mã Huffman với bảng tần suất dưới đây:

C T D L G
23 61 43 70 12

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

huffman-tree

Từ đó, khi đi từ gốc đến từng lá, ta thu được bảng mã của các chữ cái như sau:

Chữ cái Tần suất Mã Huffman
T 61 11
D 43 01
L 70 10
C 23 000
G 12 001

Thuật toán giải mã

Procedure huffmanDecode(B)
Begin
	Đặt p trỏ đến gốc của cây Huffman
	While <chưa kết thúc xâu B>
	Begin
		x ← bit tiếp theo trong xâu B;
		if x=0 then p ← con trái của p
		else p ← con phải của p;
		if <p trỏ đến lá> then
		begin
			<Hiển thị ký hiệu tương ứng với nút lá>
			<Đặt lại p là gốc cây Huffman>
		end;
	end;
end;

Ứng dụng mã hóa Huffman để nén file

Các bước thực hiện nén:

  • Đọc file và xác định các ký tự xuất hiện trong file & tần suất của chúng
  • Dựng cây mã Huffman
  • Dựa vào cây mã thu được mã hóa từng ký tự và ghi vào file nén
  • Lưu cây mã vào cuối file nén

Các bước giải nén ngược lại.

Nhược điểm của thuật toán Huffman trên (Huffman tĩnh) là quá trình mã hóa phải duyệt dữ liệu 2 lần: một lần để xác định tần suất & dựng cây mã, một lần nữa để mã hóa. Do đó, thuật toán Huffman động được đề xuất (độc lập) bởi Faller (1973), Gallager (1978) và năm 1985, Knuth đưa ra một số cải tiến và hoàn chỉnh thuật toán (vì thế thuật toán này còn được gọi là thuật toán FGK). Nó có một số ưu điểm so với Huffman tĩnh là không cần tính trước số lần xuất hiện của các kí tự, không cần lưu thông tin phục vụ cho việc giải nén, quá trình nén chỉ cần một lần duyệt file và có thể nén trên dữ liệu phát sinh theo thời gian thực.

Khi trích dẫn bài viết từ tek.eten.vn, xin vui lòng ghi rõ nguồn. Chúng tôi sẽ rất cảm ơn bạn!