Sparse set lossy compression algorithm

Question

I am looking for algorithm or idea for the following problem.

Suppose we have a data type, say 64-bit integer. Now we have a relatively small set of such items, say few hundred at most. The simplest way to program that is to have a list of items, that means a sparse set.

Now the problem: I want to compress that list so it is much smaller, possibly losing some information.

Requirements:

1. There must be a way to check if an item belongs to the set and it must be rather fast.
2. Generation of the compressed set may be slow.
3. If an item was present in the uncompressed set, then it must show positive in the compressed set.
4. If an item was absent from the uncompressed set, then it may be present in the compressed set, however probability of such event must be low.

One idea I had: if we have some pseudorandom number generator, then we look for such seed, so that in the first few thousands of iterations all requested items are present. The seed would be the compressed representation. Another idea: neural networks (description will be the representation).

Answer 1

What you are looking for is called a minimal perfect hash. If you have, say, 256 items out of a data space 1024 bit wide, a hash such as MD5 would map them to 128 bit hashes, possibly with collisions.

If you took the last 8 bits of the MD5, you would still get a hash (of sorts), with a much larger risk of collisions.

A minimal perfect hash is a function that maps your 256 tokens into the numbers from 0 to 255, thereby squeezing out the eight bits of information you need.

A trivial "hash" generator would be

if (token == token1) { return hash1; }
if (token == token2) { return hash2; }

and has complexity O(n). I seem to remember that the ideal generator has a much lower complexity of O(log2(n)).

Random searching is indeed one method of generating such a hash function.

You will probably want to check out tools such as this.

Answer 2

Since you allow false positives, you do not need a perfect hash. Instead, you can use a bloom filter. A bloom filter consists of a bit vector and a set of different hash functions.

To add an item to the bloom filter, you has the item with each hash function and use each hash as an index to the bit vector. You then set each addressed bit to true.

To test whether an item is in the set, you use the hash functions to retrieve the corresponding bits from the bit vector. If all those bits are true, the item was probably part of the input.

This approach is quite fast, since hash functions can be very simple. You can use a family of hash functions that are parametrized by some constant to generate your set of hash functions. Together with the bit vector, these parameters make up the stored data.

It is important to choose a sensible relation between the size of the input set n, the size of the bit vector m, the number of hash functions k, and the acceptable rate of false positives p. The relevant math is explained in the linked Wikipedia article. Each input item affects k bits in the bit vector regardless of the size of the item, so considerable space savings are possible when you only use few hash functions.

While a bloom filter allows for a test whether the set contains an item, it is not possible to enumerate all items in a set; this information is lost through the hash functions.