Publication Abstract

Cohn M., and Khazan, R. Parsing with Suffix and Prefix Dictionaries. Proc. Data Compression Conference (DCC '96) March 31-April 3, 1996, Snowbird, Utah. IEEE Computer Society Press, Los Alamitos, California.

Abstract

We show that greedy left-to-right (right-to-left) parsing is optimal with respect to 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.