| 1 |
Dynamic Suffix Array with Polylogarithmic Queries and Updates ...
|
|
|
|
BASE
|
|
Show details
|
|
|
| 2 |
Breaking the $O(n)$-Barrier in the Construction of Compressed Suffix Arrays ...
|
|
|
|
BASE
|
|
Show details
|
|
|
| 6 |
Engineering External Memory LCP Array Construction: Parallel, In-Place and Large Alphabet
|
|
Kempa, Dominik. - : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. : LIPIcs - Leibniz International Proceedings in Informatics. 16th International Symposium on Experimental Algorithms (SEA 2017), 2017
|
|
Abstract:
The suffix array augmented with the LCP array is perhaps the most important data structure in modern string processing. There has been a lot of recent research activity on constructing these arrays in external memory. In this paper, we engineer the two fastest LCP array construction algorithms (ESA 2016) and improve them in three ways. First, we speed up the algorithms by up to a factor of two through parallelism. Just 8 threads is sufficient for making the algorithms essentially I/O bound. Second, we reduce the disk space usage of the algorithms making them in-place: The input (text and suffix array) is treated as read-only and the working disk space never exceeds the size of the final output (the LCP array). Third, we add support for large alphabets. All previous implementations assume the byte alphabet.
|
|
Keyword:
Data processing Computer science; external memory algorithms; LCP array; suffix array
|
|
URN:
urn:nbn:de:0030-drops-76116
|
|
URL: https://doi.org/10.4230/LIPIcs.SEA.2017.17
https://drops.dagstuhl.de/opus/volltexte/2017/7611/
|
|
BASE
|
|
Hide details
|
|
|
| 7 |
Engineering External Memory LCP Array Construction: Parallel, In-Place and Large Alphabet ...
|
|
|
|
BASE
|
|
Show details
|
|
|
| 8 |
Optimal Construction of Compressed Indexes for Highly Repetitive Texts ...
|
|
|
|
BASE
|
|
Show details
|
|
|
| 9 |
Faster External Memory LCP Array Construction
|
|
Kempa, Dominik. - : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. : LIPIcs - Leibniz International Proceedings in Informatics. 24th Annual European Symposium on Algorithms (ESA 2016), 2016
|
|
BASE
|
|
Show details
|
|
|
| 11 |
Faster Sparse Suffix Sorting
|
|
I, Tomohiro; Kempa, Dominik. - : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2014. : LIPIcs - Leibniz International Proceedings in Informatics. 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014
|
|
BASE
|
|
Show details
|
|
|
|
|
