LZ77 computation based on the run-length encoded BWT
From MaRDI portal
Publication:724214
DOI10.1007/S00453-017-0327-ZzbMath1392.68186OpenAlexW2736180370MaRDI QIDQ724214
Nicola Prezza, Alberto Policriti
Publication date: 25 July 2018
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/11385/192332
Lempel-Ziv factorizationrepetition-aware data structuresrepetitive text collectionsrun-length encoded BWT
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05) Algorithms on strings (68W32)
Related Items (9)
r-indexing the eBWT ⋮ Computational graph pangenomics: a tutorial on data structures and their applications ⋮ Lempel-Ziv-like parsing in small space ⋮ A faster implementation of online RLBWT and its application to LZ77 parsing ⋮ A combinatorial view on string attractors ⋮ When a dollar makes a BWT ⋮ Unnamed Item ⋮ Dynamic index and LZ factorization in compressed space ⋮ Refining the \(r\)-index
Uses Software
Cites Work
- On compressing and indexing repetitive sequences
- Large alphabets and incompressibility
- Computing longest previous factor in linear time and applications
- Burrows-Wheeler transform and Sturmian words
- Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
- Average Linear Time and Compressed Space Construction of the Burrows-Wheeler Transform
- Composite Repetition-Aware Data Structures
- Lempel-Ziv Factorization Revisited
- Self-Indexed Grammar-Based Compression
- Approximating LZ77 via Small-Space Multiple-Pattern Matching
- The Smallest Grammar Problem
- A universal algorithm for sequential data compression
- Range Predecessor and Lempel-Ziv Parsing
- Fully Dynamic Data Structure for LCE Queries in Compressed Space
- Efficient LZ78 Factorization of Grammar Compressed Text
- Converting SLP to LZ78 in almost Linear Time
- Linear Time Lempel-Ziv Factorization: Simple, Fast, Small
- Optimal Dynamic Sequence Representations
- String Processing and Information Retrieval
- Factorizations of the Fibonacci Infinite Word
- Run-Length Compressed Indexes Are Superior for Highly Repetitive Sequence Collections
This page was built for publication: LZ77 computation based on the run-length encoded BWT
