文章基本信息

标题：Engineering External Memory LCP Array Construction: Parallel, In-Place and Large Alphabet
本地全文：下载
作者：Juha K{\"a}rkk{\"a}inen ; Dominik Kempa
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：75
页码：17:1-17:14
DOI：10.4230/LIPIcs.SEA.2017.17
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：LCP array; suffix array; external memory algorithms