1
$\begingroup$

A (memoryless) source generates symbols $a_1, a_2, \dots, a_n$ with relative frequencies $f_1, f_2, \dots, f_n$. Assume that the frequencies are all positive.

An optimal prefix-free code for this source can be determined using most variants of the Huffman algorithm or possibly other algorithms.

While there are many different optimal prefix-free codes for this source, they all have the same expected codeword length:

$$\frac{f_1 l_1 + f_2 l_2 + \dots + f_n l_n}{f_1 + f_2 + \dots + f_n}$$

Here, $l_i$ denotes the length, in bits, of the codeword assigned to symbol $a_i$.

Call two such frequency lists equivalent if the expected codeword lengths of the optimal prefix-free codes that they determine are equal.

Problem

Describe an algorithm that, given list of strictly positive frequencies, produces an equivalent list, consisting only of (positive) integers and whose largest element is minimal.

Partial Answer

In the hopes of encouraging progress towards a full solution, I'll post a sketch of a partial solution that I thought of but couldn't complete.

Any full binary tree with $n$ leaves determines a prefix code for $n$ symbols. If the leaves are labelled with the given frequencies, and the internal nodes are labelled with the sum of the frequencies of their children then the sum of the labels of the internal nodes (including the root), divided by the root label, gives the expected word length of the code.

If the tree was constructed using the Huffman algorithm, then the expected word length is minimal (among prefix codes).

Start by constructing a Huffman tree for the given frequencies.

If we modify the tree in such a way that the sum of the leaf labels is preserved and the sum of the internal node labels is preserved then the resulting tree still determines an optimal prefix code.

For example, for any two leaves at the same level, increasing one leaf label and decreasing the other, by the same amount, preserves necessary invariants.

If the two leaves don't have the same level then the situation is a little more complicated, but modifications can still be made to the leaf labels that preserve the invariants.

It remains only to:

  1. define a sufficiently rich list of modifications that will suffice to "optimize" the tree (i.e. minimizes the maximum leaf label).
  2. give an algorithm for applying modifications from this list in the right order to get an optimal tree.
$\endgroup$
4
  • 1
    $\begingroup$ You want the frequencies to be positive integers? Frequencies are always between zero and one, inclusive, so the only way to do that is to have only one symbol, that symbol having frequency one. $\endgroup$ Mar 2, 2022 at 4:32
  • $\begingroup$ While probabilities need to lie between 0 and 1, in this context, frequencies don't. For example, in the sequence: aaabbaccba, the symbols a,b,c occur with frequencies 5,3,2, respectively. $\endgroup$
    – sitiposit
    Mar 2, 2022 at 14:21
  • 2
    $\begingroup$ You speak of "relative frequencies", which, I assume are the empirical frecuencies divided by the total message length. Hence they should be between zero and one, and sum up to one. $\endgroup$
    – leonbloy
    Mar 2, 2022 at 16:24
  • $\begingroup$ relative manupulations will not go anywhere as we have the two following examples with same expected length of 2: [1,1,1,1] and [5,3,2,2]. $\endgroup$
    – mnz
    Jul 22, 2023 at 19:08

0

You must log in to answer this question.

Browse other questions tagged .