Flashback: A Reversible Bilateral Run-Peeling Decomposition of Strings
This work provides a novel structural decomposition for strings, with applications in string processing and compression, though it is incremental in nature.
Flashback is a reversible string decomposition that peels maximal leading and trailing character runs, achieving O(n) time and space. It yields an exact token count of 1+[r/2] for a string with r runs, matching a lower bound for any admissible bilateral run-peeling scheme.
We introduce Flashback, a reversible string decomposition that repeatedly peels the maximal leading and trailing character runs from a sentinel-wrapped input, recording each pair as one bilateral token. Decomposition and reconstruction both run in O(n) time and space. Our central result is a run-pairing theorem: Flashback is equivalent to pairing the first run of the string with the last, the second with the second-to-last, and so on. This gives an exact token count of 1+[r/2] for a string with r maximal runs, and matches a lower bound that holds for any admissible bilateral run-peeling scheme. From the run-pairing theorem the main structural properties follow as corollaries: the irreducible peeling kernel uses at most two symbols; palindromes are precisely the strings whose run-length encoding is symmetric with an odd number of runs; the image of the decomposition admits an explicit finite-state characterisation; and changing one run length rewrites exactly one content token.