Một thuật toán đơn giản
- Tập hợp n cây Huffman ban đầu được chuẩn bị, mỗi cây là một nút lá đơn. Giữ n cây trên một hàng đợi ưu tiên được sắp xếp theo trọng số (tần suất).
- Loại bỏ hoặc xóa hai cây đầu tiên (những cây có trọng lượng nhỏ nhất). Gộp hai cây này lại để tạo ra một cây mới có gốc gắn liền với hai cây khi còn nhỏ và trọng lượng của nó là tổng trọng lượng của hai cây con.
- Giữ cây mới này vào hàng đợi ưu tiên.
- Lặp lại các bước 2-3 cho đến khi và trừ khi tất cả các cây Huffman từng phần đã được ghép thành một.
Đó là một thuật toán tham lam:ở mỗi lần lặp, thuật toán tạo ra một quyết định "tham lam" để hợp nhất hai cây con có trọng số nhỏ nhất. Thuật toán có thể đưa ra kết quả mong muốn không?
- Bổ đề:Gọi x và y là hai ký tự có tần suất thấp nhất. Có một cây mã tối ưu trong đó x và y là anh em ruột có độ sâu nhỏ nhất bằng bất kỳ nút lá nào khác trong cây.
- Định lý:Mã Huffman được coi là mã nhị phân không có tiền tố tối ưu (Thuật toán tham lam xây dựng cây Huffman với trọng số đường dẫn bên ngoài tối thiểu cho một tập hợp các chữ cái nhất định).