# Proving that this Huffman tree construction is valid

"Abstract":
I have recently crafted a new algorithm for constructing code trees which I believe are optimal (the same thing that is constructed using Huffman's algorithm, at Wikipedia). It is based on one observation which is in form of an illegal property (i.e. code trees with that property are not optimal) and several other propertires which aren't exactly illegal in the same sense but help recognize a more favorable code tree. This ambiguity at the end is exactly what I fail to analyze and hope someone will help me at. I will try to explain all of my notation so people with any background can understand this.

The main goal:
Produce a simple algorithm which builds an optimal code tree for a sorted set of frequencies in linear time.
The sample C++ code is here, look at the function ht.

For that sake let's say we are given a sorted array of "frequencies" $$f$$ of length $$n$$: $$f(a)\ge f(b)$$ whenever $$1\le a\le b\le n$$. (We can think of $$f(i)$$ as of the probability that the $$i$$-th symbol will occur in a string, but they are not normalized - their sum isn't 1).
The length of the code for the $$i$$-th symbol I will call $$h(i)$$.

The main observation:
The lengths of the codes should be ordered oppositely of the frequencies: $$a\le b\Rightarrow h(a)\le h(b)$$. If for some $$a we have that $$f(a)>f(b)+f(b+1)$$, then an optimal $$h$$ must satisfy $$h(a).

Now let me give the argument for proving this. Assume the opposite: $$h(a)=h(b+1)=:H$$ (we define $$H$$ to equal this). Consider the range of all indices which map to $$H$$ under $$h$$ (the preimage of $$h$$), say this range has indices $$x\le y$$. So now we have that $$h(x-1) (assuming $$x-1$$ and $$y+1$$ are valid indices, of course). We must have that $$y\ge b+1\ge a+2\ge x+2$$. Now the claim is (which I have proven, but won't write it here in attempt to keep this question short) that if we change the values of $$h(x)$$, $$h(y-1)$$ and $$h(y)$$ to $$h(x)-1$$, $$h(y-1)+1$$ and $$h(y)+1$$, then this new $$h$$ still admits a valid binary tree (code tree), which has the lower value of $$\sum f(i)h(i)$$, which is the very thing we want to minimize.

An opposite respectively holds: if for some $$a we have that $$f(a), then an optimal $$h$$ must satisfy $$h(a)+1\ge h(b)$$ (which is similar to $$h(a)+1\le h(b+1)$$ from before). This means that the values of $$h$$ can't get too high either. In some sense they are in tight relationships.

The algorithm:
Using these two observations I meditated on this procedure:

1. Set the current index, $$c$$, to $$1$$ and currect weight, $$t$$, to $$0$$.
2. While $$c\le n$$:
2.1. Find the least index $$b$$ such that $$f(a)\ge f(b-1)+f(b)$$ if such exists, otherwise set $$b=n+1$$.
2.2. Set $$h(i)$$ to $$t$$ for all $$i$$ for which $$a\le i, and then set $$c$$ to $$b$$ and increment $$t$$.

Now the problem is that the sum $$\sum2^{-h(i)}$$ should be a power of $$2$$, but this procedure doesn't guarantee it. Now, I know that I can increment some of the values of $$h$$ so that they don't cross the bounds I described in my observations. I performed this correction using this:

1. Define the $$i$$-th weigth, $$w(i)$$, to be $$2^{-h(i)}$$.
2. Calculate the sum $$S:=\sum w(i)$$.
3. Find the smallest power of $$2$$, $$P$$, which is strictly greater than $$S$$, and then calculate their difference $$D:=P-S$$.
4. Set the currect index, $$c$$, to $$1$$.
Now we proceed to cut the $$D$$... down to $$0$$.
5. While $$c\le n$$:
5.1. If $$D\ge w(c)$$, set $$D$$ to $$D-w(c)$$ and decrement $$h(c)$$.
5.2. Increment $$c$$.
6. (renormalization) Recalculate $$w$$'s and $$S$$. $$S$$ will be a power of $$2$$: $$S=2^m$$ for some non-negative integer $$m$$.
7. Add $$m$$ to every $$h(i)$$.

This should produce the optimal lengths $$h$$ of binary codes for frequencies $$f$$. That is my hypothesis. I would appreciate if someone could tell me some illegal property and then analyze my algorithm to see whether it avoids it or not, ultimately maybe prove it or give a counter-example. My reach is the discovery of these tight bounds, but I fail to confidently analyze the rest.

• In your observation proof, when $h(x)$ is changed to $h(x)−1$. You are decreasing the length of the codeword, but what exactly would be the valid codeword for $x$? May 22 at 22:24
• @InuyashaYagami Hi. I have just realized that a good simplification of that whole argument is contained in this statement: For a given array $h$ of codeword lengths, there exist codewords with these lengths if and only if $\sum_{i=1}^n2^{-h(i)}=1$. Can you now see when and why there can be constructed the actual codewords? Maybe I should edit the question to include this... May 22 at 22:30