Decoding from code lengths
A DEFLATE archive does not store the Huffman tree. At the start of a block only the code lengths of all the characters are written, and the recipient restores the codes themselves by a common rule, the canonical code:
- the characters are ordered by code length, and with equal lengths by Unicode code point;
- the first character gets a code of all zeros;
- each next one gets the previous code plus one, written in binary; if the length has grown, zeros are appended on the right up to the new length.
For example, with lengths A — 1, B — 2, C — 2 the codes are A = 0, B = 10, C = 11. You are given a description of the code and a bit stream. Restore the text.
One of the tests is a piece of the first volume of War and Peace in the Russian original, encoded with the Huffman code of the whole novel: 165 characters, codes from 3 to 21 bits long.
Input
The first line holds the number of characters n (1 ≤ n ≤ 1000). Then come n lines: a character’s Unicode code point and the length of its code, from 1 to 30. The lengths define a valid prefix code. The last line holds a stream of zeros and ones of length up to 106; it consists of a whole number of codes.
Output
The decoded text. It may contain spaces and line breaks; print them as they are.
Examples
Example 1
10 32 3 44 4 1072 2 1074 3 1076 4 1077 4 1085 4 1086 4 1088 3 1090 4 11010001010110111110100110001011111000001100101001011010001011111000001111000101011100111001100
на дворе трава, на траве дрова
Example 2
3 65 1 66 2 67 2 0101100
ABCAA
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 9 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
First restore the codes by the rule in the statement and check on the first example: «а» has length 2, the space, «в» and «р» 3, the rest 4. What code will the comma get?
2Hint 2
The trickiest place is moving to a greater length. After the three-bit codes 010, 011, 100 the next number is 101, and a zero is appended to it: 1010. If the zero is not appended, you get 0101, and this code begins with 010: the prefix property is gone.
3Hint 3
You can put the codes into a dictionary “code → character” and read the stream, collecting bits into a string. This works, but the string grows and is compared at every bit. Codes of one length are consecutive numbers: can the character be found by subtraction?
4The idea
For each length L remember the first code of this length first[L], how many there are count[L], and where they start in the canonical order. While reading the stream, keep a number code and the length len of the piece read. If code − first[len] is less than count[len], a whole code has been read, and the character is number first_index[len] + (code − first[len]) in the canonical order. Otherwise read the next bit.
5Walkthrough
The first codes are computed as in RFC 1951: first[L] = (first[L − 1] + count[L − 1]) · 2. This is the same rule “plus one and append zeros”, written at once for a whole length.
Why is the check code − first[len] < count[len] enough? In a canonical code all the codes of length L are numerically smaller than the length-L beginnings of longer codes: longer codes come later, and their first L bits are a number no smaller than first[L] + count[L]. And the number read cannot be smaller than first[L]: then its beginning would be a whole shorter code, and we would already have stopped.
DEFLATE decoders work exactly like this, only several bits at a time: they look at the next bits with a table and find the character in one access.
5+Solution
6Complexity
Preparation is O(n log n) for the sort. Decoding is O(1) per bit, O(B) in all for a stream of B bits. A “string → character” dictionary also gives O(B) accesses, but each with a string of up to 30 bits.
7Common mistakes
- No shift when the length grows. The codes stop being prefix codes, and decoding falls apart at the first long code.
- Ordering by character only. The canonical order is by length first, and only for equal lengths by code point.
- One character. Its code is the single bit 0; a stream of 1000 zeros is 1000 characters.
- A line break in the text. Character number 10 is an ordinary character of the code; print it, do not skip it.