Template Class CanonicalHuffman

Class Documentation

template<class C>
class CanonicalHuffman

the canonical prefix code of the given lengths of the symbols of type C

Public Types

using symbol_type = C

Public Functions

explicit CanonicalHuffman(const std::map<C, int> &lengths)

the canonical code of the lengths

Pre:

lengths not empty, each in [ 1 , 63 ], sum of 2^-l at most 1

inline const std::map<C, int> &lengths(void) const

the lengths of the codes

inline int maxLength(void) const

the longest length

std::uint64_t firstCode(int l) const

fc[ l ], the value of the first code of length l

Pre:

1 <= l <= maxLength()

std::string code(const C &c) const

the code of c, a string of ‘0’ and ‘1’

Pre:

c has a code

void encode(const C &c, PackedBitWriter &w) const

appends the code of c to w

Pre:

c has a code

std::vector<std::uint8_t> encode(std::span<const C> text) const

the codes of the symbols of text, packed in bytes

Pre:

each symbol of text has a code

Post:

decode( result , text.size() ) == text (an audit)

C decode(PackedBitReader &r) const

the symbol whose code is next in r

Pre:

the next bits of r are a code

std::vector<C> decode(const std::vector<std::uint8_t> &bits, std::size_t n) const

the first n symbols encoded in bits

Pre:

bits begins with n codes

Public Static Functions

template<class F>
static CanonicalHuffman fromFrequencies(const std::map<C, F> &freq)

the canonical code of the code of Huffman of the frequencies

Pre:

as huffmanLengths()