Show simple item record

Authordc.contributor.authorNogueira Nunes, Daniel 
Authordc.contributor.authorLouza, Felipe 
Authordc.contributor.authorGog, Simon 
Authordc.contributor.authorAyala-Rincon, Mauricio 
Authordc.contributor.authorNavarro, Gonzalo 
Admission datedc.date.accessioned2019-05-31T15:20:02Z
Available datedc.date.available2019-05-31T15:20:02Z
Publication datedc.date.issued2018
Cita de ítemdc.identifier.citationData Compression Conference Proceedings, 2018
Identifierdc.identifier.issn10680314
Identifierdc.identifier.other10.1109/DCC.2018.00012
Identifierdc.identifier.urihttps://repositorio.uchile.cl/handle/2250/169427
Abstractdc.description.abstractWe introduce GCIS, a grammar compression algorithm based on the induced suffix sorting algorithm SAIS, presented by Nong et al. in 2009. Our solution builds on the factorization performed by SAIS during suffix sorting. We construct a context-free grammar on the input string which can be further reduced into a shorter string by substituting each substring by its corresponding factor. The resulting grammar is encoded by exploring some redundancies, such as common prefixes between suffix rules, which are sorted according to SAIS framework. When compared to well-known compression tools such as Re-Pair and 7-zip under repetitive sequences, our algorithm is faster at compressing and achieves compression ratio close to that of Re-Pair, at the cost of being the slowest at decompressing.
Lenguagedc.language.isoen
Publisherdc.publisherInstitute of Electrical and Electronics Engineers Inc.
Type of licensedc.rightsAttribution-NonCommercial-NoDerivs 3.0 Chile
Link to Licensedc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/cl/
Sourcedc.sourceData Compression Conference Proceedings
Keywordsdc.subjectalgorithm
Keywordsdc.subjectgrammar compression
Keywordsdc.subjectinduced suffix sorting
Títulodc.titleA grammar compression algorithm based on induced suffix sorting
Document typedc.typeArtículo de revista
Catalogueruchile.catalogadorjmm
Indexationuchile.indexArtículo de publicación SCOPUS
uchile.cosechauchile.cosechaSI


Files in this item

Icon

This item appears in the following Collection(s)

Show simple item record

Attribution-NonCommercial-NoDerivs 3.0 Chile
Except where otherwise noted, this item's license is described as Attribution-NonCommercial-NoDerivs 3.0 Chile