How does one implement the Huffman tree algorithm in c plus plus?
As a student in 1951, David A. Huffman (1925-1999) was given the
option of sitting a final exam or submitting a term paper. He chose
the latter. The term paper outlined the problem: find the most
efficient binary code. In other words, given any amount of data,
find the most efficient method of encoding that data in the least
number of bits. When we encode data using standard 8-bit symbols,
every symbol is obviously the same length (8 bits). If we alter the
encoding so that we use shorter codes for symbols that appear most
often, and longer codes for those that appear less often, we can
encode the data more efficiently. For instance, if the most
frequent symbol could be encoded with just 1 bit (say, 0), then we
save 7 bits for every occurrence of that symbol. However, no other
symbol can use an encoding that begins with 0, they must all be
longer than 1 bit and must begin with a 1. Moreover, no symbol can
start with the same sequence of bits assigned to any other
symbol.
Huffman quickly ascertained that he was looking for a prefix
coding method. While efficient encoding methods certainly existed
at the time (Shannon-Fano being one), none could be guaranteed to
provide the most efficient coding. Indeed, Huffman had all but
given up and resigned himself to the final exam when the answer
finally dawned on him. If he used a frequency-sorted binary tree,
he could encode any symbol in the tree by tracing the path back to
the root. The symbols formed the leaves of the tree and if he
followed the left path to the leaf's parent, he prefixed a 0 bit,
otherwise he prefixed a 1 bit. Repeating this process all the way
to the root, every symbol could be assigned a unique prefix code.
Moreover, when reading the encoded data back, he simply started at
the root and followed the left or right paths according to the bits
in the prefix. When he reached a leaf node, he'd found his symbol,
and started at the root to find the next.
Huffman wasn't the first to discover this of course, but what
had eluded all the mathematicians and programmers of the day was
simply how to go about building the tree in the first place.
Normally we build trees from the top down, from the root. Huffman's
revelation was in building the tree from the bottom up, starting
with the leaves. With this simple change, not only did he complete
his term paper with honours, he exceeded even his professor's
expectations. His method proved to be the most efficient encoding
and Huffman's name was entered into the computing history
books.
Huffman started by creating a frequency table of symbols which
he then sorted in descending order of frequency. He then copied the
table and, while the copy contained more than one node, he
extracted (removed) the last two nodes and constructed a parent
node, with the last node attached to its left node, and its
predecessor to its right. The parent node's frequency was the sum
of its left and right node frequencies. The parent node was then
inserted back into the copy, maintaining the descending order of
frequency. When only one node remained in the copy, the tree was
complete. The one remaining node becomes the root of the Huffman
tree.
You then encode the tree. Initially, all nodes have no prefix
code but, starting from the root, you copy its prefix (an empty
string) to its left child and append a "0", and then recursively
encode the left child (thus its left child will be prefix "00"). Do
the same for the right child, but append a "1" instead. Thus the
child to the right of the root's left child will be prefix "01".
When you reach a leaf, its prefix code determines the precise route
you took from the root to the leaf (where "0" means go left, and
"1" means go right). Since the tree was a copy of the frequency
table, each leaf in the original frequency table will also be
encoded.
You are now ready to begin encoding the file. You begin by
outputing the original file size (so you know when to stop reading
when decoding the encoded file). You then output the binary
representation of the tree and its symbols. That is, starting from
the root node, output a 0 bit if it is a parent node, or a 1 bit
followed by the 8-bit unencoded symbol if it is a leaf. Repeat the
process for the node's left and right children if it has any (it
must have both or neither, it cannot have one but not the other).
Finally, read the original file one symbol at a time, locate it in
the frequency table, and output its prefix code. When writing
individual bits, you need to use a bitwriter that buffers up to 8
bits at a time and then write a complete byte. When you write the
final bit, pad any unused bits with zeroes to make a full byte.
To decode the encoded file, use a bitreader to read back 1 bit
at a time. Decoding is simply a matter of reading the file size,
then reconstructing the tree from its binary representation, and
then reading one bit a time to navigate the tree from the root.
when you reach a leaf, output the symbol, decrement the file size
and return to the root. Repeat until the file size is zero, at
which point the original file is restored.
The following implementation is not complete by any means. For
instance, if you were to encode a file containing the text "The
quick brown fox jumps over the lazy dog.", you will find that this
44 byte file compresses to a 66 byte file. This seems unimpressive,
but remember that the encoded file also contains the file size and
the Huffman tree as well as the encoded data. The encoded data is
actually smaller than the original file, but because the file is so
small to begin with, the overhead of the additional information
produces a larger file. Huffman encoding works best on larger files
(the bigger the better). An alternative approach is to use a static
table, thus eliminating the need to transmit the table along with
the encoded data. However this only works when the frequency table
is highly predictable -- it won't be suitable for all file types.
Another approach is to create several static tables, and use the
one that produces the smallest file. Again, this is less than
optimal, but if you have 255 different tables, then you only need
to transmit 8 additional bits to determine which table to use for
decoding (where table 0 implies no encoding, for those files that
cannot be reduced with any of the tables). But for larger files,
the overhead of the frequency table is more than outweighed by the
reduction in the encoded data. For instance, a file that contains
nothing but 0 bits can be reduced to a file a little over 1/8th the
size of the original file. Of course, such a file could easily be
compressed to a fraction of that simply by utilising run length
encoding, but you can also combine both methods, using RLE to
reduce the repeated bit sequences, and then Huffman encoding to
reduce the RLE file. These implementations (amongst many others,
many of which are patented) are left for the reader to
discover.
In the meantime, be aware that the following implementation
provides only the minimum functionality to both encode and decode
using Huffman's algorithm, and makes use of standard output for the
DESTINATION file (you may wish to make the destination file a
command-line option, and test the source and destination are
actually different files). Note also that besides some simple
error-checks (some of which are unnecessary with prudent assertions
and verifications), overall robustness has been sacrificed for the
sake of simplicity.
// Huffman.exe
// Copyright ©2013 PCForrest.
#include<iostream>
#include<list>
// The bitreader class facilitates the reading
// of binary files, 1 bit at a time.
class bitreader
{
public:
// The constructor accepts a file pointer to a file that is
// already opened for binary reading. The m_size and
m_buffer
// members are initially zero.
bitreader( FILE* file ): m_file( file ), m_buffer( 0 ), m_size(
0 ){}
~bitreader(){};
int readbit();
public:
FILE* m_file;
unsigned char m_buffer;
int m_size;
};
// Returns a single bit (0 or 1) from the file.
// Returns -1 if an error occurs.
int bitreader::readbit()
{
// Are there any bits in the buffer?
if( !m_size )
{
// Read 8 bits into the buffer.
size_t read = fread( &m_buffer, 1, 1, m_file );
if( read == 1 )
m_size = 8;
else
// Fatal error!
return( -1 );
}
// If we get this far, there is at least 1 bit in the
buffer.
// Extract the MSB from the buffer, shift the remaining bits
// left and decrement the size.
int bit = m_buffer&0x80?1:0;
m_buffer<<=1;
--m_size;
// Return the extracted bit.
return( bit );
}
// The bitwriter class facilitates the writing
// of binary files, 1 bit at a time.
class bitwriter
{
public:
// The constructor simply initialises the members.
bitwriter(): m_buffer( 0 ), m_unused_bits( 8 ){}
~bitwriter();
void writebit( unsigned char bit = 1 );
public:
char m_buffer; // The bit buffer.
int m_unused_bits; // Unused bits.
};
// The destructor pads any unwritten bits to make a full
byte.
bitwriter::~bitwriter()
{
while( m_unused_bits != 8 )
writebit( 0 );
}
// Writes a single bit to the buffer. When the buffer is
full,
// outputs the buffer to standard output and resets the
buffer.
void bitwriter::writebit( unsigned char bit /* = 1 */ )
{
// Bit must be 0 or 1.
if( bit > 1 )
return;
// Decrement the buffer length.
--m_unused_bits;
if( bit )
{
// Shift the bit left if necessary.
if( m_unused_bits )
bit <<= m_unused_bits;
// Combine bit with current buffer.
m_buffer |= bit;
}
// Do we have a complete byte?
if( !m_unused_bits )
{
// Write the byte and empty the buffer.
std::cout << m_buffer;
m_buffer = 0;
m_unused_bits = 8;
}
}
// A node object acts as both a leaf and a parent. Only the
// leafs store any symbols. Parents store both a left and
// right node. During encoding, leafs store the frequency
// of their symbols while parents store the sum of the
// frequencies of their two children. During decoding,
// the frequency is not used.
class node
{
// Used when sorting the Huffman table.
friend bool compare(const node* x, const node* y);
public:
node( unsigned char data );
node( node& left, node& right );
~node( void );
int encode( bitwriter& writer );
int decode( bitreader& reader );
char get_symbol( void ) const { return( m_symbol ); }
unsigned int get_freq( void ) const { return( m_freq ); }
const std::string& get_code( void ) const { return( m_code
); }
node* get_left( void ) const { return( m_left ); }
node* get_right( void ) const { return( m_right ); }
void inc_freq( void ){ ++m_freq; }
private:
unsigned char m_symbol;
unsigned int m_freq;
std::string m_code;
node* m_left;
node* m_right;
};
// Constructs a leaf.
node::node( unsigned char symbol )
: m_symbol( symbol )
, m_freq( 1 )
, m_code( "" )
, m_left( NULL )
, m_right( NULL ) {}
// Constructs a parent.
node::node( node& left, node& right )
: m_symbol( 0 )
, m_freq( left.m_freq + right.m_freq )
, m_code( "" )
, m_left( &left )
, m_right( &right ){}
// Recursive destructor.
node::~node( void )
{
delete( m_left );
delete( m_right );
}
// Recursively decodes (rebuilds) the tree from the given bit
reader.
int node::decode( bitreader& reader )
{
// Read the next bit.
int result = reader.readbit();
switch( result )
{
case( -1 ): // Fatal error!
return( result );
case( 0 ): // This node is a parent.
// Instantiate the left node.
if( m_left = new node(0) )
{
// Decode the left node (recursively).
result = m_left->decode( reader );
// Ensure success (zero).
if( !result )
// Instantiate the right node.
if( m_right = new node(0) )
// Decode the right node (recursively).
result = m_right->decode( reader );
}
// Return the result.
return( result );
case( 1 ): // This node is a leaf.
// Read the next 8 bits and store the resultant symbol.
for( int i=0; i<8; ++i )
{
m_symbol<<=1;
result = reader.readbit();
if( result == -1 )
return( result );
m_symbol |= result;
}
}
// Success!
return( 0 );
}
// Encodes the Huffman tree. If this node is a parent,
// write a 0 bit, otherwise write a 1 bit followed by
// the 8-bit unencoded symbol.
int node::encode(bitwriter& writer )
{
int error=-1;
// Is this node a leaf?
if( !m_left && !m_right )
{
// Write a 1 bit.
writer.writebit(1);
// Store the symbol locally.
unsigned char symbol=m_symbol;
// Write each bit from the MSB to the LSB.
for(int i=0; i<8; ++i, symbol<<=1)
writer.writebit(symbol&0x80?1:0);
// Success!
error=0;
}
// Or is this node a parent?
else if( m_left && m_right )
{
// Write a zero bit.
writer.writebit(0);
// Copy this node's code to the left node
// and append a 0.
m_left->m_code = m_code;
m_left->m_code += "0";
// Recurse for the left node.
error = m_left->encode( writer );
if( !error )
{
// Copy this node's code to the right node
// and append a 1.
m_right->m_code = m_code;
m_right->m_code += "1";
// Recurse for the right node.
error = m_right->encode( writer );
}
}
return( error );
}
// Compare method used to sort the Huffman table
// in descending order of frequency.
bool compare( const node* x, const node* y )
{
return( x->m_freq>y->m_freq );
}
// Decodes the given file name and redirects the
// decoded data to standard output.
int decode( const char* filename )
{
// Open the input file for binary reading.
FILE* input = fopen( filename,"rb" );
if( !input )
{
std::cerr<<"File access error:
"<<filename<<std::endl;
return( -1 );
}
// Instantiate a bit reader object.
bitreader reader( input );
int error = -1, bit=0;
// Determine the length of the decoded data.
unsigned int len=0;
for( int i=0; i<sizeof(unsigned int)*8; ++i )
{
len <<= 1;
bit = reader.readbit();
if( bit == -1 )
return( error );
len |= bit;
}
// Instantiate the Huffman tree root.
node root( 0 );
// Decode (rebuild) the tree.
root.decode( reader );
// Begin reading the encoded data until all symbols
// have been read.
while( len-- )
{
// Point to the root of the Huffman tree.
node* pnode = &root;
// Repeat while the current node is a parent node.
while( pnode->get_left() && pnode->get_right()
)
{
// Read the next bit.
bit = reader.readbit();
if( bit == error )
// Fatal error!
return( error );
// Navigate right if the bit is set, otherwise navigate
left.
pnode = bit?pnode->get_right():pnode->get_left();
}
// We've reached a leaf, output the data.
std::cout << pnode->get_symbol();
}
// Success!
fclose( input );
return(0);
}
// Encodes the given file name and redirects the encoded
// data to standard output.
int encode( const char* filename )
{
// Open the file for binary reading.
FILE* input=fopen( filename,"rb" );
if( !input )
{
std::cerr<<"File access error:
"<<filename<<std::endl;
return(-1);
}
// Instantiate the Huffman frequency table.
std::list<node*> table;
// Some variables.
unsigned int len=0;
char symbol=0;
// Read one symbol at a time.
while( fread( &symbol, 1, 1, input ) == 1 )
{
// Increment the file length.
++len;
// Locate the symbol in the Huffman frequency table.
std::list<node*>::iterator it=table.begin();
while( it!=table.end() )
{
// Reference the node.
node& rnode = *(*it);
// Check for equality.
if( rnode.get_symbol() == symbol )
{
// Symbol found, increment its frequency.
rnode.inc_freq();
break;
}
++it;
}
// Was the symbol found?
if( it==table.end() )
{
// No -- create a new node for the symbol
// and add it to the table.
node* pnode = new node( symbol );
table.push_back( pnode );
}
}
if( ferror( input ))
{
fclose( input );
std::cerr << "File read error: " << filename
<< std::endl;
return( -1 );
}
// Sort the Huffman frequency table in descending order of
frequency.
table.sort( compare );
// Instantiate the Huffman tree (copy the Huffman frequency
table).
std::list<node*> tree( table );
// Repeat while the Huffman tree has more than one node.
while( tree.size() > 1 )
{
// Extract the last two nodes.
std::list<node*>::reverse_iterator rit =
tree.rbegin();
node* left = *rit++;
node* right = *rit;
tree.pop_back();
tree.pop_back();
// Create a parent node for the two extracted nodes.
node* parent = new node( *left, *right );
// Add the parent node and resort the tree.
tree.push_back( parent );
tree.sort( compare );
}
// Instantiate a bit writer.
bitwriter writer;
// Write the file length (32 bits).
for(int i=0; i<sizeof( unsigned int )*8; ++i,
len<<=1)
writer.writebit( len&0x80000000?1:0 );
// Reference the root node of the Huffman tree.
node& root = *( *tree.begin() );
// Recursively encode the Huffman tree (also
// encodes the Huffman frequency table, since
// both contain pointers to the same nodes).
root.encode(writer);
// Read symbols from the start of the input file.
fseek( input, 0, SEEK_SET );
while( fread( &symbol, 1, 1, input ) == 1 )
{
// Locate the symbol in the Huffman frequency table.
for(std::list<node*>::iterator it=table.begin();
it!=table.end(); ++it )
{
// Reference the current node.
node& rnode = *(*it);
if( rnode.get_symbol() == symbol )
{
// Write the symbol's code.
for(unsigned int i=0; i<rnode.get_code().size(); ++i)
writer.writebit( rnode.get_code().at(i)=='1'?1:0 );
break;
}
}
}
if( ferror( input ))
{
fclose( input );
std::cerr << "File read error: " << filename
<< std::endl;
return( -1 );
}
// Finished with the input file.
fclose(input);
// Success!
return(0);
}
// The main function handles the command line.
int main(int argc, char* argv[])
{
if(argc==3)
{
std::string option( argv[2] );
if( !option.compare("-d") !option.compare("-D") )
if( decode(argv[1] ))
std::cerr<<"The input file cannot be
decoded.\n"<<std::endl;
else
return(0);
else if( !option.compare("-e") !option.compare("-E") )
if( encode(argv[1] ))
std::cerr<<"The input file could not be
encoded.\n"<<std::endl;
else
return(0);
}
std::cerr<<"Usage:\n\n"
<<argv[0]<<" SOURCE -switch > DEST\n"
<<"\nWhere:\n\n"
<<"\tSOURCE\t- source file name\n"
<<"\tDEST\t- destination file name\n\n"
<<"Switch:\n\n"
<<"\td\t- decode\n"
<<"\te\t- encode\n"<<std::endl;
return(-1);
}
