c++ - 用公共(public)部分压缩字符串

Question

我有一个管理大量字符串的应用程序。字符串是一种类似路径的格式，有很多共同的部分，但没有明确的规则。它们不是文件系统上的路径，但可以这样考虑。我显然需要优化内存消耗，但又不能牺牲很大的性能。

我正在考虑 2 个选项:
- 实现一个 compressed_string 类来存储压缩数据，但我需要一个固定的字典，我现在找不到一个库。我不想要字节上的霍夫曼，我想要文字上的。
- 在字符串部分实现某种享元模式。

这个问题看起来很常见，我想知道最好的解决方案是什么，或者是否有人知道针对这个问题的库。

谢谢

Answer 1

虽然针对您的问题调整特定算法可能很诱人，但这可能需要不合理的时间和精力，而标准压缩技术将立即为您解决内存消耗问题提供巨大的插入力。

处理此问题的“标准”方法是将源数据分块为小块(例如 256KB)，然后单独压缩它们。将数据访问到 block 中时，需要先对其进行解码。因此，最佳 block 大小实际上取决于您的应用程序，即应用程序流越多， block 越大；另一方面，随机访问模式越多， block 大小越小。

如果您担心压缩/解压速度，请使用高速算法。如果解压缩速度是最重要的指标(对于访问时间)，像 LZ4 这样的东西将为您提供大约 1GB/s 的解码性能每核心，因此这让您了解每秒可以处理多少 block 解码。

如果只看重解压速度，可以使用高压缩版本LZ4-HC，压缩比提升30%左右，同时解压速度也有提升。