0

我正在实现一个使用霍夫曼编码压缩文件的程序。我无法将压缩字符串的位写入另一个位集。我有一个字节向量（8 位整数）和一个字符串向量 huffCodes，它的大小为 256，用于存储每个索引的位字符串。（比如0用11表示，1用11011表示，等等。）

这是我目前的方法：

string compressed = "";
boost::dynamic_bitset<unsigned char> output;

for(byte b : bytes) 
{
    compressed += huffCodes [ ByteToInt(std::to_string(b)) ];
}

output = boost::dynamic_bitset<unsigned char> (compressed);

这会遍历每个字节并从 huffCodes 向量中获取其相应的位串，然后将该字符串附加到压缩字符串中。压缩字符串完成后，会将其转换为位集。这种方法的问题在于它非常缓慢地填充位集，因为我的向量中有 7200 万字节。不过我不喜欢这种方法，因为似乎没有必要填充这个巨大的字符串来将其转换为位集。我更喜欢这样的东西：

boost::dynamic_bitset<unsigned char> output;
string temp = "";
    for(byte b : bytes) 
    {
        temp = huffCodes [ ByteToInt(std::to_string(b)) ];
        output.append(temp);
    }

显然这不是真正的代码，但理想情况下，我会在从 huffCodes 向量中收集所有字符串的同时填充输出位集。是否可以通过某种连接或将字符串附加到位集来做到这一点？

注意：huffCodes 向量的内容是大小为 8 的字符串，仅由 1 和 0 组成

4

1 回答 1

0

您的瓶颈几乎可以肯定是这一行：

compressed += huffCodes [ ByteToInt(std::to_string(b)) ];

因为在您循环循环时，输出字符串 ( compressed) 将被重新分配和复制多次。

而不是这样做，请尝试以下操作。请注意，这会预先分配适当大小的向量，以避免需要进行昂贵的重新分配和复制。我也没有看到需要转换b为字符串然后再转换回一个int所以我把那一点去掉：

std::string s;
int nbytes = 0;
for (b : bytes)
    nbytes += huffcodes [b].size ();

{
    std::vector <char> v (nbytes + 1);
    for (b : bytes)
    {
        auto hc = huffcodes [b];
        for (auto c : hc)
            v.push_back (c);
    }

    v.push_back (0);    // NUL terminator
    s = v.data ();
}

auto output = boost::dynamic_bitset<unsigned char> (s);

如您所见，转换为字符串是在单个操作中完成的。不得不复制这么大的数据结构是一种耻辱，但似乎没有其他办法。

于 2018-12-03T00:58:34.660 回答