Тонкости реализации алгоритмы Хаффмана
При реализации алгоритма Хаффмана столкнулся с проблемой при распаковке сжатого файла: в конце дописываются символы которых нет в оригинальном файле. Это алгоритм декодирования сжатого файла. Дерево я храню в векторе, элементы в массиве child - индексы потомков.
void Huffman::decode(std::istream& src, std::ostream& dest) {
std::uint16_t size;
src.read(reinterpret_cast<char*>(&size), sizeof(size));
_tree.resize(size);
src.read(reinterpret_cast<char*>(_tree.data()), size * sizeof(Node));
std::int16_t root = size - 1;
for (char chr : streamrange(src)) {
for (char idx = 0; idx < CHAR_BIT; ++idx) {
root = _tree[root].child[(chr & 1 << idx) >> idx];
if (_isleaf(root)) {
dest.put(_tree[root].content);
root = size - 1;
}
}
}
}
Структура узла дерева:
struct Node {
char content;
std::int16_t child[2];
};
streamrange просто вот такая функция:
auto streamrange(std::istream& in) {
using iterator = std::istreambuf_iterator<char>;
struct wrapper {
std::istream& _in;
iterator begin() { return {_in}; }
iterator end () { return {}; }
};
return wrapper{in};
}
Я думал решить эту проблему добавив в дерево терминирующий префикс, но тогда у одного из символов код будет на 1 бит длиннее. Или просто записывать размер оригинального файла и убирать лишние символы. Но нет ли какого-то более красивого решения?