Lossy variants of the Ziv-Lempel family of encoders are built traditionally around the iterated quest for best matches within an assigned fidelity. Most of the resulting algorithms are inherently superlinear and not easy to implement and analyze. On the other hand, it is well known that any lossy scheme of low computational complexity must have the drawback that it cannot yield the minimal distortion which can be achieved by the optimal data compression algorithm specifically tailored for that case. This paper concentrates on parses of guaranteed low time performance, in which phrases are all distinct and generated mechanically by self-correlations of the source set forth by the parsing process. The goal of the paper is to describe the basic algorithm and some of its variants, show their good performance and latitude of practical applicability, and possibly stimulate in-depth analytical treatment, which is made particularly hard by the fact that the underlying processes are not stationary.

Compressing with Collapsible Tries

APOSTOLICO, ALBERTO;
2006

Abstract

Lossy variants of the Ziv-Lempel family of encoders are built traditionally around the iterated quest for best matches within an assigned fidelity. Most of the resulting algorithms are inherently superlinear and not easy to implement and analyze. On the other hand, it is well known that any lossy scheme of low computational complexity must have the drawback that it cannot yield the minimal distortion which can be achieved by the optimal data compression algorithm specifically tailored for that case. This paper concentrates on parses of guaranteed low time performance, in which phrases are all distinct and generated mechanically by self-correlations of the source set forth by the parsing process. The goal of the paper is to describe the basic algorithm and some of its variants, show their good performance and latitude of practical applicability, and possibly stimulate in-depth analytical treatment, which is made particularly hard by the fact that the underlying processes are not stationary.
2006
Proceedings of Information Theory Workshop
Information Theory Workshop
9781424400355
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11577/1557539
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 0
  • OpenAlex ND
social impact