A C++20 implementation of Huffman coding for lossless data compression, originally developed for a university Data Structures assignment and later refactored into a standalone project, featuring character frequency analysis, Huffman tree construction using a min-priority queue, prefix code generation, text encoding, input validation, and support for spaces, newlines, tabs, and single-character input.
This project was originally developed as part of the Data Structures university course as an assignment focused on implementing the Huffman coding algorithm for lossless data compression.
The project implements a Huffman coding system that analyzes the frequency of characters in an input text, constructs an optimal binary Huffman tree using a min-priority queue, generates a prefix code for each character, and encodes the original text using the generated codes.
The project was developed to practice and demonstrate fundamental Data Structures and Algorithms concepts in C++, including binary trees, priority queues, frequency analysis, prefix codes, recursive tree traversal, dynamic memory management, and greedy algorithm construction.
The program reads text from the external input.txt file, analyzes the character frequencies, constructs the corresponding Huffman tree, generates the binary code associated with each character, and encodes the complete input text.
The main functionality includes:
- reading text from an external input file
- handling multi-line input files
- analyzing the frequency of each character
- storing character frequencies using
std::unordered_map - creating a leaf node for each distinct character
- representing the Huffman tree using dynamically allocated binary tree nodes
- using
std::priority_queuewith a custom comparator as a min-priority queue - selecting the two nodes with the lowest frequencies
- combining nodes into a new parent node
- constructing the complete Huffman tree
- assigning
0to left branches and1to right branches - recursively generating the Huffman code for each character
- storing generated codes in a lookup table
- displaying the Huffman code associated with each character
- explicitly displaying spaces, newlines, and tabs
- encoding the original text using the generated Huffman codes
- handling empty input files
- handling input containing only a single distinct character
- releasing the dynamically allocated Huffman tree from memory
The Huffman algorithm constructs a binary tree in which each leaf represents a distinct character from the input text. The two nodes with the lowest frequencies are repeatedly removed from the min-priority queue and combined into a new parent node whose frequency is equal to the sum of the two child frequencies.
The construction process continues until only one node remains in the priority queue. This node becomes the root of the Huffman tree.
The generated codes are prefix-free, meaning that no character code is a prefix of another character code. This allows the encoded text to be represented without ambiguity and provides the foundation for lossless decoding.
The code associated with a character is obtained by traversing the Huffman tree from the root to the corresponding leaf. Moving to the left child adds 0 to the code, while moving to the right child adds 1.
Characters with higher frequencies generally receive shorter codes, while less frequent characters receive longer codes. This reduces the total number of bits required to represent the input text compared with a fixed-length encoding.
The implementation uses a custom comparator for std::priority_queue to transform it into a min-priority queue, ensuring that the node with the lowest frequency is always available at the top of the queue.
Each Huffman tree node stores:
- the character represented by the node
- the frequency of that character or subtree
- a pointer to the left child
- a pointer to the right child
Internal nodes do not represent an actual input character and use '\0' as their character value.
The generated Huffman codes are stored in an std::unordered_map<char, std::string>, which acts as a lookup table during the encoding stage. Each character from the original text is replaced with its corresponding binary Huffman code to produce the final encoded text.
The implementation also handles several edge cases. Empty input files are detected before the tree construction process begins, while input containing only one distinct character is assigned the code 0. The program also supports spaces, tabs, newline characters, punctuation, and both uppercase and lowercase characters.
The original assignment implementation was later refactored and modernized for GitHub, including English naming conventions, clearer function responsibilities, improved input handling, support for multi-line text, explicit character labels for whitespace characters, handling of single-character input, and cleaner separation between Huffman tree construction, code generation, code display, and text encoding.
The final result is a standalone C++20 console application that demonstrates how the Huffman coding algorithm can be implemented using fundamental data structures such as binary trees, priority queues, hash maps, recursion, and dynamic memory management to perform lossless text encoding.
The project was originally developed as part of the university Data Structures course as an assignment focused on implementing the Huffman coding algorithm for lossless data compression.
The original assignment requires reading a text from a file, constructing the corresponding Huffman coding tree, displaying the code associated with each character, and encoding the input text.
The assignment explicitly requires the use of a minimum priority queue (std::priority_queue with minimum priority) for constructing the Huffman tree.
The original requirement can be summarized as follows:
Read a text from a file. Construct the corresponding Huffman coding tree. Display the code corresponding to each character and encode the text using the generated Huffman codes. Use
std::priority_queueas a min-priority queue.
Huffman coding is a lossless data compression algorithm that assigns variable-length binary codes to characters based on their frequencies of occurrence.
The main idea is that characters that occur more frequently should receive shorter codes, while characters that occur less frequently can receive longer codes.
The algorithm operates on a set of characters and their frequencies. For an ASCII text, a frequency table can be used to determine how often each character occurs in the input.
For example, if a character occurs very frequently, its Huffman code may contain only a few bits, while a character with a low frequency may receive a longer code.
This allows the total representation of the text to use fewer bits than a fixed-length encoding in many cases.
Huffman coding uses prefix codes.
A prefix code is a code in which no complete code assigned to one character is a prefix of the code assigned to another character.
This property allows the encoded text to be decoded unambiguously.
For example, consider the following codes:
a -> 0
b -> 101
c -> 100
d -> 111
e -> 1101
f -> 1100
None of these codes is a prefix of another code, so a sequence of encoded bits can be uniquely separated into individual character codes.
A Huffman prefix code can be constructed using a binary Huffman tree.
In the Huffman tree:
- each leaf represents one character
- each node stores a frequency
- the left branch is assigned the value
0 - the right branch is assigned the value
1 - the code of a character is obtained by following the path from the root to its corresponding leaf
For example, if the path from the root to a character is:
left -> right -> left -> right
then the corresponding Huffman code is:
0101
An optimal Huffman code is represented by a binary tree in which every internal node has exactly two children.
The assignment describes the following procedure for constructing the Huffman tree.
First, each distinct character is placed in a leaf node together with its frequency.
All nodes are then inserted into a minimum priority queue.
The node with the smallest frequency is kept at the top of the queue.
The algorithm repeatedly performs the following steps while at least two nodes remain in the queue:
- Extract the two nodes with the smallest frequencies.
- Create a new parent node.
- Set the two extracted nodes as the left and right children of the new node.
- Set the frequency of the new node to the sum of the frequencies of its children.
- Insert the new node back into the priority queue.
The process continues until only one node remains.
That final node becomes the root of the Huffman tree.
Conceptually:
parent
/ \
node1 node2
frequency(parent) =
frequency(node1) + frequency(node2)
This is the core greedy step of the Huffman algorithm.
After the Huffman tree has been constructed, the code for every character can be generated by traversing the tree from the root.
Moving to the left child appends:
0
Moving to the right child appends:
1
When a leaf is reached, the accumulated sequence of 0 and 1 values represents the Huffman code of that character.
For example:
root
/ \
0 1
/ \ / \
a b c d
would produce:
a -> 00
b -> 01
c -> 10
d -> 11
The codes can then be stored in a look-up table, associating each character with its generated binary code.
Once the look-up table has been generated, the original text can be encoded by replacing every character with its corresponding Huffman code.
For example, if:
a -> 0
b -> 101
c -> 100
then the text:
aabca
is encoded as:
0 0 101 100 0
or, without separators:
001011000
The program therefore needs to:
- generate the Huffman code for every character
- display the generated codes
- replace every character in the original text with its corresponding code
- display the resulting encoded text
The assignment provides an example using the first six letters of the alphabet:
{a, b, c, d, e, f}
with the following frequencies:
a b c d e f
45 13 12 16 9 5
A fixed-length representation would require 3 bits per character because six different symbols need to be represented.
The assignment then presents a variable-length Huffman code:
a -> 0
b -> 101
c -> 100
d -> 111
e -> 1101
f -> 1100
The more frequent character a receives the shortest code, while less frequent characters receive longer codes.
For example, the encoded sequence:
00101100110110100
can be separated using the Huffman codes to obtain:
0 | 0 | 101 | 100 | 1101 | 101 | 0 | 0
which corresponds to:
aabcebaa
This example illustrates how the prefix-free property allows the encoded sequence to be interpreted without ambiguity.
The assignment also demonstrates Huffman coding using a sample text:
Huffman coding is a lossless data compression algorithm.
It assigns shorter codes to more frequent characters.
The character frequencies are analyzed first, and a Huffman tree is constructed based on these frequencies.
After the tree is built, each character receives a binary Huffman code according to its path from the root to the corresponding leaf.
More frequent characters generally receive shorter codes, while less frequent characters receive longer codes.
The generated codes are then used to encode the complete input text.
The assignment specifies that each Huffman tree node can contain:
- a frequency field
- a character field
- a link to the left child
- a link to the right child
- optionally, a link to the parent
A parent link is not necessary when the tree is traversed recursively to generate the character codes.
The implementation follows this approach and uses recursive traversal instead of storing parent pointers.
After the Huffman tree has been constructed, the generated codes can be stored in a look-up table.
The table associates each character with its corresponding Huffman code:
character -> Huffman code
This table is then used during the encoding phase to efficiently replace each character from the original text with its binary code.
In the implementation, this concept is represented using:
std::unordered_map<char, std::string>The assignment also explains that decoding requires the decoder to use the same Huffman tree as the encoder.
This can be achieved by:
- using the same set of characters with the same frequencies
- transmitting the Huffman tree together with the encoded text
- using another agreed method for reconstructing the same tree
The current project focuses on the tree construction, code generation, and encoding stages required by the original assignment.
The assignment specifically requires the use of a minimum priority queue for constructing the Huffman tree.
The implementation therefore uses:
std::priority_queue<Node*, std::vector<Node*>, CompareNode>together with a custom comparator that makes the node with the lowest frequency appear at the top of the queue.
The Huffman tree itself is represented using dynamically allocated binary tree nodes.
The implementation also uses:
std::unordered_map<char, int>for character frequency counting and:
std::unordered_map<char, std::string>for storing the generated Huffman codes.
The original assignment therefore focuses on the following concepts:
- Huffman coding
- lossless data compression
- character frequency analysis
- prefix codes
- binary tree construction
- minimum priority queues
- greedy algorithm construction
- recursive tree traversal
- look-up tables
- text encoding
- dynamic memory management
The final implementation fulfills the original requirement by reading a text file, constructing the corresponding Huffman tree, displaying the generated code for each character, and encoding the complete input text using the resulting Huffman codes.
-
🌳 Huffman Tree Construction
- Builds a binary Huffman tree based on character frequencies
- Creates a leaf node for each distinct character
- Stores the character and its frequency in each leaf node
- Creates internal nodes by combining the two lowest-frequency nodes
- Uses
'\0'for internal nodes that do not represent an actual character - Produces a single root node representing the complete Huffman tree
-
📊 Character Frequency Analysis
- Reads the input text from
input.txt - Counts the frequency of every character in the input
- Uses
std::unordered_map<char, int>for frequency storage - Supports letters, spaces, punctuation, tabs, and newline characters
- Treats uppercase and lowercase characters as distinct symbols
- Reads the input text from
-
⬇️ Min-Priority Queue
- Uses
std::priority_queueto manage Huffman tree nodes - Implements a custom comparator to create a min-priority queue
- Keeps the node with the lowest frequency at the top of the queue
- Extracts the two lowest-frequency nodes during tree construction
- Reinserts each newly created parent node into the priority queue
- Uses
-
🔗 Huffman Tree Merging
- Extracts the two nodes with the smallest frequencies
- Creates a new parent node containing their combined frequency
- Assigns the extracted nodes as the left and right children
- Repeats the process until only one node remains
- Uses the final remaining node as the root of the Huffman tree
-
🔢 Prefix Code Generation
- Generates a binary code for every character in the Huffman tree
- Assigns
0to left branches - Assigns
1to right branches - Uses recursive tree traversal to generate character codes
- Produces prefix-free Huffman codes
- Assigns shorter codes to more frequent characters
-
📋 Code Look-Up Table
- Stores generated Huffman codes in an
std::unordered_map - Associates each character with its corresponding binary code
- Provides efficient access to character codes during encoding
- Separates code generation from the text encoding process
- Stores generated Huffman codes in an
-
🔐 Text Encoding
- Encodes the complete input text using the generated Huffman codes
- Replaces every character with its corresponding binary code
- Produces a single encoded binary sequence
- Preserves the order of all characters from the original text
-
📄 Input File Handling
- Reads text from the external
input.txtfile - Supports multi-line input
- Reads the complete contents of the file
- Processes spaces, tabs, newline characters, and punctuation
- Uses standard C++ file stream functionality
- Reads text from the external
-
🏷️ Character Display
- Displays the Huffman code associated with every character
- Displays whitespace characters using readable labels
- Represents spaces as
[space] - Represents newlines as
[newline] - Represents tabs as
[tab] - Keeps punctuation and regular characters directly visible
-
🛡️ Input Validation
- Detects when the input file cannot be opened
- Detects empty input files
- Prevents Huffman tree construction when no input data exists
- Handles input containing only a single distinct character
-
🔤 Single-Character Input
- Handles input containing only one distinct character
- Assigns the code
0to the only character - Correctly encodes repeated occurrences of that character
- Prevents the generation of an empty Huffman code
-
🧹 Dynamic Memory Management
- Allocates Huffman tree nodes dynamically
- Connects nodes using left and right child pointers
- Uses a recursive destructor to release the complete tree
- Prevents memory leaks after the encoding process is complete
-
🧪 Test Cases
- Tested with the original assignment example
- Tested with text containing characters with different frequencies
- Tested with input containing a single distinct character
- Tested with multi-line text
- Tested with spaces and newline characters
- Tested with punctuation and uppercase characters
- Tested with an empty input file
- Verified successful Huffman tree construction and text encoding
The application follows a simple functional architecture centered around the Huffman coding algorithm and the data structures required to analyze character frequencies, construct the Huffman tree, generate prefix codes, and encode the input text.
The program is implemented using main.cpp and the Node class defined in Node.h and Node.cpp, together with the external input.txt file containing the text to be encoded.
The implementation separates the different responsibilities into dedicated functions, making each stage of the Huffman coding process independently identifiable and easier to understand.
main.cpp
│
▼
createHuffmanTree()
│
┌────────────┴────────────┐
│ │
▼ ▼
Read input.txt Count frequencies
│ │
└────────────┬────────────┘
│
▼
Min-Priority Queue
│
▼
buildHuffmanTree()
│
┌────────────┴────────────┐
│ │
▼ ▼
Extract minimum Combine nodes
│ │
└────────────┬────────────┘
│
▼
Huffman Tree
│
▼
generateCodes()
│
▼
Code Look-Up Table
│
┌────────────┴────────────┐
│ │
▼ ▼
displayCodes() encodeText()
│
▼
Encoded Text
-
Node- Represents a node in the Huffman binary tree.
- Stores a character and its frequency.
- Stores pointers to the left and right children.
- Represents both leaf nodes and internal tree nodes.
- Uses
'\0'for internal nodes that do not represent an input character. - Recursively releases its children through the destructor.
-
CompareNode- Defines the ordering used by the Huffman priority queue.
- Compares nodes according to their frequencies.
- Makes the node with the lowest frequency appear first.
- Uses the character as a secondary comparison criterion when frequencies are equal.
- Allows
std::priority_queueto operate as a min-priority queue.
-
createHuffmanTree()- Reads the complete input from
input.txt. - Supports multi-line text.
- Counts the frequency of every character.
- Stores character frequencies using
std::unordered_map<char, int>. - Creates a leaf node for every distinct character.
- Inserts all created nodes into the min-priority queue.
- Detects errors when the input file cannot be opened.
- Reads the complete input from
-
buildHuffmanTree()- Constructs the Huffman tree from the min-priority queue.
- Extracts the two nodes with the lowest frequencies.
- Creates a new parent node containing their combined frequency.
- Assigns the extracted nodes as the left and right children.
- Inserts the new parent node back into the priority queue.
- Continues until only the root node remains.
-
generateCodes()- Traverses the Huffman tree recursively.
- Adds
0when moving to a left child. - Adds
1when moving to a right child. - Stores the generated code when a leaf node is reached.
- Handles the special case where the input contains only one distinct character.
-
getCharacterLabel()- Converts special characters into readable labels for console output.
- Displays spaces as
[space]. - Displays newline characters as
[newline]. - Displays tabs as
[tab]. - Keeps regular characters and punctuation unchanged.
-
displayCodes()- Displays the Huffman code associated with every character.
- Uses the generated look-up table.
- Makes whitespace characters explicitly visible through
getCharacterLabel().
-
encodeText()- Encodes the complete input text.
- Looks up the Huffman code associated with every character.
- Concatenates the individual codes into the final encoded sequence.
- Uses the generated
std::unordered_map<char, std::string>as a look-up table.
-
main()- Acts as the application entry point.
- Initializes the min-priority queue.
- Initializes the Huffman code look-up table.
- Loads the input text and creates the initial queue.
- Validates that the input file was successfully processed.
- Handles empty input files.
- Builds the Huffman tree.
- Generates the character codes.
- Displays the generated codes.
- Encodes the original text.
- Releases the dynamically allocated Huffman tree.
The implementation uses several STL and custom data structures to support Huffman coding:
-
Node- Represents a node in the binary Huffman tree.
- Contains the character, frequency, and child pointers.
-
std::priority_queue<Node*, std::vector<Node*>, CompareNode>- Represents the Huffman min-priority queue.
- Stores pointers to Huffman tree nodes.
- Ensures that the lowest-frequency node is selected first.
-
std::unordered_map<char, int>- Stores the frequency of each character found in the input text.
-
std::unordered_map<char, std::string>- Stores the generated Huffman code for every character.
- Acts as the look-up table used during encoding.
-
std::string- Stores the input text.
- Stores generated Huffman codes.
- Stores the final encoded text.
Each distinct character is initially represented by a leaf node:
Character + Frequency
The nodes are inserted into the min-priority queue.
The two nodes with the lowest frequencies are then combined:
parent
/ \
node1 node2
frequency(parent) =
frequency(node1) + frequency(node2)
This process continues until only one node remains.
The remaining node becomes the root of the Huffman tree.
The resulting tree represents the complete prefix-code structure used by the encoder.
The Huffman codes are generated by recursively traversing the tree.
The traversal follows these rules:
left child -> append 0
right child -> append 1
For example:
root
/ \
0 1
/ \ / \
a b c d
produces:
a -> 00
b -> 01
c -> 10
d -> 11
The generated code is stored when the traversal reaches a leaf.
The frequency analysis stage processes every character from the input text.
For example, for:
aaabbc
the frequency table becomes:
a -> 3
b -> 2
c -> 1
These frequencies determine the initial priority of the leaf nodes in the min-priority queue.
Characters with higher frequencies generally receive shorter Huffman codes after the tree has been constructed.
The Huffman tree construction depends on repeatedly selecting the two nodes with the lowest frequencies.
The implementation uses:
std::priority_queue<Node*, std::vector<Node*>, CompareNode>with the custom CompareNode comparator.
The comparator reverses the normal std::priority_queue ordering:
return a->getFrequency() > b->getFrequency();This makes the lowest-frequency node appear at the top.
The queue therefore behaves as:
minHeap.top()
│
▼
lowest frequency
After two nodes are extracted, they are combined and the resulting parent node is inserted back into the queue.
The complete construction process can be represented as:
Input text
│
▼
Character frequencies
│
▼
Create leaf nodes
│
▼
Insert nodes into min-priority queue
│
▼
Extract two minimum nodes
│
▼
Create parent node
│
▼
Insert parent back into queue
│
├── More than one node ──► Repeat
│
▼
Single remaining node
│
▼
Huffman tree root
After the tree has been constructed, the generated codes are stored in:
std::unordered_map<char, std::string>The structure can be conceptually represented as:
character -> Huffman code
a -> 1011
b -> 01
c -> 0000
...
This allows the encoding stage to efficiently retrieve the code associated with each character.
The encoding process uses the generated look-up table.
For every character in the input text:
character
│
▼
Look up Huffman code
│
▼
Append code to encoded text
For example:
Input:
abc
Codes:
a -> 10
b -> 0
c -> 11
Encoded:
10011
The process continues until every character from the input has been encoded.
The application handles several invalid input cases before or during the Huffman construction process.
These include:
- input file cannot be opened
- input file is empty
- input contains only one distinct character
When the input file is empty, the application displays:
Error: The input file is empty.
If the input file cannot be opened, the application displays:
Error: Could not open the input file.
The implementation supports characters that are not directly visible in console output.
These characters are represented using explicit labels:
space -> [space]
newline -> [newline]
tab -> [tab]
This makes it possible to clearly identify their generated Huffman codes.
The implementation also treats uppercase and lowercase characters as separate symbols.
For example:
H != h
The Huffman tree uses dynamically allocated Node objects.
Each node stores pointers to its left and right children.
The Node destructor recursively deletes both children:
delete root
│
├── delete left subtree
│ ├── delete children
│ └── ...
│
└── delete right subtree
├── delete children
└── ...
Deleting the root therefore releases the complete Huffman tree from memory.
The complete execution flow is:
main()
│
▼
Read input.txt
│
▼
Count character frequencies
│
├── File error ───────► Display error and exit
│
├── Empty input ──────► Display error and exit
│
▼
Create leaf nodes
│
▼
Insert nodes into min-priority queue
│
▼
Build Huffman tree
│
▼
Generate Huffman codes
│
▼
Display character codes
│
▼
Encode input text
│
▼
Display encoded text
│
▼
Delete Huffman tree
│
▼
End program
The architecture keeps the project compact, modular, and focused on the Huffman coding algorithm.
The implementation directly reflects the requirements of the original university assignment while providing clear separation between:
- character frequency analysis
- Huffman tree construction
- min-priority queue management
- recursive code generation
- code look-up
- text encoding
- input validation
- memory management
The result is a standalone C++20 console application that demonstrates how Huffman coding can be implemented using fundamental data structures such as binary trees, priority queues, hash maps, recursion, and dynamic memory management to perform lossless text encoding.
HuffmanCoding/
├── .gitignore
├── HuffmanCoding.slnx
│
└── HuffmanCoding/
├── HuffmanCoding.vcxproj
├── HuffmanCoding.vcxproj.filters
├── main.cpp
├── Node.cpp
├── Node.h
└── input.txt
-
main.cpp- Contains the complete Huffman coding implementation.
- Reads and analyzes the input text.
- Calculates character frequencies.
- Builds the Huffman tree using a min-priority queue.
- Generates the Huffman code for each character.
- Displays the generated character codes.
- Encodes the input text using the generated codes.
- Handles empty input files and single-character input.
-
Node.h- Defines the
Nodeclass used by the Huffman tree. - Stores the character and its frequency.
- Provides pointers to the left and right child nodes.
- Declares constructors, getters, and the destructor.
- Defines the
-
Node.cpp- Contains the implementation of the
Nodeclass. - Initializes node data and child pointers.
- Implements character and frequency getters.
- Implements the recursive destructor used to release the Huffman tree.
- Contains the implementation of the
-
input.txt- Contains the text used as input for the Huffman coding algorithm.
- The program reads the complete contents of this file and analyzes the frequency of each character.
-
HuffmanCoding.slnx- Visual Studio solution file.
-
HuffmanCoding.vcxproj- Visual Studio C++ project configuration.
-
HuffmanCoding.vcxproj.filters- Defines how project files are organized inside Visual Studio.
Visual Studio generates additional files and directories when the project is compiled, such as:
x64/
└── Debug/
├── HuffmanCoding.exe
├── HuffmanCoding.pdb
└── other intermediate build files
These files are build artifacts and are not part of the source code.
Build artifacts, Visual Studio intermediate files, executables, debug databases, logs, and other temporary files are excluded from version control through
.gitignore.
- C++20 (ISO C++20)
- Visual Studio 2026
- Microsoft C++ Build Tools v145
- 64-bit build
- Binary Huffman Tree for representing the Huffman coding structure
std::priority_queuefor the Huffman min-priority queuestd::unordered_mapfor character frequency counting and Huffman code look-upstd::stringfor input text, generated codes, and encoded outputstd::ifstreamfor reading the input text frominput.txt- Standard Streams for console input and output
- Recursive tree traversal for Huffman code generation
- Dynamic memory management for Huffman tree nodes
-
🌳 Huffman Tree Construction
- Builds a binary Huffman tree based on character frequencies
- Creates a leaf node for every distinct character
- Combines the two lowest-frequency nodes at each step
- Uses the combined frequency for every newly created parent node
- Continues until a single root node remains
-
📊 Character Frequency Analysis
- Reads the complete input text from
input.txt - Calculates the frequency of every character
- Uses
std::unordered_map<char, int>for frequency storage - Supports letters, spaces, punctuation, tabs, and newline characters
- Treats uppercase and lowercase characters as distinct symbols
- Reads the complete input text from
-
⬇️ Min-Priority Queue
- Uses
std::priority_queueto manage Huffman tree nodes - Implements a custom comparator to create a min-priority queue
- Keeps the lowest-frequency node at the top
- Extracts the two minimum-frequency nodes during tree construction
- Reinserts newly created parent nodes into the queue
- Uses
-
🔢 Prefix Code Generation
- Generates a binary Huffman code for every character
- Assigns
0to left branches - Assigns
1to right branches - Uses recursive tree traversal to generate codes
- Produces prefix-free character codes
- Generally assigns shorter codes to more frequent characters
-
📋 Code Look-Up Table
- Stores generated Huffman codes using
std::unordered_map<char, std::string> - Associates every character with its corresponding binary code
- Provides efficient code lookup during the encoding stage
- Separates code generation from text encoding
- Stores generated Huffman codes using
-
🔐 Lossless Text Encoding
- Encodes the complete input text using the generated Huffman codes
- Replaces every character with its corresponding binary code
- Preserves the order and content of the original text
- Produces the final encoded binary sequence
-
🔤 Special Character Support
- Supports spaces, newlines, tabs, punctuation, and regular characters
- Displays spaces as
[space] - Displays newlines as
[newline] - Displays tabs as
[tab] - Keeps uppercase and lowercase characters as separate symbols
-
🔢 Single-Character Input
- Handles input containing only one distinct character
- Assigns the code
0to the only character - Correctly encodes repeated occurrences of that character
- Prevents an empty Huffman code from being generated
-
📄 Input File Handling
- Loads text from the external
input.txtfile - Reads the complete contents of the file
- Supports multi-line input
- Processes whitespace and special characters correctly
- Loads text from the external
-
🛡️ Input Validation
- Detects when
input.txtcannot be opened - Detects empty input files
- Prevents Huffman tree construction when no input data exists
- Handles single-character input separately
- Detects when
-
🧹 Dynamic Memory Management
- Uses dynamically allocated nodes for the Huffman tree
- Connects nodes through left and right child pointers
- Uses a recursive destructor to release the complete tree
- Ensures that the Huffman tree is properly deleted after encoding
-
🧪 Test Cases
- Tested with the original assignment example
- Tested with English text containing different character frequencies
- Tested with input containing a single distinct character
- Tested with multi-line input
- Tested with spaces and newline characters
- Tested with punctuation and uppercase characters
- Tested with an empty input file
- Verified successful Huffman tree construction and text encoding
-
📦 STL Data Structures
std::unordered_mapfor character frequenciesstd::unordered_mapfor Huffman code lookupstd::priority_queuefor the Huffman min-priority queuestd::vectorfor the internal storage of the priority queuestd::stringfor input text, Huffman codes, and encoded output
-
🏗️ Refactored Implementation
- English naming throughout the code
- Consistent
camelCasenaming convention - Dedicated functions for tree construction, code generation, code display, and text encoding
- Improved input file handling
- Added support for complete multi-line input
- Added explicit labels for whitespace characters
- Added single-character input handling
- Modernized C++20 implementation
- Prepared as a standalone GitHub project
-
Huffman Coding
- Lossless data compression using variable-length binary codes
- Assigns shorter codes to more frequent characters
- Assigns longer codes to less frequent characters
- Encodes the complete input text using the generated Huffman codes
-
Huffman Tree
- Binary tree representation of the Huffman coding structure
- Leaf nodes represent individual characters
- Internal nodes store the combined frequency of their children
- Left branches represent
0 - Right branches represent
1 - The root represents the complete Huffman tree
-
Greedy Algorithm
- Repeatedly selects the two nodes with the lowest frequencies
- Combines them into a new parent node
- Reinserts the combined node into the priority queue
- Continues until a single root node remains
- Builds an optimal prefix-code tree based on character frequencies
-
Prefix Codes
- Generates prefix-free binary codes
- Ensures that no character code is a prefix of another character code
- Allows the encoded sequence to be represented without ambiguity
- Generates each code from the path between the root and a character leaf
-
Character Frequency Analysis
- Counts the occurrences of every character in the input text
- Uses character frequencies to determine node priorities
- Supports letters, spaces, punctuation, tabs, and newline characters
- Treats uppercase and lowercase characters as distinct symbols
-
Min-Priority Queue
- Uses
std::priority_queueto manage Huffman tree nodes - Uses a custom comparator to create a min-priority queue
- Keeps the node with the lowest frequency at the top
- Supports efficient selection of the two lowest-frequency nodes
- Uses
-
Recursive Tree Traversal
- Traverses the Huffman tree recursively
- Appends
0when moving to the left child - Appends
1when moving to the right child - Stores the accumulated code when a leaf is reached
- Generates codes for all distinct characters
-
Code Look-Up Table
- Stores generated Huffman codes using
std::unordered_map - Associates each character with its corresponding binary code
- Provides efficient access to codes during text encoding
- Separates code generation from the encoding process
- Stores generated Huffman codes using
-
Text Encoding
- Replaces each input character with its Huffman code
- Concatenates individual codes into a single encoded sequence
- Preserves the order of the original text
- Produces the final variable-length binary representation
-
Binary Tree Representation
- Uses dynamically allocated
Nodeobjects - Stores character and frequency information
- Maintains left and right child pointers
- Represents both leaf and internal nodes
- Uses
'\0'for internal nodes without an associated character
- Uses dynamically allocated
-
Dynamic Memory Management
- Allocates Huffman tree nodes dynamically
- Connects nodes through left and right child pointers
- Uses a recursive destructor to delete the complete tree
- Releases the entire Huffman tree when the root node is deleted
-
Input Handling
- Reads the complete input from
input.txt - Supports multi-line text
- Processes whitespace and special characters
- Detects missing input files
- Detects empty input files
- Reads the complete input from
-
Special Character Handling
- Supports spaces, tabs, and newline characters
- Displays spaces as
[space] - Displays tabs as
[tab] - Displays newlines as
[newline] - Allows invisible characters to be identified clearly in the generated code table
-
Edge Case Handling
- Handles empty input files
- Handles input containing only one distinct character
- Assigns the code
0when only one character exists - Prevents an empty Huffman code for single-character input
-
STL Data Structures
std::unordered_mapfor character frequenciesstd::unordered_mapfor Huffman code lookupstd::priority_queuefor the min-priority queuestd::vectorfor the internal priority queue storagestd::stringfor input text, generated codes, and encoded output
-
Algorithmic Complexity
- Frequency analysis processes the input text in linear time
- Huffman tree construction uses a priority queue based on a binary heap
- Each tree construction step extracts and reinserts nodes through the priority queue
- Code generation visits the nodes of the Huffman tree
- Encoding processes each character using constant-time average hash-table lookup
-
Modern C++ Practices
- C++20 language standard
- Range-based
forloops constreferences to avoid unnecessary copiesautoandconst auto&where appropriatestd::stringfor dynamic text and code storage- STL containers and algorithms
- Dedicated functions for individual responsibilities
- Consistent English naming
- Consistent
camelCasefunction naming constmember functions for read-only getters- Explicit handling of dynamically allocated resources
The Huffman Coding application was manually tested through the console using multiple input texts and edge cases.
The tests covered the main functionality of the project, including:
- Character frequency analysis
- Huffman tree construction
- Min-priority queue behavior
- Huffman code generation
- Prefix-code generation
- Text encoding
- Space and newline handling
- Uppercase and lowercase characters
- Punctuation handling
- Single-character input
- Empty input handling
| Test | Scenario | Result |
|---|---|---|
| Test 1 | English text with multiple character frequencies | ✅ Passed |
| Test 2 | Input containing three distinct characters | ✅ Passed |
| Test 3 | Input containing only one distinct character | ✅ Passed |
| Test 4 | Multi-line input with spaces and special characters | ✅ Passed |
| Test 5 | English text with uppercase characters and punctuation | ✅ Passed |
| Test 6 | Empty input file | ✅ Passed |
Input:
Huffman coding is a lossless data compression algorithm.
It assigns shorter codes to more frequent characters.
The application successfully:
- calculated the frequency of every character
- constructed the Huffman tree
- generated a code for every distinct character
- handled spaces and newline characters
- handled uppercase characters
- handled punctuation
- encoded the complete input text
Example generated codes included:
Code for character c: 0000
Code for character i: 0001
Code for character f: 00111
Code for character .: 010111
Code for character n: 0010
Code for character l: 01010
Code for character d: 00110
Code for character g: 01000
Code for character h: 01001
Code for character I: 0101100
Code for character p: 0101101
Code for character s: 011
Code for character [space]: 100
Code for character t: 1010
Code for character a: 1011
Code for character e: 1100
Code for character r: 1101
Code for character m: 11100
Code for character u: 111010
Code for character q: 1110110
Code for character [newline]: 11101110
Code for character H: 11101111
Code for character o: 1111
The resulting encoded text was:
1110111111101000111001111110010110010100000011110011000010010010001000001011100101110001010111101101101010110001101110000110101110101011100000011111110001011011101110001101100011111001010010110101001000111111010001101001001111000101111110111001011001010100101101101100010100000100111000110100111111101101011001101100000011110011011000111001010111110011100111111011100100001111101110011101101110101100001010101000000010011011110110110000101011001101011010111
This test verifies the complete Huffman workflow, including frequency analysis, tree construction, code generation, special-character handling, and text encoding.
Input:
aaaaabbbbcc
The generated Huffman codes were:
Code for character c: 00
Code for character b: 01
Code for character a: 1
The resulting encoded text was:
111110101010000
This test verifies that the algorithm correctly assigns a shorter code to the most frequent character and longer codes to less frequent characters.
Input:
aaaaaaaaaa
The application generated:
Code for character a: 0
The resulting encoded text was:
0000000000
This verifies the special case where the input contains only one distinct character.
Instead of generating an empty code, the implementation assigns the character the code:
0
The application was also tested with multi-line input containing spaces and additional characters.
The generated output included explicit labels for characters that are normally invisible:
Code for character [newline]: 10010
Code for character [space]: 1100
The test successfully verified that newline characters are read from the input file instead of being discarded.
The application also generated valid Huffman codes for all characters present in the input and successfully encoded the complete multi-line text.
The English test input also contained uppercase characters and punctuation.
The generated codes included:
Code for character I: 0101100
Code for character H: 11101111
Code for character .: 010111
This verifies that:
- uppercase and lowercase characters are treated as different symbols
- punctuation is included in the frequency analysis
- punctuation receives a valid Huffman code
- all characters from the input text are encoded
For example:
H != h
and both characters can have different frequencies and Huffman codes.
The input file was cleared completely and the application was executed.
Output:
Error: The input file is empty.
This verifies that the application detects an empty input file before attempting to construct the Huffman tree.
No encoding is performed when there is no input data.
| Test | Scenario | Expected Result | Result |
|---|---|---|---|
| Test 1 | English text with multiple character frequencies | Huffman codes generated and text encoded | ✅ Passed |
| Test 2 | Multiple characters with different frequencies | Variable-length Huffman codes generated | ✅ Passed |
| Test 3 | Single-character input | Character receives code 0 |
✅ Passed |
| Test 4 | Multi-line text | Spaces and newlines handled correctly | ✅ Passed |
| Test 5 | Uppercase characters and punctuation | All characters encoded correctly | ✅ Passed |
| Test 6 | Empty input file | Display Error: The input file is empty. |
✅ Passed |
Result: All tested scenarios passed successfully. The tests verify the core functionality of the Huffman Coding application, including character frequency analysis, Huffman tree construction, min-priority queue usage, prefix-code generation, text encoding, special-character handling, single-character input, and empty-file validation.
- Windows 10 / Windows 11
- Visual Studio 2026
- Microsoft C++ Build Tools v145
- C++20 (ISO C++20)
- 64-bit build environment
Developed and tested using Visual Studio 2026 with the Microsoft C++ Build Tools v145 toolset, C++20 (ISO C++20), and a 64-bit build configuration.
- Clone the repository.
git clone <repository-url>-
Open
HuffmanCoding.slnxinVisual Studio 2026. -
Make sure the project is configured with:
Microsoft C++ Build Tools v145C++20 (ISO C++20)64-bit
- Build the solution.
Build → Build Solution
or simply press:
Ctrl + Shift + B
- Run the application.
F5
or click Start in Visual Studio.
The text used by the Huffman algorithm is read automatically from:
HuffmanCoding/input.txt
The application reads the complete contents of the file, including:
- regular characters
- spaces
- punctuation
- uppercase and lowercase characters
- tabs
- newline characters
For example:
Huffman coding is a lossless data compression algorithm.
It assigns shorter codes to more frequent characters.
When the application starts, it reads the input file and calculates the frequency of every distinct character.
The frequencies are used to create the initial Huffman tree leaf nodes.
Characters that occur more frequently receive a higher frequency and therefore have a higher priority during the Huffman tree construction process.
The application creates a min-priority queue containing one node for every distinct character.
The algorithm repeatedly:
- extracts the two nodes with the lowest frequencies
- creates a new parent node
- assigns the two extracted nodes as its left and right children
- sets the parent frequency to the sum of the two child frequencies
- inserts the new node back into the priority queue
This process continues until only one node remains.
The remaining node becomes the root of the Huffman tree.
The Huffman tree construction uses:
std::priority_queue<Node*, std::vector<Node*>, CompareNode>A custom comparator is used to make the priority queue behave as a min-priority queue, with the lowest-frequency node at the top.
After the tree is constructed, the application recursively traverses the tree to generate the code for every character.
The traversal rules are:
left child → 0
right child → 1
For example:
root
/ \
0 1
/ \ / \
a b c d
produces:
a → 00
b → 01
c → 10
d → 11
The generated codes are stored in a look-up table:
std::unordered_map<char, std::string>The application displays the generated Huffman code for every character found in the input.
Example:
Code for character a: 1
Code for character b: 01
Code for character c: 00
Special characters are displayed using readable labels:
Code for character [space]: ...
Code for character [newline]: ...
Code for character [tab]: ...
After generating the Huffman codes, the application encodes the complete input text.
Each character is replaced with its corresponding Huffman code and the individual codes are concatenated into one encoded sequence.
For example:
Input:
aaaaabbbbcc
Codes:
a → 1
b → 01
c → 00
Encoded text:
111110101010000
The resulting sequence is displayed in the console:
Encoded text: 111110101010000
The application also handles input containing only one distinct character.
For example:
aaaaaaaaaa
The character receives the code:
a → 0
and the encoded text becomes:
0000000000
This prevents the only character from receiving an empty Huffman code.
The application handles invalid input cases, including:
- missing
input.txt - empty input file
If the input file cannot be opened:
Error: Could not open the input file.
If the input file is empty:
Error: The input file is empty.
The program does not attempt to construct a Huffman tree when no input characters are available.
The application follows this execution flow:
Read input.txt
│
▼
Count character frequencies
│
▼
Create leaf nodes
│
▼
Insert nodes into min-priority queue
│
▼
Build Huffman tree
│
▼
Generate Huffman codes
│
▼
Display character codes
│
▼
Encode input text
│
▼
Display encoded text
│
▼
Release Huffman tree
│
▼
End program
The application requires no external libraries or runtime dependencies beyond the specified C++ development environment.
This project is released under the MIT License.
See the LICENSE file for more details.