2
$\begingroup$

Can a valid Huffman tree be generated if the frequency of words is same for all of them?

Example :

Value     | Frequency
--------------------
Google    | 2
Yahoo     | 2
Microsoft | 2
Amazon    | 2  
$\endgroup$

migrated from stats.stackexchange.com May 10 '15 at 13:32

This question came from our site for people interested in statistics, machine learning, data analysis, data mining, and data visualization.

2
$\begingroup$

Yes. When creating a Huffman tree, if you ever find you need to select from a set of objects with the same frequencies, then just select objects from the set at random - it will have no effect on the effectiveness of the algorithm.

Of course, one might question why you're bothering to build a Huffman tree if you know all the frequencies are the same - I can tell you what the optimal encoding is.

$\endgroup$
2
$\begingroup$

Yes. Whenever identical frequencies occur, the Huffman procedure will not result in a unique code book, but all the possible code books lead to an optimal encoding.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.