Compression 101

In this blog, we have discussed data compression more than once, but not really about its philosophy. Data compression is seen as an “enabling technology”—a technology helping make things happen—but what makes it so interesting is that it ultimately gives us insights into the very nature of data, of information itself.

Data compression is not, however, simply about “dropping redundant bits” (although it’s a great way of putting it in order to dismiss the matter with non-technical people), because bits very rarely just stand there being very conspicuously redundant¹. No, data compression is about transforming the data into a representation in which there is, after analysis, exploitable redundancy.

Recently, I gave a talk at the LISA, Université de Montréal, entitled Compression 101, introducing the main concepts of data compression, stressing on points I find particularly important.

On Hockey Pools

If you have ever played in Hockey pools (or any other kind of pools) you know that if you do not get a good drawing rank, your chances of winning anything are greatly diminished. So, here’s how a typical pool works. There are pool players that will form “teams” with league players (usually real players from the real leagues, with their standardized scores) from a total of league players.

To form the teams, the players put their numbers in a hat, and the numbers are drawn one by one, determining in which order, in each round, pool players will get to choose their next pick in the remaining league players. That is, if the order drawn is, say, 5, 3, 4, 2, 1, then pool player number 5 gets to choose first, picking one league player, then goes pool player 3, and so on, until all pool players picked a league player, thus completing one round. There are of those rounds so that each pool player has his team of league players.

The Complexity of Containers

One thing that came on topic rather often recently, and especially in connection with Python, was data structure complexity and what kind of performance operations should offer. However, it’s not as simple as it sounds. First, algorithm operations to be performed dictate, to a great extent, what container, or abstract data structure, should be favored.

But sometimes, these data structures lend themselves to alternate implementations that have different run-time and memory complexities. Maybe we should have a look.

Programming Challenge: List Intersection

The problem of computing luminance was rather of a bit-twiddling nature (and some of my readers came up with very creative solutions—far better than my own), and the problem of the Martian calendar was a bit more deductive (and still not solved, though some of the readers came close to a solution); and for the third programming challenge, I propose something a bit more algorithmic/basic data structure in tone.

The problem I propose in this challenge arises in a variety of settings, such in (simple) search engines, but performing it efficiently is not always trivial.