Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Kärkkäinen, Juha; Kempa, Dominik http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-64026
URL:

;

Faster External Memory LCP Array Construction

pdf-format:


Abstract

The suffix array, perhaps the most important data structure in modern string processing, needs to be augmented with the longest-common-prefix (LCP) array in many applications. Their construction is often a major bottleneck especially when the data is too big for internal memory. We describe two new algorithms for computing the LCP array from the suffix array in external memory. Experiments demonstrate that the new algorithms are about a factor of two faster than the fastest previous algorithm.

BibTeX - Entry

@InProceedings{krkkinen_et_al:LIPIcs:2016:6402,
  author =	{Juha K{\"a}rkk{\"a}inen and Dominik Kempa},
  title =	{{Faster External Memory LCP Array Construction}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{61:1--61:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Piotr Sankowski and Christos Zaroliagis},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6402},
  URN =		{urn:nbn:de:0030-drops-64026},
  doi =		{10.4230/LIPIcs.ESA.2016.61},
  annote =	{Keywords: LCP array, suffix array, external memory algorithms}
}

Keywords: LCP array, suffix array, external memory algorithms
Seminar: 24th Annual European Symposium on Algorithms (ESA 2016)
Issue date: 2016
Date of publication: 2016


DROPS-Home | Fulltext Search | Imprint Published by LZI