Тонкости реализации алгоритмы Хаффмана

При реализации алгоритма Хаффмана столкнулся с проблемой при распаковке сжатого файла: в конце дописываются символы которых нет в оригинальном файле. Это алгоритм декодирования сжатого файла. Дерево я храню в векторе, элементы в массиве 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 бит длиннее. Или просто записывать размер оригинального файла и убирать лишние символы. Но нет ли какого-то более красивого решения?


Ответы (0 шт):