Technical Summary: Nearly Optimal Internal Dictionary Matching

Problem Definition

The paper addresses the Internal Dictionary Matching (IDM) problem. In this setting, a large text $T$ of length $n$ is given in advance over a linearly sortable alphabet. A dictionary $D$ consists of $d$ substrings of $T$. The goal is to preprocess $T$ and $D$ to efficiently answer queries regarding the occurrences of patterns in $D$ within arbitrary substrings $T[l, r]$ of $T$.

The paper focuses on five specific query types:

1. Exists($l, r$): Determine if at least one pattern from $D$ occurs in $T[l, r]$.
2. Report($l, r$): Report all occurrences of all patterns from $D$ in $T[l, r]$.
3. ReportDistinct($l, r$): Report all distinct patterns from $D$ that occur in $T[l, r]$.
4. Count($l, r$): Count the total number of occurrences of all patterns from $D$ in $T[l, r]$.
5. CountDistinct($l, r$): Count the number of distinct patterns from $D$ that occur in $T[l, r]$.

This problem generalizes classical dictionary matching and internal pattern matching (IPM). It is particularly relevant for "internal" dictionaries where the total length of patterns $L$ is much larger than the number of patterns $d$ (e.g., dictionaries of all palindromes, squares, or non-primitive substrings), as the solution's complexity should depend on $n$ and $d$, not $L$.

Methodology: Basic Substring Structure (BASS)

The core contribution of the paper is the proposal of a novel $O(n)$-sized data structure named Basic Substring Structure (BASS). BASS organizes the substrings of $T$ using a two-dimensional grid and equivalence classes.

1. The Grid and Equivalence Classes

The structure maps every substring $T[l, r]$ to a point $(l, r)$ on a 2D grid.

• Equivalence Classes: Two substrings are equivalent if their "extensions" are identical. The extension of a substring $t$, denoted $ext(t)$, is the longest string $s$ such that $t$ is a substring of $s$ and $|occ(t)| = |occ(s)|$. This concept corresponds to nodes in the Compact Acyclic Word Graph (CDAWG).
• Blocks: In the grid, each equivalence class forms a "block" with a staircase-like shape. A block $B$ is defined by parameters: a row range $[left_B, right_B]$, a top boundary $top_B$, and a non-decreasing sequence of bottom boundaries $b_{left_B}, \dots, b_{right_B}$.
• Properties: The paper proves that all blocks within the same equivalence class share the same shape (up to translation). Furthermore, the sum of the lengths of the left and top boundaries of all distinct blocks is $O(n)$.

2. Tree Mappings

BASS integrates two modified suffix trees to formalize relationships between blocks:

• PreTree($T$): A suffix tree of $T$. It captures relationships between blocks sharing a column (ancestor-descendant relationships).
• SufTree($T$): A suffix tree of the reversed string $rev(T)$. It captures relationships between blocks sharing a row.
  These trees allow the structure to map grid coordinates to nodes efficiently, enabling $O(1)$ time location of a substring's equivalence class and its position within a block.

3. Query Processing Strategies

• Count Queries: The algorithm reduces the counting problem to a 2D range counting problem. By storing partial sums of pattern occurrences along block boundaries and utilizing a static 2D range counting data structure (based on Chan and Pătraşcu's work), the query time is optimized.
• CountDistinct Queries: This is the most complex query. The authors decompose the problem into two parts:
  1. Calculating the total occurrences ($A_1$) minus occurrences in a specific suffix range determined by a "key position" (the shortest suffix of $T[l, r]$ appearing exactly once).
  2. Subtracting overcounted patterns ($A_2$) based on the structure of the trie of suffixes.
     To handle this efficiently, the paper introduces event sets derived from Link-Cut Trees to track changes in occurrence counts as the query range shifts, allowing the computation of $A_2$ using persistent data structures.

Key Results and Contributions

The paper presents algorithms that achieve nearly optimal query and preprocessing times for all five query types. The results are summarized below (where $\tilde{O}$ suppresses polylogarithmic factors):

Query Type	Preprocessing Time	Query Time	Space
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)$

Note: $x$ denotes the length of the output.

Specific Improvements

1. CountDistinct: The paper resolves an open question from previous work [16] by providing the first algorithm that answers CountDistinct queries in $\tilde{O}(1)$ time (specifically $O(\log n)$) with $\tilde{O}(n+d)$ preprocessing. Previous best results required $\tilde{O}(m)$ query time with $\tilde{O}(n^2/m + d)$ preprocessing.
2. Count: The query time is improved from $O(\frac{\log^2 n}{\log \log n})$ to $O(\frac{\log n}{\log \log n})$, which the authors prove is optimal for data structures of size $\tilde{O}(n)$ based on lower bounds for 2D range counting.
3. ReportDistinct: The query time is improved from $O(\log n + x)$ to $O(1 + x)$.
4. General Applicability: The authors demonstrate that BASS can be applied to other internal query problems, such as the Range Longest Common Substring (RLCS) problem, achieving $O(1)$ query time and $O(n)$ preprocessing, improving upon the previous $O(\log n)$ query time.

Significance and Claims

The paper claims that BASS is the first data structure capable of handling all types of IDM queries with nearly optimal query and preprocessing times. Unlike previous works that treated different query types with tailored, disjoint approaches, BASS provides a unified framework.

The significance of the work lies in:

• Optimality: Matching known conditional lower bounds for dynamic dictionary matching (up to subpolynomial factors) and proving unconditional optimality for the Count query.
• Unified Framework: Successfully organizing equivalence classes into a 2D grid structure that bridges the gap between CDAWG concepts and efficient substring querying, a connection not fully explored in prior literature.
• Handling Large Dictionaries: Providing solutions where the complexity depends on the number of patterns $d$ rather than the total length of patterns $L$, making it suitable for complex internal dictionaries (e.g., all palindromes or squares).

The authors note that for dynamic dictionaries (where patterns can be added or deleted), they can construct algorithms that process updates in $\tilde{O}(n^\alpha)$ time and answer CountDistinct queries in $\tilde{O}(n^{1-\alpha})$ time, matching the known conditional lower bounds for this setting.