Huffman encoder. More...

#include <Huffman.H>

Collaboration diagram for Aleph::Huffman_Encoder_Engine:

Classes
struct	Get_Key

struct	Load_Key

Public Member Functions
	Huffman_Encoder_Engine ()
	Encoder constructor.

	~Huffman_Encoder_Engine ()
	Destructor - frees all allocated memory.

void	save_tree (std::ostream &output) const
	Save a Huffman tree into a stream.

void	save_tree_in_array_of_chars (const std::string &array_name, std::ostream &output) const
	Generate C/C++ array declarations for a Huffman tree.

BinNode< std::string > *&	get_root ()
	Returns the root of the Huffman decoding tree.

BinNode< std::string > *	generate_huffman_tree (const bool &with_freqs=false)
	Generate the Huffman prefix tree.

void	load_tree (std::istream &input)
	Load and build a binary tree from a stream.

Freq_Node *&	get_freq_root ()
	Returns the root of the frequency tree.

void	set_freq (const std::string &str, const size_t &freq)
	Define the frequency of a symbol.

void	read_input (char *input, const bool &with_freqs=false)
	Read a NUL-terminated character std::string, count frequencies and build the prefix tree.

void	read_input (std::istream &input, const bool &with_freqs=false)
	Read a stream, count frequencies and build the prefix tree.

void	set_end_of_stream (const std::string &str)
	Defines the end-of-stream symbol.

const std::string &	get_end_of_stream () const noexcept
	Return the configured end-of-stream symbol.

size_t	encode (char *input, BitArray &bit_stream)
	Encode the input text.

size_t	encode (std::istream &input, BitArray &bit_stream)
	Encode the input text from a stream.

Private Member Functions
void	build_prefix_encoding (BinNode< std::string > *p, BitArray &array)

void	build_encoding_map ()

bool	test_end (const std::string &str) const

void	update_freq (const std::string &str)

void	insert_end_symbol_node (const std::string &str)

void	clear_build_state () noexcept

Static Private Member Functions
static void	append_code (BitArray &bit_stream, const BitArray &symbol_code)

static void	save_string_as_bytes (const std::string &str, std::ostream &output)

static std::string	load_string_from_bytes (std::istream &input)

static void	save_leaf_keys_in_prefix (BinNode< std::string > *p, std::ostream &output)

static void	load_leaf_keys_in_prefix (BinNode< std::string > *p, std::istream &input)

Private Attributes
BinNode< std::string > *	root_

Huffman_Heap	heap_

Symbol_Map	symbol_map_

Code_Map	code_map_

Freq_Node *	freq_root_

std::string	end_symbol_

size_t	text_len_

Static Private Attributes
static const size_t	Max_Token_Size = 256

Detailed Description

Huffman encoder.

See also: Huffman_Decoder_Engine

Definition at line 114 of file Huffman.H.

Constructor & Destructor Documentation

◆ Huffman_Encoder_Engine()

Aleph::Huffman_Encoder_Engine::Huffman_Encoder_Engine ( )

inline

Encoder constructor.

Definition at line 191 of file Huffman.H.

◆ ~Huffman_Encoder_Engine()

Aleph::Huffman_Encoder_Engine::~Huffman_Encoder_Engine ( )

inline

Destructor - frees all allocated memory.

Definition at line 197 of file Huffman.H.

References clear_build_state().

Member Function Documentation

◆ append_code()

static void Aleph::Huffman_Encoder_Engine::append_code	(	BitArray &	bit_stream,
		const BitArray &	symbol_code
	)

inlinestaticprivate

Definition at line 182 of file Huffman.H.

References Aleph::blossom_maximum_cardinality_matching().

Referenced by encode(), and encode().

◆ build_encoding_map()

void Aleph::Huffman_Encoder_Engine::build_encoding_map ( )

inlineprivate

Definition at line 142 of file Huffman.H.

References ah_domain_error_if, build_prefix_encoding(), code_map_, Aleph::DynSetTree< Key, Tree, Compare >::empty(), root_, and symbol_map_.

Referenced by generate_huffman_tree(), and load_tree().

◆ build_prefix_encoding()

void Aleph::Huffman_Encoder_Engine::build_prefix_encoding	(	BinNode< std::string > *	p,
		BitArray &	array
	)

inlineprivate

Definition at line 126 of file Huffman.H.

References build_prefix_encoding(), code_map_, Aleph::BinNode< Key >::get_key(), Aleph::DynMapTree< Key, Data, Tree, Compare >::insert(), Aleph::is_leaf(), LLINK, Aleph::BitArray::pop(), Aleph::BitArray::push(), and RLINK.

Referenced by build_encoding_map(), and build_prefix_encoding().

◆ clear_build_state()

void Aleph::Huffman_Encoder_Engine::clear_build_state ( )

inlineprivatenoexcept

Definition at line 489 of file Huffman.H.

References Aleph::Huffman_Node::bin_node, Aleph::blossom_maximum_cardinality_matching(), code_map_, Aleph::DynSetTree< Key, Tree, Compare >::empty(), end_symbol_, Aleph::GenBinHeap< NodeType, Key, Compare >::getMin_ne(), heap_, Aleph::GenBinHeap< NodeType, Key, Compare >::is_empty(), symbol_map_, and text_len_.

Referenced by ~Huffman_Encoder_Engine(), and load_tree().

◆ encode() [1/2]

size_t Aleph::Huffman_Encoder_Engine::encode	(	char *	input,
		BitArray &	bit_stream
	)

inline

Encode the input text.

encode(input, bit_stream) reads input, encodes it and appends the result to bit_stream.

Parameters

[in]	input	NUL-terminated std::string containing the text to encode.
[out]	bit_stream	Bit array where the encoded stream is appended.

Returns: Total bit length of bit_stream after encoding.

Exceptions

std::domain_error if the prefix tree has not been generated.

Definition at line 598 of file Huffman.H.

References ah_domain_error_if, append_code(), Aleph::blossom_maximum_cardinality_matching(), code_map_, end_symbol_, Aleph::DynMapTree< Key, Data, Tree, Compare >::find(), Max_Token_Size, and root_.

◆ encode() [2/2]

size_t Aleph::Huffman_Encoder_Engine::encode	(	std::istream &	input,
		BitArray &	bit_stream
	)

inline

Encode the input text from a stream.

encode(input, bit_stream) reads from input until EOF, encodes the symbols and appends the result to bit_stream.

Parameters

[in]	input	Stream containing the text to encode.
[out]	bit_stream	Bit array where the encoded stream is appended.

Returns: Total bit length of bit_stream after encoding.

Exceptions

std::domain_error if the prefix tree has not been generated.

Definition at line 627 of file Huffman.H.

References ah_domain_error_if, append_code(), Aleph::blossom_maximum_cardinality_matching(), code_map_, end_symbol_, Aleph::DynMapTree< Key, Data, Tree, Compare >::find(), and root_.

◆ generate_huffman_tree()

BinNode< std::string > * Aleph::Huffman_Encoder_Engine::generate_huffman_tree ( const bool & with_freqs = false )

inline

Generate the Huffman prefix tree.

generate_huffman_tree(with_freqs) runs Huffman's algorithm and builds the prefix tree from the collected symbol frequencies. If with_freqs is true, an additional tree containing frequencies is built as well.

Parameters

[in] with_freqs If true, also build the frequency tree.

Returns: The root of the Huffman decoding (prefix) tree.

Exceptions

std::bad_alloc if there is not enough memory.

See also: build_prefix_encoding Huffman_Decoder_Engine

Definition at line 291 of file Huffman.H.

References ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), build_encoding_map(), freq_root_, Aleph::get_freq(), Aleph::BinNode< Key >::get_key(), Aleph::GenBinHeap< NodeType, Key, Compare >::getMin(), heap_, Aleph::GenBinHeap< NodeType, Key, Compare >::insert(), Aleph::GenBinHeap< NodeType, Key, Compare >::is_empty(), LLINK, RLINK, root_, Aleph::set_freq(), and Aleph::GenBinHeap< NodeType, Key, Compare >::size().

Referenced by read_input(), and read_input().

◆ get_end_of_stream()

const std::string & Aleph::Huffman_Encoder_Engine::get_end_of_stream ( ) const

inlinenoexcept

Return the configured end-of-stream symbol.

Definition at line 583 of file Huffman.H.

References end_symbol_.

◆ get_freq_root()

Freq_Node *& Aleph::Huffman_Encoder_Engine::get_freq_root ( )

inline

Returns the root of the frequency tree.

Definition at line 381 of file Huffman.H.

References ah_domain_error_if, and freq_root_.

◆ get_root()

BinNode< std::string > *& Aleph::Huffman_Encoder_Engine::get_root ( )

inline

Returns the root of the Huffman decoding tree.

Definition at line 272 of file Huffman.H.

References ah_domain_error_if, and root_.

◆ insert_end_symbol_node()

void Aleph::Huffman_Encoder_Engine::insert_end_symbol_node ( const std::string & str )

inlineprivate

Definition at line 479 of file Huffman.H.

References Aleph::blossom_maximum_cardinality_matching(), heap_, Aleph::DynMapTree< Key, Data, Tree, Compare >::insert(), Aleph::GenBinHeap< NodeType, Key, Compare >::insert(), and symbol_map_.

Referenced by read_input(), read_input(), and set_end_of_stream().

◆ load_leaf_keys_in_prefix()

static void Aleph::Huffman_Encoder_Engine::load_leaf_keys_in_prefix	(	BinNode< std::string > *	p,
		std::istream &	input
	)

inlinestaticprivate

Definition at line 464 of file Huffman.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::BinNode< Key >::get_key(), Aleph::is_leaf(), LLINK, load_leaf_keys_in_prefix(), load_string_from_bytes(), and RLINK.

Referenced by load_leaf_keys_in_prefix(), and load_tree().

◆ load_string_from_bytes()

static std::string Aleph::Huffman_Encoder_Engine::load_string_from_bytes ( std::istream & input )

inlinestaticprivate

Definition at line 428 of file Huffman.H.

References ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), and Max_Token_Size.

Referenced by load_leaf_keys_in_prefix(), and load_tree().

◆ load_tree()

void Aleph::Huffman_Encoder_Engine::load_tree ( std::istream & input )

inline

Load and build a binary tree from a stream.

load_tree(input) reads a Huffman tree previously saved with save_tree() and restores it into memory.

Parameters

[in] input Input stream containing the serialized tree.

Exceptions

std::bad_alloc	if there is not enough memory.
std::domain_error	if the stream is malformed.

See also: save_tree()

Definition at line 363 of file Huffman.H.

References Aleph::blossom_maximum_cardinality_matching(), build_encoding_map(), clear_build_state(), Aleph::destroyRec(), end_symbol_, freq_root_, Aleph::BitArray::load(), load_leaf_keys_in_prefix(), load_string_from_bytes(), Aleph::prefix(), and root_.

◆ read_input() [1/2]

void Aleph::Huffman_Encoder_Engine::read_input	(	char *	input,
		const bool &	with_freqs = `false`
	)

inline

Read a NUL-terminated character std::string, count frequencies and build the prefix tree.

read_input(input, with_freqs) reads the NUL-terminated std::string input, counts the frequency of each symbol and builds the Huffman prefix tree.

Parameters

[in]	input	NUL-terminated std::string to encode.
[in]	with_freqs	If true, also build the frequency tree.

Exceptions

std::bad_alloc if there is not enough memory.

Definition at line 514 of file Huffman.H.

References ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), end_symbol_, generate_huffman_tree(), insert_end_symbol_node(), Max_Token_Size, root_, Aleph::DynMapTree< Key, Data, Tree, Compare >::search(), set_end_of_stream(), symbol_map_, text_len_, and update_freq().

Referenced by HuffmanBtreepicTest::create_encoder(), and TEST_F().

◆ read_input() [2/2]

void Aleph::Huffman_Encoder_Engine::read_input	(	std::istream &	input,
		const bool &	with_freqs = `false`
	)

inline

Read a stream, count frequencies and build the prefix tree.

read_input(input, with_freqs) reads characters from input until EOF, counts symbol frequencies and builds the Huffman prefix tree.

Parameters

[in]	input	Stream containing the text to encode.
[in]	with_freqs	If true, also build the frequency tree.

Exceptions

std::bad_alloc if there is not enough memory.

Definition at line 547 of file Huffman.H.

References ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), end_symbol_, generate_huffman_tree(), insert_end_symbol_node(), root_, Aleph::DynMapTree< Key, Data, Tree, Compare >::search(), set_end_of_stream(), symbol_map_, text_len_, and update_freq().

◆ save_leaf_keys_in_prefix()

static void Aleph::Huffman_Encoder_Engine::save_leaf_keys_in_prefix	(	BinNode< std::string > *	p,
		std::ostream &	output
	)

inlinestaticprivate

Definition at line 448 of file Huffman.H.

References Aleph::BinNode< Key >::get_key(), Aleph::is_leaf(), LLINK, output, RLINK, save_leaf_keys_in_prefix(), and save_string_as_bytes().

Referenced by save_leaf_keys_in_prefix(), and save_tree().

◆ save_string_as_bytes()

static void Aleph::Huffman_Encoder_Engine::save_string_as_bytes	(	const std::string &	str,
		std::ostream &	output
	)

inlinestaticprivate

Definition at line 421 of file Huffman.H.

References output.

Referenced by save_leaf_keys_in_prefix(), and save_tree().

◆ save_tree()

void Aleph::Huffman_Encoder_Engine::save_tree ( std::ostream & output ) const

inline

Save a Huffman tree into a stream.

The serialization format is:

a prefix bit sequence describing the tree topology
the end-of-stream symbol (length + bytes)
the leaf keys in preorder (length + bytes)

Parameters

[out] output An output stream where the tree will be written.

Exceptions

std::domain_error if the tree has not been generated.

See also: load_tree()

Definition at line 232 of file Huffman.H.

References ah_domain_error_if, end_symbol_, output, Aleph::prefix(), root_, save_leaf_keys_in_prefix(), save_string_as_bytes(), and Aleph::tree_to_bits().

◆ save_tree_in_array_of_chars()

void Aleph::Huffman_Encoder_Engine::save_tree_in_array_of_chars	(	const std::string &	array_name,
		std::ostream &	output
	)		const

inline

Generate C/C++ array declarations for a Huffman tree.

save_tree_in_array_of_chars(array_name, output) writes two array declarations that can be used to reconstruct the binary tree:

const unsigned char array_name_cdp[n] = { ... };
const char * array_name_k[] = { ... };

The first array stores the topology as a prefix bit code (a Lukasiewicz word). The second array stores node contents in preorder. The Get_Key functor is used to stringify the node contents; internal nodes typically return an empty std::string.

Parameters

[in]	array_name	Prefix name for the generated arrays.
[out]	output	Output stream where declarations are written.

Exceptions

std::domain_error if the tree has not been generated.

See also: Aleph::load_tree_from_array()

Definition at line 264 of file Huffman.H.

References ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), output, and root_.

◆ set_end_of_stream()

void Aleph::Huffman_Encoder_Engine::set_end_of_stream ( const std::string & str )

inline

Defines the end-of-stream symbol.

Definition at line 569 of file Huffman.H.

References ah_domain_error_if, end_symbol_, insert_end_symbol_node(), root_, Aleph::DynMapTree< Key, Data, Tree, Compare >::search(), and symbol_map_.

Referenced by read_input(), and read_input().

◆ set_freq()

void Aleph::Huffman_Encoder_Engine::set_freq	(	const std::string &	str,
		const size_t &	freq
	)

inline

Define the frequency of a symbol.

set_freq(str, freq) tells the encoder that symbol str has frequency freq.

Parameters

[in]	str	Symbol.
[in]	freq	Symbol frequency.

Exceptions

std::bad_alloc if there is not enough memory.

Definition at line 397 of file Huffman.H.

References ah_domain_error, ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), heap_, Aleph::DynMapTree< Key, Data, Tree, Compare >::insert(), Aleph::GenBinHeap< NodeType, Key, Compare >::insert(), root_, Aleph::DynMapTree< Key, Data, Tree, Compare >::search(), Aleph::set_freq(), symbol_map_, and test_end().

◆ test_end()

bool Aleph::Huffman_Encoder_Engine::test_end ( const std::string & str ) const

inlineprivate

Definition at line 152 of file Huffman.H.

References end_symbol_.

Referenced by set_freq(), and update_freq().

◆ update_freq()

void Aleph::Huffman_Encoder_Engine::update_freq ( const std::string & str )

inlineprivate

Definition at line 159 of file Huffman.H.

References ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), heap_, Aleph::increase_freq(), Aleph::DynMapTree< Key, Data, Tree, Compare >::insert(), Aleph::GenBinHeap< NodeType, Key, Compare >::insert(), root_, Aleph::DynMapTree< Key, Data, Tree, Compare >::search(), symbol_map_, test_end(), and Aleph::GenBinHeap< NodeType, Key, Compare >::update().

Referenced by read_input(), and read_input().

Member Data Documentation

◆ code_map_

Code_Map Aleph::Huffman_Encoder_Engine::code_map_

private

Definition at line 119 of file Huffman.H.

Referenced by build_encoding_map(), build_prefix_encoding(), clear_build_state(), encode(), and encode().

◆ end_symbol_

std::string Aleph::Huffman_Encoder_Engine::end_symbol_

private

Definition at line 123 of file Huffman.H.

Referenced by clear_build_state(), encode(), encode(), get_end_of_stream(), load_tree(), read_input(), read_input(), save_tree(), set_end_of_stream(), and test_end().

◆ freq_root_

Freq_Node* Aleph::Huffman_Encoder_Engine::freq_root_

private

Definition at line 121 of file Huffman.H.

Referenced by generate_huffman_tree(), get_freq_root(), and load_tree().

◆ heap_

Huffman_Heap Aleph::Huffman_Encoder_Engine::heap_

private

Definition at line 117 of file Huffman.H.

Referenced by clear_build_state(), generate_huffman_tree(), insert_end_symbol_node(), set_freq(), and update_freq().

◆ Max_Token_Size

const size_t Aleph::Huffman_Encoder_Engine::Max_Token_Size = 256

staticprivate

Definition at line 419 of file Huffman.H.

Referenced by encode(), load_string_from_bytes(), and read_input().

◆ root_

BinNode<std::string>* Aleph::Huffman_Encoder_Engine::root_

private

Definition at line 116 of file Huffman.H.

Referenced by build_encoding_map(), encode(), encode(), generate_huffman_tree(), get_root(), load_tree(), read_input(), read_input(), save_tree(), save_tree_in_array_of_chars(), set_end_of_stream(), set_freq(), and update_freq().

◆ symbol_map_

Symbol_Map Aleph::Huffman_Encoder_Engine::symbol_map_

private

Definition at line 118 of file Huffman.H.

Referenced by build_encoding_map(), clear_build_state(), insert_end_symbol_node(), read_input(), read_input(), set_end_of_stream(), set_freq(), and update_freq().

◆ text_len_

size_t Aleph::Huffman_Encoder_Engine::text_len_

private

Definition at line 124 of file Huffman.H.

Referenced by clear_build_state(), read_input(), and read_input().

The documentation for this class was generated from the following file:

Huffman.H

Classes

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ Huffman_Encoder_Engine()

◆ ~Huffman_Encoder_Engine()

Member Function Documentation

◆ append_code()

◆ build_encoding_map()

◆ build_prefix_encoding()

◆ clear_build_state()

◆ encode() [1/2]

◆ encode() [2/2]

◆ generate_huffman_tree()

◆ get_end_of_stream()

◆ get_freq_root()

◆ get_root()

◆ insert_end_symbol_node()

◆ load_leaf_keys_in_prefix()

◆ load_string_from_bytes()

◆ load_tree()

◆ read_input() [1/2]

◆ read_input() [2/2]

◆ save_leaf_keys_in_prefix()

◆ save_string_as_bytes()

◆ save_tree()

◆ save_tree_in_array_of_chars()

◆ set_end_of_stream()

◆ set_freq()

◆ test_end()

◆ update_freq()

Member Data Documentation

◆ code_map_

◆ end_symbol_

◆ freq_root_

◆ heap_

◆ Max_Token_Size

◆ root_

◆ symbol_map_

◆ text_len_