Constant sensitivity on the CDAWGs

Rikuya Hamai, Hiroto Fujimaru, Shunsuke Inenaga · 2025

Read Constant sensitivity on the CDAWGs by Rikuya Hamai, Hiroto Fujimaru, Shunsuke Inenaga (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-05915.txt.

Introduction

Rikuya Hamai, Hiroto Fujimaru, and Shunsuke Inenaga study a compact index for strings called the CDAWG. Their paper is from two thousand twenty-five. The index merges like subtrees of a suffix tree, which makes it small yet useful for search, squeezing data, and finding patterns in text.

They ask what happens to its size when one character in the string is changed at any spot. An edit can insert, delete, or swap a character. They prove the new index stays within a fixed bound: at most about eight times the size of the old one, in the long run. That bound helps users trust the index under small changes.

Catalog record

CREATORRikuya Hamai, Hiroto Fujimaru, Shunsuke Inenaga
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE48 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-05915

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Constant sensitivity on the CDAWGs Rikuya Hamai, Hiroto Fujimaru, Shunsuke Inenaga Abstract Compact directed acyclic word graphs ( CDAWGs ) [Blumer et al. 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 T is obtained by merging isomorphic subtrees of the suffix tree [Weiner 1973] of the same string T T , and thus CDAWGs are a compact indexing structure. In this paper, we investigate the sensitivity of CDAWGs when a single character edit operation is performed at an arbitrary position in T T . We show that the size of the CDAWG after an edit operation on T T is asymptotically at most 8 times larger than the original CDAWG before the edit. 1 Introduction Compact directed acyclic word graphs ( CDAWGs ) [ 5 ] 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 (denoted \mathsf{CDAWG}(T) ) is a minimal partial DFA that is obtained by merging isomorphic subtrees of the suffix tree [ 25 ] of the same string T . CDAWGs permit pattern matching in optimal O(m+occ) time for a pattern P of length m when P occurs occ times in T . In practice, CDAWGs enjoy applications in natural language processing [ 24 ] and in analysis of text generated by language models (LMs) [ 18 ] . In a more theoretical perspective, CDAWGs are used as a space-efficient data structure that allows for optimal-time detection of “unusual words” (such as minimal absent words (MAWs) [ 7 ] and minimal unique substrings (MUSs) [ 11 ] ) from the input string [ 3 , 15 , 19 ] . A substring w of T which occurs at least twice in T is said to be a maximal repeat of T , if extending w to the left or to the right in T decreases the number of occurrences in T . It is known that there is a one-to-one correspondence between the internal nodes of \mathsf{CDAWG}(T) and the maximal repeats in T . Also, there is a one-to-one correspondence between the out-edges of the internal nodes of \mathsf{CDAWG}(T) and the right-extensions of the maximal repeats in T . Let \mathsf{e} denote the size (i.e. the number of edges) of the CDAWG for the input string. It is known that \mathsf{e}\leq 2n-2 holds [ 5 ] for any strings of length n , and \mathsf{e} can be much smaller for some highly repetitive strings: \mathsf{e}\in\Theta(\log n) holds for Fibonacci words, Standard Sturmian words, and Thue-Morse words of length n [ 22 , 2 , 20 ] . This contrasts to the suffix tree and the (uncompacted) directed acyclic word graph (DAWG) [ 4 ] each requiring \Theta(n) space for any string of length n . CDAWGs can thus be regarded as a compressed text indexing structure which can be stored in O(\mathsf{e}) space [ 3 , 12 ] without explicitly storing the string. In addition, a grammar compression of size O(\mathsf{e}) based on the CDAWG exists [ 3 ] . The sensitivity of string compressors, first proposed by Akagi et al. [ 1 ] , measures how much a single-character-wise edit operation on the input string can increase the size of the compressed string, which is formalized as follows: Let C be a compression algorithm and let C(T) denote the size of the output of C applied to the input string T . The worst-case multiplicative sensitivity of C is defined by \max_{T\in\Sigma^{n},T^{\prime}\in\Sigma^{n^{\prime}}}\{C(T^{\prime})/C(T):\mathsf{ed}(T,T^{\prime})=1\}, where \mathsf{ed}(T,T^{\prime}) denotes the edit distance between T and T^{\prime} , n^{\prime}=n for substitutions, n=n+1 for insertions, and n^{\prime}=n-1 for deletions. This is a natural measure for the robustness of compression algorithms in terms of errors and/or dynamic changes occurring in the input string. Such errors and dynamic changes are common in real-world scenario including DNA sequencing and versioned document maintenance. Following the earlier work of Lagarde and Perifel [ 17 ] and Akagi et al. [ 1 ] , string compressors and repetitiveness measures can be categorized into three classes: (A) Stable: Those whose sensitivity is O(1) ; (B) Changeable: Those whose sensitivity is \mathrm{polylog}(n) ; (C) Catastrophic: Those whose sensitivity is O(n^{c}) with some constant 0<c\leq 1 . For instance, it is shown in [ 1 ] that Class (A) includes the substring complexity [ 16 ] , the smallest macro scheme [ 23 ] , the Lempel-Ziv 77 families [ 26 , 23 ] , and the smallest grammar [ 21 , 6 ] . On the other hand, Class (B) includes run-length Burrows-Wheeler transform (RLBWT) [ 1 , 9 , 10 ] , and the Lempel-Ziv 78 [ 27 ] belongs to Class (C) [ 17 ] . The focus of this present article is to analyze the sensitivity of CDAWGs. In case where the edit operation to the string T is performed at either end of T , then the multiplicative sensitivity of CDAWGs is known to be asymptotically at most 2 , and it is tight [ 13 , 8 ] . However, the general case with an arbitrary single-character-wise edit on T was not well understood for CDAWGs. In this paper, we prove that any edit operation at an arbitrary position on the string can increase the size of the CDAWG asymptotically at most 8 times larger than the original, implying that CDAWGs belong to Class (A). We emphasize that the only known upper bound for the sensitivity of CDAWGs is O(n/\log n) , which trivially follows since \mathsf{e}\in O(n) and \mathsf{e}\in\Omega(\log n) for any string of length n [ 5 , 3 ] . Our technique for proving the constant sensitivity of CDAWGs is purely combinatorial, which involves new and original ideas that were not present in the special case of left/right-end edits [ 13 , 8 ] . Also, all our arguments hold without a common sentinel symbol \$ at the right-end of strings. Although the CDAWG size \mathsf{e} is regarded as a weak string repetitiveness measure (as \mathsf{e}\in\Theta(n) for string \mathtt{a}^{n-1}\mathtt{b} [ 5 ] , and reversing the string can increase \mathsf{e} by a factor of O(\sqrt{n}) [ 14 ] for some string), our result shows another virtue of CDAWGs being stable in terms of sensitivity and thus being robust against errors and edits. To our knowledge, CDAWGs are the first compressed indexing structure proven to achieve O(1) multiplicative sensitivity. 2 Preliminaries 2.1 Strings Let \Sigma be an alphabet of size \sigma . An element of \Sigma^{*} is called a string . For a string T\in\Sigma^{*} , the length of T is denoted by |T| . The empty string , denoted by \varepsilon , is the string of length 0 . For any non-negative integer n\geq 0 , let \Sigma^{n} denote the set of strings of length n . For any two strings S and T , let \mathsf{ed}(S,T) denote the edit distance between S and T . For any string T and a non-negative integer \ell\geq 0 , let \mathcal{K}(T,\ell)=\{S\mid\mathsf{ed}(S,T)=\ell\} . For string T=uvw , u , v , and w are called a prefix , substring , and

Read the complete text