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.
- There must be a way to check if an item belongs to the set and it must be rather fast.
- Generation of the compressed set may be slow.
- If an item was present in the uncompressed set, then it must show positive in the compressed set.
- 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).