Palindromes Compression and Retrieval
Michael Itzhaki · 2025
Palindromes are sequences of characters that read the same forward and backward and have fascinated computer scientists for centuries due to their unique properties. The exploration of palindromes sheds light on fundamental principles of pattern recognition, sequence alignment, and combinatorics, making them a crucial concept in theoretical and applied disciplines. We introduce a novel method for compressing palindromic structures in strings, establishing upper and lower bounds for their efficient representation. We do so by presenting a data structure capable of storing all maximal palindromes (Manacher array) in sublinear space with near-optimal access time. Our approach reduces the memory overhead of storing palindromes, offering a new avenue for optimizing compression algorithms in text processing applications.