huffman.h File Reference

High-performance Huffman encoder/decoder supporting both canonical and standard tree-based algorithms, with selectable symbol ranges (128 or 256). More...

#include <cstdint>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include "jh/metax/t_str.h"
#include "jh/pods/array.h"
#include "jh/pods/pair.h"
#include "jh/pods/bytes_view.h"

Go to the source code of this file.

Classes
class	jh::serio::huffman< Signature, Algo >
	High-performance Huffman encoder/decoder. More...

Namespaces
namespace	jh::serio
	Aggregated entry point for serialization and codec utilities.

Enumerations
enum class	jh::serio::huff_algo : std::uint8_t { jh::serio::huff128 , jh::serio::huff256 , jh::serio::huff128_canonical , jh::serio::huff256_canonical }
	Enumeration of supported Huffman algorithm variants. More...

Detailed Description

High-performance Huffman encoder/decoder supporting both canonical and standard tree-based algorithms, with selectable symbol ranges (128 or 256).

Copyright

Copyright 2025 JeongHan-Bae <mastropseudo@gmail.com>
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.

Full license: GitHub

Author

JeongHan-Bae <mastropseudo@gmail.com>

The jh::serio::huffman component provides four distinct compression algorithms:

• huff128 — Standard Huffman for ASCII (0-127)
• huff256 — Standard Huffman for full byte range (0-255)
• huff128_canonical — Canonical Huffman (ASCII)
• huff256_canonical — Canonical Huffman (full byte range)

Canonical algorithms generate deterministic codewords, enabling extremely fast decoding via table lookups without tree traversal. Normal Huffman algorithms preserve legacy tree behavior for compatibility with older formats.

Feature Comparison

Feature	huff128	huff128_canonical	huff256	huff256_canonical
Symbol range	0-127	0-127	0-255	0-255
Encoding speed	✔ Fast	✔ Fast<br>(minor setup cost)	✔ Fast	✔ Fastest overall
Decoding speed	✘ Slow<br>(tree traversal)	✔✔ Very fast (table-based)	✘ Slow<br>(tree traversal)	✔✔ Very fast (table-based)
Worst-case decode complexity	O(depth × N)	O(N)	O(depth × N)	O(N)
Codeword determinism	✘	✔ Canonical	✘	✔ Canonical
Best usage	Legacy formats / debugging	High-performance ASCII	General binary data	High-performance binary

Measured Performance

Apple Silicon M3, LLVM clang++ 20, input size 20k-200k bytes (2025).

Operation	huff128	huff128_canonical	huff256	huff256_canonical
Debug (unoptimized)
Encode	0.45-4.3 ms	0.44-4.6 ms	0.54-4.0 ms	0.48-3.8 ms
Decode	1.4-15 ms	0.39-3.8 ms	1.5-15 ms	0.44-4.2 ms
Relative decode speed	1× (baseline)	≈ 3.5-4× faster	1× (baseline)	≈ 3.5-4× faster
O3 optimized
Encode	0.155-1.51 ms	0.154-1.49 ms	0.156-1.52 ms	0.156-1.48 ms
Decode	0.406-2.27 ms	0.290-2.17 ms	0.265-2.27 ms	0.260-2.16 ms
Relative decode speed	1× (baseline)	≈1.05-1.4× faster	1× (baseline)	≈1.02-1.05× faster

Usage Example

using jh::serio::huff_algo;
using HUF = jh::serio::huffman<"demo", huff_algo::huff256_canonical>;
 
std::ostringstream out_stream(std::ios::binary);
HUF::compress(out_stream, "hello world");
 
const std::string binary = out_stream.str();
 
std::istringstream in_stream(binary, std::ios::binary);
std::string recovered = HUF::decompress(in_stream);
std::cout << recovered << std::endl;

Version

1.4.x

Date

2025