# Existence of incremental algorithm for (canonical) prefix-free codes

## Short version

Given

• the $N$ code lengths of an optimal prefix-free code $L[1..N]$ for $N$ unknown weights $W[1..N]$ of known sum $S$, and
• $N'$ new weights $W'[1..N']$ all larger than the weights of $W$,

is it possible to compute the code lengths of an optimal prefix-free code for the union of $W$ and $W'$ knowing only $S$, $W'$, and a finite amount of values from $W$ (such as the min and max)?

After a long time taking the existence of such an algorithm for granted, I now suspect it does not exist, but my mind is still foggy from assuming for so long the contrary, and I was hoping that someone with a fresher view could produce a small counter-example and clarify my mind. (This is NOT an assignment given to students, but I think it would make a nice one... if there is a clear answer to it.)

## Motivation

Among other consequences, it would prove whether the convoluted algorithm used to compute canonical prefix-free codes (compute prefix-free code, extract code lengths, forget prefix-free code, rebuild canonical prefix-free code from code lengths) can or cannot be made incremental (which would have simplified various other results).

## Background

In 1964, Schwartz et al. (1964-ACMCom-GeneratingACanonicalPrefixEncoding-SchwartzKallick), introduced the concept of canonical prefix-free code in which "the numerical values of the codes are monotone increasing and each code has the smallest possible numerical value consistent with the requirement that the code is not the prefix of any other code". They described how to compute such codes by computing first the Huffman's code, then deducing from it an optimal vector of code lengths, and then computing from the latter an optimal prefix-free canonical code, "iteratively by assigning codes to the words in order of decreasing rank".