Java Huffman Compressor

File compressor and decompressor based on Huffman coding.

Quick start with Docker

Build the image:

docker compose build app

Compress a file:

docker compose run --rm app /work/compress-test-files/frase.txt

Decompress a .huf file:

docker compose run --rm app /work/compress-test-files/frase.txt.huf

Tests (Docker)

Run all tests:

docker compose run --rm test

Notes:

• Tests run inside a Maven Java 17 container.
• The test service is defined in docker-compose.yml.
• Maven dependencies are cached in the maven-cache Docker volume.
• Tests run on a temporary copy of the project, so they do not leave test artifacts in the host workspace.

How command mode is selected:

• If input ends with .huf, it decompresses.
• Otherwise, it compresses.

Important:

• The project folder is mounted inside the container at /work.
• CLI entrypoint is huffman.main.CliMain.
• Empty files are rejected for compression.

Huffman algorithm overview

Huffman coding is a lossless compression method.

Core idea:

1. Count frequency of each byte in the input.
2. Build a binary tree where lower-frequency symbols stay deeper.
3. Assign bit codes from tree paths:
   • left edge = 0
   • right edge = 1
4. Replace each original byte with its variable-length bit code.
5. Store enough metadata in a header to rebuild the tree during decompression.

Why it compresses:

• Frequent bytes get short codes.
• Rare bytes get longer codes.
• Average bits per symbol goes down when frequency distribution is non-uniform.

How this project implements Huffman

Compression pipeline

1. Count byte frequencies

   • Reads the file byte-by-byte into a 256-entry table.
   • Class: imple.CompresorImple
   • Method: contarOcurrencias

2. Build initial node list

   • Creates one leaf node per byte with frequency > 0.
   • Sorts by frequency, then by byte value for deterministic behavior.
   • Method: crearListaEnlazada

3. Build Huffman tree

   • Uses a priority queue.
   • Repeatedly merges the two least frequent nodes into one parent.
   • Final remaining node is the root.
   • Method: convertirListaEnArbol

4. Generate bit codes

   • Traverses the tree and records each leaf code as a string of 0 and 1.
   • Method: generarCodigosHuffman
   • Helper: huffman.util.HuffmanTree

5. Write compressed file

   • First writes a custom header.
   • Then writes encoded payload bit-by-bit using BitWriter.
   • Methods: escribirEncabezado, escribirContenido
   • Bit writer: imple.BitWriterImple

Header format used in .huf

The file starts with metadata required to rebuild the exact coding tree:

1. 1 byte: number of leaves
   • value 0 means 256 leaves
2. For each leaf:
   • 1 byte: original byte value
   • 1 byte: code length in bits
   • m bytes: code bits padded to full bytes
3. 4 bytes: original file length

After that, encoded payload bits are stored.

Decompression pipeline

1. Rebuild the tree from the header

   • Reads the leaf table and reconstructs paths from code bits.
   • Method: recomponerArbol in imple.DescompresorImple

2. Skip header and decode payload bits

   • Reads one bit at a time with BitReader.
   • Walks the tree until reaching a leaf.
   • Writes the corresponding byte to output.
   • Stops after writing the original byte count.
   • Method: descomprimirArchivo
   • Bit reader: imple.BitReaderImple

Main classes

• CLI runner: src/main/java/huffman/main/CliMain.java
• Compressor implementation: src/main/java/imple/CompresorImple.java
• Decompressor implementation: src/main/java/imple/DescompresorImple.java
• Bit-level writer: src/main/java/imple/BitWriterImple.java
• Bit-level reader: src/main/java/imple/BitReaderImple.java
• Docker setup: Dockerfile and docker-compose.yml