On Sensitivity of Compact Directed Acyclic Word Graphs

Hiroto Fujimaru; Yuto Nakashima; Shunsuke Inenaga

doi:10.1007/978-3-031-33180-0_13

On Sensitivity of Compact Directed Acyclic Word Graphs

Hiroto Fujimaru, Yuto Nakashima, Shunsuke Inenaga

Mathematical Informatics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Citations (Scopus)

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.

Original language	English
Title of host publication	Combinatorics on Words - 14th International Conference, WORDS 2023, Proceedings
Editors	Anna Frid, Robert Mercaş
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	168-180
Number of pages	13
ISBN (Print)	9783031331794
DOIs	https://doi.org/10.1007/978-3-031-33180-0_13
Publication status	Published - 2023
Event	14th International Conference on Combinatorics on Words, WORDS 2023 - Umeå, Sweden Duration: Jun 12 2023 → Jun 16 2023

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13899 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	14th International Conference on Combinatorics on Words, WORDS 2023
Country/Territory	Sweden
City	Umeå
Period	6/12/23 → 6/16/23

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-031-33180-0_13

Cite this

Fujimaru, H., Nakashima, Y., & Inenaga, S. (2023). On Sensitivity of Compact Directed Acyclic Word Graphs. In A. Frid, & R. Mercaş (Eds.), Combinatorics on Words - 14th International Conference, WORDS 2023, Proceedings (pp. 168-180). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13899 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-33180-0_13

On Sensitivity of Compact Directed Acyclic Word Graphs. / Fujimaru, Hiroto; Nakashima, Yuto ; Inenaga, Shunsuke.
Combinatorics on Words - 14th International Conference, WORDS 2023, Proceedings. ed. / Anna Frid; Robert Mercaş. Springer Science and Business Media Deutschland GmbH, 2023. p. 168-180 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13899 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Fujimaru, H, Nakashima, Y & Inenaga, S 2023, On Sensitivity of Compact Directed Acyclic Word Graphs. in A Frid & R Mercaş (eds), Combinatorics on Words - 14th International Conference, WORDS 2023, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13899 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 168-180, 14th International Conference on Combinatorics on Words, WORDS 2023, Umeå, Sweden, 6/12/23. https://doi.org/10.1007/978-3-031-33180-0_13

Fujimaru H, Nakashima Y , Inenaga S. On Sensitivity of Compact Directed Acyclic Word Graphs. In Frid A, Mercaş R, editors, Combinatorics on Words - 14th International Conference, WORDS 2023, Proceedings. Springer Science and Business Media Deutschland GmbH. 2023. p. 168-180. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-33180-0_13

Fujimaru, Hiroto ; Nakashima, Yuto ; Inenaga, Shunsuke. / On Sensitivity of Compact Directed Acyclic Word Graphs. Combinatorics on Words - 14th International Conference, WORDS 2023, Proceedings. editor / Anna Frid ; Robert Mercaş. Springer Science and Business Media Deutschland GmbH, 2023. pp. 168-180 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{3c0eb6e0de074b669824711a745bdd3d,

title = "On Sensitivity of Compact Directed Acyclic Word Graphs",

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.",

author = "Hiroto Fujimaru and Yuto Nakashima and Shunsuke Inenaga",

note = "Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 14th International Conference on Combinatorics on Words, WORDS 2023 ; Conference date: 12-06-2023 Through 16-06-2023",

year = "2023",

doi = "10.1007/978-3-031-33180-0\_13",

language = "English",

isbn = "9783031331794",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "168--180",

editor = "Anna Frid and Robert Merca{\c s}",

booktitle = "Combinatorics on Words - 14th International Conference, WORDS 2023, Proceedings",

address = "Germany",

}

TY - GEN

T1 - On Sensitivity of Compact Directed Acyclic Word Graphs

AU - Fujimaru, Hiroto

AU - Nakashima, Yuto

AU - Inenaga, Shunsuke

PY - 2023

Y1 - 2023

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85173572775&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85173572775&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-33180-0_13

DO - 10.1007/978-3-031-33180-0_13

M3 - Conference contribution

AN - SCOPUS:85173572775

SN - 9783031331794

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 168

EP - 180

BT - Combinatorics on Words - 14th International Conference, WORDS 2023, Proceedings

A2 - Frid, Anna

A2 - Mercaş, Robert

PB - Springer Science and Business Media Deutschland GmbH

T2 - 14th International Conference on Combinatorics on Words, WORDS 2023

Y2 - 12 June 2023 through 16 June 2023

ER -