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
• Situação: Interrompido
• Á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
• Bolsa(s) vinculada(s): 25/22927-6 - Otimização de operações de busca em Vetores Suficientes, BE.EP.IC
• 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.