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

DOI10.1007/978-3-031-43980-3_3MaRDI QIDQ6545409FDOQ6545409

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

Publication date: 29 May 2024

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

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)

Cites Work

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