A Framework of Dynamic Data Structures for String Processing
A Framework of Dynamic Data Structures for String Processing
复制标题
字符串处理的动态数据结构框架
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
N. Prezza
中科院分区：
文献类型：
--
作者：
N. Prezza
在本文中，我们提出了动态，这是一个开源C ++库，该库实现了用于字符串操作的动态压缩数据结构。我们的框架包括有用的工具，例如可搜索的部分总和，简洁/差距编码的比特值以及熵/运行长度的压缩字符串和FM索引。我们证明了我们结构使用的资源的几乎最佳的理论界限，并表明我们的理论预测在实践中经验得到了严格的验证。总而言之，我们将注意力转向应用。我们比较了使用Dynamic实施的四种最近发布的压缩算法的性能与执行相同任务的最先进工具的压缩算法的性能。我们的实验表明，使用动态压缩数据结构的算法可以比执行相同任务的经典算法高出三个数量级（尽管慢）。
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 four 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.