A really simple approximation of smallest grammar
In this paper we present a really simple linear time algorithm constructing a context free grammar of size 4 g log 3 2 N g for the input string, where N is the size of the input string and g the size of the optimal grammar generating this string. The algorithm works for arbitrary size alphabets, but the running time is linear assuming that the alphabet S of the input string can be identified with numbers from 1 N c for some constant c. Algorithms with such an approximation guarantee and running time are known, however all of them were non trivial and their analyses were involved. The here presented algorithm computes the LZ77 factorisation and transforms it in phases to a grammar. In each phase it maintains an LZ77 like factorisation of the word with at most factors as well as additional O letters, where was the size of the original LZ77 factorisation. In one phase in a greedy way (by a left to right sweep and a help of the factorisation) we choose a set of pairs of consecutive letters to be replaced with new symbols, i.e. nonterminals of the constructed grammar. We choose at least 2/3 of the letters in the word and there are O many different pairs among them. Hence there are O log N phases, each of them introduces O nonterminals to a grammar. A more precise analysis yields a bound 4 log N As g this yields the desired bound g 4 g log N g
Theor. Comput. Sci.