Modified Adaptive Huffman Coding

This repository contains an implementation of the Modified Adaptive Huffman Coding algorithm for large alphabets (whole words) as described in Mikhail Tokovarov’s 2017 paper.

📄 View the Research Paper

---

Chat-Huffman-Py

A modern Python 3 CLI chat application that compresses every message with a modified Adaptive Huffman Coding algorithm before it hits the wire and decompresses it on arrival – saving bandwidth while remaining completely transparent to users.

---

Features

• Word-level adaptive Huffman encoding with dedicated NCW (New-Coming-Word) and NYT (Not-Yet-Transmitted) leaves.
• Fully asynchronous TCP chat server supporting multiple clients.
• Lightweight CLI client (pure standard library).
• Zero third-party runtime dependencies.

---

📝 Introduction

Adaptive Huffman Coding dynamically updates its code tree as it processes input. The classic FGK algorithm uses a single NYT (“Not Yet Transmitted”) node for both indicating where to attach new symbols and signaling their arrival. Tokovarov’s modified approach introduces a separate NCW (“New‑Coming Word”) node:

1. NYT node — marks where in the tree new symbols (words) are inserted.
2. NCW node — signals that the next bits are the raw ASCII representation of a brand‑new word.

By treating whole words as symbols, this method achieves better compression on natural language text, and the separate NCW node reduces overhead when new words arrive frequently.

🖼️ Visual Comparison: Traditional vs Modified Huffman Tree
Note how NCW separates out new word logic from insertion point.

---

📖 Background & Algorithm Overview

1. Tree Structure
   • Each node has a weight, key number, and optionally stores a word.
   • The NYT leaf always has weight 0 and the smallest key.
   • The NCW leaf also starts with weight 0 and is used solely to mark new‑word signals.

🖼️ Tree Example: Word-Based Huffman Tree
Shows how the word-level tree evolves as new tokens are added

2. Encoding

   • If a word already exists in the tree, output its current code (path from root) and update the tree.
   • Otherwise:
     1. Output the NCW node’s code.
     2. Update the NCW node’s weight.
     3. Output the word’s ASCII bytes (8‑bit each) followed by a delimiter.
     4. Insert the new word under the old NYT node and update its weight.

3. Decoding

   • Read bits until you match a leaf’s code:
     • If it’s a normal leaf, recover the word and update the tree.
     • If it’s NCW, update NCW, then read 8‑bit ASCII chunks until delimiter, reconstruct the new word, insert it, and update.

---

📊 Performance & Compression

The following figures demonstrate the bit-efficiency of this model vs classical Huffman variants.

🖼️ SOBR Comparison (Sent-to-Original Bits Ratio)

🖼️ SSOBR Delta Across Variants