| Full text | |
| Author(s): |
Nogueira Nunes, Daniel Saad
;
Louza, Felipe A.
;
Gog, Simon
;
Ayala-Rincon, Mauricio
;
Navarro, Gonzalo
;
Bilgin, A
;
Marcellin, MW
;
SerraSagrista, J
;
Storer, JA
Total Authors: 9
|
| Document type: | Journal article |
| Source: | 2018 DATA COMPRESSION CONFERENCE (DCC 2018); v. N/A, p. 10-pg., 2018-01-01. |
| Abstract | |
We 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. (AU) | |
| FAPESP's process: | 17/09105-0 - Suffix sorting and string similarity measures |
| Grantee: | Felipe Alves da Louza |
| Support Opportunities: | Scholarships in Brazil - Post-Doctoral |