CODEWITHSUNDEEP
performancealgorithmbitmap
user648129
user648129

Reputation:

Best bitmap compression for setting bits randomly

I am looking for Bitmap compression algorithm which can allow me to generate bitmaps by setting random bits and I am concerned about amount of space bitmap takes in RAM e.g.

Uncompressed bitmap to store 1073741824 bits (Around 1 Billion bits) needs around 128 MB of space and I don't have that much space at all. I would like to do this in as much less space (RAM) as possible.

I looked at WAH, EWAH etc (haven't carefully read papers yet) at others but looks like they are stream compressions and setting bits randomly in compressed format of bitmap (while creating it) isn't possible (very expensive operation) e.g. if one wants to set 100th, 200th, 300th it is works, but if requirement is to set 100th, 200th, 105th, 3000th, 1999th then it isn't possible.

The information that which bit is set and which isn't set can only be obtained randomly in my case for all bits e.g. if I am doing some operation 1073741824 times, I need to set any bit based on operation results and they wouldn't be in increasing order.

Is this correct and are there alternatives ?

Summary: Algorithm for creating a compressed bitmap while setting bits randomly. No entropy/pattern information available. Distribution can be anything.

Aim: Best algorithm to save memory. Reduce the memory taken by bitmap while creating it by setting random bits.

Upvotes: 5

Views: 1026

Answers (2)

Daniel Lemire
Daniel Lemire

Reputation: 3618

We are getting good results with Roaring bitmaps: http://roaringbitmap.org/

Upvotes: 4

usr
usr

Reputation: 171216

If no pattern is known beforehand, and you have little working memory, the following should do fine:

Tile the image into small sections (lines or rectangular tiles). The sections should be small enough that you can quickly uncompress, set bits and compress. They should be big enough to provide the encoder with enough data to actually encode (64KB?). You can use any compression algorithm at like, like Deflate or LZMA (7-zip).

Put incoming bits temporarily into a list. Once that list fills up (maybe 1MB of space taken?) you need to copy the bits to the sections of the bitmap. After doing that you can clear the list. The list is just a temporary buffer that allows to batch many updates per section into one decompress-compress cycle.

Before writing out the bits, sort them by section and position. That allows you to clear duplicates and to process all sections just once.

Note, that no guarantees can be made, that compression is even possible. If there are no compressible patterns, it is impossible to compress.

Upvotes: 0

Related Questions