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 
Cita de ítemdc.identifier.citationData Compression Conference Proceedings, 2018
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.
Publisherdc.publisherInstitute of Electrical and Electronics Engineers Inc.
Type of licensedc.rightsAttribution-NonCommercial-NoDerivs 3.0 Chile
Link to Licensedc.rights.uri
Sourcedc.sourceData Compression Conference Proceedings
Keywordsdc.subjectgrammar compression
Keywordsdc.subjectinduced suffix sorting
Títulodc.titleA grammar compression algorithm based on induced suffix sorting
Document typedc.typeArtículo de revista
Indexationuchile.indexArtículo de publicación SCOPUS

Files in this item


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