Decompressing Messages with Multithreaded Huffman Coding in C++
The provided C++ code offers an implementation of Huffman coding for decompressing messages using a multithreaded approach. Huffman coding is employed for lossless data compression, and the program showcases the creation of a Huffman tree, thread-specific data structures, and synchronization mechanisms. The thread function is designed to decompress characters concurrently, updating the Huffman tree's decompressed message and printing symbol information with thread safety ensured through mutex usage. The global nodes vector efficiently stores Huffman nodes during the decompression process. This code can serve as a valuable reference for those seeking to understand concurrent decompression algorithms and can particularly help with C++ assignment involving multithreading and Huffman coding.
Block 1: Header includes and namespace declaration
#include < iostream >
#include < vector >
#include
#include < pthread.h >
#include < semaphore.h >
#include "huffmanTree.h"
#include < sstream >
#include < list >
using namespace std;
Discussion:
- The code includes necessary header files for input/output, working with vectors, strings, threads (pthread.h), semaphores (semaphore.h), and a custom header file (huffmanTree.h). The huffmanTree.h header likely contains the declaration for the huffmanTree class and associated structures.
Block 2: Utility function – fill
string fill(string code,int max){
int filled=max-code.size();
for (int i =0;i< filled;i++){
code='0'+code;
}
return code;
}
Discussion:
- The fill function takes a binary code and a maximum length as input and pads the code with leading zeros to make it of the specified length.
- It ensures that all binary codes have the same length for uniformity.
Block 3: Struct ThreadData
struct ThreadData {
huffmanTree* tree;
HuffmanNode* node;
string binaryCode;
vector< int >* positions;
};
Discussion:
- ThreadData is a structure used to pass data to threads.
- It includes a pointer to the huffmanTree object, a pointer to HuffmanNode, the binary code, and a vector of positions.
Block 4: Global variables and Mutex
//pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
vector< HuffmanNode * > nodes;
Discussion:
- The commented line suggests that there was an intention to use a mutex, but it is not currently being used in the code.
- nodes is a global vector to store HuffmanNode pointers.
Block 5: Thread Function - threadFunction
void* threadFunction(void* arg) {
// ...
}
Discussion:
- The function executed by each thread.
- It decompresses characters and stores them in the Huffman tree's decompressed message.
- It prints information about the symbol.
- It uses a mutex to ensure thread safety.
- It frees allocated memory for the thread data.
Block 6: main function
int main() {
// ...
}
Discussion:
- The main function is the entry point of the program.
- It reads the size of the alphabet, the alphabet itself, and the compressed file.
- It initializes data structures, creates threads, waits for threads to finish, and prints the original message.
Conclusion
In summary, the provided C++ code implements Huffman coding for compression and decompression, a widely-used technique for lossless data compression. The program starts by reading the frequency of each symbol in the alphabet and then processes the compressed file to reconstruct the Huffman tree. Multi-threading is employed to enhance efficiency in the decompression process, with each thread responsible for decoding specific portions of the input. The code showcases synchronization using a mutex, ensuring thread safety during critical sections. Finally, the original message is reconstructed and printed. The structured approach, combining utility functions, structures, and threading, reflects a comprehensive implementation of Huffman coding for efficient data compression and decompression.