咨询与建议

看过本文的还看了

相关文献

该作者的其他文献

文献详情 >Efficient construction of mini... 收藏

Efficient construction of minimum-redundancy codes for large alphabets

作     者:Moffat, A Turpin, A 

作者机构:Univ Melbourne Dept Comp Sci Parkville Vic 3052 Australia 

出 版 物:《IEEE TRANSACTIONS ON INFORMATION THEORY》 (IEEE Trans. Inf. Theory)

年 卷 期:1998年第44卷第4期

页      面:1650-1657页

核心收录:

学科分类:0808[工学-电气工程] 08[工学] 0701[理学-数学] 0812[工学-计算机科学与技术(可授工学、理学学位)] 

基  金:Collaborative Information Technology Research Institute Australian Research Council, ARC 

主  题:adaptive algorithm Huffman code length-limited code minimum-redundancy code package-merge algorithm prefix-free code text compression 

摘      要:We consider the problem of calculating minimum-redundancy codes for alphabets in which there is significant repetition of symbol weights. On a sorted-by-weight alphabet of n symbols and r distinct symbol weights we show that a minimum-redundancy prefix code can be constructed in O (r + rlog(n/r)) time, and that a minimum-redundancy L-bit length-limited prefix code can be constructed in O(Lr + Lrlog(n/r)) time. When I is small relative to n-which is necessarily the case for most practical coding problems on large alphabets-these bounds represent a substantial improvement upon the best previous algorithms for these two problems, which consumed O(n) time and O(nL) time, respectively. The improved algorithms are also space-efficient.

读者评论 与其他读者分享你的观点

用户名:未登录
我的评分