LZ77 computation based on the run-length encoded BWT

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

zbMATH Keywords

Lempel-Ziv factorizationrepetition-aware data structuresrepetitive text collectionsrun-length encoded BWT

Mathematics Subject Classification ID

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

• GitHub
• DYNAMIC
• get-git-revisions
• LZ77

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