Can a huffman tree enconding be different from one person to anoher?

Question

I need to make a huffman tree for a college project, but I am really confused about how it works.I implemented the coding part of the huffman tree but it is different from http://huffman.ooz.ie/ all the time.

It can be different from one person coding to another,but correct?

Answer 1

Yes.

First off, you can arbitrarily assign 0 and 1, or 1 and 0, to each pair of branches of the tree to get equally valid codes.

Second, when finding the lowest frequency group at each step of the Huffman algorithm, you can run into cases where the lowest frequency is shared by three or more groups, or the second lowest frequency is shared by two or more groups. You then have two or more choices for which groups to combine in that step. In that case you can end up with different adjacent symbols, and even topologically distinct trees, all of which are equally optimal.

For the linked example, there are five frequency one symbols to choose from in the first step, resulting in ten different choices for the first pairing. Then there are three frequency one symbols to choose from in the second step, with three different choices for the second pairing. So right off the bat there are 30 different trees with assigned symbols that could be constructed.

Those are all topologically equivalent. It gets more interesting at the third step, where there are three choices for the second-lowest frequency, two of which are branches and one being a leaf. So there are two different topologies that can result.

In all, that particular set of frequencies can produce 24 topologically distinct trees, times a very large number of different symbol and bit assignments for each topology. So in fact the probability that you end up with exactly the same tree as shown in the example should be quite small!

Here are the 24 possible topologies for the frequencies {1, 1, 1, 1, 1, 2, 3, 3, 3, 3, 3, 4, 5, 5, 6, 7, 9, 10, 12, 16}: