Click here to Skip to main content
Click here to Skip to main content

Huffman compression class in C++

By , 9 Apr 2008
Rate this:
Please Sign up or sign in to vote.

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)

About the Author

Chesnokov Yuriy
Engineer
Russian Federation Russian Federation
No Biography provided

Comments and Discussions

 
GeneralExcellent code ! Pinmembertnl197212-May-10 1:03 
GeneralBorlandC ?! [modified] PinmemberBakaBug13-Apr-09 4:01 
AnswerRe: BorlandC ?! PinmemberChesnokov Yuriy14-Apr-09 4:53 
GeneralRe: BorlandC ?! PinmemberBakaBug14-Apr-09 8:40 
GeneralDelete it !!! PinmemberHatem Mostafa14-Apr-08 21:28 
AnswerRe: Delete it !!! PinmvpChesnokov Yuriy15-Apr-08 17:57 
GeneralRe: Delete it !!! PinmemberKarstenK22-May-08 3:41 
AnswerRe: Delete it !!! PinmvpChesnokov Yuriy26-May-08 21:01 

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

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

| Advertise | Privacy | Mobile
Web02 | 2.8.140415.2 | Last Updated 9 Apr 2008
Article Copyright 2008 by Chesnokov Yuriy
Everything else Copyright © CodeProject, 1999-2014
Terms of Use
Layout: fixed | fluid