Adaptive Huffman Coding (FGK Algorithm)

A comprehensive Java implementation of Adaptive Huffman Coding using the FGK (Faller–Gallager–Knuth) algorithm. Features single-pass compression, a modular architecture, an interactive Swing GUI visualizer for real-time tree animation, and a built-in test suite.

Algorithm Overview

Unlike standard Huffman coding, which requires two passes over the data (one for frequency counting, one for encoding), the FGK algorithm performs single-pass adaptive encoding. The encoder and decoder maintain synchronized Huffman trees that are updated dynamically as each symbol is processed.

Key Concepts

Concept	Description
NYT Node	Not-Yet-Transmitted sentinel — represents all unseen symbols
Node Numbers	Descending level-order numbering for maintaining the sibling property
Swap Condition	If a node's weight equals another node with a higher number, swap them
Short Code	8-bit ASCII representation for transmitting new symbols

Encoding Rules

1. First symbol: Transmit only its 8-bit short code.
2. New symbol (not first): Transmit NYT code + 8-bit short code, then insert into tree.
3. Existing symbol: Transmit its current Huffman code, then update tree.

FGK Tree Update

After each symbol, traverse from the affected node to the root:

1. Find the node with the same weight and highest node number (swap candidate).
2. Swap the current node with the candidate if found.
3. Increment the node's weight.
4. Move to the parent and repeat.

Features

Feature	Description
Encoder	Single-pass adaptive compression with step-by-step output
Decoder	Synchronized tree reconstruction for perfect round-trip
GUI Visualizer	Interactive Swing application with real-time tree animation
Test Suite	7 automated test cases with round-trip verification
CLI & Interactive	Both command-line arguments and interactive menu modes
Statistics	Compression ratio, space savings, and per-step analysis

Project Structure

adaptive-huffman-fgk/
├── src/
│   ├── AdaptiveHuffman.java    # Main entry point (CLI + interactive menu)
│   ├── Encoder.java            # FGK encoding logic
│   ├── Decoder.java            # FGK decoding logic
│   ├── HuffmanTree.java        # Adaptive tree with insert, update, swap
│   └── Node.java               # Tree node (symbol, weight, number, NYT)
├── test/
│   └── AdaptiveHuffmanTest.java # Automated test suite (7 tests)
├── visualization/
│   └── HuffmanTreeVisualizer.java  # Swing GUI with step/auto/decode modes
├── docs/
│   ├── report.tex              # LaTeX technical report
│   └── report.pdf              # Compiled report
├── README.md
├── LICENSE
└── .gitignore

Architecture

┌──────────────────┐     ┌──────────────┐     ┌──────────────┐
│ AdaptiveHuffman  │────▶│   Encoder    │────▶│  HuffmanTree │
│   (Main / CLI)   │     │  (Encoding)  │     │  (FGK Core)  │
└──────────────────┘     └──────────────┘     └──────┬───────┘
                         ┌──────────────┐            │
                         │   Decoder    │────────────┘
                         │  (Decoding)  │     ┌──────────────┐
                         └──────────────┘     │     Node     │
                                              │ (Tree Nodes) │
┌──────────────────┐                          └──────────────┘
│   Visualizer     │──────────────────────────────────┘
│  (Swing GUI)     │
└──────────────────┘

Prerequisites

• Java Development Kit (JDK) 8 or higher

How to Run

1. Compile Everything

javac -d out src/*.java test/*.java visualization/*.java

2. Interactive Mode

java -cp out AdaptiveHuffman

╔═══════════════════════════════════════════╗
║      ADAPTIVE HUFFMAN CODING (FGK)       ║
╠═══════════════════════════════════════════╣
║  1. Encode text from console             ║
║  2. Encode text from file                ║
║  3. Decode binary stream                 ║
║  4. Run test cases                       ║
║  5. Exit                                 ║
╚═══════════════════════════════════════════╝

3. Command-Line Mode

# Encode text
java -cp out AdaptiveHuffman -e "ABCCCAAAA"

# Decode binary stream
java -cp out AdaptiveHuffman -d "0100000101000010..."

# Encode from file
java -cp out AdaptiveHuffman -f path/to/file.txt

# Run test suite
java -cp out AdaptiveHuffman -t

4. Run Tests

java -cp out AdaptiveHuffmanTest

5. Launch GUI Visualizer

java -cp out HuffmanTreeVisualizer

The visualizer provides:

• Step-by-step encoding with tree updates
• Auto-play mode with adjustable speed
• Decode mode for binary stream input
• Real-time statistics (compression ratio, bit savings)
• Console log showing encoding decisions at each step

Test Cases

#	Test	Input	Round-Trip
1	Lecture Example	ABCCCAAAA	✓ PASSED
2	General English	hello world	✓ PASSED
3	Repeated Char	AAAA	✓ PASSED
4	All Unique	ABCDEFG	✓ PASSED
5	Single Char	A	✓ PASSED
6	Special Chars	Hello, World! 123	✓ PASSED
7	Tree Structure	Weight & node verification	✓ PASSED

Academic Context

• Course: DSAI 325 — Introduction to Information Theory
• Institution: Zewail City of Science and Technology
• Semester: Spring 2026 (Mini Project)

License

This project is licensed under the MIT License.