Length-Dinky Prefix Codes

posted June 30, 2021 by Stephan Brumme

Overview

Essentially the most regular methodology to generate prefix-free codes is the Huffman algorithm.


It is allotment of many standard compression algorithms reminiscent of JPEG,
DEFLATE (ZIP /
GZIP / PNG / etc.).


Typically it serves as an “afterburner” to compress pre-processed symbols.

The principle advantage – variable-dimension codes – is known as a excessive downside, too: if the utmost code dimension exceeds a definite threshold,
e.g. the CPU’s integer dimension, (16 / 32 / 64 bit), then the compression/decompression code becomes advanced and slows down.


All of the aforementioned file formats place a strict higher restrict on the utmost dimension of Huffman codes.


Mainly on account of their age and low quantity of distinct symbols, all of them agreed on 16 bits per code.

So-known as dimension-dinky prefix codes will not be Huffman codes anymore because they place not appear to be optimal (if the dimensions restriction develop into as soon as enforced).


The loss in compression efficiency turns out to be in most cases negligible and thus is widely authorized on account of the quite a bit of own in decompression performance.

There may perhaps be somewhat a pair of algorithms to present such dimension-dinky prefix codes. They vary referring to walk, efficiency and complexity.


I wrote a C library imposing the commonest methods. Many of the code derives from open source programs and develop into as soon as invented by others.

My vital contribution develop into as soon as to present a shared interface in remark that these algorithms are simply interchangeable:

veil

interface


unsigned char algorithmName(unsigned char maxLength, unsigned int numCodes, const unsigned int histogram[], unsigned char codeLengths[]);


There are three enter parameters:

• maxLength is the upper restrict of the quantity of bits for every and every prefix code
• numCodes is the quantity of distinct symbols (including unused symbols) ? dimension of your alphabet
• histogram is an array of numCodes counters how in most cases each and every image is portray

and one output parameter:

• codeLengths will have the bit dimension of every and every image

The return payment is:

• the longest bit dimension or zero if the algorithm failed

If you happen to like to wish to encode the sequence 0 3 1 1 2 5 2 2 then numCodes = 6 and histogram[] = { 1,2,3,1,0,1 };

Nonetheless, this shared interface comes with a diminutive bit of overhead: each and every so again and again doubling code dimension and/or execution time.


Attributable to this reality most files bear a 2nd public characteristic which is more specialized for its algorithm but may perhaps perchance perhaps also simply bear a pair of further restrictions.


An everyday case is that the histogram must be sorted and unused symbols removed.

For the time being utilized are:

Utilization

Every algorithm runs self sustaining of every and every other. There don’t appear to be any exterior dependencies, too.


Some algorithms require pre-computed Huffman codes – for these cases I added a rather modified version of
Andrew Moffat’s atmosphere friendly in-establish of dwelling Huffman code.


If you happen to like to wish to confirm out out an algorithm then all you want present is:

veil

Utilization


#consist of "packagemerge.h"
#consist of

int vital()
{
// let's own you may perhaps perchance perhaps even bear 7 symbols
unsigned int numCodes = 7;
// first one happens 270 cases, 2nd 20x, third 10x, fourth under no circumstances, fifth as soon as, sixth 6x and seventh as soon as
unsigned int histogram[7] = { 270,20,10,0,1,6,1 };

// at most 4 bits
unsigned char maxLength = 4;
// output: bits per code
unsigned char codeLengths[7];

// compute dimension-dinky codes
unsigned char longest = packageMerge(maxLength, numCodes, histogram, codeLengths);

// pronounce end result
for (unsigned int i = 0; i < numCodes; i++)
printf("code %d occurs %d times => %d bitsn", i, histogram[i], codeLengths[i]);
printf("max. code dimension is %dn", longest);

return 0;
}


When in comparison with the customary Huffman algorithm, a pair of code grew to change into shorter and a pair of grew to change into longer.


The amount of bits / codeLengths are:

As you may perhaps perchance perhaps look, limiting the utmost code lengths hurts the compression ratio.

There are quite a bit of methods to rework code lengths to proper prefix-free codes.
I derive canonical Huffman codes to be the most upright: a straightforward and hasty algorithm.


Utilizing the instance files we score these canonical codes:

An everyday program exhibiting the style to compute canonical codes (click on to open):

portray

canonical.c


#consist of "packagemerge.h"
#consist of


// produce canonical codes, for simplicity longest code must never exceed quantity of bits of an unsigned int (32 or 64)
void canonical(unsigned int numCodes, unsigned char codeLengths[], unsigned int codes[])
{
// count how in most cases each and every code dimension is portray
unsigned int numLengths[256] = { 0 };
unsigned int i;
for (i = 0; i < numCodes; i++)
numLengths[codeLengths[i]]++;

// precompute the most most considerable code of every and every code dimension
unsigned int subsequent[256];
// there isn't any code with dimension 0 and the most most considerable 1-bit code with be a zero
subsequent[1] = 0;
for (i = 2; i < 256; i++)
subsequent[i] = (subsequent[i - 1] + numLengths[i - 1]) << 1;

// now attach all codes
for (i = 0; i < numCodes; i++)
codes[i] = subsequent[codeLengths[i]]++;
}


int vital()
{
// let's own you may perhaps perchance perhaps even bear 7 symbols
unsigned int numCodes = 7;
// first one happens 270 cases, 2nd 20x, third 10x, fourth no at all, fifth as soon as, sixth 6x and seventh as soon as
unsigned int histogram[7] = { 270,20,10,0,1,6,1 };

// at most 4 bits
unsigned char maxLength = 4;
// output: bits per code
unsigned char codeLengths[7];

// compute dimension-dinky codes
unsigned char longest = packageMerge(maxLength, numCodes, histogram, codeLengths);

// produce canonical codes
unsigned int codes[7];
canonical(numCodes, codeLengths, codes);

// pronounce end result
unsigned int i;
for (i = 0; i < numCodes; i++)
{
printf("code %d occurs %d timest=> %d bits", i, histogram[i], codeLengths[i]);

// binary represenation of canonical code
printf("t=> ");
if (codeLengths[i] > 0)
{
int shift;
for (shift = codeLengths[i] - 1; shift >= 0; shift--)
printf(codes[i] & (1 << shift) ? "1" : "0");
}
printf("n");
}
printf("max. code length is %dn", longest);

return 0;
}


Benchmark

Here are a few results from the first 64k bytes of enwik, measured on a Core i7 / GCC x64:

time ./benchmark 1 12 100000

• where 1 is the algorithm’s ID and was between 0 and 6
• limiting the code length to at most 12 bits
• note: the unadjusted Huffman codes have up to 16 bits
• each algorithm ran 100000 times

For comparison: the uncompressed data has 64k bytes = 524,288 bits:

Remember: each algorithm was repeated 100,000 times, so a single iteration finished in about 4 to 17 microseconds.

Changing the code length limit significantly influences both execution time and compression ratio.


I picked the two “best” algorithms, used the same data set and repeated each procedure 100,000 times:

For comparison: Moffat’s Huffman algorithm needs 0.55 seconds and its longest prefix code has 16 bits.

Package-Merge

Package-Merge is an algorithm that guarantees to produce optimal length-limited prefix codes.


Its name is based on the conception of putting numbers in packages and merging these.

Unfortunately, the original paper by Lawrence L. Larmore and Daniel S. Hirschberg isn’t very accessible.


Moreover, further information is pretty scarce on the internet: the Wikipedia entry doesn’t help a lot.


The best introduction – in my opinion – is Sebastian Gesemann’s Bachelor’s Thesis but it’s available in German only.


The diagrams on page 24 and 26 walk through an example and page 29 gives pseudo code.

There are two prerequisites:

• remove all unused symbols before running Package-Merge
• and symbols must must be sorted in ascending order of their frequency

Let’s process the sample data shown above:

Obviously, the prerequisites aren’t fulfilled yet: unused symbol 3 needs to be removed and the remaining symbols must be in ascending order of their count:


(the order of symbols with the same count doesn’t matter)

Since there were 6 symbols (plus an unused one), we need at least 3 bits to encode them.


Naturally you can’t have an active symbol with zero bits, the minimum code length is 1 bit.


Package-Merge adds one bit in each iteration so there is a minimum of two iterations (2+1=3) but for whatever reason I decided to have this example with maxLength=4.

Now we add these counts pairwise, we build packages. If there is an odd number of symbols then the last (which is the largest) is discarded:

These packages have to be merged with the original sequence in ascending order.


If a package is identical to a count of the original sequence then that item from the original sequence comes first.


In the next table packages are shown in a bold font:

This was one iteration of phase 1. Each iteration represents one bit.


Therefore we need to repeat that procedure two more times to reach our goal maxLength=4.


However, there is one little pitfall: pairs are made using the sequence from the previous step but you always merge them with the original sequence.


That last sentence is important and was probably my most critical insight when I learned about the Package-Merge algorithm.

Okay, let’s create package for the second bit:

As you can see, there is an odd number of items and thus the last item (290 in the upper row) must be discarded.


The four values in the lower row are merged with the original sequence:

One more time “packaging”:

And merging:

Phase 1 has completed. Let’s gather all intermediate results from each iteration in one table:

Phase 2 processes the output of each iteration, going from the bottom row to the top row.


The actual values in the table don’t matter – it’s only relevant whether a value is a package (bold) or not (plain).

Code lengths for all symbols are initially set to zero.


If a value isn’t bold then the code length of a symbol has to be incremented.

The first iteration processes the first 2*numCodes-2=10 values of the bottom row, that means 1,1,...,270 but not 560.


Two counters symbol and numMerged are set to zero.

For each table entry a decision has to be made:

• if that value is a package (bold) then increment numMerged
• otherwise increment codeLengths[symbol] and then symbol

The next iteration has to look at the first 2*numMerged table entries.

Let’s go step-by-step through the example – as mentioned before we start with the bottom row.


The code length of all symbols was set to zero.

What happened ? We looked at ten values of iteration 3 of the first phase:

1. a 1 which wasn’t bold ? codeLength[0] = 1 and then symbol = 1
2. another 1 which wasn’t bold ? codeLength[1] = 1 and then symbol = 2
3. a 2 which is bold ? numMerged = 1
4. a 6 which wasn’t bold ? codeLength[2] = 1 and then symbol = 3
5. a 8 which is bold ? numMerged = 2
6. a 10 which wasn’t bold ? codeLength[3] = 1 and then symbol = 4
7. a 18 which is bold ? numMerged = 3
8. a 20 which wasn’t bold ? codeLength[4] = 1 and then symbol = 5
9. a 46 which is bold ? numMerged = 4
10. a 270 which wasn’t bold ? codeLength[5] = 1 and then symbol = 6

Somehow that wasn’t very exciting … all code lengths changed from zero to one.


Because the final value of numMerged is 4, we look at the first 4*2=8 values of the second-to-last row.


Its content was (just a copy, I stroke through irrelevant entries):

This time we cope only with three bold entries and five non-bold.


That means numMerged = 3 and the code length of all-but-the-last symbol becomes 2.


That last symbol, which had the highest count, suddenly gets assigned a lower code length than all the other symbols.

Again, a copy of phase 1’s iteration 1 (where only 2*numMerged = 6 will be handled):

There are two bold entries (merged packages) and four non-bold.


You probably already understand that the first four symbol’s code length needs to be incremented and


we will look at the first 2*numMerged = 4 numbers of the final row (the top row).

Obviously there can’t be any bold values.


The first four symbol’s code length is incremented again. Let’s take a look at the code lengths of each step:

That’s it ! The bottom code contains the final code lengths.


No symbol’s number of bits is higher than maxLength=4 and the Kraft-McMillan inequality holds true as well: 2^-4 + 2^-4 + 2^-4 + 2^-4 + 2^-2 + 2^-1 = 1.


The algorithm is guaranteed to create optimal code lengths for a prefix-free code. No other combination of code lengths will be better.

I left out any theoretical stuff, such as proofs etc., and skipped practical optimizations to keep things short and sweet.


Take a look at my code (click below) or read the scientific papers to learn more details.

show

packagemerge.c


// //////////////////////////////////////////////////////////
// packagemerge.c
// written by Stephan Brumme, 2021
// see https://create.stephan-brumme.com/length-limited-prefix-codes/
//

#include "packagemerge.h"
#include // malloc/free/qsort


// ----- package-merge algorithm -----

// to me the best explanation is Sebastian Gesemann's Bachelor Thesis (in German only / University of Paderborn, 2004)

// data types (switching to unsigned int is faster but fails if sum(histogram) > 2^31 or maxLength > 31)
typedef unsigned prolonged prolonged BitMask;
typedef unsigned prolonged prolonged HistItem;

/// compute dinky prefix code lengths according to Larmore/Hirschberg's equipment-merge algorithm
/- histogram must be in ascending pronounce and no entry must be zero
- the characteristic rejects maxLength > 63 but I don't look any gleaming reasons you'd desire a elevated restrict ...
@param maxLength maximum code dimension, e.g. 15 for DEFLATE or JPEG
@param numCodes quantity of codes, equals the array dimension of histogram and codeLength
@param A [in] how in most cases each and every code/image develop into as soon as found out [out] computed code lengths
@end result proper maximum code dimension, 0 if error
*/
unsigned char packageMergeSortedInPlace(unsigned char maxLength, unsigned int numCodes, unsigned int A[])
{
// skip zeros
while (numCodes > 0 && A[0] == 0)
{
numCodes--;
A++;
}

// at the least one code desires to be in employ
if (numCodes == 0 || maxLength == 0)
return 0;

// one or two codes are repeatedly encoded with a single bit
if (numCodes <= 2)
{
A[0] = 1;
if (numCodes == 2)
A[1] = 1;
return 1;
}

// A[] is an input parameter (stores the histogram) as well as
// an output parameter (stores the code lengths)
const unsigned inthistogram = A;
unsigned intcodeLengths = A;

// my allround variable for various loops
unsigned int i;

// check maximum bit length
if (maxLength > 8*sizeof(BitMask) - 1) // 8*8-1 = 63
return 0;

// at the least log2(numCodes) bits required for every and every legit prefix code
unsigned prolonged prolonged encodingLimit = 1ULL << maxLength;
if (encodingLimit < numCodes)
return 0;

// need two buffers to direction of iterations and an array of bitmasks
unsigned int maxBuffer = 2 numCodes;
// allocate memory
HistItempresent = (HistItem*) malloc(sizeof(HistItem) maxBuffer);
HistItemprevious = (HistItem*) malloc(sizeof(HistItem) maxBuffer);
BitMaskisMerged = (BitMask*) malloc(sizeof(BitMask) maxBuffer);

// initial payment of "previous" is a straightforward replica of the sorted histogram
for (i = 0; i < numCodes; i++)
previous[i] = histogram[i];
unsigned int numPrevious = numCodes;
// no must initialize "present", it is entirely rebuild each and every iteration

// withhold word which applications are merged (compact bitmasks):
// if equipment p develop into as soon as merged in iteration i then (isMerged[p] & (1 << i)) != 0
for (i = 0; i < maxBuffer; i++)
isMerged[i] = 0; // there are no merges before the first iteration

// the last 2 packages are irrelevant
unsigned int numRelevant = 2 numCodes - 2;

// ... and preparation is finished

// //////////////////////////////////////////////////////////////////////
// iterate through potential bit lengths while packaging and merging pairs
// (step 1 of the algorithm)
// - the histogram is sorted (prerequisite of the function)
// - the output must be sorted, too
// - thus we have to copy the histogram and every and then insert a new package
// - the code keeps track of the next package and compares it to
// the next item to be copied from the history
// - the smaller value is chosen (if equal, the histogram is chosen)
// - a bitmask named isMerged is used to keep track which items were packages
// - repeat until the whole histogram was copied and all packages inserted

// bitmask for isMerged
BitMask mask = 1;
unsigned char bits;
for (bits = maxLength - 1; bits > 0; bits--)
{
// ignore closing ingredient if numPrevious is atypical (can't be paired)
numPrevious &= ~1; // bit-twiddling trick to clear the bottom bit, same as numPrevious -= numPrevious % 2

// first merged equipment
present[0] = histogram[0]; // a sum can't be smaller than its system
present[1] = histogram[1]; // therefore it is very unlikely to search out a equipment at index 0 or 1
HistItem sum = present[0] + present[1]; // same as previous[0] + previous[1]

// replica histogram and insert merged sums whenever that you may perhaps perchance perhaps presumably be also enlighten of
unsigned int numCurrent = 2; // present[0] and present[1] had been already establish of dwelling
unsigned int numHist = numCurrent; // we took them from the histogram
unsigned int numMerged = 0; // but thus a long way no equipment inserted (on the opposite hand, it is precomputed in "sum")
for (;;) // end/damage is within the loop
{
// the subsequent equipment isn't higher than the subsequent histogram merchandise ?
if (numHist < numCodes && histogram[numHist] <= sum)
{
// copy histogram item
current[numCurrent++] = histogram[numHist++];
continue;
}

// okay, we have a package being smaller than next histogram item

// mark output value as being "merged", i.e. a package
isMerged[numCurrent] |= mask;

// store package
current [numCurrent] = sum;
numCurrent++;

// already finished last package ?
numMerged++;
if (numMerged 2 >= numPrevious)
damage;

// precompute subsequent sum
sum = previous[numMerged 2] + previous[numMerged 2 + 1];
}

// make sure each and every code from the histogram is included
// (relevant if histogram may perhaps be very skewed with a pair of outliers)
while (numHist < numCodes)
present[numCurrent++] = histogram[numHist++];

// put together subsequent conceal
conceal <<= 1;

// performance tweak: abort as soon as "previous" and "current" are identical
if (numPrevious >= numRelevant) // ... at the least their relevant system
{
// fundamentally a bool: FALSE == 0, TRUE == 1
char keepGoing = 0;

// review each and every arrays: if they're same then end
for (i = numRelevant - 1; i > 0; i--) // collisions are presumably at the pause
if (previous[i] != present[i])
{
keepGoing++;
damage;
}

// early exit ?
if (keepGoing == 0)
damage;
}

// swap pointers "previous" and "present"
HistItemtmp = previous;
previous = present;
present = tmp;

// no must swap their sizes because finest numCurrent wanted in subsequent iteration
numPrevious = numCurrent;
}

// shifted one bit too a long way
conceal >>= 1;

// withhold finest isMerged
free(previous);
free(present);

// //////////////////////////////////////////////////////////////////////
// tracking all merges will create the code lengths
// (step 2 of the algorithm)
// - analyze each and every bitlength's conceal in isMerged:
// a "pure" image => amplify bitlength of that image
// a merged code => upright amplify counter
// - end if no more merged codes found out
// - if m merged codes had been found out then finest word
// the most most considerable 2*m system within the subsequent iteration
// (because finest they fashioned these merged codes)

// reset code lengths
for (i = 0; i < numCodes; i++)
codeLengths[i] = 0;

// initiate with examining the most most considerable 2n-2 values
unsigned int numAnalyze = numRelevant;
while (conceal != 0) // stops if nothing but symbols are found out in an iteration
{
// quantity of merged applications seen thus a long way
unsigned int numMerged = 0;

// the most most considerable two system must be symbols, they may be able to't be applications
codeLengths[0]++;
codeLengths[1]++;
unsigned int image = 2;

// glimpse at applications
for (i = image; i < numAnalyze; i++)
{
// check bitmask: not merged if bit is 0
if ((isMerged[i] & mask) == 0)
{
// we have a single non-merged symbol, which needs to be one bit longer
codeLengths[symbol]++;
symbol++;
}
else
{
// we have a merged package, so that its parts need to be checked next iteration
numMerged++;
}
}

// look only at those values responsible for merged packages
numAnalyze = 2 numMerged;

// note that the mask was originally slowly shifted left by the merging loop
mask >>= 1;
}

// closing iteration can't bear any merges
for (i = 0; i < numAnalyze; i++)
codeLengths[i]++;

// it's a free world ...
free(isMerged);

// first symbol has the longest code because it's the least frequent in the sorted histogram
return codeLengths[0];
}


// the following code is almost identical to function moffat() in moffat.c


// helper struct for qsort()
struct KeyValue
{
unsigned int key;
unsigned int value;
};
// helper function for qsort()
static int compareKeyValue(const voida, const voidb)
{
struct KeyValueaa = (struct KeyValue*) a;
struct KeyValuebb = (struct KeyValue*) b;
// negative if a < b, zero if a == b, positive if a > b
if (aa->key < bb->key)
return -1;
if (aa->key > bb->key)
return +1;
return 0;
}


/// same as sooner than but histogram might be in any pronounce and may perhaps perchance perhaps simply have zeros, the output is kept in a dedicated parameter
/- the characteristic rejects maxLength > 63 but I don't look any gleaming reasons you'd desire a elevated restrict ...
@param maxLength maximum code dimension, e.g. 15 for DEFLATE or JPEG
@param numCodes quantity of codes, equals the array dimension of histogram and codeLength
@param histogram how in most cases each and every code/image develop into as soon as found out
@param codeLength [out] computed code lengths
@end result proper maximum code dimension, 0 if error
*/
unsigned char packageMerge(unsigned char maxLength, unsigned int numCodes, const unsigned int histogram[], unsigned char codeLengths[])
{
// my allround variable for assorted loops
unsigned int i;

// reset code lengths
for (i = 0; i < numCodes; i++)
codeLengths[i] = 0;

// count non-zero histogram values
unsigned int numNonZero = 0;
for (i = 0; i < numCodes; i++)
if (histogram[i] != 0)
numNonZero++;

// reject an empty alphabet because malloc(0) is undefined
if (numNonZero == 0)
return 0;

// allocate a buffer for sorting the histogram
struct KeyValuemapping = (struct KeyValue*) malloc(sizeof(struct KeyValue) numNonZero);
// replica histogram to that buffer
unsigned int storeAt = 0;
for (i = 0; i < numCodes; i++)
{
// skip zeros
if (histogram[i] == 0)
continue;

mapping[storeAt].key = histogram[i];
mapping[storeAt].payment = i;
storeAt++;
}
// now storeAt == numNonZero

// invoke C regular library's qsort
qsort(mapping, numNonZero, sizeof(struct KeyValue), compareKeyValue);

// extract ascendingly ordered histogram
unsigned intsorted = (unsigned int*) malloc(sizeof(unsigned int) numNonZero);
for (i = 0; i < numNonZero; i++)
sorted[i] = mapping[i].key;

// sprint equipment-merge algorithm
unsigned char end result = packageMergeSortedInPlace(maxLength, numNonZero, sorted);

// "unsort" code lengths
for (i = 0; i < numNonZero; i++)
codeLengths[mapping[i].value] = sorted[i];

// let it scoot ...
free(sorted);
free(mapping);

return end result;
}


Kraft-McMillan Inequality

In a single among the closing sentences I talked about the Kraft-McMillan inequality (each and every so again and again McMillan is forgotten).


It is core message is: if sum(2^-codeLength[0...numCodes]) then a prefix-free code exists.