Faster Lyndon factorization algorithms for SLP and LZ78 compressed text

DOI10.1016/J.TCS.2016.03.005MaRDI QIDQ507399zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• Compression of individual sequences via variable-rate coding
• Converting SLP to LZ78 in almost Linear Time
• Detecting regularities on grammar-compressed strings
• Efficient Lyndon factorization of grammar compressed text
• Factorizing words over an ordered alphabet
• Fast parallel Lyndon factorization with applications
• Free differential calculus. IV: The quotient groups of the lower central series
• Lyndon + Christoffel = digitally convex
• Parallel RAM algorithms for factorizing words
• The level ancestor problem simplified
• Tying up the loose ends in fully LZW-compressed pattern matching

Cited in

(16)

• Efficient Lyndon factorization of grammar compressed text
• A faster algorithm for the computation of string convolutions using LZ78 parsing
• Lyndon factorization of grammar compressed texts revisited
• Online algorithms for constructing linear-size suffix trie
• Constructing and indexing the bijective and extended Burrows-Wheeler transform
• Longest Lyndon Substring After Edit
• Linear time online algorithms for constructing linear-size suffix trie
• Dynamic and internal longest common substring
• Efficient algorithms to compute compressed longest common substrings and compressed palindromes
• Inferring strings from Lyndon factorization
• Converting SLP to LZ78 in almost Linear Time
• Efficient LZ78 factorization of grammar compressed text
• Lyndon factorization algorithms for small alphabets and run-length encoded strings
• Access, rank, and select in grammar-compressed 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)