Greedy algorithms for on-line data compression

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

doi:10.1006/jagm.1997.0885

Greedy algorithms for on-line data compression

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

Research output: Contribution to journal › Article › Academic › peer-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 language	English
Pages (from-to)	274-289
Number of pages	16
Journal	Journal of Algorithms
Volume	25
Issue number	2
DOIs	https://doi.org/10.1006/jagm.1997.0885
Publication status	Published - 1997

Access to Document

10.1006/jagm.1997.0885

Cite this

@article{c84e80a8b11a4e348c5a175cd90e62c5,

title = "Greedy algorithms for on-line data compression",

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.",

author = "J. B{\'e}k{\'e}si and G. Galambos and U. Pferschy and G.J. Woeginger",

year = "1997",

doi = "10.1006/jagm.1997.0885",

language = "English",

volume = "25",

pages = "274--289",

journal = "Journal of Algorithms",

issn = "0196-6774",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - Greedy algorithms for on-line data compression

AU - Békési, J.

AU - Galambos, G.

AU - Pferschy, U.

AU - Woeginger, G.J.

PY - 1997

Y1 - 1997

N2 - 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.

AB - 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.

U2 - 10.1006/jagm.1997.0885

DO - 10.1006/jagm.1997.0885

M3 - Article

SN - 0196-6774

VL - 25

SP - 274

EP - 289

JO - Journal of Algorithms

JF - Journal of Algorithms

IS - 2

ER -

Greedy algorithms for on-line data compression

Abstract

Access to Document

Fingerprint

Cite this