# 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

# PHP Strings: How to Get the Extension of a File

## EXE or GIF or DLL or …

Most of the code chunks I’ve seen about getting a file extension from a string are based on some sort of string manipulation.

```\$filename = '/my/path/image.jpeg'; echo substr(\$filename, strrpos(\$filename, '.') + 1);```

Howerver there is a more elegant solution.

```\$filename = '/my/path/image.jpeg'; echo strtolower(pathinfo(\$filename, PATHINFO_EXTENSION));```

Thus you rely on PHP built in functions and it’s harder to overlook the exact string manipulation approach.

Common question when speaking about web site optimization is: where should I start. As I mentioned before almost every technology used in the building of a web project can be improved. The bad news is that this improvement needs effort and when it comes to changing some code that’s already written that’s bad. The good news, as it exists, is that in the most cases most of the traffic of a site comes by images and/or other media and their optimization doesn’t have to deal with coding and can simply be optimized.

## Optimize every image

The first thing that you can do to improve your site image is to optimize them. Sometimes the files you put on the site as they are JPEG, GIF and PNGs can be improved just by using some software that strips useless information from their headers and using various algorithms to smooth the similar pixels. As you may know in the case of PNG and GIF this is particularly natural. Stoyan Stefanov a lead Yahoo! developer is know as guru when it comes image optimization. You can check more detailed information about software and tools on his blog here. The reality is that you don’t need extra info into the images, as useless information about the camera, which is often setup into the image header, and when it comes to the web that’s really good. In fact according to some researches this can spend you more than 30% of traffic. Continue reading Optimizing the web. Start with the images!

# Optimize your images – improve the performance

## Overview

In a series of articles I’ll share what’s my experience with image optimization. Of course the most images you have the most page weight you have. That’s why optimizing your images should be your primary task.

## Image Formats

First, I’m gonna mention several formats, which everyone of the webdevs are using widely. There are GIF, JPEG and PNG, where PNG can be either PNG8 and PNG24 (PNG32 is also available as name of that format).

What are the differences between them and when to use one or another?

Well some of us just use one or another even without knowing the difference or without thinking about the optimization. I remember when I just put the images in JPEG with no idea what are the other formats before.

In fact all the formats has pros and cons.

## JPEG

The JPEG format can be either progressive or baseline. The difference is that the progressive JPEG can be loaded directly in the browser with very low quality and then to load with better quality. Some experts insist that this is old school, but I don’t think so. When the image is not the required one (think of a wallpaper preview) the user can skip and go to another without waiting the hole image. The baseline JPEG is loading the good quality image but starting from top to bottom. With portions of the image.

### IE and progressive JPEGs

Of course the Internet Explorer 6 don’t support the progressive downloading of an JPEG even if it’s progressive. Well this is no issue till the IE loads the image like a baseline JPEG.

### Which JPEG is progressive and which is baseline

You can certainly make some test to determine which JPEG is progressive and which is baseline, from the loading behaviour in your browser. If you’d like to convert an image to a progressive JPEG or baseline you can use a free open source programs out there in the wild online space. Once they are converted to one or another format you can use them widely. Because most of the tools are comand line open source tools you can automate them on the server where the user uploads it’s images. Now every big image can be converted to be progressive.

### When to use progressive and baseline JPEGs?

Well the tests show that for images small than 10 K best compression you get with baseline, and for bigger images the small size you get is with progressive JPEGs. There’s the rule use the baseline for thumbs and progressive for any other big image.

## GIF

This format is well known from the early ages of the web. It allows transparency and animation. Actually the problem with the GIF images is that they don’t support semi-transparency which is a problem nowadays. Today the web users are used to good quality images and somehow the GIF is not suitable. But it’s still the most used format for icons and of course animations.

### When should I use GIF?

Well as I’ll mention in a while the PNG8 is a better format than GIF for transparent small icons. But if you should use some kind of an animation like ajax loading circle (or bar) the GIF format is suitable for you. Than you must use a GIF.

## PNG

As I said PNG can be either PNG8 or PNG24 (which is also called PNG32). Actually PNG8 acts just like GIF, with the important exception that it supports semi-transparency, but yet again on every browser except IE6. In IE6 the PNG8 is just the same like GIF which is not so bad. If you’d like to use GIF for an icon, you should make it PNG8. There are semi-transparent pixels (except IE6 and above) and you get better experience on other browsers than GIF.

### PNG32 transparency?

In fact PNG32 is not transparent on IE6 (on transparent pixels IE puts some kind of gray pixels). There you can use AlphaImageLoader filter, but that can dramaticaly slow down your browser, so it’s not a good idea.

You should avoid the PNG32 transparent images and the usage of AlphaImageLoader filter.

## Conclusion

For every of these formats there lots of tools that remove system information from the image crash and crunch the files so that they become smaller. They can be automated and used on the server.

Now when you use different formats you can be aware of the differences between them and to use the appropriate ones.