💻 computer science

Nearly Optimal Internal Dictionary Matching

Dit artikel introduceert de Basic Substring Structure (BASS), een $O(n)$ -grote datastructuur die bijna optimale query- en preprocesseringstijden bereikt voor het interne dictionary matching-probleem, inclusief de eerste $\tilde{O}(1)$ -tijd oplossing voor het tellen van het aantal unieke patroon-instanties.

Oorspronkelijke auteurs: Jingbang Chen, Jiangqi Dai, Qiuyang Mang, Qingyu Shi, Tingqiang Xu

Gepubliceerd 2026-07-02

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Jingbang Chen, Jiangqi Dai, Qiuyang Mang, Qingyu Shi, Tingqiang Xu

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een enorm, eindeloos boek hebt (laten we het Tekst T noemen). In dit boek zit een speciale lijst met woorden of zinnen verborgen (het Woordenboek D) die allemaal ergens in het boek zelf te vinden zijn.

Het probleem dat dit artikel oplost, is als een spelletje "Waar is Waldo?", maar dan met een twist: je wilt niet alleen één specifiek woord vinden. Je wilt vragen kunnen stellen over elk willekeurig deel van het boek. Bijvoorbeeld:

"Hoe vaak komen mijn speciale woorden voor in pagina 50 tot 100?"
"Hoeveel verschillende speciale woorden komen er in dat gedeelte voor?"
"Kun je elke keer dat ze voorkomen aan me laten zien?"

In het verleden was het beantwoorden van deze vragen traag of vereiste het een enorme hoeveelheid geheugen, vooral als het woordenboek uit duizenden kleine fragmenten uit het boek bestond. Dit artikel introduceert een nieuwe, super-efficiënte manier om het boek te organiseren, zodat je deze vragen bijna direct kunt beantwoorden.

Het Grote Idee: De "Basic Substring Structure" (BASS)

De auteurs hebben een nieuw hulpmiddel gebouwd genaamd BASS. Denk aan BASS als een gigantisch, magisch 2D-raster of een spreadsheet die elk mogelijk stukje van het boek in kaart brengt.

Het Raster: Stel je een spreadsheet voor waarbij de rijen de "waar een woord begint" vertegenwoordigen en de kolommen de "waar een woord eindigt". Elke cel in dit raster is een specifiek tekstfragment uit het boek.
De Kleuring: In plaats van alleen tekst in de cellen te schrijven, "kleuren" de auteurs de cellen. Als een stuk tekst deel uitmaakt van je speciale Woordenboek, krijgt die cel een speciale kleur.
De Blokken: Hier zit de magische truc. De auteurs realiseerden zich dat veel cellen die er verschillend uitzien, zich eigenlijk hetzelfde gedragen. Ze groeperen deze cellen in "blokken" die lijken op trappen. Alle cellen in één trappenblok delen dezelfde "persoonlijkheid" (ze komen in het boek op exact dezelfde plaatsen voor).

Door het boek op deze trappenblokken te organiseren, hoeft de computer niet elke pagina te controleren. De computer controleert simpelweg de "trap" om te zien wat er aan de hand is.

Wat kan dit hulpmiddel doen?

Het artikel beweert dat je met BASS vijf soorten vragen sneller en met minder geheugen kunt beantwoorden dan ooit tevoren:

Aantal voorkomens tellen (Count): "Hoe vaak komen mijn woorden voor in dit gedeelte?"
- De verbetering: Voorheen duurde dit een tijdje. Nu is het bijna direct klaar. De auteurs hebben bewezen dat dit de snelst mogelijke snelheid is voor dit type vraag.
Aantal unieke woorden tellen (CountDistinct): "Hoeveel verschillende woorden uit mijn lijst verschijnen hier?"
- De doorbraak: Dit was een moeilijk probleem. Voorheen moest je gissen of een trage methode gebruiken. De auteurs hebben dit volledig opgelost, waardoor er bijna direct (in logaritmische tijd) een antwoord wordt gegeven na een snelle setup.
Rapporteren (Report & ReportDistinct): "Laat me precies zien waar de woorden zijn."
- De verbetering: Het hulpmiddel kan de locaties nu zo snel opgeven als de computer ze kan uitprinten, zonder extra wachttijd.
Bestaan (Exists): "Is er enig woord uit mijn lijst in dit gedeelte?"
- De verbetering: Dit wordt nu in een fractie van een seconde beantwoord.

Hoe het werkt (De Analogie)

Stel je voor dat je op zoek bent naar specifieke ingrediënten in een gigantisch magazijn (het boek).

De Oude Manier: Je moest elk gangpad aflopen, elke plank controleren en de items tellen. Als je over een ander gedeelte wilde weten, moest je het hele magazijn opnieuw doorlopen.
De BASS-manier: De auteurs hebben een kaart van het magazijn gemaakt.
- Ze realiseerden zich dat bepaalde gangpaden altijd met dezelfde opstelling van dozen hebben. Ze hebben deze gangpaden gegroepeerd in "Super-Gangpaden" (de equivalentieklassen/blokken).
- Ze hebben een boom gebouwd (zoals een stamboom) die deze Super-Gangpaden met elkaar verbindt. Als je weet waar één doos is, vertelt de boom je precies waar de gerelateerde dozen zijn, zonder dat je er zelf naartoe hoeft te lopen.
- Ze hebben ook een tweede boom gebouwd die naar het magazijn kijkt vanuit de andere richting (beginnend bij het einde van het gangpad in plaats van het begin).

Door deze twee bomen en de rasterkaart samen te gebruiken, kan de computer direct naar het antwoord springen. De computer hoeft niet het hele magazijn door te lopen; hij kijkt gewoon op de kaart, volgt een paar takken op de boom en zegt: "Hier zijn de antwoorden."

Waarom dit belangrijk is (Volgens het Artikel)

Het artikel benadrukt dat dit een statisch probleem is, wat betekent dat het boek en de lijst met woorden niet veranderen terwijl je vragen stelt.

Snelheid: Ze hebben "bijna optimale" snelheid bereikt. Dit betekent dat ze zo snel zijn als de wiskunde toestaat voor dit type probleem.
Geheugen: Het hulpmiddel dat ze hebben gebouwd is zeer compact. Het neemt slechts ruimte in beslag die evenredig is aan de grootte van het boek, en niet aan de grootte van het woordenboek vermenigvuldigd met het boek.
Veelzijdigheid: Hoewel ze zich concentreerden op het probleem van het matchen van woordenboeken, hebben ze aangetoond dat deze "raster en boom"-structuur ook andere tekstproblemen kan oplossen, zoals het vinden van de langste gedeelde zin tussen twee verschillende boeken.

Kortom, de auteurs hebben een rommelig, complex probleem van het zoeken in tekst georganiseerd in een net, trapachtig raster verbonden door stambomen, waardoor computers bijna onmiddellijk antwoorden kunnen vinden.

Technisch Overzicht: Bijna Optimale Interne Dictionair Matching

Probleemdefinitie

Het artikel behandelt het Internal Dictionary Matching (IDM) probleem. In deze setting wordt vooraf een grote tekst $T$ van lengte $n$ gegeven over een lineair sorteerbaar alfabet. Een woordenboek $D$ bestaat uit $d$ deelstrings van $T$ . Het doel is om $T$ en $D$ voor te bewerken om efficiënt queries te beantwoorden met betrekking tot de voorkomens van patronen uit $D$ binnen willekeurige deelstrings $T[l, r]$ van $T$ .

Het artikel richt zich op vijf specifieke querytypen:

Exists( $l, r$ ): Bepaal of ten minste één patroon uit $D$ voorkomt in $T[l, r]$ .
Report( $l, r$ ): Rapporteer alle voorkomens van alle patronen uit $D$ in $T[l, r]$ .
ReportDistinct( $l, r$ ): Rapporteer alle verschillende patronen uit $D$ die in $T[l, r]$ voorkomen.
Count( $l, r$ ): Tel het totale aantal voorkomens van alle patronen uit $D$ in $T[l, r]$ .
CountDistinct( $l, r$ ): Tel het aantal verschillende patronen uit $D$ dat in $T[l, r]$ voorkomt.

Dit probleem generaliseert klassieke dictionary matching en internal pattern matching (IPM). Het is bijzonder relevant voor "interne" woordenboeken waar de totale lengte van de patronen $L$ veel groter is dan het aantal patronen $d$ (bijv. woordenboeken van alle palindromen, vierkanten of niet-primitieve deelstrings), aangezien de complexiteit van de oplossing afhankelijk moet zijn van $n$ en $d$ , en niet van $L$ .

Methodologie: Basic Substring Structure (BASS)

De kernbijdrage van het artikel is de voorstel van een nieuwe, $O(n)$ -grote datastructuur genaamd Basic Substring Structure (BASS). BASS organiseert de deelstrings van $T$ met behulp van een tweedimensionaal rooster en equivalentieklassen.

1. Het Rooster en de Equivalentieklassen

De structuur brengt elke deelstring $T[l, r]$ in kaart als een punt $(l, r)$ op een 2D-rooster.

Equivalentieklassen: Twee deelstrings zijn equivalent als hun "extensies" identiek zijn. De extensie van een deelstring $t$ , aangeduid als $ext(t)$, is de langste string $s$ waarvoor $t$ een deelstring is van $s$ en $|occ(t)| = |occ(s)|$. Dit concept komt overeen met knopen in de Compact Acyclic Word Graph (CDAWG).
Blokken: In het rooster vormt elke equivalentieklasse een "blok" met een trapvormige structuur. Een blok $B$ wordt gedefinieerd door parameters: een rijbereik $[left_B, right_B]$ , een bovenrand $top_B$ , en een niet-dalende sequentie van onderranden $b_{left_B}, \dots, b_{right_B}$ .
Eigenschappen: Het artikel bewijst dat alle blokken binnen dezelfde equivalentieklasse dezelfde vorm delen (op een translatie na). Bovendien is de som van de lengtes van de linker- en bovenranden van alle verschillende blokken $O(n)$ .

2. Boom-mappings

BASS integreert twee aangepaste suffixbomen om de relaties tussen blokken te formaliseren:

PreTree( $T$ ): Een suffixboom van $T$ . Het legt de relaties vast tussen blokken die een kolom delen (voorouder-afstammeling relaties).
SufTree( $T$ ): Een suffixboom van de omgekeerde string $rev(T)$. Het legt de relaties vast tussen blokken die een rij delen.
Deze bomen maken het mogelijk om de roostercoördinaten efficiënt in kaart te brengen naar knopen, wat $O(1)$ tijd mogelijk maakt voor het lokaliseren van de equivalentieklasse van een deelstring en de positie ervan binnen een blok.

3. Strategieën voor Queryverwerking

Count Queries: Het algoritme reduceert het telprobleem tot een 2D-range counting probleem. Door partiële sommen van patroonvoorkomens langs de grenzen van blokken op te slaan en gebruik te maken van een statische 2D range counting datastructuur (gebaseerd op het werk van Chan en Pătraşcu), wordt de querytijd geoptimaliseerd.
CountDistinct Queries: Dit is de meest complexe query. De auteurs ontleden het probleem in twee delen:
1. Het berekenen van het totale aantal voorkomens ( $A_1$ ) minus de voorkomens in een specifieke suffix-range bepaald door een "sleutelpositie" (de kortste suffix van $T[l, r]$ die precies één keer voorkomt).
2. Het aftrekken van overgetelde patronen ( $A_2$ ) gebaseerd op de structuur van de trie van suffixes.
  Om dit efficiënt af te handelen, introduceert het artikel event sets afgeleid van Link-Cut Trees om veranderingen in het aantal voorkomens bij het verschuiven van het querybereik bij te houden, waardoor de berekening van $A_2$ met persistente datastructuren mogelijk wordt.

Belangrijkste Resultaten en Bijdragen

Het artikel presenteert algoritmen die bijna optimale query- en voorbereidingstijden bereiken voor alle vijf de querytypen. De resultaten worden hieronder samengevat (waarbij $\tilde{O}$ polylogaritmische factoren onderdrukt):

Querytype	Voorbereidingstijd	Querytijd	Ruimte
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)$

Opmerking: $x$ duidt de lengte van de output aan.

Specifieke Verbeteringen

CountDistinct: Het artikel lost een openstaande vraag uit eerder werk [16] op door het eerste algoritme te bieden dat CountDistinct queries in $\tilde{O}(1)$ tijd (specifiek $O(\log n)$ ) beantwoordt met $\tilde{O}(n+d)$ voorbereidingstijd. Eerdere beste resultaten vereisten $\tilde{O}(m)$ querytijd met $\tilde{O}(n^2/m + d)$ voorbereidingstijd.
Count: De querytijd is verbeterd van $O(\frac{\log^2 n}{\log \log n})$ naar $O(\frac{\log n}{\log \log n})$ , wat de auteurs bewijzen optimaal is voor datastructuren van grootte $\tilde{O}(n)$ gebaseerd op ondergrenzen voor 2D range counting.
ReportDistinct: De querytijd is verbeterd van $O(\log n + x)$ naar $O(1 + x)$ .
Algemene Toepasbaarheid: De auteurs demonstreren dat BASS kan worden toegepast op andere interne queryproblemen, zoals het Range Longest Common Substring (RLCS) probleem, waarbij een $O(1)$ querytijd en $O(n)$ voorbereidingstijd wordt bereikt, wat de eerdere $O(\log n)$ querytijd verbetert.

Betekenis en Claims

Het artikel claimt dat BASS de eerste datastructuur is die in staat is om alle typen IDM-queries te behandelen met bijna optimale query- en voorbereidingstijden. In tegenstelling tot eerdere werken die verschillende querytypen met op maat gemaakte, uiteenlopende benaderingen behandelden, biedt BASS een verenigd kader.

De betekenis van het werk ligt in:

Optimaliteit: Het evenaren van bekende conditionele ondergrenzen voor dynamische dictionary matching (tot subpolynomiale factoren) en het bewijzen van onvoorwaardelijke optimaliteit voor de Count-query.
Verenigd Kader: Het succesvol organiseren van equivalentieklassen in een 2D-roosterstructuur die de kloof overbrugt tussen CDAWG-concepten en efficiënte deelstring-querying, een connectie die in eerdere literatuur niet volledig werd verkend.
Afhandeling van Grote Dictionaria: Het bieden van oplossingen waarbij de complexiteit afhangt van het aantal patronen $d$ in plaats van de totale lengte van de patronen $L$ , wat het geschikt maakt voor complexe interne woordenboeken (bijv. alle palindromen of vierkanten).

De auteurs merken op dat voor dynamische woordenboeken (waar patronen kunnen worden toegevoegd of verwijderd), zij algoritmen kunnen construeren die updates verwerken in $\tilde{O}(n^\alpha)$ tijd en CountDistinct queries beantwoorden in $\tilde{O}(n^{1-\alpha})$ tijd, wat overeenkomt met de bekende conditionele ondergrenzen voor deze setting.