Grammar compression by induced suffix sorting

Abstract

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.