Optimally computing compressed indexing arrays based on the compact directed acyclic word graph

DOI10.1007/978-3-031-43980-3_3MaRDI QIDQ6545409zbMATH OpenFDO

Authors Hiroki Arimura, Shunsuke Inenaga, Yasuaki Kobayashi, Yuto Nakashima, Mizuki Sue

Publication date 29 May 2024

zbMATH Keywords

longest common prefixsuffix treehighly-repetitive text

Mathematics Subject Classification ID

Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)

Recommendations

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

Cites work

• Algorithms on Strings, Trees and Sequences
• Burrows-Wheeler transform of words defined by morphisms
• Complete inverted files for efficient text retrieval and analysis
• Composite repetition-aware data structures
• Computing longest previous factor in linear time and applications
• Converting SLP to LZ78 in almost Linear Time
• Linear-size CDAWG: new repetition-aware indexing and grammar compression
• Measuring the clustering effect of BWT via RLE
• On the Approximation Ratio of Ordered Parsings
• On the structure of compacted subword graphs of Thue-Morse words and their applications
• Permuted Longest-Common-Prefix Array
• Representing the suffix tree with the CDAWG

Cited in

(1)

• Space-efficient conversions from SLPs

This page was built for publication: Optimally computing compressed indexing arrays based on the compact directed acyclic word graph

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