Esercizio - sottosequenza quasi palindroma di lunghezza massima (compito dell'8 luglio 2024, es. 2)

Fonte: compito di Algoritmi per l'Ingegneria, Ing. Informatica UniPD, 8 luglio 2024, seconda parte, esercizio 2 (17 punti).

Testo

Una stringa di interi $Z = \langle z_1, z_2, \dots, z_m \rangle \in \mathbb{Z}^*$ si dice quasi palindroma se, per ogni $h = 0, 1, \dots, m - 1$, si ha $|z_{1+h} - z_{m-h}| \le 1$. Data una stringa $X = \langle x_1, x_2, \dots, x_n \rangle \in \mathbb{Z}^*$, il problema della Longest Quasi Palindrome Subsequence (LQPS) consiste nel determinare la massima lunghezza di una sottosequenza quasi palindroma di $X$.

• (a) [7 punti] Si formuli una proprietà di sottostruttura ottima per il problema sullo spazio delle sottostringhe $\mathcal{I}_X = \{X_{i..j} : 1 \le i \le j \le n\}$ della stringa $X$ e se ne provi la correttezza.
• (b) [5 punti] Sulla base della proprietà provata al punto (a), si derivi una ricorrenza sulla lunghezza della LQPS.
• (c) [5 punti] Si scriva lo pseudocodice bottom-up associato al calcolo della ricorrenza sviluppata al punto precedente e se ne valuti la correttezza e la complessità, in funzione del numero di addizioni e sottrazioni tra i caratteri della stringa.

Soluzione

Idea

Una stringa quasi palindroma è una palindroma in cui "uguale" è sostituito da "differisce al più di $1$": le coppie simmetriche $(z_1, z_m)$, $(z_2, z_{m-1})$, ... devono essere vicine. Per esempio $\langle 3, 5, 4, 4, 2 \rangle$ lo è: $|3 - 2| = 1$, $|5 - 4| = 1$ e il centro $4$ è confrontato con sé stesso. È il problema della sottosequenza palindroma più lunga (Allineamento di stringhe e sottosequenza palindroma più lungadue problemi di DP su stringhe con la stessa struttura della LCS. Allineamento ottimo di due stringhe di DNA con matrice di score S e penalità di gap g: C(i,j) = max{C(i-1,j-1) + s(x_i,y_j), C(i-1,j) + g, C(i,j-1) + g}, C(i,0) = i g, C(0,j) = j g; Theta(mn) tempo, spazio Theta(min{m,n}) con un solo vettore se serve solo il costo. Sottosequenza palindroma più lunga (LPS) sullo spazio delle sottostringhe X_(i..j): p(i,j) = 2 + p(i+1,j-1) se x_i = x_j, altrimenti max{p(i+1,j), p(i,j-1)}; scansione per diagonali, n(n-1)/2 confronti.Allineamento di stringhe e sottosequenza palindroma più lunga →) con una relazione di "compatibilità" tra gli estremi più larga dell'uguaglianza. Come per quella, si tolgono i caratteri dai due estremi, quindi lo spazio dei sottoproblemi è quello delle sottostringhe $X_{i..j}$ ($\Theta(n^2)$).

Una stringa di un solo carattere è sempre quasi palindroma, e una di due caratteri lo è se e solo se i due differiscono di al più $1$.

(a) Proprietà di sottostruttura ottima

Proprietà. Per ogni $1 \le i \le j \le n$ esiste una $Z = \langle z_1, \dots, z_k \rangle$, LQPS di $X_{i..j}$, tale che:

1. se $i = j$: $Z = \langle x_i \rangle$;
2. se $j = i + 1$ e $|x_i - x_j| \le 1$: $Z = \langle x_i, x_j \rangle$;
3. se $j = i + 1$ e $|x_i - x_j| > 1$: $Z = \langle x_i \rangle$;
4. se $j > i + 1$ e $|x_i - x_j| \le 1$: $z_1 = x_i$, $z_k = x_j$ e $Z_{2..k-1}$ è una LQPS di $X_{i+1..j-1}$;
5. altrimenti ($j > i + 1$ e $|x_i - x_j| > 1$): $Z$ è la più lunga tra una LQPS di $X_{i..j-1}$ e una LQPS di $X_{i+1..j}$.

(Come nei problemi analoghi, il punto 4 dice che esiste una LQPS con estremi $x_i$ e $x_j$, non che tutte le LQPS li abbiano: basta per un algoritmo corretto.)

Dimostrazione. I punti 1, 2 e 3 sono banali (una stringa di un carattere è quasi palindroma; una di due caratteri lo è se e solo se la differenza è al più $1$).

Punto 4. Sia $j > i + 1$ e $|x_i - x_j| \le 1$. Sia $Z' = \langle x_{j_1}, \dots, x_{j_k} \rangle$ una LQPS qualsiasi di $X_{i..j}$, con $i \le j_1 < \dots < j_k \le j$. Poiché $\langle x_i, x_j \rangle$ è quasi palindroma, $k \ge 2$.

• Non possono valere insieme $j_1 > i$ e $j_k < j$: altrimenti $\langle x_i, Z', x_j \rangle$ sarebbe una sottosequenza di $X_{i..j}$ (indici $i < j_1$ e $j_k < j$), quasi palindroma (le coppie interne sono quelle di $Z'$ e la coppia esterna $(x_i, x_j)$ è compatibile) e più lunga di $Z'$, contro la massimalità. Quindi $j_1 = i$ oppure $j_k = j$.
• Se $j_1 = i$ e $j_k < j$, si sostituisce l'ultimo carattere di $Z'$ con $x_j$ (indice $j > j_{k-1}$); se $j_1 > i$ e $j_k = j$, si sostituisce il primo con $x_i$. La stringa $Z$ ottenuta ha la stessa lunghezza $k$, è sottosequenza di $X_{i..j}$, e resta quasi palindroma: le coppie interne non cambiano e la coppia esterna è ora $(x_i, x_j)$, compatibile. Quindi $Z$ è una LQPS con $z_1 = x_i$ e $z_k = x_j$ (se $j_1 = i$ e $j_k = j$ non occorre sostituire nulla).
• $Z_{2..k-1}$ è quasi palindroma ed è sottosequenza di $X_{i+1..j-1}$. Se non ne fosse una LQPS, sostituendola con una LQPS $W$ di $X_{i+1..j-1}$ (cut-and-paste) si otterrebbe $\langle x_i, W, x_j \rangle$, quasi palindroma e più lunga di $Z$: contraddizione.

Punto 5. Sia $Z'$ una LQPS qualsiasi di $X_{i..j}$ con $j > i + 1$ e $|x_i - x_j| > 1$. Se $Z'$ usasse entrambi gli indici $i$ e $j$ come primo e ultimo elemento (con $k \ge 2$), la coppia esterna $(x_i, x_j)$ violerebbe la condizione. Quindi $j_1 > i$ oppure $j_k < j$ (se $k = 1$ vale $j_k < j$ oppure $j_1 > i$ perché $i < j$). Nel primo caso $Z'$ è una sottosequenza quasi palindroma di $X_{i+1..j}$, nel secondo di $X_{i..j-1}$; in entrambi deve essere la migliore, altrimenti con il cut-and-paste se ne troverebbe una più lunga anche in $X_{i..j}$. Poiché le LQPS delle due sottostringhe sono anche sottosequenze quasi palindrome di $X_{i..j}$, $Z'$ è la più lunga delle due. $\square$

(b) Ricorrenza

Sia $\ell(i, j)$ la lunghezza di una LQPS di $X_{i..j}$, per $1 \le i \le j \le n$. Dalla proprietà:

$$\ell(i, j) = \begin{cases} 1 & i = j \\ 2 & (i = j - 1) \ \land \ (|x_i - x_j| \le 1) \\ 1 & (i = j - 1) \ \land \ (|x_i - x_j| > 1) \\ 2 + \ell(i+1, j-1) & (i < j - 1) \ \land \ (|x_i - x_j| \le 1) \\ \max\{\ell(i, j-1),\ \ell(i+1, j)\} & \text{altrimenti} \end{cases}$$

La risposta è $\ell(1, n)$.

(c) Algoritmo bottom-up

La cella $(i, j)$ dipende da $(i+1, j-1)$, $(i, j-1)$ e $(i+1, j)$, relative a sottostringhe più corte (di lunghezza $\ell - 2$, $\ell - 1$, $\ell - 1$ se $\ell = j - i + 1$): una scansione per diagonali di lunghezza crescente nel triangolo superiore della tabella $L[1..n, 1..n]$ è coerente. (Anche "righe dalla $n$ alla $1$" e "colonne con righe decrescenti" lo sono.)

LQPS(X)
  n <- |X|                                   { X = <x_1, ..., x_n> }
  for i <- 1 to n-1 do
    L[i, i] <- 1
    if |x_i - x_{i+1}| <= 1 then L[i, i+1] <- 2
    else L[i, i+1] <- 1
  L[n, n] <- 1                               { casi base: diagonali l = 1 e l = 2 }
  for l <- 3 to n do
    for i <- 1 to n-l+1 do
      j <- i + l - 1                         { sottostringa X_{i..j} }
      if |x_i - x_j| <= 1 then L[i, j] <- 2 + L[i+1, j-1]
      else L[i, j] <- MAX(L[i, j-1], L[i+1, j])
  return L[1, n]

Correttezza. Per induzione sulla lunghezza della sottostringa: le prime due diagonali realizzano i casi base della ricorrenza; per $\ell \ge 3$ le tre celle da cui dipende $(i, j)$ sono su diagonali già complete e corrette per ipotesi induttiva, e l'assegnamento implementa il caso corrispondente della ricorrenza, che è corretta per la proprietà (a). Per $n = 1$ si restituisce $L[1,1] = 1$. L'algoritmo è stato confrontato con l'enumerazione di tutte le sottosequenze su $600$ vettori casuali di interi piccoli (lunghezza fino a $10$): stesso risultato in tutti i casi.

Esempio. $X = \langle 3, 5, 4, 8, 4, 2, 6 \rangle$ ($n = 7$). Tabella $L[i, j]$ (triangolo superiore):

Alcune celle: $L[3,4]$: $|4 - 8| = 4 > 1$, quindi $\max\{L[3,3], L[4,4]\} = 1$. $L[2,5]$: $|5 - 4| = 1 \le 1$, quindi $2 + L[3,4] = 3$. $L[1,6]$: $|3 - 2| = 1$, quindi $2 + L[2,5] = 5$. $L[1,7]$: $|3 - 6| = 3 > 1$, quindi $\max\{L[1,6], L[2,7]\} = \max\{5, 5\} = 5$. Una LQPS di lunghezza $5$ è $\langle 3, 5, 4, 4, 2 \rangle$, con indici $1, 2, 3, 5, 6$ (coppie $(3,2)$, $(5,4)$ e centro $4$).

Complessità. Si fa una sola sottrazione tra caratteri (il valore assoluto e il confronto con $1$ non si contano) per ogni sottostringa di lunghezza $\ell \ge 2$, cioè una per ogni diagonale $\ell = 2, \dots, n$ e ogni cella:

$$T(n) = \sum_{\ell=2}^{n} \sum_{i=1}^{n-\ell+1} 1 = \sum_{\ell=2}^{n} (n - \ell + 1) = \sum_{\ell'=1}^{n-1} \ell' = \frac{n(n-1)}{2} = \Theta(n^2).$$

(Nella penultima uguaglianza si pone $\ell' = n - \ell + 1$, che va da $n - 1$ a $1$.) Per l'esempio $n = 7$: $21$ sottrazioni. Con le somme $2 + L[i+1, j-1]$ sui valori della tabella il conto resta quadratico; il numero di addizioni e sottrazioni tra i caratteri della stringa è quello sopra. Lo spazio è $\Theta(n^2)$, riducibile a lineare con tre vettori se serve solo la lunghezza.