Huffman Coding implementation in C++

Question

Here is an implementation of compression with Huffman coding. It works well by my testing. It compresses a 1 GB string in about 30 seconds, and decompresses in about 15 seconds with VisualStudio 2022 "Release Mode x64" on my machine.

I've used std::vector<bool> as the "bitset", but simply replacing that type with boost::dynamic_bitset and leaving everything else as-is also works fine.

I would appreciate all comments.

[GitHub Repository]

---

Huffman.h:

// Huffman coding
// https://en.wikipedia.org/wiki/Huffman_coding

#ifndef HUFFMAN_H
#define HUFFMAN_H
#pragma once

#include <cstddef>
#include <cstdint>
#include <span>
#include <string_view>
#include <vector>

namespace Huffman {
namespace detail {
// Easily serializable:
// Trivial type with well-defined size of all fields.
struct Node {
  std::int16_t left;   // Left Node in tree. -1 means 'none'
  std::int16_t right;  // Right Node in tree. -1 means 'none'
  std::uint8_t value;  // Char value but always unsigned

  [[nodiscard]] constexpr bool isLeaf() const noexcept {
    return (left == -1) && (right == -1);
  }
};
}  // namespace detail

// This class represents fully compressed text
struct Encoded {
 private:
  std::vector<bool> binary_data_;     // bitset to store data compactly
  std::vector<detail::Node> nodes_;   // the tree

  void init_tree(std::span<std::uint8_t const> input_data);
  void init_binary_data(std::span<std::uint8_t const> input_data);

  // Root element is always the last one.
  // There is _always_ at least 1 element.
  [[nodiscard]] auto const &root() const {
    return nodes_.back();
  }
  [[nodiscard]] auto root_index() const {
    return static_cast<int16_t>(nodes_.size() - 1);
  }

 Encoded() = default;

 public:
  static Encoded encode(std::span<std::uint8_t const> input_data);
  static Encoded encode(void const *source, std::size_t size);
  static Encoded encode(std::span<std::byte const> input_data);
  static Encoded encode(std::string_view input_data);

  [[nodiscard]] std::string decode() const;
};
}  // namespace Huffman

#endif  // HUFFMAN_H

---

Huffman.cpp:

#include "Huffman.h"

#include <array>
#include <cassert>
#include <cstdint>
#include <execution>
#include <queue>
#include <span>

using Huffman::detail::Node, Huffman::Encoded, std::int16_t, std::uint8_t, std::size_t;

// We need the counts while encoding, but not later one.
struct NodeWithCount {
  Node node;
  size_t count;
};

// Given a range of bytes, return the count of each unique value.
constexpr auto count_bytes(std::span<uint8_t const> const bytes) noexcept {
  std::array<size_t, UCHAR_MAX + 1> counts = {};

  for (auto const ch: bytes) {
    ++counts[ch];
  }

  return counts;
}

// Given the number of each unique byte value, form the "leaf" nodes of our tree
static auto make_leaf_nodes(std::span<size_t const> const counts) {
  std::vector<NodeWithCount> nodes;

  for (size_t i = 0, sz = counts.size(); i < sz; ++i) {
    if (counts[i]) {
      nodes.push_back(NodeWithCount{Node{-1, -1, static_cast<uint8_t>(i)}, counts[i]});
    }
  }

  return nodes;
}

// This type is intended to store the "path" to each character
// in our tree. Used to "encode" the data initially.
// '\0' -> left
// '\1' -> right
using CharDictT = std::array<std::string, UCHAR_MAX + 1>;

static auto init_dict(std::vector<Node> const &nodes, int16_t root,
                      CharDictT &dict, std::string &key) {
  if (root < 0) {
    return;
  }
  assert(root < nodes.size());

  auto const &elm = nodes[root];

  if (elm.isLeaf()) {
    dict[elm.value] = key;
    return;
  }

  key.push_back(0);
  init_dict(nodes, elm.left, dict, key);
  key.back() = 1;
  init_dict(nodes, elm.right, dict, key);
  key.pop_back();
}

std::string Huffman::Encoded::decode() const {
  // https://en.wikipedia.org/wiki/Huffman_coding#Decompression

  auto node = root();
  std::string str;

  for (bool i: binary_data_) {
    auto const go_right = i;
    node = nodes_[go_right ? node.right : node.left];
    if (node.isLeaf()) {
      str += static_cast<char>(node.value);
      node = root();
    }
  }

  return str;
}

Encoded Encoded::encode(std::span<std::uint8_t const> input_data) {
  // https://en.wikipedia.org/wiki/Huffman_coding#Compression

  Encoded encoded;
  encoded.init_tree(input_data);
  encoded.init_binary_data(input_data);
  return encoded;
}

void Encoded::init_tree(std::span<std::uint8_t const> const input_data) {
  auto nodes_with_size = make_leaf_nodes(count_bytes(input_data));

  auto const cmp = [&nodes_with_size](int16_t const lhs,
                                      int16_t const rhs) noexcept -> bool {
    // reverse compare
    return nodes_with_size[lhs].count > nodes_with_size[rhs].count;
  };

  auto queue =
      std::priority_queue<int16_t, std::vector<int16_t>, decltype(cmp)>(cmp);

  for (int16_t i = 0, sz = static_cast<int16_t>(nodes_with_size.size());
       i < sz; ++i) {
    if (nodes_with_size[i].count) {
      queue.push(i);
    }
  }

  // 0 and 1 are trivial cases that the later while loop does not handle.
  switch (queue.size()) {
    case 0: nodes_ = {Node{-1, -1, 0}};
      return;
    case 1: nodes_ = {Node{-1, -1, input_data.front()}, Node{-1, 0, 0}};
      return;
    default: break;
  }

  while (queue.size() > 1) {
    auto back1 = queue.top();
    queue.pop();
    auto back2 = queue.top();
    queue.pop();
    nodes_with_size.push_back(
        NodeWithCount{Node{back1, back2, 0},
                      nodes_with_size[back1].count + nodes_with_size[back2].count});
    queue.push(static_cast<int16_t>(nodes_with_size.size() - 1));
  }

  nodes_.resize(nodes_with_size.size());

  std::transform(nodes_with_size.begin(), nodes_with_size.end(),
                 nodes_.begin(), [](NodeWithCount const &withCount) -> auto & { return withCount.node; });
}

static auto init_dict(std::vector<Node> const &nodes, int16_t root,
                      CharDictT &dict) {
  std::string key;
  init_dict(nodes, root, dict, key);
}

void Huffman::Encoded::init_binary_data(std::span<std::uint8_t const> const input_data) {
  // Step 1: Create a dictionary with paths for all characters

  CharDictT dict = {};

  init_dict(nodes_, root_index(), dict);

  // Step 2: Calculate the final length of the binary data

  // This binary operator handles out-of-sequence sums for std::reduce
  struct BinOp {
    // The dictionary is just a pointer, because functors are often copied in C++,
    // and we don't want to copy 256 std::strings left and right.
    CharDictT *dict;

    [[nodiscard]] auto operator()(size_t const a, size_t const b) const noexcept { return a + b; }
    [[nodiscard]] auto operator()(size_t const a, uint8_t const b) const noexcept {
      return a + (*dict)[b].size();
    }
    [[nodiscard]] auto operator()(uint8_t const a, size_t const b) const noexcept {
      return (*dict)[a].size() + b;
    }
    [[nodiscard]] auto operator()(uint8_t const a, uint8_t const b) const noexcept {
      return (*dict)[a].size() + (*dict)[b].size();
    }
  };

  auto const size = std::reduce(std::execution::par_unseq, input_data.begin(),
                                input_data.end(), size_t{}, BinOp{&dict});

  binary_data_.resize(size);

  // Step 3: Concat all paths

  size_t bit_iter = 0;
  for (uint8_t ch: input_data) {
    for (auto const &bit: dict[ch]) {
      binary_data_[bit_iter++] = !!bit;
    }
  }
}

Encoded Encoded::encode(void const *const source, std::size_t const size) {
  return encode(std::span{static_cast<std::uint8_t const *>(source), size});
}

Encoded Encoded::encode(std::span<std::byte const> const input_data) {
  return encode(input_data.data(), input_data.size());
}

Encoded Encoded::encode(std::string_view const input_data) {
  return encode(input_data.data(), input_data.size());
}

---

main.cpp:

#include "Huffman.h"

#include <string_view>
#include <iostream>

int main() {
  constexpr std::string_view str =
      "Four score and seven years ago our fathers brought forth on this continent, a new nation, "
      "conceived in Liberty, and dedicated to the proposition that all men are created equal.\n"
      "Now we are engaged in a great civil war, testing whether that nation, or any nation so "
      "conceived and so dedicated, can long endure.We are met on a great battle - field of that "
      "war.We have come to dedicate a portion of that field, as a final resting place for those "
      "who here gave their lives that that nation might live.It is altogether fittingand proper that we should do this.\n"
      "But, in a larger sense, we can not dedicate - we can not consecrate - we can not "
      "hallow - this ground.The brave men, livingand dead, who struggled here, have consecrated "
      "it, far above our poor power to add or detract.The world will little note, nor long remember "
      "what we say here, but it can never forget what they did here.It is for us the living, rather, "
      "to be dedicated here to the unfinished work which they who fought here have thus far so nobly "
      "advanced.It is rather for us to be here dedicated to the great task remaining before us - that "
      "from these honored dead we take increased devotion to that cause for which they gave the last "
      "full measure of devotion - that we here highly resolve that these dead shall not have died in "
      "vain - that this nation, under God, shall have a new birth of freedom - and that government of "
      "the people, by the people, for the people, shall not perish from the earth.";

  auto const encoded = Huffman::Encoded::encode(str);
  auto const decoded = encoded.decode();

  if (str == decoded) {
    std::cout << "Test Passed\n";
  } else {
    std::cout << "Test Failed\n";
  }
}

Answer 1

Storing codewords as std::string

// This type is intended to store the "path" to each character
// in our tree. Used to "encode" the data initially.
// '\0' -> left
// '\1' -> right
using CharDictT = std::array<std::string, UCHAR_MAX + 1>;

Having an array of codewords is a good idea, storing them as strings is good for debugging purposes but not so good for anything else. As an alternative, you may consider storing a pair of (length, bits) as eg an pair<size_t, size_t> or some other suitable integer types. Having a pair of length and bits in hand, rather than a string, would then enable you to append those bits to your compressed storage using a couple of efficient bitwise operations, rather than an iteration through a string and a bunch of bit-by-bit appends.

An approach like that wouldn't combine well with vector<bool> which unfortunately has an interface that required bit-by-bit operations to begin with, but something like an vector<uint8_t> (or some other fixed-width unsigned integer type) could be suitable. Note that with the data stored as vector<uint8_t> (or similar), the decoder would need some independent mechanism to detect the end of the data (such as storing the uncompressed length, or an end-of-data symbol, or both), otherwise it may try to decode the padding bits in the last element.

As a quick test, I implemented such a thing so as to be compatible with your decoder (when each byte of the result is read bit-by-bit from the most significant bit down). The code that does the encoding looked like this: (this is just a quickly thown-together implementation of this technique)

size_t out_index = 0;
uint32_t buffer = 0;
size_t bits_in_buffer = 0;
for (uint8_t ch : input_data) {
    auto& code = dict[ch];
    buffer <<= code.first;
    buffer |= code.second;
    bits_in_buffer += code.first;
    while (bits_in_buffer >= 8) {
        binary_data_[out_index++] = buffer >> (bits_in_buffer - 8);
        bits_in_buffer -= 8;
    }
}
if (bits_in_buffer) {
    binary_data_[out_index++] = buffer << (8 - bits_in_buffer);
}

On my PC, compressing about 1GB of data (I used your test string, concatenated with itself a bunch of times) took around 8000 milliseconds with the string-based method, and around 1900 milliseconds with the bitmath-based method.

Serializing the whole tree

Serializing the whole tree could cost 8 bytes per node (thanks to alignment) or at least 5 bytes (if packed), with roughly twice as many nodes as leafs that amounts to around 10-16 bytes per symbol in the alphabet. That could be 4KB just for the tree. Using canonical Huffman code makes it easy to build a decoding table^{(see below)} straight from merely the array of code lengths, which could be easily stored in 1 byte each, or could be compressed further if you want (eg DEFLATE uses both Huffman coding and run-length encoding to compress its table of code lengths, see section 3.2.7).

Bit-by-bit decoding

Bit-by-bit decoding is simple but inherently inefficient, there are more efficient alternatives based on decoding multiple bits at once using lookup tables. You can see that as turning the binary tree into a k-ary trie, eg a 4-ary trie with 4 children per node would mostly decode 2 bits at the time, though it does not perfectly halve the depth of the tree due to odd length "wasting" some of the potential (resulting in a node that has fewer than 4 unique children, with one or two being duplicated). If you set a length limit on the codes that the encoder produces (many application of Huffman coding specify a length limit for this reason), k can be set equal to that limit, meaning that the decoding trie becomes just a single-layer aka a decoding array, with which a symbol can be decoded in just one lookup. Naturally that array would be full of duplicates, having a length of 2^k but only UCHAR_MAX + 1 unique values.

I've explained that approach to decoding in more detail in earlier answers to different questions such as Huffman Coding library implemented in C but I'd be happy to go in whatever detail you want.

By the way it may be attractive to set k high or to leave it unlimited, but while that is required for the theoretical proof of optimality of Huffman coding (under the assumptions which that proof makes), increasing the length limit above 16 is typically underwhelming in practice^{(see below)}. DEFLATE sets a limit of 15, JPEG sets a limit of 16, Bzip2 sets a limit of 20 which is on the high end. High k can be supported with a small decoding table by using advanced decoding techniques.

As a practical example, I took the common text compression test file "alice29.txt", concatenated it 10 times, and compressed it with length-limited Huffman codes (using a simple length limiting scheme, not optimal length-limited codes), using 32-bit output chunks instead of 8-bit but that matters little. The "natural" maximum codeword length was 17 bits, so going above that automatically makes no difference. Sizes include the file header.

length limit	compressed size (in bytes)
17	876948
16	876952
15	877000
14	877128
13	877504
12	877504 (not a copy&paste mistake)
11	878244
10	881016

10 bits was noticeably worse than the others, but 15 bits was already so far into the diminishing returns that increasing the codelength limit from 14 to 15 represents an improve of about one in ten thousand.

Data with a more skewed distribution benefits more from a higher codelength limit, so these results should not be generalized too much.

Answer 2

Tests

Firstly, thank you for providing test code to help with the review - that's always useful. We could improve the testing by adding some additional test cases; encoding the empty string is a good start, as is decoding invalid input (probably run that under Valgrind or similar to ensure it doesn't access uninitialised or invalid memory). Also, make sure that \0 round-trips successfully.

The test could be further improved (probably by using one of the common test frameworks) to show at what point the reconstituted string differs from the encoder input.

---

Interface

The [[nodiscard]] attribute seems overkill - none of the functions so marked will ever be called for side-effects, so it's very unlikely that their return values will be ignored. And if so, that's harmless, unlike ignoring a C-style error indication.

Instead of writing struct Encoded and immediately beginning with a private: section, I recommend declaring it as class. Some style guides prohibit private members when using struct.

A default-constructed Encoded appears to have problems (e.g. root() calls back() on an empty vector). It's probably better to remove the default constructor and change the encode() functions to be constructors.

Do we really need that many encode() functions? I recommend a generic function accepting a range (perhaps constrained on the range's value type).

There's not much we can do with an Encoded other than to decode() it. Compression is of limited use unless you're able to transmit or store the compressed data. We'll also need to be able to reconstruct one from a byte-stream.

---

Implementation

BinOp is poorly named. It's a specific kind of binary operation, namely an accumulator. It has a pointer member, dict, which can more safely and conveniently be a reference member.

Some of the algorithms could be written more simply using the Ranges version. For example:

  std::transform(nodes_with_size.begin(), nodes_with_size.end(),
                 nodes_.begin(), [](NodeWithCount const &withCount) -> auto & { return withCount.node; });

becomes:

std::ranges::transform(nodes_with_size, nodes_.begin(), &NodeWithCount::node);

For reasonable size char, the parallel reduce() overheads probably mean a straightforward (sequential) std::accumulate() will be a better choice. If CHAR_BIT is 16, we'd need to benchmark; more than that, then consider the parallel algorithm.