𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Greedy Algorithms for On-Line Data Compression

✍ Scribed by József Békési; Gábor Galambos; Ulrich Pferschy; Gerhard J Woeginger

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
191 KB
Volume
25
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

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 w x Katajainen and Raita 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. ᮊ 1997 Academic Press

1. Introduction

Recent advances in computer technologyᎏboth in the field of hardware and in the field of softwareᎏstrongly require large amounts of data to be moved between various components or to be stored in bounded capacity

📜 SIMILAR VOLUMES

A Greedy On-Line Algorithm for thek-Trac
A Greedy On-Line Algorithm for thek-Track Assignment Problem
✍ U Faigle; W Kern; W.M Nawijn 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 107 KB

Given a collection I I of n jobs that are represented by intervals, we seek a maximal feasible assignment of the jobs to k machines such that not more than Ž . c M intervals overlap pairwise on any machine M and that a job is only assigned to a machine if it fits into one of several prescribed time

Application of new systems techniques an
Application of new systems techniques and the greedy algorithm for reliability data reconstruction
✍ Hamid R. Jafari; Fouad N. Jalbout; Thomas F. Hassett 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 254 KB 👁 2 views

The main objective of this paper is to apply new systems techniques for condensing information that is contained in a reliability data set. These techniques, augmented with the Greedy Algorithm, were used to develop an algorithm for reduced data set reconstruction. The techniques go beyond tradition