License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2017.11
URN: urn:nbn:de:0030-drops-76028
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7602/
Go to the corresponding LIPIcs Volume Portal

Prezza, Nicola

A Framework of Dynamic Data Structures for String Processing

pdf-format:
LIPIcs-SEA-2017-11.pdf (0.5 MB)

Abstract

In this paper we present DYNAMIC, an open-source C++ library implementing dynamic compressed data structures for string manipulation. Our framework includes useful tools such as searchable partial sums, succinct/gap-encoded bitvectors, and entropy/run-length compressed strings and FM indexes. We prove close-to-optimal theoretical bounds for the resources used by our structures, and show that our theoretical predictions are empirically tightly verified in practice. To conclude, we turn our attention to applications. We compare the performance of five recently-published compression algorithms implemented using DYNAMIC with those of state-of-the-art tools performing the same task. Our experiments show that algorithms making use of dynamic compressed data structures can be up to three orders of magnitude more space-efficient (albeit slower) than classical ones performing the same tasks.

BibTeX - Entry

@InProceedings{prezza:LIPIcs:2017:7602,
  author =	{Nicola Prezza},
  title =	{{A Framework of Dynamic Data Structures for String Processing}},
  booktitle =	{16th International Symposium on Experimental Algorithms (SEA 2017)},
  pages =	{11:1--11:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-036-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{75},
  editor =	{Costas S. Iliopoulos and Solon P. Pissis and Simon J. Puglisi and Rajeev Raman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7602},
  URN =		{urn:nbn:de:0030-drops-76028},
  doi =		{10.4230/LIPIcs.SEA.2017.11},
  annote =	{Keywords: C++, dynamic, compression, data structure, bitvector, string}
}

Keywords: C++, dynamic, compression, data structure, bitvector, string
Collection: 16th International Symposium on Experimental Algorithms (SEA 2017)
Issue Date: 2017
Date of publication: 07.08.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI