Fast label extraction in the CDAWG

DOI10.1007/978-3-319-67428-5_14MaRDI QIDQ5150929zbMATH OpenOpenAlexFDO

Authors Djamal Belazzougui, Fabio Cunial

Publication date 16 February 2021

Published in String Processing and Information Retrieval (Search for Journal in Brave)

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

zbMATH Keywords

CDAWGcount querylocate querymatching statisticsmaximal repeatminimal absent wordsstraight-line programsuffix tree

Mathematics Subject Classification ID

Data structures (68P05) Information storage and retrieval of data (68P20) Algorithms on strings (68W32)

Abstract: The compact directed acyclic word graph (CDAWG) of a string $T$ of length $n$ takes space proportional just to the number $e$ of right extensions of the maximal repeats of $T$, and it is thus an appealing index for highly repetitive datasets, like collections of genomes from similar species, in which $e$ grows significantly more slowly than $n$. We reduce from $O(mloglogn)$ to $O(m)$ the time needed to count the number of occurrences of a pattern of length $m$, using an existing data structure that takes an amount of space proportional to the size of the CDAWG. This implies a reduction from $O(mloglogn+mathttocc)$ to $O(m+mathttocc)$ in the time needed to locate all the $mathttocc$ occurrences of the pattern. We also reduce from $O(kloglogn)$ to $O(k)$ the time needed to read the $k$ characters of the label of an edge of the suffix tree of $T$, and we reduce from $O(mloglogn)$ to $O(m)$ the time needed to compute the matching statistics between a query of length $m$ and $T$, using an existing representation of the suffix tree based on the CDAWG. All such improvements derive from extracting the label of a vertex or of an arc of the CDAWG using a straight-line program induced by the reversed CDAWG.

Recommendations

• Representing the suffix tree with the CDAWG
• Linear-size CDAWG: new repetition-aware indexing and grammar compression
• On-line construction of compact directed acyclic word graphs
• scientific article; zbMATH DE number 1786457
• scientific article; zbMATH DE number 1962793

Cites work

• Algorithms on Strings, Trees and Sequences
• Automata and forbidden words
• Combinatorial Pattern Matching
• Composite repetition-aware data structures
• Finding level-ancestors in trees
• Fully compressed suffix trees
• scientific article; zbMATH DE number 3883638 (Why is no real title available?)
• scientific article; zbMATH DE number 1998342 (Why is no real title available?)
• Large alphabets and incompressibility
• Linear-size suffix tries
• On maximal repeats in strings
• Representing the suffix tree with the CDAWG
• Run-Length Compressed Indexes Are Superior for Highly Repetitive Sequence Collections
• The level ancestor problem simplified

Cited in

(12)

• Universal compressed text indexing
• Efficient computation of substring equivalence classes with suffix arrays
• scientific article; zbMATH DE number 7559178 (Why is no real title available?)
• Online algorithms for constructing linear-size suffix trie
• Representing the suffix tree with the CDAWG
• Linear-size CDAWG: new repetition-aware indexing and grammar compression
• On Sensitivity of Compact Directed Acyclic Word Graphs
• Optimally computing compressed indexing arrays based on the compact directed acyclic word graph
• Linear time online algorithms for constructing linear-size suffix trie
• Linear-size suffix tries and linear-size CDAWGs simplified and improved
• Computing minimal absent words and extended bispecial factors with CDAWG space
• Tight bounds for the sensitivity of CDAWGs with left-end edits

This page was built for publication: Fast label extraction in the CDAWG

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