Skip navigation
Use este identificador para citar ou linkar para este item: http://repositorio.unb.br/handle/10482/45251
Arquivos associados a este item:
Não existem arquivos associados a este item.
Registro completo de metadados
Campo DCValorIdioma
dc.contributor.authorNunes, Daniel Saad Nogueira-
dc.contributor.authorLouza, Felipe A.-
dc.contributor.authorGog, Simon-
dc.contributor.authorAyala-Rincón, Mauricio-
dc.contributor.authorNavarro, Gonzalo-
dc.date.accessioned2022-12-05T18:20:59Z-
dc.date.available2022-12-05T18:20:59Z-
dc.date.issued2022-08-26-
dc.identifier.citationNUNES, Daniel S. N. et. al. Grammar compression by induced suffix sorting. ACM Journal of Experimental Algorithmics, v. 27, dez. 2022. DOI 10.1145/3549992. Disponível em: https://dl.acm.org/doi/10.1145/3549992. Acesso em: 05 dez. 2022.pt_BR
dc.identifier.urihttps://repositorio.unb.br/handle/10482/45251-
dc.language.isoInglêspt_BR
dc.publisherACMpt_BR
dc.rightsAcesso Restritopt_BR
dc.titleGrammar compression by induced suffix sortingpt_BR
dc.typeArtigopt_BR
dc.subject.keywordTeoria da computaçãopt_BR
dc.subject.keywordCompressão de dados (Computação)pt_BR
dc.subject.keywordGestão de dadospt_BR
dc.subject.keywordAlgoritmo de compressão gramaticalpt_BR
dc.identifier.doihttps://doi.org/10.1145/3549992pt_BR
dc.relation.publisherversionhttps://dl.acm.org/doi/10.1145/3549992pt_BR
dc.description.abstract1A grammar compression algorithm, called GCIS, is introduced in this work. GCIS is based on the induced suffix sorting algorithm SAIS, presented by Nong et al. in 2009. The proposed solution builds on the factorization performed by SAIS during suffix sorting. A context-free grammar is used to replace factors by non-terminals. The algorithm is then recursively applied on the shorter sequence of non-terminals. The resulting grammar is encoded by exploiting some redundancies, such as common prefixes between right-hands of rules, sorted according to SAIS. GCIS excels for its low space and time required for compression while obtaining competitive compression ratios. Our experiments on regular and repetitive, moderate and very large texts, show that GCIS stands as a very convenient choice compared to well-known compressors such as Gzip 7-Zip; and RePair the gold standard in grammar compression; and recent compressors such as SOLCA, LZRR, and LZD. In exchange, GCIS is slow at decompressing. Yet, grammar compressors are more convenient than Lempel-Ziv compressors in that one can access text substrings directly in compressed form without ever decompressing the text. We demonstrate that GCIS is an excellent candidate for this scenario, because it shows to be competitive among its RePair based alternatives. We also show that the relation with SAIS makes GCIS a good intermediate structure to build the suffix array and the LCP array during decompression of the text.pt_BR
dc.identifier.orcidhttps://orcid.org/0000-0001-6870-1397pt_BR
dc.identifier.orcidhttps://orcid.org/0000-0003-2931-1470pt_BR
dc.identifier.orcidhttps://orcid.org/0000-0002-5450-8630pt_BR
dc.identifier.orcidhttps://orcid.org/0000-0003-0089-3905pt_BR
dc.identifier.orcidhttps://orcid.org/0000-0002-2286-741Xpt_BR
Aparece nas coleções:Artigos publicados em periódicos e afins

Mostrar registro simples do item Visualizar estatísticas



Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.