Faster Lyndon factorization algorithms for SLP and LZ78 compressed text
DOI10.1016/J.TCS.2016.03.005zbMATH Open1356.68302OpenAlexW2293945882MaRDI QIDQ507399FDOQ507399
Authors: Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Tomohiro I 
Publication date: 6 February 2017
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2016.03.005
Recommendations
- Lyndon factorization of grammar compressed texts revisited
- Efficient Lyndon factorization of grammar compressed text
- Efficient LZ78 factorization of grammar compressed text
- Lyndon factorization algorithms for small alphabets and run-length encoded strings
- Linear Time Lempel-Ziv Factorization: Simple, Fast, Small
Analysis of algorithms (68W40) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)
Cites Work
- Efficient Lyndon factorization of grammar compressed text
- Factorizing words over an ordered alphabet
- Compression of individual sequences via variable-rate coding
- The level ancestor problem simplified
- Lyndon + Christoffel = digitally convex
- Free differential calculus. IV: The quotient groups of the lower central series
- Converting SLP to LZ78 in almost Linear Time
- Parallel RAM algorithms for factorizing words
- Fast parallel Lyndon factorization with applications
- Detecting regularities on grammar-compressed strings
- Tying up the loose ends in fully LZW-compressed pattern matching
Cited In (16)
- Online algorithms for constructing linear-size suffix trie
- Longest Lyndon Substring After Edit
- Efficient Lyndon factorization of grammar compressed text
- Efficient algorithms to compute compressed longest common substrings and compressed palindromes
- Converting SLP to LZ78 in almost Linear Time
- Inferring strings from Lyndon factorization
- Lyndon factorization of grammar compressed texts revisited
- Linear time online algorithms for constructing linear-size suffix trie
- Dynamic and internal longest common substring
- Access, Rank, and Select in Grammar-compressed Strings
- Efficient LZ78 factorization of grammar compressed text
- A faster algorithm for the computation of string convolutions using LZ78 parsing
- Constructing and indexing the bijective and extended Burrows-Wheeler transform
- Lyndon factorization algorithms for small alphabets and run-length encoded strings
- Indexing the bijective BWT
- On the size of overlapping Lempel-Ziv and Lyndon factorizations
This page was built for publication: Faster Lyndon factorization algorithms for SLP and LZ78 compressed text
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q507399)
