DocumentCode
2087435
Title
Design of context-free grammars for lossless data compression
Author
Kieffer, John C. ; Yang, En-Hui
Author_Institution
Dept. of Electr. & Comput. Eng., Minnesota Univ., Minneapolis, MN, USA
fYear
1998
fDate
22-26 Jun 1998
Firstpage
84
Lastpage
85
Abstract
Any context-free grammar G generates a language L(G). We are interested in context-free grammars G in which L(G) consists of exactly one string. Given a data string a over a finite alphabet and a context-free grammar G such that L(G)={x} one can reduce G to a simpler grammar G´ for which L(G´)={x} and for which certain constraints are satisfied. One then losslessly compresses x by losslessly compressing the grammar G´. The redundancy performance of this compression algorithm based upon reduced grammars is discussed
Keywords
context-free grammars; data compression; encoding; compression algorithm; context-free grammars design; data string; encoding; finite alphabet; language; lossless data compression; reduced grammars; redundancy performance; Arithmetic; Compression algorithms; Data compression; Decoding; Production;
fLanguage
English
Publisher
ieee
Conference_Titel
Information Theory Workshop, 1998
Conference_Location
Killarney
Print_ISBN
0-7803-4408-1
Type
conf
DOI
10.1109/ITW.1998.706446
Filename
706446
Link To Document