Practical Evaluation of Lyndon Factors via Alphabet Reordering
We evaluate the influence of different alphabet orderings on the Lyndon factorization of a string. Experiments with <span style="font-variant: small-caps;">Pizza&Chili</span> datasets show that for most alphabet reorderings, the number of Lyndon factors is usually small, an...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-12-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/11/1/139 |
| _version_ | 1797431453177348096 |
|---|---|
| author | Marcelo K. Albertini Felipe A. Louza |
| author_facet | Marcelo K. Albertini Felipe A. Louza |
| author_sort | Marcelo K. Albertini |
| collection | DOAJ |
| description | We evaluate the influence of different alphabet orderings on the Lyndon factorization of a string. Experiments with <span style="font-variant: small-caps;">Pizza&Chili</span> 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. |
| first_indexed | 2024-03-09T09:45:17Z |
| format | Article |
| id | doaj.art-dd343d33191a4540ad4fcde86ae0bae4 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-09T09:45:17Z |
| publishDate | 2022-12-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-dd343d33191a4540ad4fcde86ae0bae42023-12-02T00:38:50ZengMDPI AGMathematics2227-73902022-12-0111113910.3390/math11010139Practical Evaluation of Lyndon Factors via Alphabet ReorderingMarcelo K. Albertini0Felipe A. Louza1Faculdade de Computação, Universidade Federal de Uberlândia, Uberlândia 38400-902, BrazilFaculdade de Engenharia Elétrica, Universidade Federal de Uberlândia, Uberlândia 38400-902, BrazilWe evaluate the influence of different alphabet orderings on the Lyndon factorization of a string. Experiments with <span style="font-variant: small-caps;">Pizza&Chili</span> 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.https://www.mdpi.com/2227-7390/11/1/139Lyndon factorizationalphabet reorderingalgorithms |
| spellingShingle | Marcelo K. Albertini Felipe A. Louza Practical Evaluation of Lyndon Factors via Alphabet Reordering Mathematics Lyndon factorization alphabet reordering algorithms |
| title | Practical Evaluation of Lyndon Factors via Alphabet Reordering |
| title_full | Practical Evaluation of Lyndon Factors via Alphabet Reordering |
| title_fullStr | Practical Evaluation of Lyndon Factors via Alphabet Reordering |
| title_full_unstemmed | Practical Evaluation of Lyndon Factors via Alphabet Reordering |
| title_short | Practical Evaluation of Lyndon Factors via Alphabet Reordering |
| title_sort | practical evaluation of lyndon factors via alphabet reordering |
| topic | Lyndon factorization alphabet reordering algorithms |
| url | https://www.mdpi.com/2227-7390/11/1/139 |
| work_keys_str_mv | AT marcelokalbertini practicalevaluationoflyndonfactorsviaalphabetreordering AT felipealouza practicalevaluationoflyndonfactorsviaalphabetreordering |