# Computer Algorithms: Data Compression with Bitmaps

## Overview

In my previous post we saw how to compress data consisting of very long runs of repeating elements. This type of compression is known as “run-length encoding” and can be very handy when transferring data with no loss. The problem is that the data must follow a specific format. Thus the string “aaaaaaaabbbbbbbb” can be compressed as “a8b8”. Now a string with length 16 can be compressed as a string with length 4, which is 25% of its initial length without loosing any information. There will be a problem in case the characters (elements) were dispersed in a different way. What would happen if the characters are the same, but they don’t form long runs? What if the string was “abababababababab”? The same length, the same characters, but we cannot use run-length encoding! Indeed using this algorithm we’ll get at best the same string.

In this case, however, we can see another fact. The string consists of too many repeating elements, although not arranged one after another. We can compress this string with a bitmap. This means that we can save the positions of the occurrences of a given element with a sequence of bits, which can be easily converted into a decimal value. In the example above the string “abababababababab” can be compressed as “1010101010101010”, which is 43690 in decimals, and even better AAAA in hexadecimal. Thus the long string can be compressed. When decompressing (decoding) the message we can convert again from decimal/hexadecimal into binary and match the occurrences of the characters. Well, the example above is too simple, but let’s say only one of the characters is repeating and the rest of the string consists of different characters like this: “abacadaeafagahai”. Then we can use bitmap only for the character “a” – “1010101010101010” and compress it as “AAAA bcdefghi”. As you can see all the example strings are exactly 16 characters and that is a limitation. To use bitmaps with variable length of the data is a bit tricky and it is not always easy (if possible) to decompress it.

Continue reading Computer Algorithms: Data Compression with Bitmaps

Related to the post with bitmaps with round corners, here’s the source code.

# Flex 3 bitmap with round corners

It is a common question, can it be used a bitmap into Flex with round corners.

Actually the answer is yes, but the formal answer is “No”. Directly imported into the application the bitmap cannot be rounded. The solution is to cast it to bitmap. You can download the source code here.

# Bitmaps in actionscript 3

In actionscript 3 the bitmaps are stored with 4 bytes for each pixel. There are three bytes for RGB and one for the alpha channel. So you should be carefull when passing images to the flash, cause 20×20 pixel image will be using apx. 1600 bytes of RAM, to optimize this send the image as it should appear on stage and do not resize.