Huffman Encoding

Question

Q29.
4. A file contains the following characters and their corresponding frequencies as shown below:
\[
\mathrm{a}: 45, \mathrm{~b}: 13, \mathrm{c}: 12, \mathrm{~d}: 16, \mathrm{e}: 9, \mathrm{f}: 5
\]

If we use Huffman coding for data comparisons, what is the difference between maximum and minimum number of comparisons?

Comments

136??

---

Here is a post which explaing Huffman Coding. May be once you understand the concept, you can find it for yourself :)

http://techieme.in/huffman-decoding/

---

could you please explain how you calculated that?

---

@gabbar bro how u calculated miniumum and maximum no of comparision?

---

there is n1 and n2 characters total  n1+n2
worst case : n-1 comparison
Best case : n1 comparisons

 i.e. n1=5 and n2=9   worst case=5+9-1 Best case=5
Build Huffman Tree and each stage calculate comparisons.
THis way i have done ! not sure

---

i think the algorithm of OPTIMAL MERGE PATTERN will play some role here

Answer 1

construct huffman tree max number of comparisions nothing but max heights of the tree

min number of comparisions nothing but min height.(like no comparisions in a b-tree)

Comments

bro i think its 4-1=3

---

how is minimum number of comparisons equal to 2?