用公共部分压缩字符串

Question

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

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

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

谢谢

Answer 1

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

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

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

如果只注重解压速度，您可以使用高压缩变体 LZ4-HC，它将压缩比提高约 30%，同时还提高解压速度。

Answer 2

字符串采用类似路径的格式，并且有许多公共部分，但没有明确的规则。

从某种意义上说，它们是 name、(separator、name)* 形式的层次结构中的定位器？如果是这样，您可以使用interning：存储 name 部分作为指向字符串池的 char const * 元素。这样，您就可以有效地将使用 n 次的名称压缩到刚好超过 n * sizeof(char const *) + strlen(name) 字节。完整路径将成为一系列内部名称，例如 std::vector。

看起来 sizeof(char const *) 在 64 位硬件上很大，但您也节省了一些分配开销。或者，如果您出于某种原因知道您永远不会需要超过 65536 个字符串，您可以将它们存储为

class interned_name
{
    uint16_t tab_idx;

  public:
    char const *c_str() const
    {
        return NAME_TABLE[tab_idx];
    }
};

NAME_TABLE 是 static std::unordered_map。