Flashback: A Reversible Bilateral Run-Peeling Decomposition of Strings

1. Enunciato del Problema

La maggior parte degli algoritmi tradizionali di decomposizione delle stringhe (ad esempio, Lempel-Ziv, Trasformata di Burrows-Wheeler, Codifica a Lunghezza di Corsa) elabora le stringhe in modo lineare e unidirezionale (da sinistra a destra o tramite permutazione). Sebbene efficaci per la compressione o il clustering, questi metodi spesso oscurano la simmetria strutturale dall'esterno verso l'interno di una stringa. Nello specifico, non catturano esplicitamente come le corse (run) ai bordi di una stringa possano essere rimosse strato per strato per rivelare un nucleo interno.

Il documento affronta la necessità di un metodo di decomposizione che:

1. Elabori le stringhe da entrambe le estremità simultaneamente (bilaterale).
2. Operi a livello di corse massimali (caratteri identici consecutivi) piuttosto che di singoli caratteri.
3. Sia esattamente reversibile e computazionalmente efficiente.
4. Fornisca intuizioni strutturali sulla simmetria delle stringhe, i palindromi e la località delle modifiche.

2. Metodologia: L'Algoritmo Flashback

Gli autori propongono Flashback, un algoritmo deterministico che scompone una stringa in una sequenza di "token bilaterali".

Meccanismo Principale

1. Racchiusura con Sentinelle: La stringa di input $s$ viene racchiusa tra due caratteri sentinella unici, @ e $, che non fanno parte dell'alfabeto originale $\Sigma$. Ciò garantisce che le corse iniziali e finali al primo passo siano distinte e di lunghezza 1.
2. Rimozione Bilaterale:
   • Ad ogni passo, l'algoritmo identifica la corsa massima iniziale e la corsa massima finale dell'intervallo attivo corrente.
   • Queste due corse vengono concatenate in un'unica stringa di simboli $\sigma$.
   • Viene registrata una posizione di divisione $p$, che rappresenta la lunghezza della corsa iniziale.
   • La coppia $(\sigma, p)$ forma un token bilaterale.
   • L'algoritmo procede in modo ricorsivo sul sottostringa "centrale" rimanente (la parte compresa tra le corse rimosse).
3. Terminazione: Il processo si interrompe quando la parte centrale è vuota o consiste in una singola corsa (o due corse adiacenti che coprono l'intervallo), emettendo un token terminale in cui la posizione di divisione $p=0$.

Ricostruzione ($F^{-1}$)

La ricostruzione è il processo inverso, che lavora dall'interno verso l'esterno:

• Prende la sequenza di token e alloca un buffer.
• Elabora i token dall'ultimo (più interno) al primo (più esterno).
• Per ogni token, scrive la parte anteriore della stringa, riempie ricorsivamente il gap interno e quindi scrive la parte posteriore.
• Infine, i caratteri sentinella vengono rimossi per recuperare la stringa originale.

3. Contributi Chiave e Risultati Teorici

A. Il Teorema dell'Accoppiamento delle Corse (Nucleo Teorico)

Il risultato centrale del documento stabilisce che Flashback è matematicamente equivalente all'accoppiamento delle corse della Codifica a Lunghezza di Corsa (RLE) dall'esterno verso l'interno.

• Se una stringa ha $r$ corse massimali, Flashback accoppia la 1ª corsa con la $r$-esima, la 2ª con la $(r-1)$-esima, e così via.
• Numero di Token: Il numero esatto di token $k$ è dato da:
  $$k = 1 + \lceil r/2 \rceil$$
  (Il $+1$ tiene conto del token sentinella iniziale).
• Ottimalità: Gli autori dimostrano che questo approccio "greedy" (rimuovere corse intere) è ottimale. Nessun altro schema di rimozione bilaterale delle corse ammissibile può produrre meno token. Se $r$ è pari, Flashback è lo schema unico che minimizza i token.

B. Proprietà Strutturali

1. Nucleo Irriducibile: Il token terminale (il "nucleo" della decomposizione) contiene al massimo due simboli distinti.
   • Se $r$ è dispari, il nucleo è una singola corsa.
   • Se $r$ è pari, il nucleo è costituito da due corse adiacenti.
2. Caratterizzazione dei Palindromi: Una stringa è un palindromo se e solo se:
   • La sua RLE ha un numero dispari di corse ($r$ è dispari).
   • La sua RLE è simmetrica (la $i$-esima corsa corrisponde alla $(r+1-i)$-esima corsa sia nel simbolo che nella lunghezza).
   • In termini di Flashback, ciò significa che il nucleo è una singola corsa e ogni token non terminale ha simboli anteriore/posteriore corrispondenti con lunghezze uguali.
3. Caratterizzazione delle Immagini: Gli autori forniscono una caratterizzazione a stati finiti delle sequenze di token valide. Una sequenza è un output Flashback valido se e solo se soddisfa vincoli locali specifici riguardanti le posizioni di divisione, l'alternanza delle corse e le forme terminali.

C. Località delle Modifiche

La decomposizione esibisce una forte località delle modifiche:

• Cambiamenti di Lunghezza di Corsa: Modificare la lunghezza di una singola corsa $m_i$ (senza cambiare il simbolo) influenza esattamente un token di contenuto. Nello specifico, riscrive il token alla profondità $\min(i, r+1-i)$.
• Modifiche ai Caratteri: Inserimenti, cancellazioni o sostituzioni modificano al massimo due confini di corsa, alterando il numero di token di al massimo 1 e potenzialmente spostando il contenuto in un numero limitato di token.

4. Analisi della Complessità

• Complessità Temporale: Sia la decomposizione ($F$) che la ricostruzione ($F^{-1}$) operano in tempo $O(n)$.
  • La decomposizione scansiona ogni carattere un numero costante di volte (una volta per identificare le corse, una volta per emettere i token).
  • La ricostruzione scrive ogni carattere direttamente nella sua posizione finale nel buffer di output.
• Complessità Spaziale: L'algoritmo utilizza spazio $O(n)$.
  • La decomposizione può essere implementata in modo iterativo (eliminazione della ricorsione di coda) per utilizzare $O(1)$ spazio ausiliario oltre ai buffer di input/output.

5. Significato e Applicazioni

• Strumento Strutturale vs Compressione: Gli autori dichiarano esplicitamente che Flashback non è uno schema di compressione. Il conteggio totale dei caratteri nei token è uguale a $n+2$ (la lunghezza originale più le sentinelle). Piuttosto, è uno strumento strutturale per ragionare sulla simmetria delle stringhe e sulle proprietà a livello di corsa.
• Complementarità: A differenza di Lempel-Ziv (che trova sottostringhe ripetute) o BWT (che raggruppa caratteri identici), Flashback cattura l'annidamento bilaterale. Rivela la struttura "a cipolla" di una stringa.
• Intuizione Teorica: Il documento colma il divario tra la semplice codifica a lunghezza di corsa e la decomposizione strutturale complessa, mostrando che una semplice strategia di accoppiamento "dall'esterno verso l'interno" produce una rappresentazione unica, ottimale e altamente locale della simmetria delle stringhe.
• Palindromi e Nuclei: Offre una nuova prospettiva algoritmica sui palindromi e sul "nucleo" di una stringa, definendoli attraverso le proprietà del nucleo di rimozione.

Riepilogo

Flashback è una decomposizione di stringhe reversibile e innovativa che rimuove corse massimali da entrambe le estremità di una stringa simultaneamente. Il suo contributo teorico principale è il Teorema dell'Accoppiamento delle Corse, che dimostra che la decomposizione è equivalente all'accoppiamento delle corse RLE dall'esterno verso l'interno, risultando in un numero di token pari a $1 + \lceil r/2 \rceil$. Il metodo opera in tempo lineare, offre una precisa località delle modifiche e fornisce un quadro rigoroso per analizzare la simmetria delle stringhe e i palindromi, distinguendosi dagli algoritmi di compressione tradizionali privilegiando l'intuizione strutturale sulla riduzione dei dati.