article · IRIS - Institutional Research Information System (Libera Università Internazionale degli Studi Sociali Guido Carli) · 2017

A framework of dynamic data structures for string processing

Nicola Prezza

Cited by 20Open access

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 stateof-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.

Cite this paper

APA 7

Prezza, N. (2017). A framework of dynamic data structures for string processing. IRIS - Institutional Research Information System (Libera Università Internazionale degli Studi Sociali Guido Carli). https://doi.org/10.4230/lipics.sea.2017.11

MLA 9

Prezza, Nicola. “A framework of dynamic data structures for string processing.” IRIS - Institutional Research Information System (Libera Università Internazionale degli Studi Sociali Guido Carli), 2017, https://doi.org/10.4230/lipics.sea.2017.11.

Chicago

Prezza, Nicola. 2017. “A framework of dynamic data structures for string processing.” IRIS - Institutional Research Information System (Libera Università Internazionale degli Studi Sociali Guido Carli). https://doi.org/10.4230/lipics.sea.2017.11.

Harvard

Prezza, N. (2017) ‘A framework of dynamic data structures for string processing’, IRIS - Institutional Research Information System (Libera Università Internazionale degli Studi Sociali Guido Carli). Available at: https://doi.org/10.4230/lipics.sea.2017.11.

BibTeX

@article{prezza2017framework,
  title = {{A framework of dynamic data structures for string processing}},
  author = {Prezza, Nicola},
  journal = {IRIS - Institutional Research Information System (Libera Università Internazionale degli Studi Sociali Guido Carli)},
  year = {2017},
  doi = {10.4230/lipics.sea.2017.11}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.