GREEDY ALGORITHMS FOR ONLINE DATA-COMPRESSION

We consider on-lint text-compression problems where compression is don e by substituting substrings according to some fixed static dictionary (code book). Due to the long running time of optimal algorithms, seve ral heuristics have been introduced in the literature. In this paper, we continue the investigations of Katajainen and Raita [3]. We complet e the worst-case analysis of the longest matching algorithm and of the differential greedy algorithm for several types of special dictionari es and we derive matching low-er and upper bounds for all variants of this problem. (C) 1997 Academic Press.