Flashback: A Reversible Bilateral Run-Peeling Decomposition of Strings

1. Problem Statement

Most traditional string decomposition algorithms (e.g., Lempel-Ziv, Burrows-Wheeler Transform, Run-Length Encoding) process strings in a linear, unidirectional manner (left-to-right or via permutation). While effective for compression or clustering, these methods often obscure the outside-in structural symmetry of a string. Specifically, they do not explicitly capture how the boundary runs of a string can be peeled away layer by layer to reveal an inner core.

The paper addresses the need for a decomposition method that:

1. Processes strings from both ends simultaneously (bilateral).
2. Operates at the level of maximal runs (consecutive identical characters) rather than individual characters.
3. Is exactly reversible and computationally efficient.
4. Provides structural insights into string symmetry, palindromes, and edit locality.

2. Methodology: The Flashback Algorithm

The authors propose Flashback, a deterministic algorithm that decomposes a string into a sequence of "bilateral tokens."

Core Mechanism

1. Sentinel Wrapping: The input string $s$ is wrapped in two unique sentinel characters, @ and $, which are not part of the original alphabet $\Sigma$. This ensures the leading and trailing runs at the first step are distinct and of length 1.
2. Bilateral Peeling:
   • At each step, the algorithm identifies the maximal leading run and the maximal trailing run of the current active span.
   • These two runs are concatenated into a single symbol string $\sigma$.
   • A split position $p$ is recorded, representing the length of the leading run.
   • The pair $(\sigma, p)$ forms a bilateral token.
   • The algorithm recurses on the remaining "middle" substring (the part between the peeled runs).
3. Termination: The process stops when the middle is empty or consists of a single run (or two adjacent runs that cover the span), emitting a terminal token where the split position $p=0$.

Reconstruction ($F^{-1}$)

Reconstruction is the inverse process, working from the inside out:

• It takes the token sequence and allocates a buffer.
• It processes tokens from the last (innermost) to the first (outermost).
• For each token, it writes the front part of the string, recursively fills the inner gap, and then writes the back part.
• Finally, the sentinel characters are stripped to recover the original string.

3. Key Contributions and Theoretical Results

A. The Run-Pairing Theorem (Theoretical Core)

The paper's central result establishes that Flashback is mathematically equivalent to pairing the runs of the Run-Length Encoding (RLE) from the outside in.

• If a string has $r$ maximal runs, Flashback pairs the 1st run with the $r$-th, the 2nd with the $(r-1)$-th, and so on.
• Token Count: The exact number of tokens $k$ is given by:
  $$k = 1 + \lceil r/2 \rceil$$
  (The $+1$ accounts for the initial sentinel token).
• Optimality: The authors prove that this "greedy" approach (peeling full runs) is optimal. No other admissible bilateral run-peeling scheme can produce fewer tokens. If $r$ is even, Flashback is the unique token-minimal scheme.

B. Structural Properties

1. Irreducible Kernel: The terminal token (the "kernel" of the decomposition) contains at most two distinct symbols.
   • If $r$ is odd, the kernel is a single run.
   • If $r$ is even, the kernel is two adjacent runs.
2. Palindrome Characterization: A string is a palindrome if and only if:
   • Its RLE has an odd number of runs ($r$ is odd).
   • Its RLE is symmetric (the $i$-th run matches the $(r+1-i)$-th run in both symbol and length).
   • In Flashback terms, this means the kernel is a single run, and every non-terminal token has matching front/back symbols with equal lengths.
3. Image Characterization: The authors provide a finite-state characterization of valid token sequences. A sequence is a valid Flashback output if and only if it satisfies specific local constraints regarding split positions, run alternation, and terminal forms.

C. Edit Locality

The decomposition exhibits strong edit locality:

• Run-Length Changes: Changing the length of a single run $m_i$ (without changing the symbol) affects exactly one content token. Specifically, it rewrites the token at depth $\min(i, r+1-i)$.
• Character Edits: Insertions, deletions, or substitutions change at most two run boundaries, altering the token count by at most 1 and potentially shifting content in a bounded number of tokens.

4. Complexity Analysis

• Time Complexity: Both decomposition ($F$) and reconstruction ($F^{-1}$) run in $O(n)$ time.
  • Decomposition scans each character a constant number of times (once to identify runs, once to emit tokens).
  • Reconstruction writes each character directly to its final position in the output buffer.
• Space Complexity: The algorithm uses $O(n)$ space.
  • The decomposition can be implemented iteratively (tail-recursion elimination) to use $O(1)$ auxiliary space beyond the input/output buffers.

5. Significance and Applications

• Structural Tool vs. Compression: The authors explicitly state Flashback is not a compression scheme. The total character count in the tokens equals $n+2$ (the original length plus sentinels). Instead, it is a structural tool for reasoning about string symmetry and run-level properties.
• Complementarity: Unlike Lempel-Ziv (which finds repeated substrings) or BWT (which clusters identical characters), Flashback captures bilateral nesting. It reveals the "onion-like" structure of a string.
• Theoretical Insight: The paper bridges the gap between simple run-length encoding and complex structural decomposition, showing that a simple "outside-in" pairing strategy yields a unique, optimal, and highly local representation of string symmetry.
• Palindromes and Kernels: It offers a new, algorithmic perspective on palindromes and the "core" of a string, defining them through the properties of the peeling kernel.

Summary

Flashback is a novel, reversible string decomposition that peels maximal runs from both ends of a string simultaneously. Its primary theoretical contribution is the Run-Pairing Theorem, which proves that the decomposition is equivalent to pairing RLE runs from the outside in, resulting in a token count of $1 + \lceil r/2 \rceil$. The method runs in linear time, offers precise edit locality, and provides a rigorous framework for analyzing string symmetry and palindromes, distinguishing itself from traditional compression algorithms by prioritizing structural insight over data reduction.