VietTechiesHIỂU CÔNG NGHỆ. MỞ GÓC NHÌN.
☰ Chuyên mục

Suýt bỏ bài tiểu luận cao học, David Huffman tìm ra cách mã hóa nhị phân từng ký hiệu có tần suất đã biết với độ dài trung bình ngắn nhất, không từ mã nào là phần đầu của từ mã khác

21/10/2026 · VietTechies · Biên tập

Bố cục ảnh tư liệu chia đôi, với những dải băng giấy đục lỗ cuộn lại bên cạnh các ghi chú kỹ thuật về nén dữ liệu


Năm 1951, David A. Huffman, một học viên cao học tại Viện Công nghệ Massachusetts (MIT), đứng trước lựa chọn: làm bài thi cuối kỳ hoặc viết một bài tiểu luận. Đề tài được giao là tìm ra cách hiệu quả nhất để biểu diễn thông tin bằng mã nhị phân; Huffman đã chọn làm tiểu luận, và lời giải của ông về sau được biết đến với tên gọi mã hóa Huffman (Huffman coding).

Đề bài này do Robert M. Fano đưa ra trong một khóa học cao học ngành kỹ thuật điện về lý thuyết thông tin — một lĩnh vực mới nổi thời bấy giờ. Fano yêu cầu các sinh viên giải quyết một bài toán thoạt nhìn rất đơn giản: với một tập hợp gồm chữ cái, chữ số hoặc ký hiệu có tần suất xuất hiện đã biết, làm thế nào để gán các chữ số nhị phân (bit) cho từng ký hiệu sao cho toàn bộ thông điệp sau khi mã hóa sử dụng ít bit nhất có thể? Về sau, Huffman cho biết lúc đó ông không hề hay biết rằng Fano và Claude E. Shannon — người đặt nền móng cho lý thuyết thông tin — cũng từng chật vật tìm lời giải cho bài toán này.

Bất cập của mã có độ dài cố định và những khoảng dừng

Thoạt nhìn, việc truyền văn bản kỹ thuật số có vẻ rất đơn giản. Nếu máy tính gán cho mỗi chữ cái một độ dài cố định là 8 bit, việc giải mã rất dễ dàng: cứ mỗi 8 chữ số nhị phân sẽ biểu diễn một ký tự. Thế nhưng, cách dùng cùng một độ dài mã cho mọi ký tự tuy đơn giản lại gây lãng phí dung lượng. Những chữ cái phổ biến như E xuất hiện thường xuyên hơn nhiều so với các ký tự hiếm như Q, đồng nghĩa với việc mã có độ dài cố định tiêu tốn lượng bit cho ký hiệu hiếm ngang bằng với ký hiệu dùng hằng ngày.

Khoảng một thế kỷ trước đó, Samuel Morse và Alfred Vail đã phát triển mã Morse, trong đó gán một dấu chấm ngắn cho chữ E và các tổ hợp dấu chấm cùng dấu gạch dài hơn cho những chữ cái hiếm hơn. Nhưng mã Morse mắc phải một nhược điểm căn bản: vì độ dài các mã không đồng đều, nhân viên điện báo không thể giải mã thông điệp nếu thiếu những khoảng dừng giữa các chữ cái. Không có những khoảng trống ngăn cách đó, người nhận không thể phân biệt được các tổ hợp ký tự khác nhau có cùng chuỗi chấm và gạch.

Fano hiểu rằng lời giải đòi hỏi thứ mà các nhà toán học gọi là mã tiền tố (prefix-free code): một cách sắp xếp sao cho không có từ mã nào là phần mở đầu của một từ mã khác. Nếu chữ S được gán mã 01, thì không có ký hiệu nào khác trong bảng chữ cái được phép bắt đầu bằng 01. Nhờ quy tắc này, bên nhận có thể đọc một luồng nhị phân liên tục từ trái sang phải và nhận ra ngay điểm kết thúc của từng ký tự mà không cần đến các dấu phân cách.

Xây dựng từ trên xuống

Để gán các mã tiền tố này, Fano xây dựng cây nhị phân, đặt các ký hiệu ở phần cuối của các nhánh. Ông bắt đầu từ đỉnh cây và đi dần xuống dưới, sắp xếp bảng chữ cái theo tần suất rồi cố gắng chia thành hai nhóm con có tổng xác suất xấp xỉ bằng nhau. Nếu nhánh rẽ sang trái, ông thêm số 0; nếu rẽ sang phải, ông thêm số 1.

Dù trực quan, cách chia cân bằng từ trên xuống này chỉ mang tính xấp xỉ. Chẳng hạn, khi mã hóa từ “schoolroom” — trong đó chữ O xuất hiện 4 lần và 6 chữ cái khác mỗi chữ xuất hiện 1 lần — cách chia nhóm theo hướng cân bằng của Fano tạo ra thông điệp cần 27 bit. Cách này gần đạt hiệu quả tối ưu, nhưng Fano biết rằng phải tồn tại một cách xây dựng tối ưu về mặt toán học.

Bước đột phá bên thùng rác

Suốt nhiều tháng, Huffman thử nghiệm nhiều cách tiếp cận khác nhau cho bài toán, nhưng không thể chứng minh bất kỳ cách nào là hiệu quả nhất. Cuối cùng, ông nản lòng trước việc tìm kiếm lời giải và quyết định quay sang ôn tập cho kỳ thi cuối kỳ.

Bước đột phá ập đến trong khoảnh khắc bừng sáng ngay khi ông chuẩn bị vứt bỏ các tập ghi chép. Sau này, Huffman nhớ lại khoảnh khắc ấy khi trò chuyện với nhà báo Gary Stix trong bài viết chân dung năm 1991 trên tạp chí Scientific American: “Đó là khoảnh khắc độc nhất vô nhị trong đời tôi. Tôi chợt hiểu ra, như có một tia chớp lóe lên.”

Huffman đảo ngược hướng đi mà Fano và Shannon từng chọn. Fano và Shannon cố gắng xây dựng cây từ gốc đi xuống, phỏng đoán cách chia đôi toàn bộ không gian xác suất. Còn Huffman nhận ra rằng nơi duy nhất có cấu trúc chắc chắn về mặt toán học lại nằm ở tận cùng bên dưới.

Bắt đầu từ những ký hiệu hiếm nhất

Luôn tồn tại một mã tiền tố nhị phân tối ưu mà trong đó hai ký hiệu có xác suất thấp nhất mang các từ mã có độ dài lớn nhất và là hai nút anh em (sibling) cùng chung một nút cha. Thay vì chia tách toàn bộ bảng chữ cái từ trên đỉnh, Huffman bắt đầu từ hai phần tử hiếm nhất.

Ông lấy hai ký hiệu có tần suất thấp nhất, ghép chúng thành một nút tổng hợp duy nhất rồi cộng xác suất của chúng lại với nhau. Thao tác đơn giản ấy đã chuyển đổi một bài toán có N ký hiệu thành một bài toán đơn giản hơn với N trừ một ký hiệu. Huffman lặp lại quy tắc đó: xét các ký hiệu còn lại cùng với nút tổng hợp mới, tìm hai phần tử có xác suất nhỏ nhất rồi lại ghép chúng với nhau.

Huffman lặp lại phép ghép cặp cho đến khi chỉ còn lại một nút gốc duy nhất. Tương tự như trong cây của Fano, mỗi lần đi theo nhánh trái ta thêm số 0, còn theo nhánh phải thì thêm số 1; dãy số trên đường đi từ gốc đến từng ký hiệu tạo thành từ mã tương ứng. Với từ “schoolroom”, phương pháp từ dưới lên của Huffman đã bớt đi một bit, chỉ cần 26 bit thay vì 27 bit. Khi Huffman trình bày kết quả với Fano, vị giáo sư nhìn vào bài chứng minh gọn gàng, tinh tế ấy và thốt lên: “Hóa ra chỉ có thế thôi sao!”

Tối ưu trong phạm vi xác định

Vào tháng 9 năm 1952, Huffman công bố phát hiện của mình trên tập san Proceedings of the Institute of Radio Engineers (IRE) với tiêu đề “A Method for the Construction of Minimum-Redundancy Codes”. Bài báo chứng minh rằng với bất kỳ tập hợp tần suất ký hiệu cho trước nào, thuật toán từ dưới lên của ông đều tạo ra một mã tiền tố có độ dài từ mã trung bình nhỏ nhất có thể.

Dù vậy, bảo đảm toán học này đi kèm những giới hạn cụ thể. Mã hóa Huffman chỉ bảo đảm tối ưu khi mã hóa từng ký hiệu riêng lẻ dựa trên phân bố xác suất đã xác định trước. Thuật toán không thể nén mọi tệp dữ liệu tùy ý, bởi các lập luận đếm chứng minh rằng không thuật toán nén không mất dữ liệu nào có thể thu nhỏ mọi đầu vào mà không làm phình to một số đầu vào khác. Hơn nữa, vì mã hóa Huffman xử lý các ký hiệu độc lập với nhau, nó không tự phát hiện được các mẫu chuỗi gồm nhiều ký tự — đó là lý do các định dạng nén như ZIP kết hợp cây Huffman với kỹ thuật khớp chuỗi. Mã hóa Huffman cũng không thể biến JPEG thành định dạng nén không mất dữ liệu: bước lượng tử hóa của JPEG đã loại bỏ các chi tiết nhỏ trong hình ảnh trước khi mã hóa Huffman xử lý các giá trị thu được.

Huffman chưa bao giờ tìm cách đăng ký bằng sáng chế cho thuật toán của mình; Stix ghi nhận rằng phần thưởng chính mà Huffman nhận được là được miễn thi cuối kỳ. Cách xây dựng của Huffman dựa trên một nguyên lý đơn giản: kết hợp những trường hợp nhỏ nhất, rồi áp dụng chính quy tắc ấy cho bài toán đã được thu gọn. Con đường giúp ông thoát khỏi kỳ thi cuối kỳ đã bắt đầu từ chính hai ký hiệu hiếm nhất.

Bài liên quan

Đọc bằng ngôn ngữ khác: English

Nguồn