A file compressor to compress and decompress files using Huffman coding algorithm.
Make sure that Rust is installed, and then clone the repo:
git clone https://github.com/emirhan8180/file-compressor.git
cd file-compressorcargo run -- compress [path-to-file]And it will output the compressed data to the same location as the file with .huf extension appended.
cargo run -- decompress [path-to-file]And it will output the decompressed data to the same location as the file with .huf extension removed (the file needs to have .huf extension).
Run the following to benchmark performance of both compression and decompression:
cargo benchThe Huffman coding algorithm is implemented as is with some modifications to improve the compression/decompression performance.
For counting each symbol's frequency, it divides the contents into chunks of 64 KB and each chunk's frequency table is processed in a separate thread. To be able to construct the tree while decoding, the tree is also compressed and added to the beginning of the output. In the compressed tree, a bit value of 0 represents an internal node and 1 represents a leaf node. When the decoder sees a 1, it reads the next 8 bits to get the value of the symbol that the leaf node represents. Then the contents are splitted into chunks of 64 KB to share the work accross different threads and make decompression more performant.
However by doing so we face a problem: now we can't simply concatenate each thread's results with each other because each result will almost certainly going to have some additional bits at the end (since Huffman code is a continuous bit stream and it does not always fit into fixed bytes) and the decompressed data will be different than the orignal one. A second problem is that the decompressor won't know where to split the code to decompress it in multiple threads, because the same amount of data can be encoded in different sizes of bytes. For example a chunk of 64 KB that contains the most frequent symbols more may be compressed in a few KBs, but another chunk with the same size that contains less frequent symbols more might result in a larger compressed data. So we need to inform the decompressor where a chunk starts and where it ends.
For that I decided to add 5 bytes before each chunk indicating where the chunk ends. After decompressing the tree, the decompressor will need to read the next byte which indicates how many bits the last byte contains. And then the next 4 bytes will indicate how many bytes the decompressor should read to get the next compressed chunk, in big endian notation. (Actually I'm not sure if 4 bytes are too much for indicating the number of bytes for the next chunk. Assuming that a symbol's compressed length can not exceed 32 in practice, and also assuming that each chunk is 64 * 1024 bytes (symbols), theoretically a compressed chunk may contain up to (32 * 64 * 1024) / 8 = 262144 bytes, which should at least be stored in a u32 number so 4 bytes. But in practice less bytes might be enough.). And then it repeats the same process for the remaining bytes, until that it reaches to the end of the file.
After that the results of threads are simply appended in order, and the decoder first decompresses the tree, and then identifies the chunks, and decompresses each chunk, optionnally each in a separate thread to increase the speed.
- Add more compression algorithms and compare their performance (Lempel-Ziv-Welch, Arithmetic coding, Burrows-Wheeler transform)
- Optimize the code more by comparing benchmarks for different chunk sizes
- In compression use the linear-time method to create the Huffman tree
The Wikipedia article on Huffman coding helped me a lot while building this program. The steps and the explanations are clear, the article helped me understand the algorithm very easily.