Compressão gramatical com extração eficiente

• Ano de defesa: 2024
• Autor(a) principal: Angelo, Danyelle da Silva Oliveira
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Uberlândia; Brasil; Programa de Pós-graduação em Administração
• Palavras-chave em Português: Compressão; Extração; Gramática; Estrutura de dados compactas; Algoritmos; Compression; Extraction; Grammar; Compact data structures; Algorithms; CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO; CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO::ANALISE DE ALGORITMOS E COMPLEXIDADE DE COMPUTACAO; Computação; ODS::ODS 9. Indústria, Inovação e infraestrutura - Construir infraestrutura resiliente, promover a industrialização inclusiva e sustentável, e fomentar a inovação.
• Link de acesso: https://repositorio.ufu.br/handle/123456789/42067; https://doi.org/10.14393/ufu.di.2024.341

We present a grammar compressor, called GCX (Grammar Compression modulo X), based on the induced suffix sorting grammar compression technique introduced in GCIS. Our method incorporates the text factorization used by algorithm DC3 to create a context-free grammar that produces the input string. We evaluated the performance of our algorithm using different values of covering X, and we introduce a heuristic based on the average longest common prefix between the rules of the grammar to define this coverage. GCX supports very fast extraction on the encoded grammar without the need to complete decompression. Experiments with real and artificial datasets showed that GCX, compared with GCIS, in most cases, is faster to compress, faster to decompress, have worse compression ratio most often; however, it has an extraction speed approximately 100 times larger. Similar behavior is observed when comparing the performance of GCX with that of RePair.