0
$\begingroup$

I have an array of distinct integers which I want to save in the most compact manner. I may have to do occasional lookups, deletions, and insertions in this array so the compression algorithm must adjust for such cases. What is the appropriate algorithm/ data structure that I should think of?

Is there anything along the lines of Huffman encoding but for numbers?

$\endgroup$
  • 1
    $\begingroup$ Huffman coding doesn't care about the underlying "character set". However, without knowing something about the distribution of the numbers, it's impossible to suggest any compression scheme. And, for any choice of compression scheme, there will be arrays that can't be compressed at all. Are you sure you want/need to compress? In practical terms, I doubt it's beneficial unless you're literally running out of memory and can't throw more hardware at the problem. $\endgroup$ – David Richerby Aug 30 '18 at 9:03
  • $\begingroup$ @DavidRicherby Huffman encoding works for repeated characters. I know for sure that all my characters are distinct. I am designing a cache and need this mechanism for storing numbers outside the cache. $\endgroup$ – user248884 Aug 30 '18 at 9:05
  • 1
    $\begingroup$ Huffman coding has nothing to do with repeated characters and it works for any byte stream. "All the numbers are distinct" is probably the hardest case and no compression scheme can exploit that alone. If that's literally all you know about the data, no compression scheme will work, on average. $\endgroup$ – David Richerby Aug 30 '18 at 9:12
  • $\begingroup$ Does the order of the elements matter? $\endgroup$ – orlp Aug 30 '18 at 9:12
  • 1
    $\begingroup$ boolean array if the set is compact enough $\endgroup$ – Bulat Aug 30 '18 at 10:52
2
$\begingroup$

If your integers have small difference between them you can use a bitset with an offset. In this way if the difference between the largest and the smallest is n you need n bits + the size of the offset in bits. If your integer set is sparse you can use a sparse bitset implementation like Roaring bitmap .

$\endgroup$

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.