DocumentCode :
2743471
Title :
Dynamic Shannon coding
Author :
Gagie, Travis
Author_Institution :
Dept. of Comput. Sci., Toronto Univ., Ont., Canada
fYear :
2004
fDate :
23-25 March 2004
Firstpage :
540
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Data Compression Conference, 2004. Proceedings. DCC 2004
ISSN :
1068-0314
Print_ISBN :
0-7695-2082-0
Type :
conf
DOI :
10.1109/DCC.2004.1281516
Filename :
1281516
Link To Document :
بازگشت