Skip navigation
Veuillez utiliser cette adresse pour citer ce document : http://repositorio.unb.br/handle/10482/43873
Fichier(s) constituant ce document :
Fichier Description TailleFormat 
2022_DanielSaadNogueiraNunes.pdf10,8 MBAdobe PDFVoir/Ouvrir
Titre: Grammar compression by induced suffix sorting
Auteur(s): Nunes, Daniel Saad Nogueira
Orientador(es):: Ayala-Rincón, Mauricio
Assunto:: Compressão por gramática
Sufixos por indução
Gramática livre
Date de publication: 1-jui-2022
Référence bibliographique: NUNES, Daniel Saad Nogueira. Grammar compression by induced suffix sorting. 2022. x, 110 f., il. Tese (Doutorado em Informática) — Universidade de Brasília, Brasília, 2022.
Résumé: Este trabalho apresenta um novo método de compressão por gramáticas chamado GCIS. Este método é baseado na abordagem de ordenação de sufixos por indução, SAIS, apresentada por Nong et al. em 2009. A solução proposta utiliza os fatores produzidos pela ordenação SAIS para construir uma gramática livre de contexto que gera o texto. As regras das gramáticas são formadas substituindo cada fator encontrado pela ordenação SAIS por um símbolo não terminal. O método é aplicado recursivamente na sequência composta por não terminais que substitui o texto original até que todos os fatores produzidos sejam distintos. A gramática gerada ainda pode ser comprimida ao explorar redundâncias, tais como os prefixos comuns compartilhado pelo lado direito das regras de produção, que por construção, estão ordenadas. O método GCIS se destaca pelo seu tempo de compressão enquanto mantém a taxa de compressão competitiva. Através de experimentos sobre textos regulares, repetitivos e imensos, GCIS demonstra ser uma escolha factível quando comparado com outros compressores como: Gzip, 7-zip, RePair, a principal referência para compressores baseados em gramáticas, e as recentes alternativas; SOLCA; LZRR; e LZD. Em contrapartida, GCIS não possui uma descompressão tão rápida. Contudo, compressores baseados em gramáticas são mais convenientes do que aqueles baseados nas técnicas de compressão Lempel-Ziv haja vista que possibilitam a extração de subpalavras diretamente da informação comprimida, sem que seja necessário gerar o texto original para tal. Neste cenário, de compressores por gramática, GCIS possui pontos fortes quando comparado aos demais. Também apresentamos que, devido a sua proximidade com a abordagem SAIS, podemos usar GCIS para construir os vetores de sufixos e longest common prefix do texto, estruturas fundamentais no processamento de palavras, durante a descompressão da informação.
Abstract: A 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 to construct a context-free grammar that replaces each distinct factor with a nonterminal. The algorithm is then recursively applied on the shorter sequence of nonterminals. The resulting grammar is encoded by exploiting 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, repetitive, moderate, and very large texts show that GCIS is a very convenient choice compared to well-known compressors such as Gzip, 7-Zip, RePair, the gold standard in grammar compression, and recent compressors like SOLCA, LZRR, and LZD. In exchange, GCIS is slow at decompressing. Nevertheless, 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 and longest common prefix arrays during decompression of the text.
metadata.dc.description.unidade: Instituto de Ciências Exatas (IE)
Departamento de Ciência da Computação (IE CIC)
Description: Tese (doutorado) — Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2022.
metadata.dc.description.ppg: Programa de Pós-Graduação em Informática
Licença:: A concessão da licença deste item refere-se ao termo de autorização impresso assinado pelo autor com as seguintes condições: Na qualidade de titular dos direitos de autor da publicação, autorizo a Universidade de Brasília e o IBICT a disponibilizar por meio dos sites www.bce.unb.br, www.ibict.br, http://hercules.vtls.com/cgi-bin/ndltd/chameleon?lng=pt&skin=ndltd sem ressarcimento dos direitos autorais, de acordo com a Lei nº 9610/98, o texto integral da obra disponibilizada, conforme permissões assinaladas, para fins de leitura, impressão e/ou download, a título de divulgação da produção científica brasileira, a partir desta data.
Collection(s) :Teses, dissertações e produtos pós-doutorado

Affichage détaillé " class="statisticsLink btn btn-primary" href="/jspui/handle/10482/43873/statistics">



Tous les documents dans DSpace sont protégés par copyright, avec tous droits réservés.