This project implements Huffman Coding — a data compression technique — in Java. It was developed as part of the Data Structures and Operating Systems module in 2021.
The application performs both encoding (compression) and decoding (decompression) of strings using a custom-built Huffman tree, simulating real-world compression techniques.
- 📊 Builds a frequency table from input data
- 🌳 Constructs a Huffman tree using custom
LeafandBranchclasses - 🔁 Traverses the tree to generate binary codes for characters
- 📥 Encodes string data into a compressed format
- 📤 Decodes compressed data back to original input
- 🧠 Analyzes time complexity of each function (e.g., O(n), O(n²))
FreqTable()– Generates frequency of characters (O(n))treeFromFreqTable()– Builds Huffman tree with priority queue (O(n²))traverse()– Recursively assigns binary codes to charactersbuildcode()– Builds final encoding mapencode()– Integrates all above methods to compress input
treeFromCode()– Reconstructs Huffman tree from stored codes (O(n²))decode()– Uses the tree to decode the binary stream into original text
- HashMap – Stores character-code mappings
- Priority Queue – Used to construct optimal Huffman tree
- Custom Tree – Built using
LeafandBranchnodes - Boolean Lists – Represent binary paths for each character
A greedy algorithm that assigns shorter binary codes to more frequent characters. It results in efficient lossless data compression.
The report also discusses how data structures and algorithms like:
- Buddy System (memory management)
- Hash Tables (page tables, file systems)
are used in operating systems for efficient data handling.
| Method | Time Complexity |
|---|---|
| Frequency Table | O(n) |
| Tree Construction | O(n²) |
| Tree Traversal | O(n) |
| Encoding/Decoding | O(n), O(n²) |
- Tanenbaum, Modern Operating Systems
- Doeppner, Operating Systems in Depth (2010)
- GeeksForGeeks, Hashed Page Tables in Operating System (2020)
Vickshan Vicknakumaran
University of Brighton
Data Structures & Operating Systems | 2021