Compressing a set of hash values
Suppose you have a set of k hash values, each n bits long. Can you compress the set into less than kn bits?
It’s not possible to compress a list of hashes into less than kn bits, but you can hash a set into fewer bits.
Suppose you have a set of 230, roughly a billion, 64-bit hashes. Sort the set and look at the size of gaps between elements. You might expect that consecutive items on the list are roughly 234 apart, and so you could reconstruct the list by reporting the first item and the gaps between the rest, which are 34-bit numbers, not 64-bit numbers, a savings of 30 bits per hash.
This doesn’t exactly work, but it’s the kernel of a good idea. We don’t know that the distance between hashes can be represented by a 34 bit number. The gap could be more or less than 234, but we don’t expect it to often be much more than 234. So we use a variable-length encoding such that when the distance between values is on the order of 234, or less, we save bits, but we allow for the distance to be any size.
Applications
What we’ve described is the essence of Golomb-Rice coding. Its implementation in the Bitcoin protocol is referred to as Golomb-Coded Sets (GCS), described in BIP 158. Golomb-Rice coding is also used other applications where the set of values to be compress is are not hashes, such as in lossless auto compression.
Encoding
Let’s go into some detail as to how the distances between sorted values are represented. Suppose you expect the differences to be on the order of M where M is a power of 2. For each difference d, let q and r be the quotient and remainder by M, i.e.
d = qM + r.
Encode q as a unary number, i.e. string of q 1s, and encode r as an ordinary binary number. Then Golomb-Rice coding of d is the concatenation of the representations of q and r. with a 0 in the middle as a separator. Using || to denote string concatenation we have
unary(q) || 0 || binary(r).
In general, unary encoding is extremely inefficient, but we’re betting that q will typically be quite small.
The reason we require M to be a power of 2 is so the representation of r will have a fixed length [1].
Let’s work out an example. Suppose M = 220 and
d = 222 + 123456 = 4 × M + 123456.
Then we write q as 1111 and r as 0011110001001000000 and encode d as the string
111100011110001001000000
Decoding
You can concatenate the encodings of consecutive d values and still be able to unambigiously decode the result. Because the r representations have a constant length, you know when an r ends and the next q begins.
For example, suppose we have the following string of bits.
1110010011001011001011111001000000110010001110011101111000101111011
We decode the string from left to right. We count how many ones we see, skip over a 0, then regarding the next 20 bits as a binary number.
111 0 01001100101100101111 1 0 01000000110010001110 0 11101111000101111011
We see three 1s before the first 0 and so we conclude q1 = 3. We skip over the 0 and read the value of r.
r1 = 01001100101100101111two = 314159.
Next we see a single 1 before the next 0, so q2 = 1. We read the next value of r as
r2 = 01000000110010001110two = 265358.
Next we see a 0, i.e. there are no 1s, and so the final q3 = 0. And we have
r3 = 11101111000101111011two = 979323.
So our reconstructed values of d are
d1 = q1 M+ r1 = 3 × 220 + 314159 = 3459887
d2 = q2 M+ r2 = 1 × 220 + 265358 = 1313934
d3 = q3 M+ r3 = 0 × 220 + 979323 = 979323.
Now these are difference values. We need to know the smallest value m in order to construct the original set of values from the differences. Then the full values are m, m + d1, m + d1 + d2, and m + d1 + d2 + d3,.
Related posts
[1] This is the Rice part. Robert Rice simplified Samual Golomb’s encoding scheme in the special case that M is a power of 2.
The post Compressing a set of hash values first appeared on John D. Cook.
