Home
Shoelacer's Design
Initial tests with simple dictionary schemes ruled it out of my selection. Dictionary sizes for reasonable compression performance grew too large for my satisfaction. On the other hand, simple order-1 context modelling had impressive performance, and although naive model storage required far too much space, drastic reductions were easy to imagine. Thus the context modeling scheme was selected, and from there, space savings were engineered (sometimes at the cost of compression performance) until what became Shoelacer.
Shoelacer generates its models based on blended order-2 and order-0 context models. Specifically, the model consists of 512 contexts indexed by a perfect hash, with one byte representing each entry per module containing a checksum of the context bytes, and the index of a quantized distribution. The number of unique distributions typically ranges from 16 to 64. They are represented so that they are convenient for Rice coding with varying power-of-two divisors. If the checksum fails to match the context hashed to it, a default "order-0" distribution is used, which may or may not be used by contexts normally. Steps Shoelacer performs:
...ver the lazy do... Context modeling is very powerful, and has been used in many high-performance compression algorithms (e.g. all the prediction by partial matching variants), but it also has a few problems. The most notable of which is the unseen-context problem. What do you do if you're faced with a context you've never seen before? This is the extreme of another problem: What do you do if you're faced with a context that you've only seen once or a few times before? In both cases, there's too little information acquired to make a good decision. The obvious heuristic would be to encode the symbol literally (that is, as if using an order-(-1) context model). The extension of this is to use a lower order model in which the lower order context has been observed a sufficient number of times. (e.g. look at the last two characters instead of 3) This is called blending. While even order-1 context modeling can lead to good compression performance, I wanted at least a bit better. The danger is that with higher order context models, blending becomes more necessary, and complexity increases accordingly. Also, with higher orders, more contexts are required, so only a small portion of the 'context space' can be represented. After experimentation, order-2 appeared to be a reasonable compromise.
Why is this not optimal elimination? Because unknown contexts are treated as order-0. If the distribution of symbols after an order-2 context is identical to the order-0 context, storing this context gains us nothing, and we've duplicated the order-0 information in memory. Actually, Shoelacer mitigates the latter problem, but the context is still explicitly stored needlessly.
Instead, I borrow from the domain of lossy compression to compress the probability distributions. Treating the distributions of the top 512 contexts, Shoelacer performs vector quantization via the LBG algorithm using a Euclidean metric. Put another way, many of the probability distributions are very similar. One tool to reduce a larger set of vectors (one possible representation of the distributions) into a smaller set is vector quantization. The number of points quantized to is a power of two between 1 and 128 inclusive.
A couple of interesting aspects arise. First, the algorithm must actually produce distributions. That is, the sum of all the entries must be 1. The LBG algorithm relies on iterative averaging of distributions, and the average of a collection of distributions is provably a distribution, so this requirement is met. Secondly, the distortion we wish to minimize is not a actually a metric! None-the-less, even when a pseudo-metric was used that was far more representative of actual entropy, the results were weaker than using the Euclidean metric. Also, through experimentation, a post-quantization step which takes entropy entirely into consideration and readjusts the quantization points was found to increase compression performance. However, a better quantization scheme likely exists.
The 'unknown' symbol is an escape for any symbol which is not accounted for in this representation of a distribution. The data table is sorted by frequency of symbol. The 'distribution scheme' is an indicator of how to interpret the data table. Initially, the various 'distribution schemes' supported were Elias gamma and Rice coding. After experimentation, Elias gamma coding was found to be mostly unused, and thus now this byte serves to represent the length of the Rice coding divisor. (I call it the 'base', but this is confusing due to the generic nature of Golomb-Rice coding, and its actual use in literature.)
Perfect hashing lends itself well to these circumstances. Bob Jenkins has implemented a perfect hash generation algorithm which generates hashes in the style of a^tab[b] where (a,b) is a unique pair of hashes of the index. In our case, where p is the previous character, and c is the current character, a=p; b=p+c; are the "hashes". They seem sufficient for a wide variety of data, despite their simplistic and mocking nature compared to what a canonical hash function should be. The table consists of 256 short (2-byte) integers. The result of running the hash algorithm is this table which maps each pair (a,b) to a unique number between 0 and 511 inclusive. These are used as the indices to a table containing an entry per each stored context. The entries are one byte long. The lower bits of the byte are used to store which distribution is used. The high bits are used as a checksum (the low bits of 'b') to reduce the number of false positives matched to the entry. Consequently, as the number of distributions increases, so does the number of false positives. False positives decrease compression performance, while the more distributions increases it. Finally, the distributions themselves have a table of indices (2-byte integer entries, one per distribution) to where, from the model data start, each compact representation begins.
Compression performance ranges from 3.4 to 4.6 bits per byte on data including executables, books, and databases that I've tested in varying degrees.
Hosting for this project is provided by: |