On-line construction of compact directed acyclic word graphs

DOI10.1016/j.dam.2004.04.012zbMath1084.68137OpenAlexW2090957374WikidataQ57518591 ScholiaQ57518591MaRDI QIDQ1764897

Setsuo Arikawa, Ayumi Shinohara, Shunsuke Inenaga, Giulio Pavesi, Hiromasa Hoshino, Giancarlo Mauri, Masayuki Takeda

Publication date: 22 February 2005

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2004.04.012

zbMATH Keywords

Directed acyclic word graphsPattern matching on stringsSuffix treesCompact directed acyclic word graphsOn-line and linear-time algorithms

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Permutations, words, matrices (05A05) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Data structures (68P05)

Related Items

Linear-size suffix tries ⋮ From Nerode's congruence to suffix automata with mismatches ⋮ General suffix automaton construction algorithm and space bounds ⋮ Efficient computation of substring equivalence classes with suffix arrays ⋮ On Sturmian graphs ⋮ The palindromization map ⋮ On the Suffix Automaton with Mismatches ⋮ Linear-time computation of DAWGs, symmetric indexing structures, and MAWs for integer alphabets ⋮ On the structure of compacted subword graphs of Thue-Morse words and their applications ⋮ On Sensitivity of Compact Directed Acyclic Word Graphs ⋮ Algorithms for Indexing Highly Similar DNA Sequences ⋮ WEIGHTED AUTOMATA FOR FULL-TEXT INDEXING ⋮ Online algorithms for constructing linear-size suffix trie ⋮ Data compression for proof replay ⋮ Sliding suffix tree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximate string matching with suffix automata
• Compact directed acyclic word graphs for a sliding window
• The smallest automaton recognizing the subwords of a text
• Structures in logic and computer science. A selection of essays in honor of Andrzej Ehrenfeucht (65th birthday on August 8, 1997)
• Approximate string matching using factor automata
• Transducers and repetitions
• A speed-up for the commute between subword trees and DAWGs.
• Reducing space for index implementation.
• Discovering characteristic expressions in literary works.
• On-line construction of suffix trees
• Suffix Arrays: A New Method for On-Line String Searches
• Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)
• A Space-Economical Suffix Tree Construction Algorithm
• Algorithms on Strings, Trees and Sequences
• Jewels of Stringology
• Complete inverted files for efficient text retrieval and analysis