self doubt on HUFFMAN closed

Question

in Huffman Code, we get extract the minimum at each time, but my minimum is creating duplicate, then which one i choose?

i am getting the same avg.no.of bits for every Huffman tree, but the problem is my tree is changing therefore representing the character also changed, if some one asks convert the message using Huffman, then ambiguity comes.

ex :- frequencies of A,B,C,D,E,F,G and H are $\frac{1}{30},\frac{1}{30},\frac{1}{30},\frac{2}{30},\frac{3}{30},\frac{5}{30},\frac{5}{30}$ and $\frac{12}{30} $

Comments

if it is not greater , just no need to change it's position

I mean , if ambiguity comes like 1,1,1 just huffman code from left to right, without changing it's position

I  want to tell, when repeating value comes , donot swap them

Add them in huffman tree as they came in  calculation without exchanging it's position

Now, see if every huffman tree give unique value

right?

---

mam,

a=1,b=1,c=1 ===> temp=2,c=1,d=2, now what should i consider taking temp and c or c and d

and why? i mean anywhere you read it? if yes please provide the link

---

then huffman tree will be

c=1,temp=2,d=2

No, It is not mentioned. But I experimented it and got correct result

U tell me, u got correct result or not??

---

when you combine c and d, first then you are tree is optimal ( i mean height of the tree is minimum )

---

why u do that? Then it will violate property of huffman coding

---

@ srestha mam, how it violating Huffman property?

we have that c=1, temp=2, d=2

i am saying there are two possibilities

i) combine c and temp

ii) combine c and d

you are saying choose 1st  one,

by ii) process we are getting minimum height tree. but i am not getting where ii) is violating Huffman coding

 

---

how height optimal for ii) ??

draw it

---

Height should be same for both

---

i am getting same avg no.of bits for both trees... but problem with height (no.of bits to represent b) and moreover if tree is changed, then representation of characters should be changed.

---

1st one is incorrect

it is violating huffman property

C should be merge left side of A,B always

---

then what about F and G?

combining them also leads to violating huffman property

---

yes F,G drawn wrong

it should be left of tree

---

mam, then the result of F and G is grater than 8

for at node 18, F and G are at left side and 8 is right side.

---

huffman coding greedy algo

always evaluate smallest 2 value first

https://www.geeksforgeeks.org/greedy-algorithms-set-3-huffman-coding/

---

link is not useful for me.....

always evaluate smallest 2 value first

you are coming from starting again... i know this point... but ambiguity comes to choose them

 

1st one is incorrect

it is violating huffman property

C should be merge left side of A,B always

this point i am not getting. 

---

When u got huffman values

1) first sort them

2) then apply greedy approach for 1st two values

No ambiguity should come

read huffman tree construction, where u get it easy

There shouldnot be any ambiguity

---

Mam, I understand that

It's depend upon STABLE property of Algorithm...

We can make any algorithm stable if we want, otherwise me can make any algorithm unstable if we want

So, in the question he have to mention that, using data structures (Heaps or something else which are using to get minimum element ) are having stable property or not.

---

Mam is these two values can be from variables and temp right?

---

Can someone please tell me that we arrange in ascending order after every iteration right then compare search min 2 then combine? Right? (Consider no repeated values) and data related to frequency is given @shaik

---

yes, @pmona

---

Ok thanks @shaik, although I have come accross quite a few questions in which I've seen this to be wrong then... for example in this image 15 is less than 18 but since they already arrange th data in ascending order they don't take 15 on left side of 18