How many bits the text takes
An archivist wants to know in advance how much space a text will take if it is encoded with a Huffman code. The code itself is not needed, only the total: how many bits all the characters of the text will take together if each character has its own binary code, no code is the beginning of another, and the code lengths are chosen in the best way. Service data, the code table and headers, are not counted.
It is known how many times each character occurs. If the text has only one character, it still needs a code of at least one bit.
Among the tests are the characters of War and Peace and of its English translation, the words of the novel and the letters of the genome of phage lambda.
Input
The first line holds the number of distinct characters n (1 ≤ n ≤ 200,000). The second holds n numbers: how many times each character occurs, from 1 to 109.
Output
One number: the smallest total number of bits.
Examples
Example 1
5 15 7 6 6 5
87
Example 2
1 42
42
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 12 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 best code lengths are given by the Huffman code. But you do not have to build the tree and walk it to find the depths of the leaves.
2Hint 2
Each gluing of two trees with weights a and b lowers all the leaves of both trees by one level. By how many bits does the encoded text get longer?
3Hint 3
The answer to the previous hint: by exactly a + b, since every occurrence of every character from these trees gets one more bit.
4The idea
The cost of a Huffman code equals the sum of the weights of all the gluings. This can also be seen from the tree: the weight of an internal node is how many times the character codes pass through it, and each such pass is one bit. So a heap of numbers is enough: take out the two smallest, add their sum to the answer and put the sum back.
5Walkthrough
n − 1 times: two extractions from the heap, an addition, an insertion. The answer for the characters of War and Peace is 14,119,218 bits, exactly what the listing from the article computes.
The first example is one where the top-down way comes out worse. Shannon–Fano splits the frequencies 15, 7, 6, 6, 5 into {15, 7} and {6, 6, 5}, with codes 00, 01, 10, 110, 111 and 89 bits in all. Huffman glues 5 + 6 = 11, 6 + 7 = 13, 11 + 13 = 24, 15 + 24 = 39: the sum is 87, and the frequent character has a one-bit code.
With one character there are no gluings, but a code of zero bits will not do: the recipient will not know how many characters the text has. The answer is its number of occurrences.
5+Solution
6Complexity
O(n log n) with a heap. If the frequencies are sorted, two queues and O(n) after sorting are enough: the gluing sums come out non-decreasing.
7Common mistakes
- Splitting from the top. The Shannon–Fano code is not always optimal (the first example).
- 32 bits. In the ninth test the answer is about 2·1015; even the sum of two frequencies may not fit in
int32. In Go useint64. - Floating-point numbers.
float64holds integers exactly only up to 253 ≈ 9·1015; that is enough here, but the habit is dangerous. - One character. The gluing loop runs zero times, and the answer 0 is wrong.
- Sorting once. After a gluing the sum must go back into the heap in its place: if you just glue neighbours of a sorted list from left to right, the tree becomes a caterpillar.