检索结果-内蒙古大学图书馆

optimal prefix codes and Huffman codes

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 2003年第6期80卷 727-742页

作者： Long, DY Jia, WJ Li, M Zhongshan Univ Dept Comp Sci Guangzhou 510275 Peoples R China Chinese Acad Sci State Key Lab Informat Secur Beijing 100039 Peoples R China City Univ Hong Kong Dept Comp Sci Kowloon Hong Kong Peoples R China Natl Univ Singapore Sch Comp Singapore 119260 Singapore

Existence of the optimal prefix codes is shown in this paper. Relationship between the optimal prefix code and the Huffman code is also discussed. We prove that all Huffman codes are optimal prefix codes and conversely optimal prefix codes need not be Huffman codes. Especially, the problem of whether the optimal prefix code has to be maximal is presented. Although for information source alphabets of being not greater than four letters we show that an optimal prefix code must be maximal, it remains to be an open problem in general. As seen from Huffman codes, optimal prefix codes are used not only for statistical modeling but also for dictionary methods. Moreover, it is obtained that the complexity of breaking an optimal prefix code is NP-complete from the viewpoint of computational difficulty.

关键词： data transmission and compression Huffman code optimal prefix code maximal prefix code

来源：评论

学校读者我要写书评

暂无评论

A general framework for codes involving redundancy minimization

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2006年第1期52卷 344-349页

作者： Baer, MB Stanford Univ Dept Elect Engn Stanford CA 94305 USA

A framework with two scalar parameters is introduced for various problems of finding a prefix code minimizing a coding penalty function. The framework encompasses problems previously proposed by Huffman, Campbell, Nath, and Drmota and Szpankowski, shedding light on the relationships among these problems. In particular, Nath's range of problems can be seen as bridging the minimum average redundancy problem of Huffman with the minimum maximum pointwise redundancy problem of Drmota and Szpankowski. Using this framework, two linear-time Huffman-like algorithms are devised for the minimum maximum pointwise redundancy problem, the only one in the framework not previously solved with a Huffman-like algorithm. Both algorithms provide solutions common to this problem and a subrange of Nath's problems, the second algorithm being distinguished by its ability to find the minimum variance solution among all solutions common to the minimum maximum pointwise redundancy and Nath problems. Simple redundancy bounds are also presented.

关键词： Huffman algorithm minimax redundancy optimal prefix code Renyi entropy unification

来源：评论

学校读者我要写书评

暂无评论

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2011年第4期57卷 2278-2290页

作者： Baer, Michael B. Vista Res Monterey CA 93940 USA

This paper presents new lower and upper bounds for the compression rate of binary prefix codes optimized over memoryless sources according to various nonlinear codeword length objectives. Like the most well-known redundancy bounds for minimum average redundancy coding-Huffman coding-these are in terms of a form of entropy and/or the probability of an input symbol, often the most probable one. The bounds here, some of which are tight, improve on known bounds of the form L is an element of [H, H + 1), where H is some form of entropy in bits (or, in the case of redundancy objectives, 0) and L is the length objective, also in bits. The objectives explored here include exponential-average length, maximum pointwise redundancy, and exponential-average pointwise redundancy (also called d(th) exponential redundancy). The first of these relates to various problems involving queueing, uncertainty, and lossless communications;the second relates to problems involving Shannon coding and universal modeling. Also explored here for these two objectives is the related matter of individual codeword length.

关键词： Huffman codes optimal prefix code queueing Renyi entropy Shannon codes worst case minimax redundancy

来源：评论

学校读者我要写书评

暂无评论

Source coding for quasiarithmetic penalties

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2006年第10期52卷 4380-4393页

作者： Baer, Michael B. Stanford Univ Dept Elect Engn Stanford CA 94305 USA

Whereas Huffman coding finds a prefix code minimizing mean codeword length for a given finite-item probability distribution, quasiarithmetic or quasilinear coding problems have the goal of minimizing a generalized mean of the form phi(-1)(Sigma(i)p(i)phi(l(i))), where l(i) denotes the length of the ith codeword, P-i denotes the corresponding probability, and phi is a monotonically increasing cost function. Such problems, proposed by Campbell, have a number of diverse applications. Several cost functions are shown here to yield quasiarithmetic problems with simple redundancy bounds in terms of a generalized entropy. A related property, also shown here, involves the existence of optimal codes: For "well-behaved" cost functions, optimal codes always exist for (possibly infinite-alphabet) sources having finite generalized entropy. An algorithm is introduced for finding binary codes optimal for convex cost functions. This algorithm, which can be extended to other minimization utilities, can be performed using quadratic time and linear space. This reduces the computational complexity of a problem involving minimum delay in a queue, allows combinations of previously considered problems to be optimized, and greatly expands the set of problems solvable in quadratic time and linear space.

关键词： generalized entropies generalized means Huffman codes optimal prefix code quasiarithmetic means queueing

来源：评论

学校读者我要写书评

暂无评论

Huffman coding with an infinite alphabet

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 1996年第3期42卷 977-984页

作者： Kato, A Han, TS Nagaoka, H Univ of Electro-Communications Tokyo Jpn

A new type of sufficient condition is provided for a probability distribution on the nonnegative integers to be given an optimal D-ary prefix code by a Huffman-type algorithm, In the justification of our algorithm, we introduce two new (essentially one) concepts as the definition of the ''optimality'' of a prefix D-ary code, which are shown to be equivalent to that defined in the traditional way, These new concepts of the optimality are meaningful even for the case where the Shannon entropy H(P) diverges.

关键词： optimal prefix code Huffman algorithm Shannon entropy infinite alphabet coding of integers

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：