New algorithms and lower bounds for sequential-access data compression

Gagie T (2009)
Bielefeld (Germany): Bielefeld University.

Bielefelder E-Dissertation | Englisch
 
Download
OA
Autor*in
Gagie, Travis
Gutachter*in / Betreuer*in
Abstract / Bemerkung
This thesis concerns sequential-access data compression, i.e., by algorithms that read the input one or more times from beginning to end. In one chapter we consider adaptive prefix coding, for which we must read the input character by character, outputting each character's self-delimiting codeword before reading the next one. We show how to encode and decode each character in constant worst-case time while producing an encoding whose length is worst-case optimal. In another chapter we consider one-pass compression with memory bounded in terms of the alphabet size and context length, and prove a nearly tight tradeoff between the amount of memory we can use and the quality of the compression we can achieve. In a third chapter we consider compression in the read/write streams model, which allows us passes and memory both polylogarithmic in the size of the input. We first show how to achieve universal compression using only one pass over one stream. We then show that one stream is not sufficient for achieving good grammar-based compression. Finally, we show that two streams are necessary and sufficient for achieving entropy-only bounds.
Stichworte
Datenkompression , Sequentieller Zugriff , ,
Jahr
2009
Page URI
https://pub.uni-bielefeld.de/record/2303240

Zitieren

Gagie T. New algorithms and lower bounds for sequential-access data compression. Bielefeld (Germany): Bielefeld University; 2009.
Gagie, T. (2009). New algorithms and lower bounds for sequential-access data compression. Bielefeld (Germany): Bielefeld University.
Gagie, Travis. 2009. New algorithms and lower bounds for sequential-access data compression. Bielefeld (Germany): Bielefeld University.
Gagie, T. (2009). New algorithms and lower bounds for sequential-access data compression. Bielefeld (Germany): Bielefeld University.
Gagie, T., 2009. New algorithms and lower bounds for sequential-access data compression, Bielefeld (Germany): Bielefeld University.
T. Gagie, New algorithms and lower bounds for sequential-access data compression, Bielefeld (Germany): Bielefeld University, 2009.
Gagie, T.: New algorithms and lower bounds for sequential-access data compression. Bielefeld University, Bielefeld (Germany) (2009).
Gagie, Travis. New algorithms and lower bounds for sequential-access data compression. Bielefeld (Germany): Bielefeld University, 2009.
Alle Dateien verfügbar unter der/den folgenden Lizenz(en):
Copyright Statement:
Dieses Objekt ist durch das Urheberrecht und/oder verwandte Schutzrechte geschützt. [...]
Volltext(e)
Access Level
OA Open Access
Zuletzt Hochgeladen
2019-09-25T06:17:55Z
MD5 Prüfsumme
d2601b2bc84bf445a049bb2258c083e8


Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Suchen in

Google Scholar