Grammar-based codes: A new class of universal lossless source codes

被引：226
作者：
Kieffer, JC [1 ]
Yang, EH
机构：
[1] Univ Minnesota, Dept Elect & Comp Engn, Minneapolis, MN 55455 USA
[2] Univ Waterloo, Dept Elect & Comp Engn, Waterloo, ON N2L 3G1, Canada
来源：
IEEE TRANSACTIONS ON INFORMATION THEORY | 2000年 / 46卷 / 03期
基金：
美国国家科学基金会; 加拿大自然科学与工程研究理事会;
关键词：
Chomsky hierarchy; context-free grammars; entropy; Kolmogorov complexity; lossless coding; redundancy; universal coding;
D O I：
10.1109/18.841160
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
We investigate a type of lossless source code called a grammar-based code, which, in response to any input data string a: over a fixed finite alphabet, selects a contest-free grammar G(x) representing x in the sense that x is the unique string belonging to the language generated by G(x), Lossless compression of a: takes place indirectly,ia compression of the production rules of the grammar G(x), It is shown that, subject to some mild restrictions, a grammar-based code is a universal code with respect to the family of finite-state information sources over the finite alphabet. Redundancy bounds for grammar-based codes are established. Reduction rules for designing grammar-based codes are presented.
引用
收藏
页码：737 / 754
页数：18
相关论文
共 27 条
[1]  
Aho Alfred V., 1986, ADDISON WESLEY SERIE
[2]   SOURCE ENCODING USING SYNTACTIC INFORMATION SOURCE MODELS [J].
CAMERON, RD .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1988, 34 (04) :843-850
[3]  
COOK CM, 1976, INFORM SCIENCES, V10, P59, DOI 10.1016/0020-0255(76)90061-X
[4]  
Cover T. M., 2005, ELEM INF THEORY, DOI 10.1002/047174882X
[5]  
COVER TM, 1973, IEEE T INFORM THEORY, V19, P73, DOI 10.1109/TIT.1973.1054929
[6]  
CSISZAR I, 1981, INFORMATION THEORY C
[7]   UNIVERSAL NOISELESS CODING [J].
DAVISSON, LD .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1973, 19 (06) :783-795
[8]  
Deller Jr J. R., 1993, DISCRETE TIME PROCES
[9]   SOME STRUCTURE THEOREMS FOR STATIONARY PROBABILITY-MEASURES ON FINITE STATE SEQUENCES [J].
HOBBY, C ;
YLVISAKER, ND .
ANNALS OF MATHEMATICAL STATISTICS, 1964, 35 (02) :550-&
[10]  
Hopcroft J. E., 2007, Introduction to Automata Theory, Languages and Computation
123