A combinatorial approach to Golomb forests

Optimal binary prefix-free codes for infinite sources with geometrically di stributed frequencies, e.g., P = {p(i)(I - p)}(i=0)(infinity) 0 < p < 1, we re first (implicitly) suggested by Golomb over 30 years ago in the context of run-length encodings. Ten years later Gallager and Van Voorhis exhibited such optimal codes for all values of p. These codes were derived by using the Huffman encoding algorithm to build optimal codes for finite sources an d then showing that the finite codes converge in a very specific sense to t he infinite one. In this note, we present a new combinatorial approach to s olve the same problem, one that does not use the Huffman algorithm, but ins tead treats a coding tree as an infinite sequence of integers and derives p roperties of the sequence. One consequence of this new approach is a comple te characterization of all of the optimal codes; in particular, it shows th at for all p, 0 < p < 1, except for an easily describable countable set, th ere is a unique optimal code, but for each p in this countable set there ar e an uncountable number of optimal codes. Another consequence is a derivati on of infinite codes for geometric sources when the encoding alphabet is no longer restricted to be the binary one. A final consequence is the extensi on of the results to optimal forests instead of being restricted to optimal trees. (C) 2001 Elsevier Science B.V. All rights reserved.