Optimal prefix-free binary code with several codewords already assigned

The classic Huffman algorithm, as Wikipedia states, finds an optimal prefix-free binary code with minimum expected codewords length, given a set of symbols and their weights. Now, suppose codewords for some (but not all) symbols are already assigned (maybe in a suboptimal way). How should we assign remaining codewords to the remaining symbols so as to minimize the minimum expected codewords length, assuming that there exists at least one binary sequence such that none existing codewords have it as their prefix, and neither of the existing codewords is its prefix?

I wonder if there's a known solution to this problem. Yet I have been trying to develop an own one borrowing ideas from this proof.

• Very nice problem. – gnasher729 Apr 13 at 21:54
• There's a subtle and easily fixed error in this proof: "If there is more than one symbol that has the lowest frequency, then take two that have the biggest depth" should be "If there is more than one pair of satisfying symbols, then take two that have the biggest depth". Otherwise, there might be a uniquely lowest-frequency symbol, which we could assign to $y$, and two or more second-lowest-frequency symbols at distinct depths, all as deep as or deeper than $y$. We could then choose the one of the less-deep to be $w$ and hit case 3, but "By our choice of w, f(w) < f(z)" would fail. – j_random_hacker Apr 14 at 17:09

"Ordinary" Huffman is suboptimal

Let's call a symbol "free" if it has not yet been assigned any codeword. Here's an easy counterexample to the optimality of running the ordinary Huffman algorithm on the set of free symbols:

Suppose we have three symbols $$a, b, c$$, with frequencies $$0.5, 0.25, 0.25$$, of which $$b$$ and $$c$$ are free; $$a$$ has already been assigned the codeword $$00$$. Then the unique minimum-size tree in which $$b$$ and $$c$$ -- the lowest-frequency free symbols -- are siblings is

  /\
/ /\
a b  c


with expected codeword length $$0.5*2 + 0.25*2 + 0.25*2 = 2$$, which is strictly greater than that of either of the two trees in which they are not siblings:

  /\        /\
/\ c      /\ b
a  b      a  c


which each have expected codeword length $$0.5*2 + 0.25*2 + 0.25*1 = 1.75$$.