Riepilogo Tecnico: Corrispondenza di Dizionario Interno Quasi Ottimale

Definizione del Problema

Il documento affronta il problema della Corrispondenza di Dizionario Interno (Internal Dictionary Matching - IDM). In questo contesto, viene fornito in anticipo un testo $T$ di grandi dimensioni di lunghezza $n$ su un alfabeto linearmente ordinabile. Un dizionario $D$ consiste in $d$ sottostringhe di $T$. L'obiettivo è preelaborare $T$ e $D$ per rispondere efficientemente alle query riguardanti le occorrenze di pattern presenti in $D$ all'interno di arbitrarie sottostringhe $T[l, r]$ di $T$.

Il documento si concentra su cinque tipi specifici di query:

1. Exists($l, r$): Determina se almeno un pattern da $D$ occorre in $T[l, r]$.
2. Report($l, r$): Riporta tutte le occorrenze di tutti i pattern da $D$ in $T[l, r]$.
3. ReportDistinct($l, r$): Riporta tutti i pattern distinti da $D$ che occorrono in $T[l, r]$.
4. Count($l, r$): Conta il numero totale di occorrenze di tutti i pattern da $D$ in $T[l, r]$.
5. CountDistinct($l, r$): Conta il numero di pattern distinti da $D$ che occorrono in $T[l, r]$.

Questo problema generalizza la classica corrispondenza di dizionario e l'internal pattern matching (IPM). È particolarmente rilevante per i dizionari "interni" dove la lunghezza totale dei pattern $L$ è molto più grande del numero di pattern $d$ (ad esempio, dizionari di tutti i palindromi, quadrati o sottostringhe non primitive), poiché la complessità della soluzione deve dipendere da $n$ e $d$, non da $L$.

Metodologia: Basic Substring Structure (BASS)

Il contributo principale del documento è la proposta di una nuova struttura dati di dimensione $O(n)$ denominata Basic Substring Structure (BASS). BASS organizza le sottostringhe di $T$ utilizzando una griglia bidimensionale e classi di equivalenza.

1. La Griglia e le Classi di Equivalenza

La struttura mappa ogni sottostringa $T[l, r]$ in un punto $(l, r)$ su una griglia 2D.

• Classi di Equivalenza: Due sottostringhe sono equivalenti se le loro "estensioni" sono identiche. L'estensione di una sottostringa $t$, denotata $ext(t)$, è la stringa più lunga $s$ tale che $t$ sia una sottostringa di $s$ e $|occ(t)| = |occ(s)|$. Questo concetto corrisponde ai nodi in un Grafo Aciclico di Parole Compatto (CDAWG).
• Blocchi: Nella griglia, ogni classe di equivalenza forma un "blocco" con una forma a gradini. Un blocco $B$ è definito dai parametri: un intervallo di righe $[left_B, right_B]$, un confine superiore $top_B$ e una sequenza non decrescente di confini inferiori $b_{left_B}, \dots, b_{right_B}$.
• Proprietà: Il documento dimostra che tutti i blocchi all'interno della stessa classe di equivalenza condividono la stessa forma (salvo traslazione). Inoltre, la somma delle lunghezze dei confini sinistro e superiore di tutti i blocchi distinti è $O(n)$.

2. Mappature ad Albero

BASS integra due alberi di suffissi modificati per formalizzare le relazioni tra i blocchi:

• PreTree($T$): Un albero dei suffissi di $T$. Cattura le relazioni tra i blocchi che condividono una colonna (relazioni antenato-discendente).
• SufTree($T$): Un albero dei suffissi della stringa invertita $rev(T)$. Cattura le relazioni tra i blocchi che condividono una riga.
  Questi alberi permettono alla struttura di mappare le coordinate della griglia ai nodi in modo efficiente, consentendo la localizzazione in tempo $O(1)$ di una classe di equivalenza di una sottostringa e della sua posizione all'interno di un blocco.

3. Strategie di Elaborazione delle Query

• Query di Conteggio (Count): L'algoritmo riduce il problema del conteggio a un problema di conteggio di intervalli 2D. Utilizzando la memorizzazione di somme parziali delle occorrenze dei pattern lungo i confini dei blocchi e un'apposita struttura dati per il conteggio di intervalli 2D statici (basata sul lavoro di Chan e Pătraşcu), il tempo di query viene ottimizzato.
• Query di Conteggio Distinto (CountDistinct): Questa è la query più complessa. Gli autori decompongono il problema in due parti:
  1. Calcolo delle occorrenze totali ($A_1$) meno le occorrenze in un intervallo di suffissi specifico determinato da una "posizione chiave" (il suffisso più breve di $T[l, r]$ che appare esattamente una volta).
  2. Sottrazione dei pattern contati più volte ($A_2$) basandosi sulla struttura del trie dei suffissi.
     Per gestire ciò in modo efficiento, il documento introduce insiemi di eventi derivati da Link-Cut Trees per tracciare i cambiamenti nei conteggi delle occorrenze al variare dell'intervallo di query, consentendo il calcolo di $A_2$ tramite strutture dati persistenti.

Risultati Chiave e Contributi

Il documento presenta algoritmi che raggiungono tempi di query e di preelaborazione quasi ottimali per tutti i cinque tipi di query. I risultati sono riassunti di seguito (dove $\tilde{O}$ sopprime i fattori polilogaritmici):

Tipo di Query	Tempo di Preelaborazione	Tempo di Query	Spazio
Exists	$O(n + d)$	$O(1)$	$O(n + d)$
Report	$O(n + d)$	$O(1 + x)$	$O(n + d)$
Count	$O(n + d\sqrt{\log n})$	$O(\frac{\log n}{\log \log n})$	$O(n + d)$
ReportDistinct	$O(n \log n + d)$	$O(1 + x)$	$O(n + d)$
CountDistinct	$O(n \log^2 n + d\sqrt{\log n})$	$O(\log n)$	$O(n \log^2 n + d)$

Nota: $x$ indica la lunghezza dell'output.

Miglioramenti Specifici

1. CountDistinct: Il documento risolve una questione aperta del lavoro precedente [16] fornendo il primo algoritmo capace di rispondere alle query CountDistinct in tempo $\tilde{O}(1)$ (specificamente $O(\log n)$) con preelaborazione $\tilde{O}(n+d)$. I migliori risultati precedenti richiedevano un tempo di query $\tilde{O}(m)$ con preelaborazione $\tilde{O}(n^2/m + d)$.
2. Count: Il tempo di query è migliorato da $O(\frac{\log^2 n}{\log \log n})$ a $O(\frac{\log n}{\log \log n})$, che gli autori dimostrano essere ottimale per strutture dati di dimensione $\tilde{O}(n)$ basandosi sui lower bound per il conteggio di intervalli 2D.
3. ReportDistinct: Il tempo di query è migliorato da $O(\log n + x)$ a $O(1 + x)$.
4. Applicabilità Generale: Gli autori dimostrano che BASS può essere applicato ad altri problemi di query interna, come il problema della Longest Common Substring di Intervallo (RLCS), ottenendo un tempo di query $O(1)$ e una preelaborazione $O(n)$, migliorando il precedente tempo di query $O(\log n)$.

Significato e Rivendicazioni

Il documento afferma che BASS è la prima struttura dati in grado di gestire tutti i tipi di query IDM con tempi di query e di preelaborazione quasi ottimali. A differenza dei lavori precedenti che trattavano diversi tipi di query con approcci specializzati e disgiunti, BASS fornisce un framework unificato.

La significatività del lavoro risiede in:

• Ottimalità: Il raggiungimento dei conosciuti lower bound condizionali per la corrispondenza di dizionario dinamica (fino ai fattori subpolinomiali) e la dimostrazione dell'ottimalità incondizionata per la query Count.
• Framework Unificato: L'organizzazione riuscita delle classi di equivalenza in una struttura a griglia 2D che colma il divario tra i concetti di CDAWG e l'efficiente interrogazione delle sottostringhe, una connessione non pienamente esplorata nella letteratura precedente.
• Gestione di Dizionari Grandi: La fornitura di soluzioni dove la complessità dipende dal numero di pattern $d$ piuttosto che dalla lunghezza totale dei pattern $L$, rendendole adatte a dizionari interni complessi (ad esempio, tutti i palindromi o i quadrati).

Gli autori osservano che per i dizionari dinamici (dove i pattern possono essere aggiunti o eliminati), possono costruire algoritmi che elaborano gli aggiornamenti in tempo $\tilde{O}(n^\alpha)$ e rispondono alle query CountDistinct in $\tilde{O}(n^{1-\alpha})$ tempo, eguagliando i noti lower bound condizionali per questo scenario.