Compact directed acyclic word graphs for a sliding window

DOI10.1016/S1570-8667(03)00064-9MaRDI QIDQ876704zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, S. Arikawa

Publication date 26 April 2007

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s1570-8667(03)00064-9

zbMATH Keywords

author keywords: on-line text compressioncompact directed acyclic word graphslinear-time algorithmsliding window

Mathematics Subject Classification ID

Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Nonnumerical algorithms (68W05)

Recommendations

• Sliding suffix tree
• Truncated suffix trees and their application to data compression.
• How much is that DAWG in the window? a moving window algorithm for the directed acyclic word graph
• On-line construction of compact directed acyclic word graphs
• scientific article; zbMATH DE number 1786457

Cites work

• A Space-Economical Suffix Tree Construction Algorithm
• Algorithms on Strings, Trees and Sequences
• Complete inverted files for efficient text retrieval and analysis
• scientific article; zbMATH DE number 3913711 (Why is no real title available?)
• scientific article; zbMATH DE number 2052919 (Why is no real title available?)
• scientific article; zbMATH DE number 1786457 (Why is no real title available?)
• scientific article; zbMATH DE number 1929950 (Why is no real title available?)
• scientific article; zbMATH DE number 801745 (Why is no real title available?)
• On-line construction of suffix trees

Cited in

(13)

• Truncated suffix trees and their application to data compression.
• On-line construction of compact directed acyclic word graphs
• Sliding suffix tree
• Compact morphic directed acyclic word graphs
• Weighted automata for full-text indexing
• How much is that DAWG in the window? a moving window algorithm for the directed acyclic word graph
• Compressed directed acyclic word graph with application in local alignment
• On-line suffix tree construction with reduced branching
• scientific article; zbMATH DE number 2052919 (Why is no real title available?)
• On the Structure of Consistent Partitions of Substring Set of a Word
• Minimizers in semi-dynamic strings
• Maintaining the size of LZ77 on semi-dynamic strings
• Ternary directed acyclic word graphs

This page was built for publication: Compact directed acyclic word graphs for a sliding window

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