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.

A framework of dynamic data structures for string processing / Prezza, N.. - 75:(2017), pp. 1-15. ((Intervento presentato al convegno 16th Symposium on Experimental Algorithms, SEA 2017 tenutosi a London, UK nel June 21-23, 2017 [10.4230/LIPIcs.SEA.2017.11].

A framework of dynamic data structures for string processing

Prezza N.
2017

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.
Bitvector; C++; Compression; Data structure; DYNAMIC; String
A framework of dynamic data structures for string processing / Prezza, N.. - 75:(2017), pp. 1-15. ((Intervento presentato al convegno 16th Symposium on Experimental Algorithms, SEA 2017 tenutosi a London, UK nel June 21-23, 2017 [10.4230/LIPIcs.SEA.2017.11].
File in questo prodotto:
File Dimensione Formato  
framework.pdf

Open Access

Tipologia: Versione dell'editore
Licenza: Creative commons
Dimensione 521.2 kB
Formato Adobe PDF
521.2 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11385/194137
Citazioni
  • Scopus 9
  • ???jsp.display-item.citation.isi??? ND
social impact