Unit 1 — Data¶

Exercise Practical 1.1 PDF

What is information?¶

Everything a computer does — storing, transforming, transferring (see Hardware) — is done to one thing: information. But what is it?

• Information is anything that has a meaning to us
• Or might lead us to a meaning

"Information is the reduction of uncertainty" — Claude Shannon

Information ≈ Data¶

Careful: data and information are not exactly the same thing.

• Data = the raw symbols (a 0, a letter, a number...)
• Information = data with meaning

The same data can mean very different things — the meaning is ours, not the computer's:

• 24/05 — a date? a score? a code?
• C/Cóndor, 9, 07181 — an address? a licence plate? a password?
• 971 230 470 — a phone number? a lottery ticket?

Data becomes information when we give it context. And information becomes knowledge when we connect it with what we already know and use it to make decisions.

Information can be:

• Numeric (1, 2, 3, ...)
• Alphabetic (A, B, ... Z)
• Alphanumeric (letters, digits and symbols mixed — note that you can't do math on them: A1 is text, not a number)
• Others (CR, LF, ...)

Shannon's mathematics of information¶

In 1948, an engineer at Bell Labs named Claude Shannon published a paper with a modest title — A Mathematical Theory of Communication — and quietly invented the digital age. He asked a question nobody had asked precisely before:

How much information does a message actually contain — and what is the least I need to send it?

No formulas here, just the ideas:

Information = surprise¶

Shannon's core insight: the information in a message is how much uncertainty it removes.

• "The sun rose this morning." → You already knew it. Zero information.
• "Tomorrow's exam is cancelled." → You didn't know that. Lots of information.

The more surprising the message, the more information it carries. Rare events are informative; obvious events are not.

Entropy: average surprise¶

A source of messages (a person, a sensor, a file) has an average level of surprise. Shannon called this entropy:

• A fair coin flip is maximally unpredictable → maximum information for its size.
• A weighted coin (99% heads) is boring → each flip tells you little.
• A source that always says the same thing carries zero information — you can skip it entirely.

Entropy is why some files shrink and others don't: a file that repeats itself a lot has low entropy and is easy to compress; a file that looks like random noise has high entropy and resists compression.

Language is redundant — on purpose¶

Try reading this: Ths sntnc hs n vwls. You could, right?

Natural languages carry far more symbols than strictly needed: predictable letters, grammar that lets you fix typos, repeated phrases. Shannon measured it — English is roughly 75% redundant: delete most letters and a good reader still reconstructs the message.

That redundancy is not waste. It is protection against noise: it is why you can chat in a loud room, why scratched DVDs still play, and why your Wi-Fi works through walls. Shannon showed there is a precise trade-off: redundancy can be spent to fight errors.

Huffman: short codes for common symbols¶

Shannon told us how few bits a message could need. He did not give a practical recipe to get there. That came in 1952, from a student.

David Huffman was a graduate student at MIT. His professor, Robert Fano, offered the class a choice: sit the final exam, or write a term paper on finding the most efficient binary code. Huffman picked the paper, struggled for months, and was about to give up and study for the exam — when he found the answer. His method beat the one his own professor had been working on.

The idea is one you already know from Morse code: the most common letter in English, E, is a single dot, while a rare letter like Q is – – · –. Huffman made that exact:

Huffman coding: give the shortest codes to the most frequent symbols and the longest codes to the rarest ones.

Take the word BANANA. ASCII spends 8 bits per letter, whatever the letter: 6 × 8 = 48 bits. But the letters are not equally common:

The recipe to build the codes: take the two rarest symbols and join them into one group; repeat until everything is joined. Each join is a fork in a tree: going left writes a 0, going right writes a 1.

flowchart TB
    ROOT(["<b>BANANA</b><br>6 letters"]) -->|"0"| A["<b>A</b><br>3 times<br>code 0"]
    ROOT -->|"1"| NB(["<b>N + B</b><br>3 times"])
    NB -->|"0"| N["<b>N</b><br>2 times<br>code 10"]
    NB -->|"1"| B["<b>B</b><br>1 time<br>code 11"]

Now encode it:

B   A  N   A  N   A
11  0  10  0  10  0     →   9 bits instead of 48

Same word, less than a fifth of the bits. And nothing is lost: the receiver gets back exactly BANANA. This is lossless compression — the opposite of lossy compression (JPEG, video streaming), which throws away detail you hopefully won't miss.

The prefix rule: no separators needed¶

Wait. The bit stream 110100100 has no spaces. How does the receiver know where one letter ends?

Look at the codes again: 0, 10, 11. No code is the beginning of another one. This is the prefix rule, and Huffman's tree guarantees it, because every letter sits at the end of its own branch. So the receiver reads bit by bit, and the moment the bits match a code, that letter is done.

1 0 0 1 1 0 0   →   ?

Huffman coding is still everywhere, 70 years later: it is one of the stages inside ZIP, PNG, JPEG and MP3 files.

The deep part: prediction¶

Here is where Shannon's entropy meets Huffman. The best possible code length for a symbol depends on how predictable it is:

• If you can guess the next symbol almost surely, it costs almost nothing to encode — just note "no surprise".
• If the next symbol is a total shock, it costs a lot.

Flip that statement around and you get the central idea of this section:

Modern compressors are built exactly like this:

• ZIP keeps a sliding window of recent data and encodes "repeat what appeared 50 bytes ago" instead of the bytes themselves.
• PNG tries to predict each pixel from its neighbours and encodes only the difference.
• Video codecs predict each frame from the previous one and encode only what changed — which is why a video of a static scene is tiny and a confetti storm is huge.

In every case: the better the model predicts, the fewer bits are needed. A perfect predictor compresses to almost nothing.

And AI? A language model is a compressor¶

Now connect the dots. What does an LLM (a system like ChatGPT) train to do?

Given all the text so far, predict the next word (more precisely, the next token).

That is literally the objective of a compressor — guess the next symbol, only encode the surprise. The difference is the model:

Train a language model, then use it as a compressor: it beats ZIP on text by a huge margin. And it must understand something about the content to do it — you cannot predict "mat" without some notion of how cats, sitting and sentences work.

So the chain is:

more predictable data → more compressible
better model → better predictions → better compression
best known text predictors → AI language models

One caveat to keep us honest: an LLM is a lossy compressor of the internet — it keeps the patterns, not the exact pages. Ask it for a quotation and it will give you something plausible, not necessarily something exact. Compression without the guarantee of getting back the original.

Key takeaways¶

• Data = raw symbols; information = data with meaning — and the meaning is added by us, never by the machine.
• Information = reduction of uncertainty (Shannon): surprise is measurable, and the unit is the bit.
• Computers speak binary because two states are impossible to confuse: cheap and reliable.
• 8 bits = 1 byte = 256 values = one ASCII character.
• Capacity is measured in bytes, speed in bits per second: divide by 8 before comparing.
• Huffman coding gives short codes to frequent symbols; the prefix rule means no separators are needed.
• Compression = prediction: pay bits only for the surprise. Huffman does it with letter frequencies; an LLM does it with a model of the whole world.

Quick check¶

Test yourself: