Advanced search
Start date
Betweenand

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.

News published in Agência FAPESP Newsletter about the scholarship:
More itemsLess items
Articles published in other media outlets ( ):
More itemsLess items
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)