Utilize este identificador para referenciar este registo: http://hdl.handle.net/10400.21/568
Título: On the Suitability of Suffix Arrays for Lempel-Ziv Data Compression
Autor: Ferreira, Artur J.
Oliveira, Arlindo L.
Figueiredo, Mário A. T.
Palavras-chave: Construction
Algorithm
Data: 2009
Editora: Springer-Verlag Berlin
Citação: Ferreira A J, Oliveira A L, Figueiredo M A T. On the Suitability of Suffix Arrays for Lempel-Ziv Data Compression. E-Business and Telecommunications. 2009; 48: 267-280.
Resumo: Lossless compression algorithms of the Lempel-Ziv (LZ) family are widely used nowadays. Regarding time and memory requirements, LZ encoding is much more demanding than decoding. In order to speed up the encoding process, efficient data structures, like suffix trees, have been used. In this paper, we explore the use of suffix arrays to hold the dictionary of the LZ encoder, and propose an algorithm to search over it. We show that the resulting encoder attains roughly the same compression ratios as those based on suffix trees. However, the amount of memory required by the suffix array is fixed, and much lower than the variable amount of memory used by encoders based on suffix trees (which depends on the text to encode). We conclude that suffix arrays, when compared to suffix trees in terms of the trade-off among time, memory, and compression ratio, may be preferable in scenarios (e.g., embedded systems) where memory is at a premium and high speed is not critical.
Peer review: yes
URI: http://hdl.handle.net/10400.21/568
ISBN: 978-3-642-05196-8
ISSN: 1865-0929
Aparece nas colecções:ISEL - Eng. Elect. Tel. Comp. - Artigos

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
On the Suitability of Suffix Arrays for Lempel-Ziv Data Compression_rep.pdf51,12 kBAdobe PDFVer/Abrir


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.