Mã Huffman
Đề bài
Mô tả
Dan McAmbi là thành viên của một đội phản gián tinh nhuệ và vừa thu được một phần nội dung của một tệp chứa thông tin sống còn đối với lợi ích quốc gia. Tệp này đã được nén bằng mã hóa Huffman. Không may, phần tệp mà Dan có chỉ chứa các mã Huffman, không chứa dữ liệu đã nén. Vì mã Huffman dựa trên tần suất của các ký tự trong thông điệp gốc, sếp của Dan cho rằng có thể khai thác được thông tin nào đó nếu Dan đảo ngược quá trình mã hóa Huffman để tìm lại tần suất ký tự từ các mã Huffman. Phản ứng tự nhiên của Dan là cùng một bộ mã có thể sinh ra từ rất nhiều phân bố tần suất khác nhau, nhưng sếp của anh không bị thuyết phục bởi lập luận này. Vì vậy Dan nhờ bạn đưa ra một bằng chứng chắc chắn hơn để trình sếp.
Mã hóa Huffman là một phương pháp nén dữ liệu tối ưu nếu biết trước tần suất tương đối của các chữ cái trong văn bản cần nén. Phương pháp này trước hết xây dựng một cây Huffman như sau. Bắt đầu với một rừng các cây, mỗi cây chỉ gồm một nút chứa một ký tự của văn bản và tần suất của nó (giá trị ký tự chỉ dùng ở các lá của cây kết quả). Ở mỗi bước, thuật toán lấy hai cây có giá trị tần suất nhỏ nhất (chọn tùy ý nếu có nhiều cây bằng nhau) và thay chúng bằng một cây mới, tạo thành bằng cách nối hai cây đó làm cây con trái và cây con phải của một nút gốc mới. Tần suất của gốc mới bằng tổng tần suất của hai cây con. Quá trình lặp lại cho đến khi chỉ còn một cây. Ví dụ, với một tệp chỉ có ký tự A, B, C, D và E với tần suất lần lượt là , , , và : đầu tiên ghép A () với B () thành cây ; tiếp theo ghép E () với cây thành cây ; sau đó ghép D () với C () thành cây ; cuối cùng ghép cây với cây thành cây . Cây Huffman thu được như hình dưới (số trong mỗi nút là tần suất, nhãn trên cạnh là bit của mã).
dot
graph {
node [shape=circle];
r [label="100"];
x [label="44"];
y [label="56"];
z [label="24"];
E [label="20\nE"];
A [label="10\nA"];
B [label="14\nB"];
D [label="25\nD"];
C [label="31\nC"];
r -- x [label="0"];
r -- y [label="1"];
x -- E [label="0"];
x -- z [label="1"];
z -- A [label="0"];
z -- B [label="1"];
y -- D [label="0"];
y -- C [label="1"];
}
Sau khi xây dựng cây Huffman, gán mã Huffman cho các ký tự như sau: ghi trên mỗi nhánh trái và trên mỗi nhánh phải. Đọc các nhãn từ gốc xuống tới một ký tự cho ta mã Huffman của ký tự đó. Cây ở trên cho các mã Huffman sau: A là 010, B là 011, C là 11, D là 10 và E là 00.
Trong bài này, cây có tần suất nhỏ hơn luôn trở thành cây con trái của cây mới. Nếu hai cây có tần suất bằng nhau thì cây nào làm cây con trái cũng được. Lưu ý rằng điều này có nghĩa là với một số phân bố tần suất, có nhiều bộ mã Huffman hợp lệ.
Cùng một bộ mã Huffman có thể thu được từ nhiều phân bố tần suất khác nhau: đổi thành và thành , bạn vẫn nhận được cùng một cây và do đó cùng một bộ mã. Dan muốn bạn viết chương trình xác định tổng số cách phân biệt để nhận được một bộ mã Huffman cho trước, giả sử mọi tỉ lệ phần trăm đều là số nguyên dương (tổng bằng ). Lưu ý rằng hai phân bố tần suất chỉ khác nhau về thứ tự các tỉ lệ phần trăm (ví dụ và ) không được coi là khác nhau.
Dữ liệu vào
Dữ liệu vào gồm nhiều bộ test. Mỗi bộ test nằm trên một dòng, bắt đầu bằng một số nguyên dương () là số ký tự khác nhau trong tài liệu đã nén, tiếp theo là xâu nhị phân là mã Huffman của từng ký tự. Bạn có thể giả sử rằng các xâu này đúng là một bộ mã Huffman của một phân bố tần suất nào đó (dù vậy, với các giả thiết bổ sung của bài, đáp án vẫn có thể bằng , xem bộ test cuối của ví dụ 1).
Sau bộ test cuối cùng là một dòng chứa số .
Dữ liệu ra
Với mỗi bộ test, in ra một dòng gồm số thứ tự của bộ test (bắt đầu từ ) và số phân bố tần suất phân biệt có thể sinh ra bộ mã Huffman đã cho, theo đúng định dạng trong ví dụ.
Ràng buộc
- ; các mã là các xâu khác rỗng gồm ký tự
0và1, là các lá của một cây nhị phân đầy đủ (mỗi nút trong có đúng hai con). - Mỗi file dữ liệu vào có không quá bộ test.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 010 011 11 10 00 8 00 010 011 10 1100 11010 11011 111 8 1 01 001 0001 00001 000001 0000001 0000000 0 |
Case 1: 3035 Case 2: 11914 Case 3: 0 |
Bộ 1 là bộ mã của cây trong hình. Bộ 3: mỗi lá có mã kết thúc bằng 1 là con phải, nên tần suất của nó không nhỏ hơn cây con trái anh em (tổng mọi lá sâu hơn). Do đó tổng tần suất ít nhất gấp đôi sau mỗi tầng đi lên: tổng của lá ít nhất là , không có phân bố nào thỏa mãn. |
| 2 0 1 3 0 10 11 4 00 01 10 11 4 1 01 001 000 0 |
Case 1: 50 Case 2: 233 Case 3: 598 Case 4: 2600 |
Bộ 1: các phân bố với . Bộ 2: các bộ với và . Bộ 3: các bộ với tổng và . Bộ 4: các bộ , , với tổng , và . |
Bình luận