The purpose of this thesis is to study the behavior of
the Hu-Tucker algorithm for building Optimal Alphabetic Binary
Search Trees (OABST), to design an efficient implementation,
and to evaluate the performance of the algorithm, and the implementation.
The three phases of the algorithm are described and
their time complexities evaluated. Two separate implementations for
the most expensive phase, Combination, are presented achieving
time and O
) space complexity.
The break even point between them is experimentally established
and the complexities of the implementations are compared against their
theoretical time complexities.
The electronic version of ``The Complete Works of William Shakespeare''
is compressed using the Hu-Tucker algorithm and other popular
compression algorithms to compare the performance of the
The experiments justified the price that has to be paid to
implement the Hu-Tucker algorithm. It is shown that
an efficient implementation can process extremely large data sets
relatively fast and can achieve optimality close to the Optimal
Binary Tree, built using the Huffman algorithm, however
the OABST can be used in both encoding and decoding processes,
unlike the OBT where an additional mapping mechanism is needed for
the decoding phase.