Parsing with suffix and prefix dictionaries

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.