Giải thích mã hóa Huffman

Máy tính thường lưu mỗi chữ cái bằng cùng một số bit, tám bit trong ASCII thông thường. Cách đó đơn giản nhưng lãng phí, vì có những chữ cái phổ biến hơn hẳn những chữ khác. Năm 1951, một sinh viên đã tìm ra cách tốt nhất để cho mỗi ký hiệu một mã có độ dài riêng, ngắn cho ký hiệu thường gặp và dài cho ký hiệu hiếm, bằng một cách xây dựng đơn giản đến mức chỉ cần vài dòng. Ngày nay mã hóa Huffman có mặt trong hầu hết mọi tệp nén, hình ảnh và âm thanh bạn mở.

Một cây Huffman với các chữ cái của ABRACADABRA làm lá, các cạnh đánh dấu 0 và 1, và mã ngắn của A được tô sáng
Một cây Huffman với các chữ cái của ABRACADABRA làm lá, các cạnh đánh dấu 0 và 1, và mã ngắn của A được tô sáng

Mã ngắn cho ký hiệu phổ biến

Mã Morse đã dùng ý tưởng này từ những năm 1830: E, chữ cái phổ biến nhất trong tiếng Anh, chỉ là một chấm, còn Q là gạch gạch chấm gạch. Một mã như vậy tiết kiệm thời gian và không gian mỗi khi có những ký hiệu xuất hiện thường xuyên hơn những ký hiệu khác. Nhưng độ dài thay đổi đặt ra một vấn đề mà Morse giải quyết bằng các khoảng ngắt: làm sao biết một mã kết thúc ở đâu và mã tiếp theo bắt đầu ở đâu? Và nên gán độ dài nào cho mỗi ký hiệu để tổng nhỏ nhất có thể?

Mã tiền tố

Vấn đề thứ nhất biến mất nếu không mã nào là phần đầu của mã khác. Với các mã A = 0, B = 10, C = 110 và D = 111, chuỗi bit 0101100 chỉ có thể đọc là A B C A: ngay khi các bit đã đọc tạo thành một mã, mã đó là hoàn chỉnh. Các mã tiền tố như vậy tương ứng chính xác với các cây nhị phân có ký hiệu ở lá, trong đó mỗi nhánh trái là 0 và mỗi nhánh phải là 1. Chọn một mã chính là chọn một cây.

Cách xây dựng của Huffman

Bắt đầu với mỗi ký hiệu một lá, có trọng số là số lần ký hiệu đó xuất hiện. Lấy hai cây nhẹ nhất, ghép chúng dưới một nút mới có trọng số bằng tổng của chúng, và lặp lại cho đến khi chỉ còn một cây. Đó là toàn bộ thuật toán. Các ký hiệu hiếm được ghép trước và nằm sâu trong cây, với mã dài; các ký hiệu phổ biến được ghép sau cùng và ở gần đỉnh, với mã ngắn. Với một hàng đợi ưu tiên, thời gian chạy tỷ lệ với n log n cho n ký hiệu.

Vì sao nó tối ưu

Trong một cây tốt nhất có thể, hai ký hiệu hiếm nhất luôn có thể được đặt làm hai nút anh em ở tầng sâu nhất: hoán đổi chúng với bất cứ thứ gì đang ở đó chỉ có thể làm tổng ngắn đi. Ghép chúng thành một ký hiệu với trọng số gộp lại, phần còn lại là cùng bài toán với ít hơn một ký hiệu, nên bước tham lam không bao giờ chặn mất đáp án tốt nhất. Tổng số bit được dùng bằng tổng trọng số của mọi nút trong, và việc ghép giữ tổng này nhỏ nhất có thể.

Một bài tiểu luận thay cho kỳ thi

Năm 1951, David Huffman, nghiên cứu sinh tại MIT, theo học môn lý thuyết thông tin của Robert Fano. Fano cho sinh viên lựa chọn: dự kỳ thi cuối kỳ hoặc viết một bài tiểu luận về việc tìm mã nhị phân hiệu quả nhất. Huffman suýt bỏ cuộc với bài tiểu luận, rồi nhận ra rằng xây dựng cây từ dưới lên, thay vì chia từ trên xuống như phương pháp Shannon–Fano, luôn cho kết quả tốt nhất. Ông công bố nó năm 1952; phương pháp của cậu sinh viên đã vượt qua phương pháp mà giáo sư của mình xây dựng cùng Claude Shannon.

David Huffman, chụp khi ông là giáo sư tại UC Santa Cruz. Năm 1951, khi còn là nghiên cứu sinh tại MIT, ông tìm ra mã tối ưu của mình trong một bài tiểu luận cho môn học của Robert Fano.
David Huffman, chụp khi ông là giáo sư tại UC Santa Cruz. Năm 1951, khi còn là nghiên cứu sinh tại MIT, ông tìm ra mã tối ưu của mình trong một bài tiểu luận cho môn học của Robert Fano.
Claude Shannon, năm 1948 tại Bell Labs đã xác định chính xác lượng thông tin trong một thông điệp và đo bằng bit.
Claude Shannon, năm 1948 tại Bell Labs đã xác định chính xác lượng thông tin trong một thông điệp và đo bằng bit.

Gần với entropy

Claude Shannon chứng minh rằng không mã nào có thể dùng trung bình ít bit mỗi ký hiệu hơn entropy của nguồn. Mã Huffman đạt đúng entropy khi mọi xác suất đều là lũy thừa của một nửa, và không bao giờ cao hơn nó trọn một bit mỗi ký hiệu. Khoảng cách này đáng kể khi có một ký hiệu rất phổ biến: một ký hiệu chiếm 99% vẫn cần ít nhất một bit trọn vẹn, dù nó chỉ mang khoảng 0,015 bit thông tin. Mã hóa số học và hệ thống số bất đối xứng (ANS) của các trình nén mới hơn tránh được giới hạn đó.

Mã Huffman ở khắp nơi

Mã hóa Huffman hiếm khi được dùng riêng lẻ mà thường là công đoạn cuối của nhiều định dạng. Deflate, bên trong ZIP, gzip và PNG, trước tiên thay các đoạn lặp bằng tham chiếu rồi ghi kết quả bằng mã Huffman. JPEG dùng nó cho các con số còn lại sau phép biến đổi ảnh, MP3 cho dữ liệu âm thanh, và máy fax cho độ dài các loạt điểm đen và trắng. Các định dạng thường gửi một mã Huffman chính tắc, trong đó chỉ cần lưu độ dài các mã, vì bản thân các mã có thể được dựng lại từ đó.

Tự khám phá

Mở công cụ dựng mã Huffman để xây dựng cây của ABRACADABRA, MISSISSIPPI RIVER, một câu của riêng bạn hay bất kỳ văn bản nào khác, từng bước một. Xem hai cây nhẹ nhất ghép lại ở mỗi bước, nhấp vào một lá để xem mã của nó, theo dõi một ký hiệu qua các bit đã mã hóa, và so sánh tổng với mã độ dài cố định, UTF-8 và entropy.

Câu hỏi thường gặp

Mã hóa Huffman và Shannon–Fano khác nhau thế nào?

Mã hóa Shannon–Fano xây dựng cây từ trên xuống, chia các ký hiệu thành hai nhóm có trọng số gần bằng nhau, lặp đi lặp lại. Nó thường tốt nhưng không phải lúc nào cũng tối ưu. Huffman xây dựng cây từ dưới lên bằng cách ghép hai cây nhẹ nhất, và luôn cho mã tiền tố ngắn nhất có thể.

Bộ giải mã có cần cây không?

Có, nó cần đúng mã đó. Vì vậy các tệp nén lưu mã lại, thường dưới dạng danh sách độ dài mã cho một mã chính tắc, chỉ tốn vài chục byte. Với văn bản ngắn, phần phụ trội này có thể lớn hơn phần tiết kiệm; công cụ này chỉ đếm các bit đã mã hóa.

Mã hóa Huffman có thể làm tệp lớn hơn không?

Các ký hiệu đã mã hóa không bao giờ tốn nhiều bit hơn một mã độ dài cố định cho cùng các ký hiệu. Nhưng bảng mã cũng phải được lưu, nên với dữ liệu rất ngắn hoặc gần như ngẫu nhiên, kết quả có thể lớn hơn bản gốc một chút.

Bất đẳng thức Kraft nói gì?

Rằng một mã tiền tố với các độ dài mã l₁, l₂, … tồn tại khi và chỉ khi tổng của 2 mũ −l trên mọi ký hiệu không vượt quá 1. Với một cây đầy đủ, như mọi cây Huffman có ít nhất hai ký hiệu, tổng này đúng bằng 1.

Sẵn sàng thử chưa?

Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.

Mở công cụ dựng mã Huffman