Faster Lyndon factorization algorithms for SLP and LZ78 compressed text
From MaRDI portal
Publication:507399
DOI10.1016/j.tcs.2016.03.005zbMath1356.68302OpenAlexW2293945882MaRDI QIDQ507399
Yuto Nakashima, Hideo Bannai, Masayuki Takeda, Shunsuke Inenaga, 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
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)
Related Items (10)
Access, Rank, and Select in Grammar-compressed Strings ⋮ Inferring strings from Lyndon factorization ⋮ Constructing and indexing the bijective and extended Burrows-Wheeler transform ⋮ Dynamic and internal longest common substring ⋮ Lyndon factorization algorithms for small alphabets and run-length encoded strings ⋮ Online algorithms for constructing linear-size suffix trie ⋮ On the size of overlapping Lempel-Ziv and Lyndon factorizations ⋮ Indexing the bijective BWT ⋮ Longest Lyndon Substring After Edit ⋮ Lyndon factorization of grammar compressed texts revisited
Cites Work
- Unnamed Item
- The level ancestor problem simplified
- Lyndon + Christoffel = digitally convex
- Parallel RAM algorithms for factorizing words
- Detecting regularities on grammar-compressed strings
- Factorizing words over an ordered alphabet
- Compression of individual sequences via variable-rate coding
- Fast parallel Lyndon factorization with applications
- Converting SLP to LZ78 in almost Linear Time
- Efficient Lyndon Factorization of Grammar Compressed Text
- Free differential calculus. IV: The quotient groups of the lower central series
This page was built for publication: Faster Lyndon factorization algorithms for SLP and LZ78 compressed text