Sequitur algorithm

Sequitur, also called the Nevill-Manning and Witten algorithm, is a recursive algorithm developed by Craig Nevill-Manning and Ian H. Witten in 1997. It reads a sequence of discrete symbols and infers a hierarchical structure from it in the form of a context-free grammar, working in linear space and time. It builds the grammar by replacing phrases that repeat in the input with new rules, which gives a concise representation of the sequence, and so it can be used in data compression software. Two constraints keep the grammar efficient. Digram uniqueness means no pair of adjacent symbols may occur more than once in the grammar, so a repeated pair is replaced by a new rule. Rule utility means every rule must be used more than once on the right-hand sides of the grammar, so a rule used only once is removed and its contents are put back in place. For example the sequence abcab produces the grammar S goes to AcA with A going to ab. A reference implementation is available in C++, Java and other languages.