Sintesi Tecnica: Corrispondenza di Permutazioni sotto Budget di Parikh

1. Definizione del Problema

Il documento affronta il problema della Corrispondenza di Pattern di Permutazione (Jumbled/Abelian) su un alfabeto generale $\Sigma$. Dato un pattern $P$ di lunghezza $m$ e un testo $T$ di lunghezza $n$, il compito classico è determinare se $T$ contiene una sottostringa di lunghezza $m$ il cui multiset di simboli corrisponde a quello di $P$. Ciò equivale a verificare se il vettore di Parikh (vettore di frequenza) di una finestra in $T$ è uguale al vettore di Parikh di $P$.

Oltre alla mera rilevazione, gli autori estendono l'ambito a due varianti di ottimizzazione:

1. Sottostringa Massima Fattibile sotto Fornitura di Pattern (MFSP): Trattando i conteggi dei simboli di $P$ come un budget di risorse (vettore di fornitura), l'obiettivo è trovare la sottostringa più lunga $S$ di $T$ tale che i conteggi dei simboli di $S$ siano componenti per componente limitati da quelli di $P$ (ovvero, $freq(S) \preceq freq(P)$).
2. Selezione Non Sovrapposta: Dato un insieme di tutte le corrispondenze di permutazione in $T$, selezionare il sottoinsieme a cardinalità massima di queste corrispondenze in modo che nessuna due corrispondenze selezionate si sovrappongano. Poiché tutte le corrispondenze hanno lunghezza $m$, questo viene modellato come un problema di packing di intervalli.

2. Metodologia e Algoritmi

Il documento propone un framework unificato basato su algoritmi a finestra scorrevole (sliding-window) e mantenimento della differenza del vettore di Parikh.

2.1 Corrispondenza di Permutazione in Tempo Lineare (Baseline)

Gli autori presentano un algoritmo per rilevare occorrenze di permutazione in $O(n + \sigma)$ tempo e $O(\sigma)$ spazio, dove $\sigma = |\Sigma|$.

• Meccanismo: Invece di ricalcolare i vettori di frequenza per ogni finestra, l'algoritmo mantiene un vettore di differenza $\Delta_i(c) = freq(W_i)(c) - freq(P)(c)$ per la finestra corrente $W_i$.
• Ottimizzazione: Un singolo contatore intero, $nz_i$, traccia il numero di voci non nulle in $\Delta_i$. Una finestra è una corrispondenza se e solo se $nz_i = 0$.
• Aggiornamenti: Quando la finestra scorre, solo due coordinate di $\Delta$ cambiano (un carattere esce, uno entra). L'algoritmo aggiorna $nz$ in tempo costante in base al fatto che una coordinata attraversi lo zero.

2.2 MFSP: Sottostringa Massima Fattibile

Per risolvere la variante di packing, gli autori introducono un algoritmo a due puntatori (finestra scorrevole) che opera anch'esso in $O(n + \sigma)$ tempo.

• Meccanismo: L'algoritmo mantiene una finestra $T[\ell..r]$ e un array di conteggio cnt per la finestra corrente. Un contatore di violazioni viol traccia quanti simboli superano il loro budget definito da $freq(P)$.
• Logica: Il puntatore destro $r$ espande la finestra. Se l'aggiunta di un carattere causa una violazione (ovvero, cnt eccede sup), il puntatore sinistro $\ell$ avanza finché la fattibilità non viene ripristinata.
• Correttezza: L'algoritmo si basa sulla monotonicità della fattibilità: restringere una finestra da sinistra non aumenta mai i conteggi dei simboli. La prova stabilisce che per ogni estremo destro $r$, l'algoritmo trova la sottostringa massima fattibile che termina in $r$, garantendo l'ottimalità globale.

2.3 Selezione Non Sovrapposta tramite Interval Packing

Una volta enumerate tutte le corrispondenze di permutazione (usando l'algoritmo baseline), il problema di selezione viene risolto tramite una strategia greedy.

• Meccanismo: Poiché tutte le corrispondenze corrispondono a intervalli di uguale lunghezza $m$, il problema si riduce alla selezione del massimo numero di intervalli disgiunti.
• Strategia: L'algoritmo scansiona il testo da sinistra a destra, selezionando la prima corrispondenza disponibile e poi saltando in avanti di $m$ posizioni verso la successiva potenziale corrispondenza non sovrapposta.
• Prova: Un argomento di scambio dimostra che questa regola greedy "a fine più precoce" (o inizio più precoce, data l'uguaglianza delle lunghezze) produce un insieme a cardinalità massima.

3. Contributi Chiave

1. Framework Unificato: Un approccio conciso a finestra scorrevole che gestisce rilevamento, ottimizzazione (MFSP) e selezione utilizzando il mantenimento della differenza di Parikh.
2. Complessità Ottimale: Tutti gli algoritmi proposti raggiungono un tempo di $O(n + \sigma)$ e uno spazio di $O(\sigma)$. Questo corrisponde al limite inferiore per la lettura dell'input ed è ottimale per alfabeti generali.
3. Formulazione MFSP: L'introduzione del problema MFSP, che inquadra il matching jumbled come un problema di packing con vincoli di risorse, risolto con un algoritmo a due puntatori provabilmente corretto in tempo lineare.
4. Ottimalità Greedy: Una prova formale che una semplice scansione greedy è ottimale per selezionare corrispondenze di permutazione non sovrapposte quando tutte hanno la stessa lunghezza.

4. Risultati e Osservazioni Sperimentali

Gli autori riportano leggere osservazioni sperimentali per corroborare i limiti teorici:

• Scalabilità: Sia la corrispondenza di permutazione che l'MFSP mostrano una scalabilità lineare con la lunghezza del testo $n$, coerente con l'analisi $O(n + \sigma)$.
• Fattori di Performance: Il tempo di esecuzione è dominato dai pattern di accesso alla memoria degli array/mappe di conteggio e dalla densità delle corrispondenze (che influenza il volume dell'output ma non la logica di scansione).
• Gestione dell'Alfabeto: Per alfabeti grandi, la compressione dell'alfabeto (mappare i simboli che appaiono in $P$ e $T$ in interi $1 \dots \sigma'$) riduce significativamente l'impronta di memoria e migliora la località del cache, mantenendo l'efficienza anche quando $\sigma$ è grande ma $\sigma'$ è piccolo.
• Efficienza MFSP: Il meccanismo del contatore di violazioni in MFSP evita controlli completi di fattibilità, garantendo che ogni carattere venga aggiunto o rimosso al massimo una volta, aderendo allo standard dell'ammortamento a due puntatori.

5. Significato e Ambito

Il documento posiziona il matching di stringhe basato su frequenza non solo come un compito di rilevamento, ma come una base per primitivi di ottimizzazione combinatoria.

• Contributo Teorico: Collega il classico problema del matching jumbled alla ottimizzazione di tipo packing, fornendo limiti stretti e algoritmi concisi.
• Utilità Pratica: Gli algoritmi sono progettati per la scansione in un unico passaggio (single-pass), rendendoli adatti ad applicazioni che richiedono l'elaborazione in tempo reale o l'ottimizzazione sotto vincoli di risorse (ad esempio, budget di token nell'elaborazione del testo).
• Modestia: Gli autori dichiarano esplicitamente che il loro focus è sui primitivi di rilevamento e ottimizzazione piuttosto che sulla costruzione di indici per query multiple. Riconoscono che lavori futuri potrebbero esplorare estensioni pesate o approssimate di MFSP, ma il contributo attuale è strettamente limitato a soluzioni esatte in tempo lineare per i problemi definiti.

Il lavoro conclude che, mantenendo le differenze del vettore di Parikh e utilizzando semplici strategie greedy o a due puntatori, è possibile risolvere varianti complesse della corrispondenza di permutazione con una correttezza dimostrabile e una complessità ottimale in tempo lineare.