Résumé Technique : Correspondance de Dictionnaire Interne Presque Optimale

Définition du Problème

L'article traite du problème de la Correspondance de Dictionnaire Interne (IDM - Internal Dictionary Matching). Dans ce cadre, un texte $T$ de grande taille de longueur $n$ est donné à l'avance sur un alphabet linéairement triable. Un dictionnaire $D$ est constitué de $d$ sous-chaînes de $T$. L'objectif est de prétraiter $T$ et $D$ pour répondre efficacement aux requêtes concernant les occurrences de motifs de $D$ dans des sous-chaînes arbitraires $T[l, r]$ de $T$.

L'article se concentre sur cinq types de requêtes spécifiques :

1. Exists($l, r$) : Déterminer si au moins un motif de $D$ apparaît dans $T[l, r]$.
2. Report($l, r$) : Rapporter toutes les occurrences de tous les motifs de $D$ dans $T[l, r]$.
3. ReportDistinct($l, r$) : Rapporter tous les motifs distincts de $D$ qui apparaissent dans $T[l, r]$.
4. Count($l, r$) : Compter le nombre total d'occurrences de tous les motifs de $D$ dans $T[l, r]$.
5. CountDistinct($l, r$) : Compter le nombre de motifs distincts de $D$ qui apparaissent dans $T[l, r]$.

Ce problème généralise la correspondance de dictionnaire classique et la correspondance de motifs internes (IPM). Il est particulièrement pertinent pour les dictionnaires « internes » où la longueur totale des motifs $L$ est beaucoup plus grande que le nombre de motifs $d$ (par exemple, les dictionnaires de tous les palindromes, carrés ou sous-chaînes non primitives), car la complexité de la solution doit dépendre de $n$ et $d$, et non de $L$.

Méthodologie : Basic Substring Structure (BASS)

La contribution centrale de l'article est la proposition d'une nouvelle structure de données de taille $O(n)$ nommée Basic Substring Structure (BASS). BASS organise les sous-chaînes de $T$ en utilisant une grille bidimensionnelle et des classes d'équivalence.

1. La Grille et les Classes d'Équivalence

La structure associe chaque sous-chaîne $T[l, r]$ à un point $(l, r)$ sur une grille 2D.

• Classes d'Équivalence : Deux sous-chaînes sont équivalentes si leurs « extensions » sont identiques. L'extension d'une sous-chaîne $t$, notée $ext(t)$, est la plus longue chaîne $s$ telle que $t$ est une sous-chaîne de $s$ et $|occ(t)| = |occ(s)|$. Ce concept correspond aux nœuds d'un Graphe Acyclique Compact de Mots (CDAWG).
• Blocs : Dans la grille, chaque classe d'équivalence forme un « bloc » avec une forme en escalier. Un bloc $B$ est défini par des paramètres : une plage de lignes $[left_B, right_B]$, une limite supérieure $top_B$, et une séquence non décroissante de limites inférieures $b_{left_B}, \dots, b_{right_B}$.
• Propriétés : L'article prouve que tous les blocs au sein d'une même classe d'équivalence partagent la même forme (à un facteur de translation près). De plus, la somme des longueurs des limites gauche et supérieure de tous les blocs distincts est de $O(n)$.

2. Mappages d'Arbres

BASS intègre deux arbres de suffixes modifiés pour formaliser les relations entre les blocs :

• PreTree($T$) : Un arbre de suffixes de $T$. Il capture les relations entre les blocs partageant une colonne (relations ancêtre-descendant).
• SufTree($T$) : Un arbre de suffixes de la chaîne inversée $rev(T)$. Il capture les relations entre les blocs partageant une ligne.
  Ces arbres permettent à la structure de mapper les coordonnées de la grille vers les nœuds efficacement, permettant de localiser en $O(1)$ la classe d'équivalence d'une sous-chaîne et sa position au sein d'un bloc.

3. Stratégies de Traitement des Requêtes

• Requêtes de Comptage (Count) : L'algorithme réduit le problème de comptage à un problème de comptage de plages 2D. En stockant les sommes partielles des occurrences de motifs le long des frontières des blocs et en utilisant une structure de données de comptage de plages 2D statique (basée sur les travaux de Chan et Pătraşcu), le temps de requête est optimisé.
• Requêtes de Comptage Distinct (CountDistinct) : C'est la requête la plus complexe. Les auteurs décomposent le problème en deux parties :
  1. Calculer le nombre total d'occurrences ($A_1$) moins les occurrences dans une plage de suffixe spécifique déterminée par une « position clé » (le suffixe le plus court de $T[l, r]$ apparaissant exactement une fois).
  2. Soustraire les motifs comptés plusieurs fois ($A_2$) basées sur la structure du trie des suffixes.
     Pour gérer cela efficacement, l'article introduit des ensembles d'événements dérivés des Link-Cut Trees pour suivre les changements des comptes d'occurrences à mesure que la plage de requête se déplace, permettant le calcul de $A_2$ à l'aide de structures de données persistantes.

Résultats Clés et Contributions

L'article présente des algorithmes qui atteignent des temps de requête et de prétraitement presque optimaux pour les cinq types de requêtes. Les résultats sont résumés ci-dessous (où $\tilde{O}$ supprime les facteurs polylogarithmiques) :

Type de Requête	Temps de Prétraitement	Temps de Requête	Espace
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$ désigne la longueur de la sortie.

Améliorations Spécifiques

1. CountDistinct : L'article résout une question ouverte issue de travaux précédents [16] en fournissant le premier algorithme capable de répondre aux requêtes CountDistinct en temps $\tilde{O}(1)$ (spécifiquement $O(\log n)$) avec un prétraitement en $\tilde{O}(n+d)$. Les meilleurs résultats précédents nécessitaient un temps de requête de $\tilde{O}(m)$ avec un prétraitement de $\tilde{O}(n^2/m + d)$.
2. Count : Le temps de requête est amélioré de $O(\frac{\log^2 n}{\log \log n})$ à $O(\frac{\log n}{\log \log n})$, ce que les auteurs prouvent être optimal pour des structures de données de taille $\tilde{O}(n)$ basées sur les bornes inférieures pour le comptage de plages 2D.
3. ReportDistinct : Le temps de requête est amélioré de $O(\log n + x)$ à $O(1 + x)$.
4. Applicabilité Générale : Les auteurs démontrent que BASS peut être appliqué à d'autres problèmes de requêtes internes, tels que le problème de la Plus Longue Sous-Chaîne Commune de Plage (RLCS), atteignant un temps de requête de $O(1)$ et un prétraitement de $O(n)$, améliorant ainsi le précédent $O(\log n)$ de temps de requête.

Signification et Revendications

L'article affirme que BASS est la première structure de données capable de gérer tous les types de requêtes IDM avec des temps de requête et de prétraitement presque optimaux. Contrairement aux travaux précédents qui traitaient différents types de requêtes avec des approches disjointes et sur mesure, BASS fournit un cadre unifié.

La signification du travail réside dans :

• Optimalité : Correspondre aux bornes inférieures conditionnelles connues pour la correspondance de dictionnaire dynamique (jusqu'aux facteurs sous-polynomials) et prouver l'optimalité inconditionnelle pour la requête Count.
• Cadre Unifié : Réussir à organiser les classes d'équivalence dans une structure de grille 2D qui comble le fossé entre les concepts de CDAWG et l'interrogation efficace des sous-chaînes, une connexion qui n'avait pas été pleinement explorée dans la littérature antérieure.
• Gestion de Dictionnaires Volumineux : Fournir des solutions où la complexité dépend du nombre de motifs $d$ plutôt que de la longueur totale des motifs $L$, ce qui les rend adaptées aux dictionnaires internes complexes (par exemple, tous les palindromes ou carrés).

Les auteurs notent que pour les dictionnaires dynamiques (où les motifs peuvent être ajoutés ou supprimés), ils peuvent construire des algorithmes qui traitent les mises à jour en temps $\tilde{O}(n^\alpha)$ et répondent aux requêtes CountDistinct en $\tilde{O}(n^{1-\alpha})$, correspondant aux bornes inférieures conditionnelles connues pour ce cadre.