Я реализую программу, которая использует кодирование Хаффмана для сжатия файла. У меня проблемы с записью битов сжатой строки в другой набор битов. У меня есть вектор байтов (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, а затем добавляет эту строку в сжатую строку. Как только сжатая строка завершена, она преобразует ее в набор битов. Проблема этого метода заключается в том, что он очень медленно заполняет набор битов, потому что в моем векторе 72 миллиона байт. Мне не нравится этот метод, потому что, кажется, нет необходимости заполнять эту огромную строку, просто чтобы преобразовать ее в набор битов. Я бы предпочел что-то вроде этого:
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
Ваше узкое место почти наверняка это линия:
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);
Как видите, преобразование в строку выполняется за одну операцию. Обидно, что нужно копировать такую большую структуру данных, но другого пути, похоже, не существует.
Других решений пока нет …