trang chủ / đề bài / icpcwf08_e

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ó 5 ký tự A, B, C, D và E với tần suất lần lượt là 10%, 14%, 31%, 25% và 20%: đầu tiên ghép A (10) với B (14) thành cây 24; tiếp theo ghép E (20) với cây 24 thành cây 44; sau đó ghép D (25) với C (31) thành cây 56; cuối cùng ghép cây 44 với cây 56 thành cây 100. 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 0 trên mỗi nhánh trái và 1 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 14% thành 13% và 31% thành 32%, 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 100%). 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ụ 30% 70% và 70% 30%) 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 n (2≤n≤20) là số ký tự khác nhau trong tài liệu đã nén, tiếp theo là n 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 0, 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ố 0.

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ừ 1) 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

  • 2≤n≤20; các mã là các xâu khác rỗng gồm ký tự 0 và 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á 100 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 8 lá ít nhất là 27=128>100, 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ố {a,100−a} với 1≤a≤50. Bộ 2: các bộ x≤y≤z với x+y+z=100 và z≤x+y. Bộ 3: các bộ a≤b≤c≤d với tổng 100 và d≤a+b. Bộ 4: các bộ a≤b, c, d với tổng 100, a+b≤c và a+b+c≤d.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0