Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2021.15
URN: urn:nbn:de:0030-drops-145961
URL: https://drops.dagstuhl.de/opus/volltexte/2021/14596/
Bertram, Nico ; Ellert, Jonas ; Fischer, Johannes
Lyndon Words Accelerate Suffix Sorting
| pdf-format: |
|
Abstract
Suffix sorting is arguably the most fundamental building block in string algorithmics, like regular sorting in the broader field of algorithms. It is thus not surprising that the literature is full of algorithms for suffix sorting, in particular focusing on their practicality. However, the advances on practical suffix sorting stalled with the emergence of the DivSufSort algorithm more than 10 years ago, which, up to date, has remained the fastest suffix sorter. This article shows how properties of Lyndon words can be exploited algorithmically to accelerate suffix sorting again. Our new algorithm is 6-19% faster than DivSufSort on real-world texts, and up to three times as fast on artificial repetitive texts. It can also be parallelized, where similar speedups can be observed. Thus, we make the first advances in practical suffix sorting after more than a decade of standstill.
BibTeX - Entry
@InProceedings{bertram_et_al:LIPIcs.ESA.2021.15,
author = {Bertram, Nico and Ellert, Jonas and Fischer, Johannes},
title = {{Lyndon Words Accelerate Suffix Sorting}},
booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)},
pages = {15:1--15:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-204-4},
ISSN = {1868-8969},
year = {2021},
volume = {204},
editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14596},
URN = {urn:nbn:de:0030-drops-145961},
doi = {10.4230/LIPIcs.ESA.2021.15},
annote = {Keywords: Suffix array, suffix sorting, Lyndon words, string algorithms}
}
| Keywords: | Suffix array, suffix sorting, Lyndon words, string algorithms | |
| Seminar: | 29th Annual European Symposium on Algorithms (ESA 2021) | |
| Issue date: | 2021 | |
| Date of publication: | 31.08.2021 | |
| Supplementary Material: |
Software: https://github.com/jonas-ellert/gsaca-double-sort Software: https://github.com/jonas-ellert/gsaca-lyndon |
