Compact directed acyclic word graphs (CDAWGs) (Blumer et al. in J ACM 34(3):578–595, 1987) are a fundamental data structure on strings with applications in text pattern searching, data compression, and pattern discovery. Intuitively, the CDAWG of a string T is obtained by merging isomorphic subtrees of the suffix tree (Weiner, in: Proceedings of the 14th annual symposium on switching and automata theory, pp 1–11, 1973) of the same string T, thus CDAWGs are a compact indexing structure. In this paper, we investigate the sensitivity of CDAWGs when a single character edit operation (insertion, deletion, or substitution) is performed at the left-end of the input string T, namely, we are interested in the worst-case increase in the size of the CDAWG after a left-end edit operation. We prove that if <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="236_2025_478_Article_IEq1.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="9" /> </InlineMediaObject> <EquationSource Format="TEX">$\textsf{e}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">e</mi> </math></EquationSource> </InlineEquation> is the number of edges of the CDAWG for string T, then the number of new edges added to the CDAWG after a left-end edit operation on T does not exceed <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="236_2025_478_Article_IEq2.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="9" /> </InlineMediaObject> <EquationSource Format="TEX">$\textsf{e}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">e</mi> </math></EquationSource> </InlineEquation>. Further, we present a matching lower bound on the sensitivity of CDAWGs for left-end insertions, and almost matching lower bounds for left-end deletions and substitutions. We then generalize our lower-bound instance for left-end insertions to leftward online construction of the CDAWG, and show that it requires <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="236_2025_478_Article_IEq3.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="42" /> </InlineMediaObject> <EquationSource Format="TEX">$\Omega (n^2)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Ω</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mn>2</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> time for some string of length n.

Tight bounds for the sensitivity of CDAWGs with left-end edits

期刊论文
发表日期：

2025年2月4日

查看全文

Hiroto Fujimaru,
Yuto Nakashima,
Shunsuke Inenaga

摘要

Compact directed acyclic word graphs (CDAWGs) (Blumer et al. in J ACM 34(3):578–595, 1987) are a fundamental data structure on strings with applications in text pattern searching, data compression, and pattern discovery. Intuitively, the CDAWG of a string T is obtained by merging isomorphic subtrees of the suffix tree (Weiner, in: Proceedings of the 14th annual symposium on switching and automata theory, pp 1–11, 1973) of the same string T, thus CDAWGs are a compact indexing structure. In this paper, we investigate the sensitivity of CDAWGs when a single character edit operation (insertion, deletion, or substitution) is performed at the left-end of the input string T, namely, we are interested in the worst-case increase in the size of the CDAWG after a left-end edit operation. We prove that if $\textsf{e}$ $e$ is the number of edges of the CDAWG for string T, then the number of new edges added to the CDAWG after a left-end edit operation on T does not exceed $\textsf{e}$ $e$ . Further, we present a matching lower bound on the sensitivity of CDAWGs for left-end insertions, and almost matching lower bounds for left-end deletions and substitutions. We then generalize our lower-bound instance for left-end insertions to leftward online construction of the CDAWG, and show that it requires $\Omega (n^2)$ $Ω (n^{2})$ time for some string of length n.