What are applications of alphabetic trees?

Question

Earlier this week a paper was released describing an algorithm for building optimal alphabetic ternary trees. The alphabetic property as described on Wikipedia as

Alphabetic trees are Huffman trees with the additional constraint on order, or, equivalently, search trees with the modification that all elements are stored in the leaves. Faster algorithms exist for optimal alphabetic binary trees (OABTs).

From this, I understand that an alphabetic binary tree will produce shorter paths from root to element for elements that have been inserted into the tree more times than elements that haven't, and the alphabetic property would be described the same way for a ternary tree.

I haven't been able to find a lot of discussion about applications for the alphabetic property outside of Huffman coding but it is not a requirement to implement the algorithm. Are there any applications where the alphabetic property would be a requirement, and if not, are there any benefits to guaranteeing the alphabetic property that justifies increased implementation complexity?

Answer 1

You use alphabetic trees when you need nodes to keep their input order in the resulting code. Huffman trees are used for coding purposes, and alphabetic trees for storing data and for allowing quick search and edit.

One example application is storing textual data in alphabetic order. The complete works of Shakespeare were stored in an OAT (optimal alphabetic tree), which was constructed using the Hu-Tucker algorithm. See here for another $O(n \log n)$ algorithm for constructing OATs.

Answer 2

Huffman codes are often used to efficiently encode a small alphabet, such as all bytes. In this case, the codewords can be stored in a lookup table. What happens if the source data consists of strings rather than indices? For example, suppose that we are interested in constructing a prefix code for all words in the English language. Given a word, how do we convert it to an index that can be looked up in a table?

Prefix codes can be alternatively thought of as decision trees. Every internal node has two children, and the corresponding pair of edges are labeled "0" and "1". The codeword corresponding to a leaf is the concatenation of labels on the path from the root to the leaf. We can think of each internal node as a query, the answer to which determines whether we take the edge labeled "0" or the one labeled "1".

The queries constructed by Huffman's algorithm can be completely arbitrary, which makes it hard to implement them. In contrast, the queries in an alphabetic tree correspond to simple comparisons: we can identify each internal node with an object $x_i$ in the domain, and given an input $x$ to be encoded, we take the edge labeled "0" if $x \leq x_i$, and the edge labeled "1" if $x > x_i$. By storing the $x_i$ in the node, we facilitate efficient encoding.

For more on this perspective, see the paper Twenty (simple) questions.