FilesExpand file tree

 master

/

CanonicalCode.hpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

101 lines (78 loc) · 2.85 KB

 master

/

CanonicalCode.hpp

Copy path

Top

File metadata and controls

• Code
• Blame

101 lines (78 loc) · 2.85 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

/*

* Reference Huffman coding

* Copyright (c) Project Nayuki

*

* https://www.nayuki.io/page/reference-huffman-coding

* https://github.com/nayuki/Reference-Huffman-coding

*/

#pragma once

#include <cstdint>

#include <vector>

#include "CodeTree.hpp"

/*

* A canonical Huffman code, which only describes the code length of

* each symbol. Immutable. Code length 0 means no code for the symbol.

* The binary codes for each symbol can be reconstructed from the length information.

* In this implementation, lexicographically lower binary codes are assigned to symbols

* with lower code lengths, breaking ties by lower symbol values. For example:

* Code lengths (canonical code):

* Symbol A: 1

* Symbol B: 3

* Symbol C: 0 (no code)

* Symbol D: 2

* Symbol E: 3

*

* Sorted lengths and symbols:

* Symbol A: 1

* Symbol D: 2

* Symbol B: 3

* Symbol E: 3

* Symbol C: 0 (no code)

*

* Generated Huffman codes:

* Symbol A: 0

* Symbol D: 10

* Symbol B: 110

* Symbol E: 111

* Symbol C: None

*

* Huffman codes sorted by symbol:

* Symbol A: 0

* Symbol B: 110

* Symbol C: None

* Symbol D: 10

* Symbol E: 111

*/

class CanonicalCode final {

/*---- Field ----*/

private: std::vector<std::uint32_t> codeLengths;

/*---- Constructors ----*/

// Constructs a canonical Huffman code from the given array of symbol code lengths.

// Each code length must be non-negative. Code length 0 means no code for the symbol.

// The collection of code lengths must represent a proper full Huffman code tree.

// Examples of code lengths that result in under-full Huffman code trees:

// - [1]

// - [3, 0, 3]

// - [1, 2, 3]

// Examples of code lengths that result in correct full Huffman code trees:

// - [1, 1]

// - [2, 2, 1, 0, 0, 0]

// - [3, 3, 3, 3, 3, 3, 3, 3]

// Examples of code lengths that result in over-full Huffman code trees:

// - [1, 1, 1]

// - [1, 1, 2, 2, 3, 3, 3, 3]

public: explicit CanonicalCode(const std::vector<std::uint32_t> &codeLens);

// Builds a canonical Huffman code from the given code tree.

public: explicit CanonicalCode(const CodeTree &tree, std::uint32_t symbolLimit);

// Recursive helper method for the above constructor.

private: void buildCodeLengths(const Node *node, std::uint32_t depth);

/*---- Various methods ----*/

// Returns the symbol limit for this canonical Huffman code.

// Thus this code covers symbol values from 0 to symbolLimit&minus;1.

public: std::uint32_t getSymbolLimit() const;

// Returns the code length of the given symbol value. The result is 0

// if the symbol has node code; otherwise the result is a positive number.

public: std::uint32_t getCodeLength(std::uint32_t symbol) const;

// Returns the canonical code tree for this canonical Huffman code.

public: CodeTree toCodeTree() const;

};