Converting SLP to LZ78 in almost Linear Time

DOI10.1007/978-3-642-38905-4_6MaRDI QIDQ4928557zbMATH OpenOpenAlexFDO

Authors Hideo Bannai, Paweł Gawrychowski, Shunsuke Inenaga, Masayuki Takeda

Publication date 14 June 2013

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-38905-4_6

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

• Faster Lyndon factorization algorithms for SLP and LZ78 compressed text
• From LZ77 to the run-length encoded Burrows-Wheeler transform, and back
• A faster algorithm for the computation of string convolutions using LZ78 parsing
• Conversion from RLBWT to LZ77
• Linear-time text compression by longest-first substitution
• Approximating LZ77 via Small-Space Multiple-Pattern Matching
• On the approximation ratio of LZ-end to LZ77
• A separation between RLSLPs and LZ77
• Constructing LZ78 tries and position heaps in linear time for large alphabets

Cited in

(10)

• A separation between RLSLPs and LZ77
• Constructing LZ78 tries and position heaps in linear time for large alphabets
• Longest common extensions in trees
• Longest common extensions in trees
• Efficient LZ78 factorization of grammar compressed text
• Faster Lyndon factorization algorithms for SLP and LZ78 compressed text
• Conversion from RLBWT to LZ77
• Optimally computing compressed indexing arrays based on the compact directed acyclic word graph
• LZ78 substring compression in compressed space
• LZ77 computation based on the run-length encoded BWT

This page was built for publication: Converting SLP to LZ78 in almost Linear Time

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