Use este identificador para citar ou linkar para este item: https://repositorio.ufu.br/handle/123456789/42067
ORCID:  http://orcid.org/0009-0003-6793-609X
Tipo do documento: Dissertação
Tipo de acesso: Acesso Aberto
Título: Compressão gramatical com extração eficiente
Título(s) alternativo(s): Grammar compression with efficient extraction
Autor(es): Angelo, Danyelle da Silva Oliveira
Primeiro orientador: Louza, Felipe Alves da
Primeiro coorientador: Telles, Guilherme Pimentel
Primeiro membro da banca: Albertini, Marcelo Keese
Segundo membro da banca: Badino, Gonzalo Navarro
Resumo: Apresentamos um compressor, denominado GCX (Grammar Compression modulo X), baseado na técnica de compressão gramatical por ordenação de sufixos induzida, introduzida no GCIS. Nosso método incorpora a fatoração de textos utilizada pelo algoritmo de ordenação de sufixos DC3, para criar uma gramática livre de contexto capaz de produzir o texto de entrada. Nós avaliamos o desempenho do nosso algoritmo utilizando diferentes valores de cobertura X, e introduzimos uma heurística baseada na média do prefixo comum mais longo entre as regras da gramática para definir o valor dessa cobertura. GCX suporta operações de extração rápidas sobre o texto codificado sem a necessidade de descompressão completa. Nossos experimentos foram realizados com conjuntos de dados reais e artificiais e os resultados mostraram que o GCX, em comparação com o GCIS, na maioria dos casos é mais rápido para comprimir, mais rápido para descomprimir, tem uma taxa de compressão pior na maioria das vezes; por outro lado, possui velocidade de extração, aproximadamente 100 vezes mais rápida. Observa-se um comportamento semelhante ao comparar o desempenho do GCX com o do método RePair.
Abstract: 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.
Palavras-chave: Compressão
Extração
Gramática
Estrutura de dados compactas
Algoritmos
Compression
Extraction
Grammar
Compact data structures
Algorithms
Área(s) do CNPq: 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
Assunto: Computação
Idioma: por
País: Brasil
Editora: Universidade Federal de Uberlândia
Programa: Programa de Pós-graduação em Administração
Referência: ANGELO, Danyelle da Silva Oliveira. Compressão Gramatical com extração eficiente. 2024. 88 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Uberlândia, Uberlândia, 2024. DOI http://doi.org/10.14393/ufu.di.2024.341.
Identificador do documento: https://doi.org/10.14393/ufu.di.2024.341
URI: https://repositorio.ufu.br/handle/123456789/42067
Data de defesa: 6-Mai-2024
Objetivos de Desenvolvimento Sustentável (ODS): 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.
Aparece nas coleções:DISSERTAÇÃO - Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
GrammarCompressionEfficient.pdfDissertação11.89 MBAdobe PDFThumbnail
Visualizar/Abrir


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