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

Lempel-Ziv 78 factorizationLyndon factorizationstraight line program

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32) Analysis of algorithms (68W40)

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

(19)

• Efficient algorithms to compute compressed longest common substrings and compressed palindromes
• Lyndon factorization algorithms for small alphabets and run-length encoded strings
• Dynamic and internal longest common substring
• Inferring strings from Lyndon factorization
• Access, rank, and select in grammar-compressed strings
• Efficient LZ78 factorization of grammar compressed text
• Converting SLP to LZ78 in almost Linear Time
• Efficient Lyndon factorization of grammar compressed text
• Indexing the bijective BWT
• On the size of overlapping Lempel-Ziv and Lyndon factorizations
• Online algorithms for constructing linear-size suffix trie
• Longest Lyndon Substring After Edit
• Lyndon factorization of grammar compressed texts revisited
• Constructing and indexing the bijective and extended Burrows-Wheeler transform
• Linear time online algorithms for constructing linear-size suffix trie
• Finding an optimal alphabet ordering for Lyndon factorization is hard
• Unveiling the connection between the Lyndon factorization and the canonical inverse Lyndon factorization via a border property
• Edit and alphabet-ordering sensitivity of lex-parse
• A faster algorithm for the computation of string convolutions using LZ78 parsing

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)