How compression makes files smaller: a maths EPQ idea
A title to start from
How can a file be made smaller without losing anything, and what is the limit?
Why it works as an EPQ
Huffman coding is a short algorithm with a proof of optimality, and entropy gives a clear limit to test against.
Scope and difficulty
Solid. Solid. Huffman coding and entropy on texts you choose.
The maths
Builds on these A Level topics: Probability · Exponentials and logarithms.
You would learn:
- Prefix codes and binary trees
- Entropy
- Optimality of Huffman codes
One possible plan
- Build Huffman codes by hand for small texts.
- Calculate the entropy and compare average code length with it.
- Implement it and test on English text, code and random data.
- Judge why some files barely compress.
Pitfalls
- Forgetting to count the space needed to store the code table.
- Lossy and lossless compression mixed up.
Where to start reading
- Search for: Huffman coding optimality proof
- Search for: Shannon entropy source coding theorem simple
Making something? Read the artefact guide first.
Frequently asked questions
Is this a good maths EPQ idea?
It can be. We rate it Solid: it needs some new maths learned on your own. Huffman coding and entropy on texts you choose.
What maths does this EPQ use?
It builds on these A Level topics: Probability; Exponentials and logarithms. You would learn: Prefix codes and binary trees; Entropy; Optimality of Huffman codes.
Next step
Turn this idea into your own title, then check it in two minutes.
Check your titleSimilar ideas
- How a neural network learnsHow does a neural network learn, and how much of it is calculus you already know?
- Quick routes for the travelling salesmanHow close can quick methods get to the best route in the travelling salesman problem?
- How computers fake randomnessHow can a computer, which follows rules, produce random numbers, and how random are they?
- Hash collisions and the birthday problemHow likely are two different files to share a hash, and what does the birthday problem say about security?
All maths and computer science ideas · all 93 ideas
Your EPQ must be your own work. How to use help and AI honestly.