Greedy algorithms for on-line data compression

J. Békési, G. Galambos, U. Pferschy, G.J. Woeginger

    Research output: Contribution to journalArticleAcademicpeer-review

    4 Citations (Scopus)

    Abstract

    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.
    Original languageEnglish
    Pages (from-to)274-289
    Number of pages16
    JournalJournal of Algorithms
    Volume25
    Issue number2
    DOIs
    Publication statusPublished - 1997

    Fingerprint Dive into the research topics of 'Greedy algorithms for on-line data compression'. Together they form a unique fingerprint.

    Cite this