2008/10/28 by Gagie, Travis
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.0810.5064
We show how to build an alphabetic minimax tree for a sequence (W = w1, >..., wn) of real weights in (O (n d log log n)) time, where d is the number of distinct integers (\lceil wi \rceil). We apply this algorithm to building an alphabetic prefix code given a sample.