Using partial-matching approach with sequitur for context-based coding
Gopal Lakhani, R. Sethuraman · 2004
This paper presents a Sequitur, which is a powerful realization of the grammar-based text compression approach. First, it derives a context-free grammar, which generates the given input as its only language. Then it represents the grammar as a single sequence of symbols, where a symbol represents either a rule head or an alphabet, and finally it uses arithmetic coder to code the sequence. Sequitur encodes each symbol individually. A modified approach is to code a rule symbol in the context of the last alphabet of the preceding rule symbol. Thereby, the partial matching (PM) approach is followed to realize code reduction. The crux of this approach is to maintain multiple dictionaries, each containing rules that begin with the same alphabet.