What is the second step in Huffman coding?

Answer 1

Step 2: Sort the probability list in descending order of probability.

The full procedure can be summarised as follows:

1. Compute the probability of each symbol in the input stream.
2. Sort the probability list in descending order.
3. Repeat while there are two or more items in the probability list:
   1. Create a new parent.
   2. Extract the last item and place it on the left of the parent.
   3. Extract the last item and place it on the right of the parent.
   4. Set the parent's probability to the sum of its children's probabilities.
   5. Insert the parent into the list using insertion sort.
4. Extract the one remaining item (the root of the Huffman tree).
5. Recursively traverse the left and right of the root and its children, computing the prefix as you go. Store the prefix in each leaf as it is encountered, and copy the leaf back to the probability list.
6. Sort the list by probability.
7. Output the input stream length.*
8. Output the encoded tree from the root (0 bit for a parent, 1 bit for a leaf followed by its symbol).
9. Read a symbol from the input stream.
10. Locate the symbol in the probability table.
11. Output the prefix.
12. Repeat from step 9 until EOF.
13. Pad any remaining bits in the final byte with 0.
14. Flush the output buffer.

*Some implementations use a pseudo-symbol rather than the input stream length to determine when to stop decoding. The pseudo-symbol must be placed at the end of the probability list after step 2 and must be output prior to padding the output step 13.