DocumentCode
3265553
Title
Parsing with suffix and prefix dictionaries
Author
Cohn, Martin ; Khazan, Roger
Author_Institution
Dept. of Comput. Sci., Brandeis Univ., Waltham, MA, USA
fYear
1996
fDate
Mar/Apr 1996
Firstpage
180
Lastpage
189
Abstract
We show that greedy left-to-right (right-to-left) parsing is optimal w.r.t. a suffix (prefix) dictionary. To exploit this observation, we show how to construct a static suffix dictionary that supports on-line, linear-time optimal parsing. From this we derive an adaptive on-line method that yields compression comparing favorably to LZW
Keywords
adaptive signal processing; data compression; grammars; LZW dictionary; adaptive online method; greedy left to right parsing; greedy right to left parsing; parsing; prefix dictionaries; static suffix dictionary; suffix dictionaries; Application software; Compression algorithms; Compressors; Computer science; Cost function; Data compression; Dictionaries; Encoding; Satellites;
fLanguage
English
Publisher
ieee
Conference_Titel
Data Compression Conference, 1996. DCC '96. Proceedings
Conference_Location
Snowbird, UT
ISSN
1068-0314
Print_ISBN
0-8186-7358-3
Type
conf
DOI
10.1109/DCC.1996.488323
Filename
488323
Link To Document