Practical Evaluation of Lyndon Factors via Alphabet Reordering

Authors:
Open Access
Publisher website
Google Scholar
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.
Funding Information
  • Conselho Nacional de Desenvolvimento Científico e Tecnológico (406418/2021-7, APQ-01217-22)
  • Fundação de Amparo à Pesquisa do Estado de Minas Gerais (406418/2021-7, APQ-01217-22)