Lyndon Factorization Algorithms for Small Alphabets and Run-Length Encoded Strings

Autor:	Sukhpal Singh Ghuman, Emanuele Giaquinta, Jorma Tarhio
Jazyk:	angličtina
Rok vydání:	2019
Předmět:	Lyndon factorization string algorithms run-length encoding Industrial engineering. Management engineering T55.4-60.8 Electronic computers. Computer science QA75.5-76.95
Zdroj:	Algorithms, Vol 12, Iss 6, p 124 (2019)
Druh dokumentu:	article
ISSN:	1999-4893
DOI:	10.3390/a12060124
Popis:	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 ρ , the other algorithm computes the Lyndon factorization of R in O ( ρ ) 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.
Databáze:	Directory of Open Access Journals
Externí odkaz:	https://doaj.org/article/e643163e88504a10853f9f7f5298406c Zobrazit plný text záznamu View record in DOAJ Plný text ve formátu PDF Plný text ve formátu HTML
Nepřihlášeným uživatelům se plný text nezobrazuje	K zobrazení výsledku je třeba se přihlásit.