| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 534.66 KB | Adobe PDF |
Advisor(s)
Abstract(s)
Lossless compression algorithms of the Lempel-Ziv (LZ) family are widely used in a variety of applications.
The LZ encoder and decoder exhibit a high asymmetry, regarding time and memory requirements, with the
former being much more demanding. Several techniques have been used to speed up the encoding process;
among them is the use of suffix trees. In this paper, we explore the use of a simple data structure, named
suffix array, to hold the dictionary of the LZ encoder, and propose an algorithm to search the dictionary.
A comparison with the suffix tree based LZ encoder is carried out, showing that the compression ratios are
roughly the same. The ammount of memory required by the suffix array is fixed, being much lower than the
variable memory requirements of the suffix tree encoder, which depends on the text to encode. We conclude
that suffix arrays are a very interesting option regarding the tradeoff between time, memory, and compression
ratio, when compared with suffix trees, that make them preferable in some compression scenarios.
Description
Keywords
Lempel-Ziv Lossless Data Compression Suffix Arrays Suffix Trees String Matching
Citation
J. Ferreira, A.; L. Oliveira, A. and A. T. Figueiredo, M. (2008). SUFFIX ARRAYS - A Competitive Choice for Fast Lempel-Ziv Compressions. In Proceedings of the International Conference on Signal Processing and Multimedia Applications (ICETE 2008) - SIGMAP; ISBN 978-989-8111-60-9, SciTePress, pages 5-12. DOI: 10.5220/0001935200050012
Publisher
SciTePress