Here's a very simple example of compression. It explains what other people have said about using redundancy to achieve compression.
(https://sites.google.com/site/usingaiforbettercompression/)
(And then it has a few quotes from different places about why AI is linked to compression.)
(Google sites is sub-optimal, and when I've finished it I'll host it elsewhere.)
(Also, submitted it here. (http://news.ycombinator.com/item?id=4616442))
EDIT: I'll just paste it here. I need to work on language and tone, apologies for being patronising.
Imagine we have a language with just 4 letters: A, B, C, and D. In this language the frequency probabilities are A = 0.5, B = 0.3, C = 0.15, and D = 0.05
A short sentence in this language may look something like this, after we strip out the spaces. There are 20 characters.
ACABBAABABAACBAADCAB
Now let's represent those letters with carefully chosen numerical values.
A = 0
B = 10
C = 110
D = 111
Our sentence becomes (first with spaces, and then without)
A C A B B A A B A B A A C B A A D C A B
0 110 0 10 10 0 0 10 0 10 0 0 110 10 0 0 111 110 0 10
0110010100010010001101000111110010
These values were chosen because they are unambiguous, even when you remove the spaces. You cannot turn the above collection of 1's and 0's into anything other than the correct sequence.
This uses 34 characters to represent the our sentence. But there's a further step.
We create another table.
00 = q
01 = w
10 = z
11 = x
And again we represent the sentence with the new letters.
0110010100010010001101000111110010
01 10 01 01 00 01 00 10 00 11 01 00 01 11 11 00 10
w z w w q w q z q x w q w x x q z
wzwwqwqzqxwqwxxqz
This is 17 characters. We have saved 3 characters. Obviously this isn't great, but it's just an example to demonstrate the process. You can see from this example why compressing random data can be hard. One feature of randomness is an equal distribution of each possible character. We cannot use redundancy to create our dictionary tables.