Practical Use of The Warm-up Algorithm on Length-Restricted Coding
Ruy Luiz Milidiú, Artur Alves Pessoa, Eduardo Sany Laber · McGill-Queen's University Press eBooks · 1997
. In this paper we present an efficient implementation of the WARM-UP Algorithm for the construction of length-restricted prefix codes. This algorithm has O(n log n + n log wn) worst case time complexity, where n is the number of symbols of the source alphabet and wn is the largest weight of the alphabet. An important feature of the proposed algorithm is its implementation simplicity. The algorithm is basically a selected sequence of Huffman trees construction for modified weights. The proposed implementation has the same time complexity, but requires only additional O(1) space. We also report some empirical experiments showing that this algorithm provides good compression and speed performances. 1 Introduction An important problem in the field of Coding and Information Theory is the Binary Prefix Code Problem. Given an alphabet \\Sigma = fa 1 ; : : : ; ang and a corresponding set of positive weights fw 1 ; : : : ; wng, the problem is to find a prefix code for \\Sigma that mi...