On Sensitivity of Compact Directed Acyclic Word Graphs

DOI10.1007/978-3-031-33180-0_13arXiv2303.01726OpenAlexW4381304394MaRDI QIDQ6134872FDOQ6134872

Shunsuke Inenaga, Author name not available (Why is that?), Yuto Nakashima

Publication date: 25 July 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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$ is obtained by merging isomorphic subtrees of the suffix tree [Weiner 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 $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$ is less than $e$. Further, we present almost matching lower bounds on the sensitivity of CDAWGs for all cases of insertion, deletion, and substitution.

Full work available at URL: https://arxiv.org/abs/2303.01726

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Cites Work

• A universal algorithm for sequential data compression
• On-line construction of compact directed acyclic word graphs
• On Sensitivity of Compact Directed Acyclic Word Graphs
• On the structure of compacted subword graphs of Thue-Morse words and their applications
• Complete inverted files for efficient text retrieval and analysis
• Composite Repetition-Aware Data Structures
• At the roots of dictionary compression: string attractors
• Towards a definitive measure of repetitiveness
• Fast Label Extraction in the CDAWG
• Linear-Size CDAWG: New Repetition-Aware Indexing and Grammar Compression
• Sensitivity of string compressors and repetitiveness measures

Cited In (3)

• On Sensitivity of Compact Directed Acyclic Word Graphs
• Compact morphic directed acyclic word graphs
• Compressed directed acyclic word graph with application in local alignment

This page was built for publication: On Sensitivity of Compact Directed Acyclic Word Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6134872)