Faster Lyndon factorization algorithms for SLP and LZ78 compressed text

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

zbMATH Keywords

Lyndon factorizationLempel-Ziv 78 factorizationstraight line program

Mathematics Subject Classification ID

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