A faster implementation of online RLBWT and its application to LZ77 parsing

DOI10.1016/J.JDA.2018.11.002zbMath1410.68417OpenAlexW2901851084WikidataQ128991069 ScholiaQ128991069MaRDI QIDQ1711660

Yoshimasa Takabatake, Kensuke Sakai, Tomohiro I., Hiroshi Sakamoto, Tatsuya Ohno

Publication date: 18 January 2019

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

Full work available at URL: https://doi.org/10.1016/j.jda.2018.11.002

zbMATH Keywords

LZ77 factorizationrecompressionrun-length Burrows-Wheeler transformation

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Online algorithms; streaming algorithms (68W27) Algorithms on strings (68W32)

Related Items (4)

Novel results on the number of runs of the Burrows-Wheeler-transform ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Refining the \(r\)-index

Uses Software

• DYNAMIC
• get-git-revisions
• r-index

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Succinct data structures for searchable partial sums with optimal worst-case performance
• LZ77 computation based on the run-length encoded BWT
• A faster implementation of online run-length Burrows-Wheeler transform
• Wheeler graphs: a framework for BWT-based data structures
• Fully Functional Static and Dynamic Succinct Trees
• Composite Repetition-Aware Data Structures
• Compressed Data Structures for Dynamic Sequences
• A universal algorithm for sequential data compression
• Dynamic Relative Compression, Dynamic Partial Sums, and Substring Concatenation
• Online LZ77 Parsing and Matching Statistics with RLBWTs
• Optimal Dynamic Sequence Representations
• Run-Length Compressed Indexes Are Superior for Highly Repetitive Sequence Collections

This page was built for publication: A faster implementation of online RLBWT and its application to LZ77 parsing