Let $X,Y,Z,W$ be words with vector frequency $(x,y,z,w)$ , Find an optimal code.

Question

Let $X,Y,Z,W$ be words with vector frequency $(x,y,z,w)$ such that $x\leq y\leq z\leq w$.

Find certain requirements about $x,y,z,w$ such that $W=00,Z=01,Y=10,X=11$ is an optimal code.

My solution :

Using Huffman coding, I think the solution is to demand $z,w\leq x+y$

The tree is :

In a case that $z,w > x+y$ the next tree is the appropriate tree:

Therefore the optimal code is $W=0,Z=10,Y=110,X=111$

Is this correct ?

Answer 1

You are right, lets run the huffman optimization. First the algorithm picks the two minimal probabilities x and y and produces x+y.

For second step, there are multiple ways that things can go either x+y < z < w or z < x+y < w or z < w < x+y. The first two cases generate your second figure!

So if it merges z and w the last step will be trivial.

Edit (Approach 2): Another way to approach this can be calculating the expected length of each code. For first one $E[c]=2$. For second one, $E[c]=w+2 z + 3 x + 3 y = 2(w+z+x+y) + x + y - w = 2 + (x+y-w)$.
Now you can see the same result.

So in general if w < x+y then the fixed length code is optimal.