Repository logo
 
Publication

Suffix Arrays: A competitive choice for fast Lempel-Ziv Compression

dc.contributor.authorJ. Ferreira, Artur
dc.contributor.authorOliveira, Arlindo L.
dc.contributor.authorFigueiredo, Mario
dc.date.accessioned2024-11-14T09:55:57Z
dc.date.available2024-11-14T09:55:57Z
dc.date.issued2008
dc.description.abstractLossless 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.pt_PT
dc.description.versioninfo:eu-repo/semantics/publishedVersionpt_PT
dc.identifier.citationJ. 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/0001935200050012pt_PT
dc.identifier.doi10.5220/0001935200050012pt_PT
dc.identifier.isbn978-989-8111-60-9
dc.identifier.urihttp://hdl.handle.net/10400.21/17902
dc.language.isoengpt_PT
dc.publisherSciTePresspt_PT
dc.subjectLempel-Zivpt_PT
dc.subjectLossless Data Compressionpt_PT
dc.subjectSuffix Arrayspt_PT
dc.subjectSuffix Treespt_PT
dc.subjectString Matchingpt_PT
dc.titleSuffix Arrays: A competitive choice for fast Lempel-Ziv Compressionpt_PT
dc.typeconference object
dspace.entity.typePublication
oaire.citation.conferencePlacejulho 2008 - Porto, Portugalpt_PT
oaire.citation.endPage12pt_PT
oaire.citation.startPage5pt_PT
oaire.citation.titleInternational Conference on Security and Cryptography (ICSC)pt_PT
person.familyNameFerreira
person.familyNameOliveira
person.familyNameFigueiredo
person.givenNameArtur
person.givenNameArlindo
person.givenNameMario
person.identifier1049438
person.identifier3015485
person.identifier.ciencia-id091A-96FB-A88C
person.identifier.ciencia-idE718-A5FB-4F7D
person.identifier.ciencia-idED1E-A787-3569
person.identifier.orcid0000-0002-6508-0932
person.identifier.orcid0000-0001-8638-5594
person.identifier.orcid0000-0002-0970-7745
person.identifier.ridAAL-4377-2020
person.identifier.ridC-1700-2008
person.identifier.ridC-5428-2008
person.identifier.scopus-author-id35315359300
person.identifier.scopus-author-id7201929537
person.identifier.scopus-author-id34769730500
rcaap.rightsopenAccesspt_PT
rcaap.typeconferenceObjectpt_PT
relation.isAuthorOfPublication734bfe75-0c68-4cdf-8a87-2aef3564f5bd
relation.isAuthorOfPublication9438f487-5556-4774-b63c-f915ed84d8bd
relation.isAuthorOfPublicationd3d068dc-5887-4ecd-bf7f-067ef06e1943
relation.isAuthorOfPublication.latestForDiscovery734bfe75-0c68-4cdf-8a87-2aef3564f5bd

Files

Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
Suffix Arrays_AJFerreira.pdf
Size:
534.66 KB
Format:
Adobe Portable Document Format
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description: