Busca avançada
Ano de início
Entree

Análise e Desenvolvimento de um Algoritmo Híbrido de Compressão de Dados Baseado em Gramáticas

Processo: 24/23313-9
Modalidade de apoio:Bolsas no Brasil - Iniciação Científica
Data de Início da vigência: 01 de abril de 2025
Data de Término da vigência: 31 de março de 2026
Área de conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
Pesquisador responsável:Guilherme Pimentel Telles
Beneficiário:João Vitor Hartung Toppa
Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
Assunto(s):Compressão de dados
Palavra(s)-Chave do Pesquisador:Algoritmos Híbridos | compressão de dados | Gcis | Gramáticas Livre de Contexto | Re-Pair | Compressão de Dados

Resumo

A compressão de dados é um problema importante em Computação, na teoria e na prática.A compressão baseada em gramáticas é uma forma de compressão de dados interessante porque alcança boas taxas de compressão ao mesmo tempo em que permite operações adicionais sobre a cadeia comprimida, como extração de subcadeias e indexação. O problema de encontrar a menor gramática que gera uma dada cadeia é NP-difícil, e na prática é resolvido usando heurísticas. Dentre as várias heurísticas existentes, a mais usada na prática é a Re-Pair. Mais recentemente, a heurística GCIS, que é recursiva, obteve boas taxas de compressão em menos tempo e usando menos memória de trabalho que a Re-Pair. Este projeto de Iniciação Científica tem como objetivo analisar uma estratégia de compressão híbrida que usa o Re-Pair para subproblemas pequenos do GCIS.A abordagem proposta será implementada e avaliada quanto à eficiência, tanto em termos de taxa de compressão quanto em termos do desempenho computacional em comparação às versões originais do Re-Pair e do GCIS.

Matéria(s) publicada(s) na Agência FAPESP sobre a bolsa:
Mais itensMenos itens
Matéria(s) publicada(s) em Outras Mídias ( ):
Mais itensMenos itens
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)