Parsing with Suffix and Prefix Dictionaries.
Authors: Martin
Cohn and Roger
Khazan.
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.
