Technisches Resümee: Nahezu optimales internes Wörterbuch-Matching

Problemdefinition

Die Arbeit befasst sich mit dem Problem des Internen Wörterbuch-Matchings (Internal Dictionary Matching, IDM). In diesem Szenario ist ein großer Text $T$ der Länge $n$ im Voraus über ein linear sortierbares Alphabet gegeben. Ein Wörterbuch $D$ besteht aus $d$ Substrings von $T$. Das Ziel ist es, $T$ und $D$ vorzuverarbeiten, um Abfragen bezüglich der Vorkommen von Mustern aus $D$ in beliebigen Teilbereichen $T[l, r]$ von $T$ effizient zu beantworten.

Die Arbeit konzentriert sich auf fünf spezifische Abfragetypen:

1. Exists($l, r$): Bestimmen, ob mindestens ein Muster aus $D$ in $T[l, r]$ vorkommt.
2. Report($l, r$): Alle Vorkommen aller Muster aus $D$ in $T[l, r]$ ausgeben.
3. ReportDistinct($l, r$): Alle distinkten Muster aus $D$ ausgeben, die in $T[l, r]$ vorkommen.
4. Count($l, r$): Die Gesamtzahl der Vorkommen aller Muster aus $D$ in $T[l, r]$ zählen.
5. CountDistinct($l, r$): Die Anzahl der distinkten Muster aus $D$ zählen, die in $T[l, r]$ vorkommen.

Dieses Problem generalisiert das klassische Wörterbuch-Matching und das interne Muster-Matching (IPM). Es ist besonders relevant für "interne" Wörterbücher, bei denen die Gesamtlänge der Muster $L$ viel größer ist als die Anzahl der Muster $d$ (z. B. Wörterbücher aller Palindrome, Quadrate oder nicht-primitiven Substrings), da die Komplexität der Lösung von $n$ und $d$ abhängen sollte, nicht von $L$.

Methodik: Basic Substring Structure (BASS)

Der Kernbeitrag der Arbeit ist der Vorschlag einer neuartigen Datenstruktur der Größe $O(n)$ namens Basic Substring Structure (BASS). BASS organisiert die Substrings von $T$ mithilfe eines zweidimensionalen Gitters und Äquivalenzklassen.

1. Das Gitter und Äquivalenzklassen

Die Struktur bildet jeden Substring $T[l, r]$ auf einen Punkt $(l, r)$ in einem 2D-Gitter ab.

• Äquivalenzklassen: Zwei Substrings sind äquivalent, wenn ihre "Erweiterungen" identisch sind. Die Erweiterung eines Substrings $t$, bezeichnet als $ext(t)$, ist der längste String $s$, sodass $t$ ein Substring von $s$ ist und $|occ(t)| = |occ(s)|$. Dieses Konzept entspricht den Knoten in einem Compact Acyclic Word Graph (CDAWG).
• Blöcke: Im Gitter bildet jede Äquivalenzklasse einen "Block" mit einer treppenartigen Form. Ein Block $B$ wird durch Parameter definiert: einen Zeilenbereich $[left_B, right_B]$, eine obere Grenze $top_B$ und eine nicht-abnehmende Sequenz von unteren Grenzen $b_{left_B}, \dots, b_{right_B}$.
• Eigenschaften: Die Arbeit beweist, dass alle Blöcke innerhalb derselben Äquivalenzklasse dieselbe Form (bis auf Translation) teilen. Zudem ist die Summe der Längen der linken und oberen Grenzen aller distinkten Blöcke $O(n)$.

2. Baum-Abbildungen

BASS integriert zwei modifizierte Suffixbäume, um die Beziehungen zwischen Blöcken zu formalisieren:

• PreTree($T$): Ein Suffixbaum von $T$. Er erfasst die Beziehungen zwischen Blöcken, die dieselbe Spalte teilen (Ahnen-Nachfahren-Beziehungen).
• SufTree($T$): Ein Suffixbaum des umgekehrten Strings $rev(T)$. Er erfasst die Beziehungen zwischen Blöcken, die dieselbe Zeile teilen.
  Diese Bäume ermöglichen es der Struktur, Gitterkoordinaten effizient auf Knoten abzubilden, was eine Lokalisierung der Äquivalenzklasse eines Substrings und seiner Position innerhalb eines Blocks in $O(1)$ Zeit ermöglicht.

3. Strategien zur Abfrageverarbeitung

• Count-Abfragen: Der Algorithmus reduziert das Zählproblem auf ein 2D-Bereichszählproblem. Durch das Speichern partieller Summen von Muster-Vorkommen entlang der Blockgrenzen und die Nutzung einer statischen 2D-Berechnungsdatenstruktur (basierend auf der Arbeit von Chan und Pătraşcu) wird die Abfragezeit optimiert.
• CountDistinct-Abfragen: Dies ist die komplexeste Abfrage. Die Autoren zerlegen das Problem in zwei Teile:
  1. Berechnung der Gesamtvorkommen ($A_1$) abzüglich der Vorkommen in einem spezifischen Suffix-Bereich, der durch eine "Schlüsselposition" bestimmt wird (der kürzeste Suffix von $T[l, r]$, der genau einmal vorkommt).
  2. Subtraktion überzähliger Muster ($A_2$) basierend auf der Struktur des Tries der Suffixe.
     Um dies effizient zu handhaben, führt die Arbeit Event-Sets ein, die aus Link-Cut-Bäumen abgeleitet sind, um Änderungen in den Vorkommenszahlen zu verfolgen, während sich der Abfragebereich verschiebt. Dies ermöglicht die Berechnung von $A_2$ unter Verwendung persistenter Datenstrukturen.

Hauptergebnisse und Beiträge

Die Arbeit präsentiert Algorithmen, die nahezu optimale Abfrage- und Vorverarbeitungszeiten für alle fünf Abfragetypen erreichen. Die Ergebnisse sind unten zusammengefasst (wobei $\tilde{O}$ polylogarithmische Faktoren unterdrückt):

Abfragetyp	Vorverarbeitungszeit	Abfragezeit	Speicherplatz
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)$

Hinweis: $x$ bezeichnet die Länge der Ausgabe.

Spezifische Verbesserungen

1. CountDistinct: Die Arbeit löst eine offene Frage früherer Arbeiten [16], indem sie den ersten Algorithmus bereitstellt, der CountDistinct-Abfragen in $\tilde{O}(1)$ Zeit (speziell $O(\log n)$) mit $\tilde{O}(n+d)$ Vorverarbeitung beantwortet. Bisherige beste Ergebnisse erforderten eine $\tilde{O}(m)$ Abfragezeit mit $\tilde{O}(n^2/m + d)$ Vorverarbeitung.
2. Count: Die Abfragezeit wird von $O(\frac{\log^2 n}{\log \log n})$ auf $O(\frac{\log n}{\log \log n})$ verbessert, was die Autoren als optimal für Datenstrukturen der Größe $\tilde{O}(n)$ basierend auf Untergrenzen für das 2D-Bereichszählen beweisen.
3. ReportDistinct: Die Abfragezeit wird von $O(\log n + x)$ auf $O(1 + x)$ verbessert.
4. Allgemeine Anwendbarkeit: Die Autoren demonstrieren, dass BASS auf andere interne Abfrageprobleme angewendet werden kann, wie das Range Longest Common Substring (RLCS) Problem, wobei eine $O(1)$ Abfragezeit und eine $O(n)$ Vorverarbeitung erreicht werden, was die bisherige $O(\log n)$ Abfragezeit verbessert.

Bedeutung und Behauptungen

Die Arbeit behauptet, dass BASS die erste Datenstruktur ist, die in der Lage ist, alle Arten von IDM-Abfragen mit nahezu optimalen Abfrage- und Vorverarbeitungszeiten zu handhaben. Im Gegensatz zu früheren Arbeiten, die verschiedene Abfragetypen mit maßgeschneiderten, getrennten Ansätzen behandelten, bietet BASS einen einheitlichen Rahmen.

Die Bedeutung der Arbeit liegt in:

• Optimalität: Erreichen der bekannten bedingten Untergrenzen für dynamisches Wörterbuch-Matching (bis hin zu subpolynomischen Faktoren) und Beweis der unbedingten Optimalität für die Count-Abfrage.
• Einheitlicher Rahmen: Erfolgreiche Organisation von Äquivalenzklassen in einer 2D-Gitterstruktur, die die Lücke zwischen CDAWG-Konzepten und effizientem Substring-Abfragen schließt – eine Verbindung, die in der bisherigen Literatur nicht vollständig untersucht wurde.
• Handhabung großer Wörterbücher: Bereitstellung von Lösungen, bei denen die Komplexität von der Anzahl der Muster $d$ statt der Gesamtlänge der Muster $L$ abhängt, was sie für komplexe interne Wörterbücher (z. B. alle Palindrome oder Quadrate) geeignet macht.

Die Autoren merken an, dass sie für dynamische Wörterbücher (bei denen Muster hinzugefügt oder gelöscht werden können) Algorithmen konstruieren können, die Updates in $\tilde{O}(n^\alpha)$ Zeit verarbeiten und CountDistinct-Abfragen in $\tilde{O}(n^{1-\alpha})$ Zeit beantworten, was den bekannten bedingten Untergrenzen für dieses Szenario entspricht.