3

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).

  • 1
    It's unclear how your data compression problem is different from any other ordinary data compression problem. Can you provide a reasonable, real-world example of such compression? – Robert Harvey Sep 25 '15 at 22:45
  • Does the set have to be compressed when checking for membership, or can it be expanded to a list by that time? If it must be compressed then the random number generator approach will not work, (it would not work anyway, but that's besides the point) because a few thousand iterations of a random number generator would not be fast. – Mike Nakis Sep 25 '15 at 22:54
  • 1
    The random number generator approach will not work for a few hundred 64-bit integers (thousands of bits) even if you wait for it until the head death of the universe. – Mike Nakis Sep 25 '15 at 22:55
  • Isn't there any other property of these 64-bit integers that could be exploited? Any relationship between them, any periodicity, any restriction in their range? – Mike Nakis Sep 25 '15 at 22:59
4

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.

5

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.

  • This should be the accepted answer. I can't believe I didn't think of Bloom filters. – LSerni Oct 3 '15 at 23:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.