Compact directed acyclic word graphs for a sliding window

DOI10.1016/S1570-8667(03)00064-9zbMath1118.68755OpenAlexW2074018443WikidataQ90345535 ScholiaQ90345535MaRDI QIDQ876704

Shunsuke Inenaga, Setsuo Arikawa, Ayumi Shinohara, Masayuki Takeda

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

sliding windowlinear-time algorithmauthor keywords: on-line text compressioncompact directed acyclic word graphs

Mathematics Subject Classification ID

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

Related Items

On the Structure of Consistent Partitions of Substring Set of a Word ⋮ On-line suffix tree construction with reduced branching ⋮ WEIGHTED AUTOMATA FOR FULL-TEXT INDEXING ⋮ On-line construction of compact directed acyclic word graphs ⋮ Sliding suffix tree

Cites Work

• On-line construction of suffix trees
• A Space-Economical Suffix Tree Construction Algorithm
• Algorithms on Strings, Trees and Sequences
• Complete inverted files for efficient text retrieval and analysis
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item