Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2016.23
URN: urn:nbn:de:0030-drops-60698
URL: https://drops.dagstuhl.de/opus/volltexte/2016/6069/
Baier, Uwe
Linear-time Suffix Sorting - A New Approach for Suffix Array Construction
| pdf-format: |
|
Abstract
This paper presents a new approach for linear-time suffix sorting. It introduces a new sorting principle that can be used to build the first non-recursive linear-time suffix array construction algorithm named GSACA. Although GSACA cannot keep up with the performance of state of the art suffix array construction algorithms, the algorithm introduces a couple of new ideas for suffix array construction, and therefore can be seen as an ’idea collection’ for further suffix array construction improvements.
BibTeX - Entry
@InProceedings{baier:LIPIcs:2016:6069,
author = {Uwe Baier},
title = {{Linear-time Suffix Sorting - A New Approach for Suffix Array Construction}},
booktitle = {27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)},
pages = {23:1--23:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-012-5},
ISSN = {1868-8969},
year = {2016},
volume = {54},
editor = {Roberto Grossi and Moshe Lewenstein},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6069},
URN = {urn:nbn:de:0030-drops-60698},
doi = {10.4230/LIPIcs.CPM.2016.23},
annote = {Keywords: Suffix array, sorting algorithm, linear time}
}
| Keywords: | Suffix array, sorting algorithm, linear time | |
| Seminar: | 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016) | |
| Issue date: | 2016 | |
| Date of publication: | 27.06.2016 |
