Resumo Técnico: Correspondência de Dicionário Interno Quase Ótima

Definição do Problema

O artigo aborda o problema da Correspondência de Dicionário Interno (IDM - Internal Dictionary Matching). Neste cenário, um texto grande $T$ de comprimento $n$ é fornecido antecipadamente sobre um alfabeto linearmente ordenável. Um dicionário $D$ consiste em $d$ substrings de $T$. O objetivo é pré-processar $T$ e $D$ para responder eficientemente a consultas relativas às ocorrências de padrões de $D$ dentro de substrings arbitrárias $T[l, r]$ de $T$.

O artigo foca em cinco tipos específicos de consulta:

1. Exists($l, r$): Determina se pelo menos um padrão de $D$ ocorre em $T[l, r]$.
2. Report($l, r$): Relata todas as ocorrências de todos os padrões de $D$ em $T[l, r]$.
3. ReportDistinct($l, r$): Relata todas as substrings distintas de $D$ que ocorrem em $T[l, r]$.
4. Count($l, r$): Conta o número total de ocorrências de todos os padrões de $D$ em $T[l, r]$.
5. CountDistinct($l, r$): Conta o número de padrões distintos de $D$ que ocorrem em $T[l, r]$.

Este problema generaliza a correspondência de dicionário clássica e a correspondência de padrões internos (IPM). É particularmente relevante para dicionários "internos" onde o comprimento total dos padrões $L$ é muito maior que o número de padrões $d$ (por exemplo, dicionários de todos os palíndromos, quadrados ou substrings não primitivas), uma vez que a complexidade da solução deve depender de $n$ e $d$, não de $L$.

Metodologia: Estrutura de Substring Básica (BASS)

A principal contribuição do artigo é a proposta de uma nova estrutura de dados de tamanho $O(n)$ chamada Estrutura de Substring Básica (BASS). A BASS organiza as substrings de $T$ usando uma grade bidimensional e classes de equivalência.

1. A Grade e as Classes de Equivalência

A estrutura mapeia cada substring $T[l, r]$ para um ponto $(l, r)$ em uma grade 2D.

• Classes de Equivalência: Duas substrings são equivalentes se suas "extensões" forem idênticas. A extensão de uma substring $t$, denotada por $ext(t)$, é a maior string $s$ tal que $t$ é uma substring de $s$ e $|occ(t)| = |occ(s)|$. Esse conceito corresponde aos nós no Grafo Acíclico Compacto de Palavras (CDAWG).
• Blocos: Na grade, cada classe de equivalência forma um "bloco" com um formato de escada. Um bloco $B$ é definido por parâmetros: um intervalo de linhas $[left_B, right_B]$, uma fronteira superior $top_B$ e uma sequência não decrescente de fronteiras inferiores $b_{left_B}, \dots, b_{right_B}$.
• Propriedades: O artigo prova que todos os blocos dentro de uma mesma classe de equivalência compartilham o mesmo formato (salvo translação). Além disso, a soma dos comprimentos das fronteiras esquerda e superior de todos os blocos distintos é $O(n)$.

2. Mapeamentos de Árvore

A BASS integra duas árvores de sufixos modificadas para formalizar as relações entre os blocos:

• PreTree($T$): Uma árvore de sufixos de $T$. Ela captura as relações entre blocos que compartilham uma coluna (relações ancestral-descendente).
• SufTree($T$): Uma árvore de sufixos da string invertida $rev(T)$. Ela captura as relações entre blocos que compartilham uma linha.
  Essas árvores permitem que a estrutura mapeie coordenadas de grade para nós eficientemente, possibilitando a localização em tempo $O(1)$ da classe de equivalência de uma substring e sua posição dentro de um bloco.

3. Estratégias de Processamento de Consulta

• Consultas de Contagem (Count): O algoritmo reduz o problema de contagem para um problema de contagem de intervalo 2D. Ao armazenar somas parciais de ocorrências de padrões ao longo das fronteiras dos blocos e utilizar uma estrutura de dados de contagem de intervalo 2D estática (baseada no trabalho de Chan e Pătraşcu), o tempo de consulta é otimizado.
• Consultas de Contagem Distinta (CountDistinct): Esta é a consulta mais complexa. Os autores decompõem o problema em duas partes:
  1. Calculando as ocorrências totais ($A_1$) menos as ocorrências em um intervalo de sufixo específico determinado por uma "posição chave" (o sufixo mais curto de $T[l, r]$ que aparece exatamente uma vez).
  2. Subtraindo padrões contados excessivamente ($A_2$) com base na estrutura da trie de sufixos.
     Para lidar com isso de forma eficiente, o artigo introduz conjuntos de eventos derivados de Árvores Link-Cut para rastrear mudanças nas contagens de ocorrências conforme o intervalo da consulta se desloca, permitindo o cálculo de $A_2$ usando estruturas de dados persistentes.

Principais Resultados e Contribuições

O artigo apresenta algoritmos que alcançam tempos de consulta e pré-processamento quase ótimos para todos os cinco tipos de consulta. Os resultados são resumidos abaixo (onde $\tilde{O}$ suprime fatores polilogarítmicos):

Tipo de Consulta	Tempo de Pré-processamento	Tempo de Consulta	Espaço
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$ denota o comprimento da saída.

Melhorias Específicas

1. CountDistinct: O artigo resolve uma questão aberta de trabalhos anteriores [16] ao fornecer o primeiro algoritmo que responde a consultas CountDistinct em tempo $\tilde{O}(1)$ (especificamente $O(\log n)$) com pré-processamento $\tilde{O}(n+d)$. Os melhores resultados anteriores exigiam tempo de consulta $\tilde{O}(m)$ com pré-processamento $\tilde{O}(n^2/m + d)$.
2. Count: O tempo de consulta é melhorado de $O(\frac{\log^2 n}{\log \log n})$ para $O(\frac{\log n}{\log \log n})$, o que os autores provam ser ótimo para estruturas de dados de tamanho $\tilde{O}(n)$ baseadas em limites inferiores para contagem de intervalo 2D.
3. ReportDistinct: O tempo de consulta é melhorado de $O(\log n + x)$ para $O(1 + x)$.
4. Aplicabilidade Geral: Os autores demonstram que a BASS pode ser aplicada a outros problemas de consulta interna, como o problema de Maior Substring Comum de Intervalo (RLCS), alcançando tempo de consulta $O(1)$ e pré-processamento $O(n)$, melhorando o tempo de consulta anterior de $O(\log n)$.

Significância e Alegações

O artigo afirma que a BASS é a primeira estrutura de dados capaz de lidar com todos os tipos de consultas IDM com tempos de consulta e pré-processamento quase ótimos. Diferente de trabalhos anteriores que tratavam diferentes tipos de consulta com abordagens distintas e especializadas, a BASS fornece um framework unificado.

A significância do trabalho reside em:

• Otimalidade: Corresponder aos limites inferiores condicionais conhecidos para correspondência de dicionário dinâmica (até fatores subpolinomiais) e provar a otimalidade incondicional para a consulta Count.
• Framework Unificado: Organizar com sucesso as classes de equivalência em uma estrutura de grade 2D que faz a ponte entre os conceitos de CDAWG e a consulta eficiente de substrings, uma conexão não totalmente explorada na literatura anterior.
• Lidar com Grandes Dicionários: Fornecer soluções onde a complexidade depende do número de padrões $d$ em vez do comprimento total dos padrões $L$, tornando-a adequada para dicionários internos complexos (ex: todos os palíndromos ou quadrados).

Os autores observam que para dicionários dinâmicos (onde padrões podem ser adicionados ou deletados), eles podem construir algoritmos que processam atualizações em tempo $\tilde{O}(n^\alpha)$ e respondem a consultas CountDistinct em $\tilde{O}(n^{1-\alpha})$ tempo, correspondendo aos limites inferiores condicionais conhecidos para este cenário.