Analysis and Development of a Grammar-Based Hybrid Data Compression Algorithm

• Grant number: 24/23313-9
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: April 01, 2025
• End date: March 31, 2026
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Guilherme Pimentel Telles
• Grantee: João Vitor Hartung Toppa
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil

Abstract

Data compression is a significant problem in Computer Science, both in theory and practice.Grammar-based compression is of particular interest in data compression because it achieves good compression rates while enabling additional operations on the compressed string, such as substring extraction and indexing. The problem of finding the smallest grammar that generates a given string is NP-hard and in practice it is solved using heuristics. Among the various existing heuristics, Re-Pair is the one most commonly used in practice. More recently, the recursive GCIS heuristic has achieved good compression rates in less time and using less working memory than Re-Pair. This Scientific Initiation project aims to analyze a hybrid compression strategy that uses Re-Pair for small subproblems within GCIS. The proposed approach will be implemented and evaluated for its efficiency in terms of both compression rates and computational performance compared to the original versions of Re-Pair and GCIS.