Greedy algorithms for on-line data compression

We consider on-line text-compression problems where compression is done by substituting substrings according to some fixed static dictionary (code book). Due to the long running time of optimal algorithms, several heuristics have been introduced in the literature. In this paper, we continue the investigations of[3]. We complete the worst-case analysis of the longest matching algorithm and of the differential greedy algorithm for several types of special dictionaries and we derive matching lower and upper bounds for all variants of this problem