Paper Info
Title
Efficient Implementation of the WARM-UP Algorithm for the Construction of Length-Restricted Prefix Codes
Abstract
Given an alphabet Σ = {a1, ..., an} with a corresponding list of positive weights {w1, ..., wn} and a length restriction L, the length-restricted prefix code problem is to find, a prefix code that minimizes Σni=1 wili, where li, the length of the codeword assigned to ai, cannot be greater than L, for i = 1, ..., n. In this paper, we present an efficient implementation of the WARM-UP algorithm, an approximative method for this problem. The worst-case time complexity of WARMUP is O(n log n + n log wn), where wn is the greatest weight. However, some experiments with a previous implementation of WARM-UP show that it runs in linear time for several practical cases, if the input weights are already sorted. In addition, it often produces optimal codes. The proposed implementation combines two new enhancements to reduce the space usage of WARM-UP and to improve its execution time. As a result, it is about ten times faster than the previous implementation of WARM-UP and overcomes the LRR Package Method, the faster known exact method.
Year
DOI
Venue
1999
10.1007/3-540-48518-X_1
ALENEX
Keywords
Field
DocType
warm-up show,warm-up algorithm,execution time,n log wn,n log n,length-restricted prefix codes,efficient implementation,proposed implementation,worst-case time complexity,linear time,previous implementation,prefix code
Discrete geometry,Discrete mathematics,Combinatorics,Algorithm complexity,Algorithm,Prefix,Execution time,Code word,Time complexity,Prefix code,Mathematics,Alphabet
Conference
Volume
ISSN
ISBN
1619
0302-9743
3-540-66227-8
Citations 
PageRank 
References 
6
0.74
15
Authors
3
Name
Order
Citations
PageRank
Ruy Luiz Milidiú119220.18
Artur Alves Pessoa227024.30
Eduardo Sany Laber322927.12