Một thuật toán đơn giản
- Chuẩn bị tập hợp n cây Huffman ban đầu, mỗi cái là một nút lá đơn. Đưa n cây vào hàng đợi ưu tiên (priority queue) sắp xếp theo trọng số (tần suất).
- Loại bỏ (remove) hai cây đầu tiên (nhỏ nhất trọng số). Kết hợp hai cây này tạo cây mới có gốc với hai cây con, trọng số bằng tổng trọng số hai cây con.
- Đưa cây mới này vào hàng đợi ưu tiên.
- Lặp lại bước 2-3 cho đến khi tất cả cây Huffman phần tử đã được gộp thành một.
Đây là thuật toán tham lam (greedy): mỗi lần lặp, thuật toán quyết định "tham lam" gộp hai cây con có trọng số nhỏ nhất. Có thể thuật toán cho kết quả mong muốn?
- Bổ đề (Lemma): Gọi x và y là hai ký tự ít xuất hiện nhất. Tồn tại cây mã tối ưu mà trong đó x và y là anh em (siblings) có độ sâu không lớn hơn bất kỳ lá nào khác trong cây.
- Định lý (Theorem): Mã Huffman là mã tiền tố nhị phân tối ưu (Thuật toán tham lam xây dựng cây Huffman với trọng số đường đi bên ngoài tối thiểu cho tập chữ cái cho trước).