Correctness of Constructing Optimal Alphabetic Trees Revisited

Abstract:

Several new observations which lead to new correctness proofs of
two known algorithms (Hu-Tucker and Garsia-Wachs) for construction
of optimal alphabetic trees are presented. A generalized version
of the Garsia-Wachs algorithm is given. Proof of this generalized
version works in a structured and illustrative way and clarifies
the usually poorly-understood behavior of both the Hu-Tucker and
Garsia-Wachs algorithms. The generalized version permits any
non-negative weights, as opposed to strictly positive weights
required in the original Garsia-Wachs algorithm. New local
structural properties of optimal alphabetic trees are given. The
concept of well-shaped segment (a part of an optimal tree)
is introduced. It is shown that some parts of the optimal tree are
known in advance to be well-shaped, and this implies correctness of
the algorithms rather easily. The crucial part of the correctness
proof of the Garsia-Wachs algorithm, namely the structural
theorem, is identified. The correctness proof of the Hu-Tucker
algorithm consists of showing a very simple mutual simulation
between this algorithm and the Garsia-Wachs algorithm. For this
proof, it is essential to use the generalized version of
Garsia-Wachs algorithm, in which an arbitrary locally minimal pair
is processed, not necessarily the rightmost minimal pair. Such a
generalized version is also needed for parallel implementations.
Another result presented in this paper is the clarification of the
problem of resolving ties (equalities between weights of items)
in the Hu-Tucker algorithm. This is related to the proof, by
simulation, of correctness of the Hu-Tucker algorithm. It is shown
that the condition that there are no ties may generally be assumed
without harm and that, essentially, the Hu-Tucker algorithm avoids
ties automatically.