See what's going on with flipcode!




This section of the archives stores flipcode's complete Developer Toolbox collection, featuring a variety of mini-articles and source code contributions from our readers.

 

  Huffman Compression
  Submitted by



This is a little huffman compressor which I made recently. I was curious on how compression algorithms work and tried to implement one and the following code is what resulted. To my big surprise, the algorithm to build the huffman-tree is only a few lines of understandable code. Note that the compression algorithms to compress a file are more an example of how to use the huffman-tree and it's definitely not meant to be an illustration of brilliant software-design. Note that this implementation is not optimized and has a few nasty hacks and neither does it beat the compression ratio of the well-known compressors out there, but for people who want to take a quick peak how these compression algorithms work this might provide a nice start.

                uncompressed        this algorithm        zip (windows commander)
.pcx file          148.750                94.055                        72.555     
.ase file          821.472               492.978                     162.102
Roger Boerdijk


Currently browsing [huffman.zip] (5,379 bytes) - [huffman.h] - (3,785 bytes)

#ifndef _HUFFMAN_COMPRESSION_HPP
#define _HUFFMAN_COMPRESSION_HPP
#include "..\defines.h"
// _    _ _    _ ______ ______ __  __          _   _ 
//| |  | | |  | |  ____|  ____|  \/  |   /\   | \ | |
//| |__| | |  | | |__  | |__  | \  / |  /  \  |  \| |
//|  __  | |  | |  __| |  __| | |\/| | / /\ \ | . ` |
//| |  | | |__| | |    | |    | |  | |/ ____ \| |\  |
//|_|  |_|\____/|_|    |_|    |_|  |_/_/    \_\_| \_|
// Huffman data compression tree     
// Roger Boerdijk 30.06.2002
// email: kitt3n@home.nl                                              

// Use the code any way you wish; you assume all responsibility for its 
// correctness and suitability should you use it. 
 
//-------------------------------------------------------------------------------------------------

class cHuffmanNode
{
  friend class cHuffmanTree;

private: U8 ch; U8 reserved[3]; U32 frequency; class cHuffmanNode *parent, *left_child, *right_child;

public:

cHuffmanNode () { ch=0; frequency=0; reserved[0]=reserved[1]=reserved[2]=0; parent=left_child=right_child=NULL; }

int operator () (const cHuffmanNode& a, const cHuffmanNode& b) const; int operator () (const cHuffmanNode* a, const cHuffmanNode* b) const; };

//------------------------------------------------------------------------------------------------- class cHuffmanTree { // Note that it's up to the client libary to store the tree // to use it for later uncompression. Also note that using // the same frequency-table, the tree can be rebuilt, so you // can either store the tree, or the frequency-table! private: cHuffmanNode* root; std::vector<pair<U8,U32> > ft;

public:

cHuffmanTree () : root (NULL) {}; cHuffmanTree (U32 frequency_table[256]); cHuffmanTree (std::vector<pair<U8, U32> > frequency_table); cHuffmanTree (U8* data, U32 size); ~cHuffmanTree ();

void getStringTable (std::vector<std::string>& bitString);

U32 getCompressedSize (U8* udata, U32 len); U32 compress (U8* udata, U32 len, U8** cdata); U32 uncompress (U8* cdata, U32 len, U8** udata); U32 compress (const I8* inname, const I8* outfile); U32 uncompress (const I8* inname, const I8* outfile); U32 getTree (std::string& theTree); void setTree (const std::string& theTree);

private: bool buildTreeDo (const std::vector<pair<U8, U32> > frequency_table); void freeTree (void); void freeTreeR (cHuffmanNode* root); char* getCharacterPath (cHuffmanNode* n, int c); bool gcp (char* s, cHuffmanNode* n, int c);

bool write_bit (bool bit, U8& theByte, bool reset=false); bool read_bit (bool& bit, U8 byte, bool reset=false);

U32 getTreeR (std::string& theTree, cHuffmanNode* node); cHuffmanNode* setTreeR (const std::string& theTree, U32& idx);

};

#endif


Currently browsing [huffman.zip] (5,379 bytes) - [huffman.cpp] - (14,306 bytes)

#include "huffman.h"

// Roger Boerdijk 30.06.2002 // email: kitt3n@home.nl // Use the code any way you wish; you assume all responsibility for its // correctness and suitability should you use it. //------------------------------------------------------------------------------------------------- int cHuffmanNode::operator () (const cHuffmanNode& a, const cHuffmanNode& b) const { return a.frequency>b.frequency; }

int cHuffmanNode::operator () (const cHuffmanNode* a, const cHuffmanNode* b) const { return a->frequency>b->frequency; }

//------------------------------------------------------------------------------------------------- cHuffmanTree::cHuffmanTree (U32 frequency_table[256]) : root(NULL) { // Constructor for a byte-frequency table - usefull for compressing files ft.resize (256); for (int i=0; i<256; i++) { ft[i].first = i; ft[i].second=frequency_table[i]; } buildTreeDo (ft); }

cHuffmanTree::cHuffmanTree (std::vector<pair<U8, U32> > frequency_table) : root (NULL) { // more generic frequency table, can contain more/less ch's with // respective frequencies than the byte-frequency-table. // Nice if you have a limited character-set, for example only // A-Z and 0-9, instead of the entire ascii-table ft = frequency_table; buildTreeDo (ft); }

cHuffmanTree::cHuffmanTree (U8* data, U32 size) : root (NULL) { // very simular to cHuffmanTree::buildTree (U32 frequency_table[256]) // only this function will build the frequency-table itself pair<U8, U32> thePair; ft.resize (256); for (int z=0; z<ft.size(); z++) { thePair.first = z; thePair.second = 0; ft[z]=thePair; }

// count frequencies for (int i=0; i<size; i++) ft[data[i]].second++;

buildTreeDo (ft); }

cHuffmanTree ::~cHuffmanTree () { freeTree (); }

//------------------------------------------------------------------------------------------------- bool cHuffmanTree::buildTreeDo (const std::vector<pair<U8, U32> > frequency_table) { // If there was already a tree, cleanup and build the new one if (root) { freeTree (); }

ft = frequency_table; std::priority_queue<cHuffmanNode*, std::vector<cHuffmanNode*>, cHuffmanNode> h; cHuffmanNode* t = NULL;

// 1. Fill a heap with characters sorted on frequency // First in heap character with highest frequency for (int i=0; i<frequency_table.size(); i++) { // We push if the symbol has at least 1 occurance, // if the symbol has 0 occurances it's not usefull // to put it in the tree. if (frequency_table[i].second!=0) { cHuffmanNode* tmp = new cHuffmanNode; assert (tmp && "cHuffman::buildTree() Failed!"); tmp->ch = frequency_table[i].first; tmp->frequency = frequency_table[i].second; h.push (tmp); } }

// 2. Build the tree from the heap while (!h.empty()) { if (h.size()==1) { // If h contains only one character X, make X the root of T t = h.top(); h.pop(); } else { // Pick two characters X and Y with the lowest frequencies // and delete them from H cHuffmanNode* X=h.top(); h.pop(); cHuffmanNode* Y=h.top(); h.pop(); // replace X and Y with a new character Z, whose frequency // is the sum of the frequencies of X and Y cHuffmanNode* Z = new cHuffmanNode; Z->frequency = X->frequency+Y->frequency; Z->left_child = X; Z->right_child = Y; h.push (Z); } }

root = t; //buildCode (frequency_table, t) return true; }

//------------------------------------------------------------------------------------------------- void cHuffmanTree::freeTree (void) { if (root) { freeTreeR (root); root=NULL; } }

void cHuffmanTree::freeTreeR (cHuffmanNode* node) { if (!node) return;

if (!(node->right_child && node->left_child)) { delete node; return; }

if (node->left_child) freeTreeR (node->left_child); if (node->right_child) freeTreeR (node->right_child);

// we deleted all of this node's children, now delete // the node itself delete node; }

//------------------------------------------------------------------------------------------------- U32 cHuffmanTree::getTree (std::string& theTree) { return getTreeR (theTree, root); }

U32 cHuffmanTree::getTreeR (std::string& theTree, cHuffmanNode* node) { // This function stores reconstruction-data for our tree // Note that the "1" and "0" do NOT represent huffman-codes // but it tells if a node is a branch or a leaf // Note that we don't store frequency data for reconstruction! if (!node) return 0;

if (!(node->left_child && node->right_child)) { // leaf char ch = node->ch; theTree.append ("1"); // note: will give problems with >256 frequency-tables! theTree+=ch; return 2; } else { // Branch theTree.append ("0"); return 1+ getTreeR (theTree, node->left_child)+ getTreeR (theTree, node->right_child); }

std::vector<std::string> bs; getStringTable (bs); }

void cHuffmanTree::setTree (const std::string& theTree) { if (root) freeTree ();

U32 index=0; root = setTreeR (theTree, index); }

cHuffmanNode* cHuffmanTree::setTreeR (const std::string& theTree, U32& idx) { // This function reconstructs our tree // Note that we don't reconstruct frequency data! if (idx>=theTree.size()) return NULL;

cHuffmanNode* n = new cHuffmanNode; U8 b = theTree[idx];

if (b == '0') { // branch n->ch = 0; n->left_child = setTreeR (theTree, ++idx); n->right_child = setTreeR (theTree, ++idx); } else { // leaf idx++; n->ch = theTree[idx]; n->left_child = NULL; n->right_child = NULL; } return n; }

//------------------------------------------------------------------------------------------------- bool cHuffmanTree::gcp(char* s, cHuffmanNode* n, int c) { // get-character-path worker function. if (!n) return 0; if (!(n->left_child && n->right_child)) { if (c == n->ch) return true; else return false; } else { char _s[256]; if (gcp(s, n->left_child, c)) { strcpy(_s, s); strcpy(s, "0"); strcat(s, _s); return true; } else if (gcp(s, n->right_child, c)) { strcpy(_s, s); strcpy(s, "1"); strcat(s, _s); return true; } else return false; } }

char* cHuffmanTree::getCharacterPath (cHuffmanNode* n, int c) { // Get the path through the tree to find the bit-string // we need to encode / decode a character. Note that // we are using a static-member ie NOT an example of // good programming! static char string[256]; strcpy(string, ""); if (gcp(string, n, c)) return string; else return ""; }

void cHuffmanTree::getStringTable (std::vector<std::string>& bitString) { // Example function which will get all string encodings of each character. // Note that '0' is a 0-bit and '1' is a 1-bit bitString.resize (ft.size()); for (int i=0; i<ft.size(); i++) { char* tmp = getCharacterPath (root, ft[i].first); bitString[i]=tmp; } }

//-------------------------------------------------------------------------------------------------

bool cHuffmanTree::write_bit (bool bit, U8& theByte, bool reset) { // grow a byte, bit by bit, and then flush it theByte reset will // initialize the function to default-state. will return true as // soon as 8 bits were written and it is up to the called to save // the value in theByte. // note that if the function returns false, theByte does not // contain any usefull value static long bit_index = 7; static U8 byte = 0x00;

bool flush = false;

if (reset) { bit_index=7; byte = 0x00; return false; }

if(bit_index == -1) { // flush byte bit_index = 7; byte = 0x00; }

//byte |= (bit ? 1 : 0) << bit_index; byte |= bit << bit_index; bit_index--; if(bit_index == -1) { theByte = byte; flush=true; } return flush; }

bool cHuffmanTree::read_bit(bool& bit, U8 byte, bool reset) { // return one bit at a time, returns true when the // byte finished and it wants the next byte static long bit_index = 7; bool requestNextByte=false; int bit_value;

if (reset) { bit_index = 7; requestNextByte=false; return true; }

// bit_value = (byte & (1 << bit_index)) ? 1 : 0; bit_value = byte & (1 << bit_index); bit = bit_value!=0; bit_index--;

if(bit_index == -1) { requestNextByte=true; bit_index = 7; }

return requestNextByte; }

U32 cHuffmanTree::getCompressedSize (U8* udata, U32 len) { assert (root && udata);

// get stringtable with compression info int i; std::vector<std::string> bs; getStringTable (bs);

// calculate datasize U32 bitsEstimated=0; U32 byteEstimated=0; for (i=0; i<len; i++) { bitsEstimated+=bs[udata[i]].length(); assert (bs[udata[i]].length()!=0 && "cHuffmanTree::compress() Unknown ch"); }

// 4 bytes (U32) extra for uncompressed size byteEstimated=bitsEstimated/8; //+bitsEstimated%8==0?0:1+4; byteEstimated+=bitsEstimated%8==0?0:1; byteEstimated+=4;

return byteEstimated; }

//------------------------------------------------------------------------------------------------- U32 cHuffmanTree::compress (U8* udata, U32 len, U8** cdata) { // NOTE: Client has to deallocate memory which we allocate here! // (maybe we can somehow change this) assert (root);

// get stringtable with compression info int i; std::vector<std::string> bs; getStringTable (bs);

U32 byteEstimated = getCompressedSize (udata, len);

U8* data = new U8[byteEstimated]; if (data) { *cdata = data; *((U32*)data)=len; data+=4;

// compress data U8 cbyte; write_bit (false, cbyte, true); // reset for (i=0; i<len; i++) { U32 bitlen = bs[udata[i]].length(); const I8* str = bs[udata[i]].c_str();

for (int j=0; j<bitlen; j++) { // write the correct bit into our temp-buffer if (write_bit(((str[j] - '0')!=0), cbyte)) { // we wrote 8 bits, copy to our compressed buffer // and prepare for next byte *data=cbyte; data++; } } }

// fill last byte to end with 0 for (int fillbit=0; fillbit<8; fillbit++) { if (write_bit(0, cbyte)) { *data=cbyte; data++; break; } } return byteEstimated; } return 0; }

U32 cHuffmanTree::uncompress (U8* cdata, U32 len, U8** udata) { // NOTE: Client has to deallocate memory which we allocate here! // (maybe we can somehow change this) U32 ulen = *((U32*)cdata); cdata+=4;

U8* data = new U8[ulen]; if (data) { *udata=data;

bool bit=0; cHuffmanNode* curnode = root; U32 decodedU8s=0;

// make sure our readbit is in initialized state read_bit (bit, cdata[0], true);

while (decodedU8s<ulen) { if (cHuffmanTree::read_bit(bit, cdata[0])) { // next byte! cdata++; }

if (bit==0) { curnode = curnode->left_child; } else { curnode = curnode->right_child; }

// if we're at a leaf, output the character and start over if (!(curnode->left_child && curnode->right_child)) { data[decodedU8s]=(curnode->ch); decodedU8s++; curnode = root; } } return ulen; } return 0; }

//------------------------------------------------------------------------------------------------- U32 cHuffmanTree::compress (const I8* inname, const I8* outfile) { bool success=false; FILE* fp, *fpout; if ((fp=fopen((char*)inname, "rb"))!=NULL) { if ((fpout=fopen((char*)outfile, "wb"))!=NULL) { // determine filesize fseek (fp, 0, SEEK_END); U32 len = ftell (fp); fseek (fp, 0, SEEK_SET);

// read entire file into ram U8* ram = new U8[len]; U8* zip; if (ram) { fread (ram, len, 1, fp); }

// build huffman tree & compress cHuffmanTree tree2 (ram, len); U32 csize = tree2.compress (ram , len, &zip);

std::string htR; tree2.getTree (htR); U16 htS = htR.size(); U8 htC;

fwrite (&htS, sizeof (htS), 1, fpout); for (int i=0; i<htR.size(); i++) { htC = htR[i]; fwrite (&htC, 1, 1, fpout); } fwrite (zip, csize, 1, fpout);

delete zip; delete ram;

fclose (fpout); success=true; } fclose (fp); } return success; }

U32 cHuffmanTree::uncompress (const I8* inname, const I8* outfile) { bool success=false; FILE* fp, *fpout; if ((fp=fopen((char*)inname, "rb"))!=NULL) { if ((fpout=fopen((char*)outfile, "wb"))!=NULL) { // determine filesize fseek (fp, 0, SEEK_END); U32 len = ftell (fp); fseek (fp, 0, SEEK_SET);

// read entire file into ram U8* zip = new U8[len]; if (zip) { fread (zip, len, 1, fp); }

// build huffman tree & decompress U16 htS = *(U16*)(zip); std::string htR; htR.resize (htS); for (int i=0; i<htS; i++) { htR[i]=*(zip+i+2); } U32 htSize = sizeof(htS)+htR.size()*sizeof(U8);

U8* ram; cHuffmanTree tree2; tree2.setTree (htR); U32 usize = tree2.uncompress (zip+htSize, len-htSize, &ram);

fwrite (ram, usize, 1, fpout); delete zip; delete ram;

fclose (fpout); success=true; } fclose (fp); } return success; }


The zip file viewer built into the Developer Toolbox made use of the zlib library, as well as the zlibdll source additions.

 

Copyright 1999-2008 (C) FLIPCODE.COM and/or the original content author(s). All rights reserved.
Please read our Terms, Conditions, and Privacy information.