  A method is presented for constructing a Tunstall code that is linear time in
the number of output items. This is an improvement on the state of the art for
non-Bernoulli sources, including Markov sources, which require a (suboptimal)
generalization of Tunstall's algorithm proposed by Savari and analytically
examined by Tabus and Rissanen. In general, if n is the total number of output
leaves across all Tunstall trees, s is the number of trees (states), and D is
the number of leaves of each internal node, then this method takes O((1+(log
s)/D) n) time and O(n) space.
