| Ký hiệu | Số lần | Mã | Bit | Tổng bit |
|---|
Công cụ dựng mã Huffman
Tại sao một chữ cái phổ biến như n lại phải tốn nhiều bit như một chữ hiếm như z? Mã hóa Huffman cho các ký hiệu thường gặp mã ngắn và các ký hiệu hiếm mã dài, và làm điều đó theo cách tốt nhất có thể. Hãy gõ một văn bản hoặc chọn một ví dụ rồi xây dựng cây Huffman của nó từng bước một: hai cây nhẹ nhất ghép lại dưới một nút mới, lặp đi lặp lại, cho đến khi chỉ còn một cây. Khi đó mỗi đường đi từ đỉnh tạo thành một mã, và bạn có thể theo dõi từng ký hiệu qua các bit đã mã hóa. Hãy gõ một văn bản hoặc chọn một ví dụ. Mỗi ký hiệu khởi đầu là một lá cùng số lần xuất hiện của nó. Đi qua từng bước xây dựng: mỗi bước ghép hai cây nhẹ nhất dưới một nút mới mang tổng của chúng, cho đến khi chỉ còn một cây. Khi đó đường đi từ đỉnh xuống một lá cho ra mã của lá đó, 0 cho nhánh trái và 1 cho nhánh phải. Nhấp vào một lá, một hàng hoặc một đoạn bit để theo dõi một ký hiệu, rồi so sánh tổng số bit với mã độ dài cố định và với entropy.
Cách nó hoạt động
- Gõ hoặc dán một văn bản, hoặc chọn một ví dụ như ABRACADABRA hay MISSISSIPPI RIVER.
- Đi qua từng bước xây dựng bằng nút “Bước tiếp theo”, hoặc nhấn “Phát”: mỗi bước ghép hai cây nhẹ nhất dưới một nút mang tổng của chúng.
- Khi cây đã hoàn chỉnh, nhấp vào một lá, một hàng của bảng hoặc một đoạn bit để theo dõi một ký hiệu, rồi so sánh các tổng trong các ô.
Cây được xây dựng như thế nào
Đếm số lần xuất hiện của mỗi ký hiệu và biến mỗi ký hiệu thành một cây chỉ có một lá, với trọng số là số lần đó. Rồi lặp lại một bước đơn giản: lấy hai cây có trọng số nhỏ nhất và treo chúng dưới một nút mới có trọng số bằng tổng của chúng. Mỗi bước bớt đi một cây, nên sau n − 1 bước với n ký hiệu chỉ còn lại một cây. Các ký hiệu hiếm được ghép trước và nằm sâu bên dưới; các ký hiệu phổ biến được ghép sau và nằm gần đỉnh.
Đọc mã
Đi xuống từ đỉnh: mỗi bước sang trái thêm một số 0, mỗi bước sang phải thêm một số 1. Đường đi tới một lá chính là mã của ký hiệu đó. Vì các ký hiệu chỉ nằm ở lá, không mã nào là phần đầu của mã khác, nên một chuỗi bit có thể được giải mã mà không cần dấu phân cách: đi theo các bit xuống cây, và mỗi khi tới một lá, ghi ký hiệu của nó rồi bắt đầu lại từ đỉnh. Với ABRACADABRA, Huffman cần 23 bit, so với 33 bit của mã cố định 3 bit mỗi chữ cái.
Câu hỏi thường gặp
Vì sao mã Huffman là tốt nhất có thể?
Trong tất cả các mã gán cho mỗi ký hiệu một chuỗi bit nguyên riêng, không mã nào có tổng ngắn hơn với cùng các số lần xuất hiện. Chứng minh đi theo chính cách xây dựng: trong một mã tối ưu, 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, và ghép chúng lại để lại một bài toán nhỏ hơn cùng loại. Tổng số bit bằng tổng trọng số của mọi nút trong của cây.
Mã tiền tố là gì?
Là mã trong đó không từ mã nào là phần đầu của một từ mã khác, chẳng hạn 0, 10, 110 và 111. Tính chất đó cho phép bộ giải mã đọc một dòng bit mà không cần dấu phân cách, vì nó luôn biết một từ mã kết thúc ở đâu. Mọi mã Huffman đều là mã tiền tố: các ký hiệu chỉ nằm ở lá của cây.
Cây Huffman có duy nhất không?
Không hẳn: khi hai cây có cùng trọng số, cây nào được lấy trước cũng được, và trái phải có thể đổi chỗ cho nhau. Những lựa chọn khác nhau cho ra những mã khác nhau, nhưng tổng số bit luôn như nhau. Công cụ này luôn xử lý trường hợp bằng nhau theo cùng một cách, nên một văn bản luôn cho ra cùng một cây.
Huffman tiến gần entropy đến mức nào?
Độ dài mã trung bình ít nhất bằng entropy và cao hơn nó chưa tới một bit. Nó bằng đúng entropy khi mọi xác suất đều là lũy thừa của một nửa, như ví dụ số lần giảm một nửa. Mã hóa số học và các bộ mã hóa khoảng (range coder) hiện đại tránh được giới hạn bit nguyên và còn tiến gần hơn nữa.
Văn bản của tôi có được gửi đi đâu không?
Không. Cây và các mã được tính trong trình duyệt của bạn, và văn bản của bạn nằm trong bộ nhớ cục bộ của trình duyệt này.
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.
Tới trình chỉnh sửa