Practical Evaluation of Lyndon Factors via Alphabet Reordering

Marcelo K. Albertini and Felipe A. Louza ()
Additional contact information
Marcelo K. Albertini: Faculdade de Computação, Universidade Federal de Uberlândia, Uberlândia 38400-902, Brazil
Felipe A. Louza: Faculdade de Engenharia Elétrica, Universidade Federal de Uberlândia, Uberlândia 38400-902, Brazil

Mathematics, 2022, vol. 11, issue 1, 1-9

Abstract: We evaluate the influence of different alphabet orderings on the Lyndon factorization of a string. Experiments with Pizza&Chili datasets show that for most alphabet reorderings, the number of Lyndon factors is usually small, and the length of the longest Lyndon factor can be as large as the input string, which is unfavorable for algorithms and indexes that depend on the number of Lyndon factors. We present results with randomized alphabet permutations that can be used as a baseline to assess the effectiveness of heuristics and methods designed to modify the Lyndon factorization of a string via alphabet reordering.

Keywords: Lyndon factorization; alphabet reordering; algorithms (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/1/139/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/1/139/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2022:i:1:p:139-:d:1017083

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().