I found a trick to significantly reduce the time needed to compute Huffman codes in my implementation of RFC1951. I was slightly surprised to find it slightly improves compression as well, something I had not anticipated.
The trick is to encode the required information about a tree node in a ulong, arranged so that the ulong values can be compared directly, rather than by calling a delegate function which accessed related arrays to get the frequency and depth. This has a substantial effect on the performance.
The symbol or tree node id goes in the bottom 16 bits, the tree depth in the next 8 bits, and the frequency ( how many times the tree node is used ) in the remaining 40 bits. The revised code is below.
I think the reason compression is improved is that the compare now includes the symbol id, this tends to assign the same number of bits to adjacent symbols if they have the same frequency, and that in turn tends to reduce the number of bits needed to encode the lengths.
Here's the revised code:
struct HuffmanCoding // Variable length coding.
{
public ushort Count; // Number of used symbols.
public byte [] Bits; // Number of bits used to encode a symbol.
public ushort [] Codes; // Huffman code for a symbol ( bit 0 is most significant ).
public int [] Used; // Count of how many times a symbol is used in the block being encoded.
private int Limit; // Maximum number of bits for a code.
private ushort [] Tree;
public HuffmanCoding( int limit, ushort symbols )
{
Limit = limit;
Count = symbols;
Bits = new byte[ symbols ];
Codes = new ushort[ symbols ];
Used = new int[ symbols * 2 ]; // Second half of array is for tree nodes.
Tree = new ushort[ symbols * 2] ; // First half is one branch, second half is other branch.
}
public int Total()
{
int result = 0, count = Count;
for ( int i = 0; i < count; i += 1 )
result += Used[i] * Bits[i];
return result;
}
public bool ComputeCodes() // returns true if Limit is exceeded.
{
ushort count = Count;
UlongHeap heap = new UlongHeap( count );
for ( ushort i = 0; i < Count; i += 1 )
{
int used = Used[ i ];
if ( used > 0 )
{
// The values are encoded as 16 bits for the symbol, 8 bits for the depth, then 32 bits for the frequency.
heap.Insert( ( (ulong)used << 24 ) + i );
}
}
int maxBits = 0;
if ( heap.Count == 1 )
{
GetBits( (ushort) heap.Remove(), 1 );
maxBits = 1;
}
else if ( heap.Count > 1 )
{
ulong treeNode = Count;
do // Keep pairing the lowest frequency TreeNodes.
{
ulong left = heap.Remove();
Tree[ treeNode - Count ] = (ushort) left;
ulong right = heap.Remove();
Tree[ treeNode ] = (ushort) right;
// Extract depth of left and right nodes ( depth is encoded as bits 16..23 ).
uint dleft = (uint)left & 0xff0000u, dright = (uint)right & 0xff0000u;
uint depth = ( dleft > dright ? dleft : dright ) + 0x10000u;
heap.Insert( ( ( left + right ) & 0xffffffffff000000 ) | depth | treeNode );
treeNode += 1;
} while ( heap.Count > 1 );
uint root = ( (uint) heap.Remove() ) & 0xffffff;
maxBits = (int)( root >> 16 );
if ( maxBits > Limit ) return true;
GetBits( (ushort)root, 0 ); // Walk the tree to find the code lengths (Bits).
}
// Compute codes, code below is from RFC 1951 page 7.
int [] bl_count = new int[ maxBits + 1 ];
for ( int i = 0; i < count; i += 1 ) bl_count[ Bits[ i ] ] += 1;
int [] next_code = new int[ maxBits + 1 ];
int code = 0; bl_count[ 0 ] = 0;
for ( int i = 0; i < maxBits; i += 1 )
{
code = ( code + bl_count[ i ] ) << 1;
next_code[ i+1 ] = code;
}
for ( int i = 0; i < count; i += 1 )
{
int length = Bits[ i ];
if ( length != 0 )
{
Codes[ i ] = (ushort)Reverse( next_code[ length ], length );
next_code[ length ] += 1;
}
}
// Reduce count if there are unused symbols.
while ( count > 0 && Bits[ count - 1 ] == 0 ) count -= 1;
Count = count;
// System.Console.WriteLine( "HuffEncoder.ComputeCodes" );
// for ( int i = 0; i < count; i += 1 ) if ( Bits[ i ] > 0 )
// System.Console.WriteLine( "i=" + i + " len=" + Bits[ i ] + " tc=" + Codes[ i ].ToString("X") + " freq=" + Used[ i ] );
return false;
}
private void GetBits( ushort treeNode, int length )
{
if ( treeNode < Count ) // treeNode is a leaf.
{
Bits[ treeNode ] = (byte)length;
}
else
{
length += 1;
GetBits( Tree[ treeNode - Count ], length );
GetBits( Tree[ treeNode ], length );
}
}
private static int Reverse( int x, int bits )
// Reverse a string of bits ( ready to be output as Huffman code ).
{
int result = 0;
for ( int i = 0; i < bits; i += 1 )
{
result <<= 1;
result |= x & 1;
x >>= 1;
}
return result;
}
} // end struct HuffmanCoding
// ******************************************************************************
struct UlongHeap // An array organised so the smallest element can be efficiently removed.
{
public int Count { get{ return _Count; } }
private int _Count;
private ulong [] Array;
public UlongHeap ( int capacity )
{
_Count = 0;
Array = new ulong[ capacity ];
}
public void Insert( ulong e )
{
int j = _Count++;
while ( j > 0 )
{
int p = ( j - 1 ) >> 1; // Index of parent.
ulong pe = Array[ p ];
if ( e >= pe ) break;
Array[ j ] = pe; // Demote parent.
j = p;
}
Array[ j ] = e;
}
public ulong Remove() // Returns the smallest element.
{
ulong result = Array[ 0 ];
_Count -= 1;
ulong e = Array[ _Count ];
int j = 0;
while ( true )
{
int c = ( j + j ) + 1; if ( c >= _Count ) break;
ulong ce = Array[ c ];
if ( c + 1 < _Count )
{
ulong ce2 = Array[ c + 1 ];
if ( ce2 < ce ) { c += 1; ce = ce2; }
}
if ( ce >= e ) break;
Array[ j ] = ce; j = c;
}
Array[ j ] = e;
return result;
}
} // end struct Heap
