Title :
Dynamic Shannon coding
Author_Institution :
Dept. of Comput. Sci., Toronto Univ., Ont., Canada
Abstract :
This paper presents a new algorithm, called dynamic Shannon coding, that uses at most (H + 1)m + O(nlogm) bits to encode string S. The key idea is to smooth the relative frequencies of characters when computing their weights. It also shows that dynamic Shannon coding can be easily modified to restrict the maximum length of any codeword in the encoding produced. The analysis of dynamic Shannon coding is much simpler than the analysis of dynamic Huffman coding.
Keywords :
Huffman codes; bit string encoding; character frequency; codeword length; dynamic Huffman coding; dynamic shannon coding; weight computation; Computer science; Councils; Data compression; Data structures; Entropy; Frequency; Heuristic algorithms; Huffman coding; Upper bound;
Conference_Titel :
Data Compression Conference, 2004. Proceedings. DCC 2004
Print_ISBN :
0-7695-2082-0
DOI :
10.1109/DCC.2004.1281516
