Unpack LZW
An old format stores text as LZW phrase numbers. The packer started with a dictionary of 256 single bytes and went through the text: extended the current phrase while it was in the dictionary, output the number of the longest known phrase and added that phrase to the dictionary, extended by the next byte. The dictionary is not transmitted with the compressed data: the decompressor must build exactly the same one while reading the numbers. Write it.
The rules of this packer:
- numbers 0–255 are single bytes; number 256 is CLEAR, the command “the dictionary is reset”; new phrases get the numbers 257, 258 and so on;
- the dictionary has at most 4096 numbers (0–4095): when it is full, new phrases are not added until CLEAR arrives;
- after CLEAR the dictionary again consists of single bytes, and the next new phrase gets number 257.
For example, the numbers 97 98 257 259 258 261 260 decompress into abababababababab. The tests include War and Peace in Russian and in English, the genome of the phage lambda and a file compressed the way the compress program does it: resetting the dictionary when compression gets worse.
Input
The first line holds the count of numbers m (1 ≤ m ≤ 300,000). Then come m numbers separated by spaces and newlines. It is guaranteed that this is the output of a packer with the rules described.
Output
The decompressed bytes unchanged (they form text in UTF-8).
Examples
Example 1
16 84 79 66 69 79 82 78 79 84 257 259 261 266 260 262 264
TOBEORNOTTOBEORTOBEORNOT
Example 2
7 97 98 257 259 258 261 260
abababababababab
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
The decompressor is a step behind the packer. The packer adds the phrase “previous + first byte of the next” at the moment it outputs the number of the previous one; the decompressor learns that byte only after reading the next number. So it adds the new phrase when it has read the next number: the previous decompressed phrase plus the first byte of the current one.
2Hint 2
Decompress 97 98 257 259 from the example by hand. On number 259 something will go wrong. What exactly, and what can this number equal?
3The idea
If a number is not yet in the dictionary, it is exactly the number the packer created on the previous step and used right away. It equals “the previous phrase + its own first byte”: by construction it starts with the previous phrase, and its last byte is its own first byte, that is, the first byte of the previous one. This happens on strings of the form KwKwK, where K is a byte and w a string: “abababa”, “aaaa”.
4Walkthrough
The dictionary is a list of phrases. For each number: CLEAR, cut the list down to 257 elements and forget the previous phrase; a known number, take the phrase; an unknown one, the previous phrase plus its first byte. Output the phrase and, if there is a previous one and the dictionary has fewer than 4096 numbers, add “previous + first byte of the current one”. This is lzw_decode from the article’s listing.
In the sixth test, on fifty thousand “a”s, the special case fires on every number until the dictionary fills up: the packer creates the phrases “a”, “aa”, “aaa”… and uses them at once.
4+Solution
5Complexity
O(the length of the result): each phrase is copied to the output once, and a new phrase is a copy of the previous one plus a byte; if phrases are stored as a reference to a prefix, the memory is O(m) too.
6Common mistakes
- No special case. The decompressor crashes on the first number not yet in the dictionary, already in the second example.
- The dictionary does not freeze. If phrases are added after 4096 numbers, the numbering drifts from the packer’s, and everything after that decompresses into garbage.
- After CLEAR. The first number after a reset is a single byte, and no new phrase may be added on it: there is no previous phrase yet.