Practical String Dictionary Compression Using String Dictionary Encoding
Practical String Dictionary Compression Using String Dictionary Encoding
复制标题
使用字符串字典编码的实用字符串字典压缩
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
M. Fuketa
中科院分区：
文献类型：
--
作者：
Shunsuke Kanda;K. Morita;M. Fuketa
字符串字典是一种用于存储一组字符串并将其映射到唯一 ID 的数据结构。它可以通过将字符串数据编码为整数来管理紧凑空间中的字符串数据。然而，最近在实践中出现了一些实例，其中字符串字典的大小已成为许多应用程序中非常大的数据集的关键问题。已经提出了许多压缩字符串字典作为解决方案。特别是，将强大的文本压缩技术Re-Pair应用于尝试和前端编码可以帮助获得支持快速字典操作的紧凑字符串字典。然而，对于大型数据集来说，使用 Re-Pair 构建此类字典的成本是不切实际的。在本文中，我们提出了一种使用字符串字典编码的替代压缩策略，并为其开发了几种字典结构。通过对真实世界数据集的实验，我们表明，我们的字符串字典的构建速度比 Re-Pair 版本快 422.5 倍，具有竞争性的空间和操作速度。
A string dictionary is a data structure for storing a set of strings that maps them to unique IDs. It can manage string data in compact space by encoding them into integers. However, instances have recently emerged in practice where the size of string dictionaries has become a critical problem for very large datasets in many applications. A number of compressed string dictionaries have been proposed as a solution. In particular, the application of Re-Pair, a powerful text compression technique, to tries and front coding can help to obtain compact string dictionaries that support fast dictionary operations. However, the cost of constructing such dictionaries using Re-Pair is impractical for large datasets. In this paper, we propose an alternative compression strategy using string dictionary encoding and develop several dictionary structures for it. We show that our string dictionaries can be constructed up to 422.5x faster than the Re-Pair versions with competitive space and operation speed, through experiments on real-world datasets.