Algorithm 428 Hu-Tucker Minimum Redundancy Alphabetic Coding Method [Z].

The article discusses an algorithm for Hu-Tucker minimum redundancy alphabetic coding method. This algorithm implements the Hu-Tucker method of variable length minimum redundancy alphabetic binary encoding. The symbols of the alphabet are considered to be an ordered forest of n terminal nodes. Two nodes in an ordered forest are said to be tentative-connecting if the sequence of nodes between the two given nodes is either empty or consists entirely of nonterminal nodes. An interval of nodes each pair of which is a tentative-connecting pair is called a tentative-connecting string. The original forest will, after a finite number of steps, be connected into a single tree. This tree will not, in general, satisfy the order-preserving requirement. However, it is shown the path lengths are feasible for the construction of a tree which does satisfy this requirement and is, moreover, minimal in cost. The present procedure finds a minimal cost tree whose longest path length and total path length are minimal.