Lyndon factorization algorithms for small alphabets and run-length encoded strings
type: Item
instance of: scholarly article
title: Lyndon factorization algorithms for small alphabets and run-length encoded strings
zbMATH Open document ID: 1461.68266
author: Sukhpal Singh Ghuman
author: Emanuele Giaquinta
author: Jorma Tarhio
published in: Algorithms
publication date: 2020-10-07T00:00:00Z
review text: Summary: We present two modifications of Duval's algorithm for computing the Lyndon factorization of a string. One of the algorithms has been designed for strings containing runs of the smallest character. It works best for small alphabets and it is able to skip a significant number of characters of the string. Moreover, it can be engineered to have linear time complexity in the worst case. When there is a run-length encoded string \(R\) of length \(\rho\), the other algorithm computes the Lyndon factorization of \(R\) in \(O(\rho)\) time and in constant space. It is shown by experimental results that the new variations are faster than Duval's original algorithm in many scenarios.
Mathematics Subject Classification ID: 68W32
zbMATH DE Number: 7257190
zbMATH Keywords: Lyndon factorization
zbMATH Keywords: string algorithms
zbMATH Keywords: run-length encoding
MaRDI profile type: MaRDI publication profile
full work available at URL: https://doi.org/10.3390/a12060124
OpenAlex ID: W2952991946
cites work: Free differential calculus. IV: The quotient groups of the lower central series
cites work: Suffixes, conjugates and Lyndon words
cites work: Factorizing words over an ordered alphabet
cites work: Fast parallel Lyndon factorization with applications
cites work: Q5506326
cites work: Faster Lyndon factorization algorithms for SLP and LZ78 compressed text
cites work: Efficient Lyndon factorization of grammar compressed text
cites work: Q4341774
cites work: Improving practical exact string matching
cites work: Fast and flexible string matching by combining bit-parallelism and suffix automata
DOI: 10.3390/A12060124
Recommended article: Fast algorithms for computing the constrained LCS of run-length encoded strings
Recommended article: Faster Lyndon factorization algorithms for SLP and LZ78 compressed text
Recommended article: Inferring strings from Lyndon factorization
Recommended article: Inferring Strings from Lyndon Factorization
Recommended article: Enhanced string factoring from alphabet orderings
Recommended article: Lyndon-like and V-order factorizations of strings
Recommended article: Generic Algorithms for Factoring Strings
Recommended article: Suffix array and Lyndon factorization of a text
Recommended article: Off-line and on-line algorithms for closed string factorization
copyright license: Creative Commons Attribution 4.0 International
description: scientific article; zbMATH DE number 7257190