Click here to Skip to main content
15,867,453 members
Articles / Desktop Programming / Win32
Article

Huffman compression class in C++

Rate me:
Please Sign up or sign in to vote.
3.64/5 (20 votes)
9 Apr 2008GPL32 min read 106.5K   9.9K   47   10
The article provides a dynamic Huffman compression and decompression class and a console application written in C++.

Introduction

I've written, some many years ago, a dynamic Huffman algorithm to compress and decompress data. It is mainly targeted to data with some symbols occurring more often than the rest (e.g., having some data file consisting of three different symbols, and their total number of occurrences in that file is s1(1000), s2(200), s3(30), so the total length of the file is 1000+200+30=1230 bytes; it is encoded, assigning one bit to s1 and two bits to s2, s3, so the encoded length is 1*1000+2*(200+30)=1460 bits=182 bytes). In the best case, a file consisting of just one symbol will be encoded with a compression ratio of 1:8. Huffman coding is used in image compression; however, in JPEG2000, an arithmetic codec is employed.

Background

The article intends to provide the code only, and is not a Huffman tutorial. You may dig for online tutorials on the subject.

Using the code

The console is straightforward to use to encode a source file to a Huffman compressed one:

>>huffman.exe e sourcefile destinationfile

or to decode a Huffman compressed source file back to the original file:

>>huffman.exe d sourcefile destinationfile

The Huffman class provides three functions to use:

  • void encode(unsigned char *dest, int &csize, unsigned char *sour, int usize) - to encode
  • void decode(unsigned char *dest, int &usize, unsigned char *sour) - to decode
  • int get_uncompressed_size(unsigned char *sour) - to get the uncompressed file size from Huffman encoded data file

dest and sour are the destination and source buffers, usize and csize are the uncompressed size of the original data and the compressed size of the Huffman encoded data. To encode, just provide your data in the sour buffer and specify its size in usize. The csize will be given the size of the compressed Huffman array you need to provide in the dest pointer. Make sure it is allocated at least the size of your original data. To decode, just provide in sour your Huffman encoded data, and query with get_uncompressed_size(sour) the size of the dest buffer you need to allocate. Upon decompression completion, the usize will be overwritten with the uncompressed data size.

Points of interest

I know storing data symbols and their frequencies into Huffman encoded files is space consuming, and that more compact representations are present.

License

This article, along with any associated source code and files, is licensed under The GNU General Public License (GPLv3)


Written By
Engineer
Russian Federation Russian Federation
Highly skilled Engineer with 14 years of experience in academia, R&D and commercial product development supporting full software life-cycle from idea to implementation and further support. During my academic career I was able to succeed in MIT Computers in Cardiology 2006 international challenge, as a R&D and SW engineer gain CodeProject MVP, find algorithmic solutions to quickly resolve tough customer problems to pass product requirements in tight deadlines. My key areas of expertise involve Object-Oriented
Analysis and Design OOAD, OOP, machine learning, natural language processing, face recognition, computer vision and image processing, wavelet analysis, digital signal processing in cardiology.

Comments and Discussions

 
QuestionIf the compression ratio is lower than 1 then you get an error! Pin
Dainius Kreivys16-Jan-17 1:05
Dainius Kreivys16-Jan-17 1:05 
PraiseSo Simple ^^ Pin
Kim Ji-Sik21-Jan-16 23:15
Kim Ji-Sik21-Jan-16 23:15 
GeneralExcellent code ! Pin
tnl197212-May-10 1:03
tnl197212-May-10 1:03 
GeneralBorlandC ?! [modified] Pin
BakaBug13-Apr-09 4:01
BakaBug13-Apr-09 4:01 
AnswerRe: BorlandC ?! Pin
Chesnokov Yuriy14-Apr-09 4:53
professionalChesnokov Yuriy14-Apr-09 4:53 
GeneralRe: BorlandC ?! Pin
BakaBug14-Apr-09 8:40
BakaBug14-Apr-09 8:40 
GeneralDelete it !!! Pin
Hatem Mostafa14-Apr-08 21:28
Hatem Mostafa14-Apr-08 21:28 
AnswerRe: Delete it !!! Pin
Chesnokov Yuriy15-Apr-08 17:57
professionalChesnokov Yuriy15-Apr-08 17:57 
GeneralRe: Delete it !!! Pin
KarstenK22-May-08 3:41
mveKarstenK22-May-08 3:41 
AnswerRe: Delete it !!! Pin
Chesnokov Yuriy26-May-08 21:01
professionalChesnokov Yuriy26-May-08 21:01 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.