1
2
3
4
5
6
7
8
9

1. Sort symbols first by increasing length, then within each length, by symbol value
2. codeword = 0 // start at 1-bit codeword 0
3. Then do
    foreach symbol in symbols
        // lengthen code
        while bitLength of codeword < bitLength of symbol codeword
            append 0 to codeword
        set leaf codeword = codeword
        add 1 to codeword

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

firstCodewordOnRow = 0 // 0 codeword
symbolFound = false
tableIndex  = point to table start
while not symbolFound
    numberOfCodes = read from table
    if numberOfCodes > 0 AND accumulator - firstCodewordOnRow < numberOfCodes
        itemIndex   = accumulator - firstCodewordOnRow
        tableIndex += itemIndex * BitsPerSymbol // skip to symbol
        symbol      = read BitsPerSymbol
        symbolFound = true
    else
        firstCodewordOnRow += numberOfCodes

        assert accumulator < 0x80000000 // catch overflows!
        accumulator = 2*accumulator + read bit from table // accumulate bits
        firstCodewordOnRow <<= 1

        // next entry
        tableIndex += numberOfCodes * BitsPerSymbol

1
2
3
4
5
6
7
8
9

1. Number of symbols encoded so decompressor knows when to stop
2. Bits per symbol (ASCII needs 7, for example, shortening many later values)
3. The table, which consists of 
   1. Bits per code length to tell how many bits are in each code length transmitted
   2. Minimum code length present
   3. Maximum code length present
   4. Then for each codeword length in increasing order, 
      4a. transmit a count of such codewords
      4b. transmit that many symbols in increasing order.

1
2
3
4
5
6
7
8

Assert value < n
k = BitsRequired n
// u = number of unused codewords
u = (1U << k) - n 
if value < u
    Write  (value) in k-1 bits
else
    Write (value + u) in k bits

1
2
3
4
5
6
7
8
9

k = BitsRequired n
// u = number of unused codewords
u = (1U << k) - n; 
x = Read k-1 bits
if x >= u 
    // need another bit
    x = 2 * x + Read 1 bit
    x -= u
return x

1
2
3
4
5
6
7
8

b = BitsRequired m
n = value
q = n/m     
r = n%m
for i = 1 to q
    Write 1
Write 0
write truncated code (r,m)

1
2
3
4
5

q = 0
while Read(1) == 1
    ++q
r = read truncated code m
return q * m + r

1
2
3

1. L = number of bits to store N > 0. Note L>0
2. Write L-1 0 bits, then a 1 bit.
3. Write N using L-1 bits (strips off the highest 1 bit of N

1
2
3
4
5

1. L1 = number of bits to store N > 0. Note L1 > 0
2. L2 = number of bits to store L1. Note L2 > 0
3. Write L2-1 0 bits
4. Write the L2 bit representation of L1, which starts with a 1.
5. Write L1-1 bits of N, stripping of the highest 1.

1
2
3
4
5
6
7
8
9

value = N
stack = new Stack<int>
while value != 1
    stack.Push(value);
    value = (BitsRequired value32) - 1
while stack not empty
    v = statck pop
    Write v in BitsRequired for v
Write 0 // terminates the value

1
2
3
4
5
6
7
8

n = 1
do
    b = Read 1
    if b != 0
        t = Read n
        n = (1U << n) + t
    while b != 0
return n

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

Recurse(n, k)
    if n < (1 << k)
        Write n in k bits
    else
        m = FloorLog2(n)
        Recurse(m - k, k)
        Write n in m + 1 bits

Encode(value,k)
    m = BitsRequired(value)
    Recurse(m,k)
    Write(0)
    Write(value in m bits

1
2
3
4
5
6
7
8

Decode(k)
    v = Read k bits
    while true
        b = Read 1 bit
        if (b == 0) // end of chain
            return Read v bits
        v = v + k
        v = (1<<v) + Read v bits

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

store number of entries if desired
b1 = BitsRequired(data[0])
store initial number of bits b1 if desired
Write(data[0])
for i = 1 to data.Count-1
    d = data[i]
    b2 = BitsRequired(d)
    if (b2 <= b1)
        // b1 is enough bits, signal with a 0
        Write(0)
        Write(d,b1)
    else
        // b2 requires more bits, tell how many
        for ik = 0; ik < b2-b1; ++ik
            Write(1)
        Write(0,1)         // end of bit count
        Write(d, b2-1)     // strip off leading '1'
    b1 = BitsRequired(d)   // for next pass

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

decode number of entries if stored
decode initial number of bits b1 if stored
xi = Read(b1)  // initial value
output(x1) to user
while more to decode
    decision = Read(1)
    if (decision == 0)
        // bi is <= b(i-1), so enough bits
        xi = Read(b1)
    else
        // bi is bigger than b(i-1), must increase it
        delta = 0
        do
        {
            decision = Read(1)
            delta++
        } while decision != 0
        b1 += delta
        xi = Read(b1 - 1); 
        // xi has implied leading 1, so reinsert it
        xi |= 1U << (int) (b1-1)
    output xi to user
    b1 = BitsRequired(xi)  // for next pass

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

// write value in chunks of possible changing size
EncodeLomont1 (value, chunkSize, deltaChunk)
    mask = (1U << chunkSize) - 1
    while value32 >= (1 << chunkSize)
    
        Write 1 // single bit - denotes another chunk coming
        Write (value & mask) in chunkSize bits
        value >>= chunkSize // shrink value
        mask = (1U << chunkSize) - 1 // new mask

        if deltaChunk != 0
            chunkSize += deltaChunk // cahange chunksize
            if chunkSize <= 0
                chunkSize = 1 // do not allow non-positive chunk sizes

    Write 0 in one bit - marks last chunk
    Write value in chunkSize bits
```C#

Decoding is easy.

### Conclusion
There is a large literature on such items. See Salomon's [Handbook of Data Compression](http://www.springer.com/us/book/9781848829022) for a solid overview.

TODO - nice table here

## Arithmetic compression
Huffman compression allocates an integral number of bits per symbol, which is optimal as long as the frequency of each symbol is a rational number with a power of 2 as denominator (because each bit effectively divides a probability by 2), but is not optimal for, say, a sequence of A's and B's here p(A) = 1/3 and p(B) = 2/3. (This is because 1/3 is non-terminating in binary). To get optimal symbol compression in such cases arithmetic compression effectively allocates partial bits to symbols.

Note however Huffman is very good in practice and rarely is arithmetic compression needed. But it's a useful tool.

### Shannon entropy
What is meant by optimal compression? At the symbol level, not taking account into larger patterns, a concept called Shannon Entropy quantifies the optimum. For symbols $a_1,a_2,...,a_m$ with probabilities $p_i = p(a_i)$, the **Shannon Entropy**.

$$\sum_{i=1}^m - p_i \log_2 p_i$$

For example if there are 2 symbols in the alphabet, each with likelihood 1/2, the Shannon Entropy is 

$$\sum_{i=1}^2 - \frac{1}{2} \log_2 \frac{1}{2} = \frac{1}{2}+\frac{1}{2}=1$$

which matches the intuitive notion that each bit requires one bit to send on average. However, suppose the two symbols occur with probability $1/8$ and $7/8$, then the Shannon Entropy is **0.54356**, much less than one. This means it takes less than a bit, on average, to store a bit. 

### Main idea
Arithmetic compression works by representing a stream of symbols as a real number between 0 and 1, where an ever shrinking interval represents the symbols seen so far. To illustrate with two symbols with probabilites $p(A)=1/3$ and $p(B)=2/3$, imagine them laid end to end: 

1
2

If the first symbol is A, then the real number will lay in the first part, else if B, in the B range. So how to encode more symbols? Subdivide the current interval with the same ratios as before (or changing if doing adaptive probabilities). Here is a few steps, with the interval stretched visually to see it, encoding ABBA (and tracking the high = 1 and low = 0 ends of the interval):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

So after encoding the symbols ABBA with the given probabilities, every number in the range [5/27,19/81] represents this stream. A decoder, given the probabilities, and number of symbols and any number in this range, can decode this string.

The problem with this simple variation is that as the stream of symbols gets longer and longer, the range gets smaller and smaller, requiring longer and longer numbers to store the endpoints. Fortunately there is a clever integer way to implement this, only using fixed length integers.


### Integer version
Here is how the integer version works, using 32-bit integers for concreteness.

Instead of probabilities we'll use counts C(S) of each symbol S, and the sum of the counts, called total.

Then let low(S) be the sum of all counts up to but not including S, and high(S) be the sum including S. These numbers, divided by total, represent the probability range.

Treat the real number range [0,1] as the integer range [0,2^31] (we don't use the last bit to allow certain calculations, below). Represent the current range as [low, high), where the right integer is one less than the max range (open ended).

Initialize the high and low to 

1
2

Then, given symbol S, update the range via

1
2

This squeezes the endpoints together, and would eventually make them too close and step would become 0, losing information. So the trick is to output known bits and rescale the integers. This happens if high < 1/2, when it is known the range is in the lower half, so we can output a 0 bit, or when 1/2 < low, when the range stays in the high half, when we can output a 1 bit. Then we stretch the range by a factor of 2. This looks like

1
2

This leaves one last problem - what if the range is shrinking, but overlaps the halfway mark? This is handled by ensuring the range never gets too small, and delaying the decision on which side the range lands in, by discarding a bit, incrementing a counter to track it, and continuing. This looks like 

1
2

So we add to the initialization setting scaling to 0. Finally, we need to output these scaling bits when relevant, which was when we knew which half we were in, so rewrite the first routine and merge to get an encoder.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

This can overflow if the range shrinks more than 2^32 times without choosing a half, since scaling can overflow. But it's unlikely, and can be checked if needed. 

The decoder does the same work. Here are example working algorithms:


This is an implementation for 32 bit architectures. The constants representing the 1/4, 1/2, 3/4, and the entire interval can be changed for other sizes.

Header:
 - number of symbols in stream
 - counts table (full or sparse). 1 bit denotes full (0) or sparse(1) table present
    - Both tables start with: 
        - min+1 and max+1 symbol index are Elias delta encoded
        - number of bits +1 in table Elias delta encoded, allows skipping table
    - Full table (when min to max symbol are mostly present):  
        - list of frequencies (max-min+1 entries) is BASC encoded
    - Sparse table (when many symbols not present, such as LZ77 distance values)
        - min+1 and max+1 symbol index are Elias delta encoded
        - number of bits +1 in table Elias delta encoded, allows skipping table
        - BASC counts
        - BASC symbols
        

All values are unsigned 32 bit integers.

Some constants - use 31 bits to allow multiplication by 2 of open intervals in algorithm without overflow

1

Initialize encoder

1
2

Encode a symbol S

1
2

Finish encoding

1
2

Initialize decoder

1
2
3

Decode a symbol S (after freq table constructed/transmitted). Mostly mimics encoder

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

And there you have it. Arithmetic compression.
        

## LZ compression
Arithmetic and Huffman compression compress symbols, and do not (without higher order probability modeling) take into account order. A static Huffman code used on AAAAAB and AABAA will be the same length. To take into account larger features in symbol streams, patterns are detected and referenced, making much stronger compression possible. Two common ones are LZ77 (after Abraham Lempel and Jacob Ziv in 1977), which looks at past data for a match on upcoming data, and stores info about the match instead of the upcoming data, and LZ78 (Lempel and Ziv, 1978), which builds a dictionary of past seen symbol strings, which outputs dictionary indices to replace longer strings as it compresses. 

These methods underlie all sorts of modern technology from image compression to internet transmission.

Each also has a *huge* amount of variants in the literature.

### LZ77
I'll explain LZSS (Lempel–Ziv–Storer–Szymanski), a decent variant to learn from.  

In this variant, for each next symbol to encode, the history (up to an optional max distance back) is searched for matching the next and upcoming data. If there is a useful match at a **distance** with **length**, then the pair (distance,length) is stored next. If there is no useful match, the symbol itself is stored. To differentiate these cases, a **decision** bit before can signal what the next item is.

All the magic is in the choices of allowed distances, the matching lengths, and tricks to encode each. Since the lengths tend to skew towards smaller numbers, Huffman encoding is often used, but sometimes Golomb coding works better. 

Another trick, instead of coding naive (distance,length) pairs is to encode them as a variant of distance *(maxLength+1)+length with truncated coding. This sometimes saves a bit per item. However, smarter encoding of them  by any more advanced method usually beats this.

### LZ78
LZ78 is like LZ77, in that it uses a dictionary of previous phrases (LZ77 used the recent memory buffer). LZ78 uses a clever method to encode tokens in a dictionary that is built (and optionally flushed) adaptively. Read elsewhere for more details.

### LZCL

LZCL, LZ77 Chris Lomont style, is a version I created using many of the above methods, in order to meet requirements for a specific project. See here http://clomont.com/software/lzcl-an-embedded-compression-library/ for details, or here https://github.com/ChrisLomont/CompressionTools for my GitHub implementation.


## Filtering

### Delta, unique, range
Sometimes data is in such a format that doing some filtering on it first allows better compression. Three basic ones are delta, unique, and range.

### Delta
Replace each value with the difference from the previous one, keeping the first one the same. This sometimes smooths out values, making runs of smaller or zero values. As an extreme example, consider the data $1,2,3,....,1000000$. Compressing this is not as nice as compressing the delta encoded version $1,1,1,...,1$, a run of 1,000,000 1's. Rarely (but sometimes!) does applying multiple delta filters help.

### Unique
This is useful when the symbols occurring are sparse compared to the possible data size. For example, if the integers $1,99,1000000$ occur in some stream, encoding the 1 and the 1000000 should use a different number of bits. A unique filter replaces these with the values $0,1,2$ and a table telling how to decode.

### Range
Similar to the unique filter, a range filter is useful when the data occurs in a certain range $[a,b]$, and shifting all data to make this range be $[0,b-a]$ allows encoding symbols in a smaller number of bits.



# Sample compression tools
The reason I wrote this up was because I needed a specialized compressor for some embedded work, and I found nothing suitable. The main requirements were very small code size and **very** low RAM usage. I needed to fit into FLASH a lot more data than the FLASH allowed uncompressed. Thus the decompressor had access to the compressed data, and only needed to decompress it once in a while to use then discard. I've developed all sorts of specialized algorithms over the years, including many compression algorithms, and this time I decided to take the time to write up some notes and create tools for myself to develop such algorithms more quickly. The result is a codebase of pluggable codecs, analysis, and development tools to make future designs happen more quickly.

The result is explained in my article [LZCL: An embedded compression library](http://clomont.com/software/lzcl-an-embedded-compression-library/), with code at GitHub at https://github.com/ChrisLomont/CompressionTools.

Happy hacking!
Chris Lomont