Huffman.java

import java.util.*;

/**
 * compresor huffman
 *
 * conceptos:
 *   - compresion sin perdida basada en frecuencias
 *   - arbol binario de minimos (min-heap)
 *   - codigos de longitud variable
 *
 * los caracteres mas frecuentes reciben codigos mas cortos.
 * el arbol se construye de abajo hacia arriba uniendo los dos nodos
 * de menor frecuencia en cada paso.
 */
public class Huffman {

    // ─── NODO DEL ARBOL ────────────────────────────────────────────

    static class Nodo implements Comparable<Nodo> {
        char caracter;
        int frecuencia;
        Nodo izquierda, derecha;

        // nodo hoja: representa un caracter real
        Nodo(char caracter, int frecuencia) {
            this.caracter = caracter;
            this.frecuencia = frecuencia;
        }

        // nodo interno: solo tiene frecuencia acumulada, no caracter
        Nodo(int frecuencia, Nodo izquierda, Nodo derecha) {
            this.frecuencia = frecuencia;
            this.izquierda = izquierda;
            this.derecha = derecha;
        }

        boolean esHoja() {
            return izquierda == null && derecha == null;
        }

        // el priority queue necesita saber como ordenar nodos
        @Override
        public int compareTo(Nodo otro) {
            return Integer.compare(this.frecuencia, otro.frecuencia);
        }
    }

    // ─── PASO 1: CONTAR FRECUENCIAS ────────────────────────────────

    static Map<Character, Integer> contarFrecuencias(String texto) {
        Map<Character, Integer> frecuencias = new HashMap<>();
        for (char c : texto.toCharArray()) {
            frecuencias.merge(c, 1, Integer::sum);
        }
        return frecuencias;
    }

    // ─── PASO 2: CONSTRUIR EL ARBOL ────────────────────────────────

    static Nodo construirArbol(Map<Character, Integer> frecuencias) {
        // min-heap: el nodo de menor frecuencia siempre queda al frente
        PriorityQueue<Nodo> heap = new PriorityQueue<>();

        for (Map.Entry<Character, Integer> entrada : frecuencias.entrySet()) {
            heap.add(new Nodo(entrada.getKey(), entrada.getValue()));
        }

        // caso especial: texto con un solo caracter distinto
        if (heap.size() == 1) {
            Nodo unico = heap.poll();
            heap.add(new Nodo(unico.frecuencia, unico, null));
        }

        // unir los dos nodos mas pequenos hasta que quede uno solo
        while (heap.size() > 1) {
            Nodo menor1 = heap.poll();
            Nodo menor2 = heap.poll();
            Nodo padre = new Nodo(menor1.frecuencia + menor2.frecuencia, menor1, menor2);
            heap.add(padre);
        }

        return heap.poll(); // raiz del arbol
    }

    // ─── PASO 3: GENERAR TABLA DE CODIGOS ──────────────────────────

    static Map<Character, String> generarCodigos(Nodo raiz) {
        Map<Character, String> codigos = new HashMap<>();
        generarCodigosRecursivo(raiz, "", codigos);
        return codigos;
    }

    // recorrido del arbol: izquierda = 0, derecha = 1
    static void generarCodigosRecursivo(Nodo nodo, String codigo, Map<Character, String> codigos) {
        if (nodo == null) return;

        if (nodo.esHoja()) {
            // si la raiz es hoja (un solo caracter), asignar "0" por convenio
            codigos.put(nodo.caracter, codigo.isEmpty() ? "0" : codigo);
            return;
        }

        generarCodigosRecursivo(nodo.izquierda, codigo + "0", codigos);
        generarCodigosRecursivo(nodo.derecha,   codigo + "1", codigos);
    }

    // ─── COMPRESION ────────────────────────────────────────────────

    static String comprimir(String texto, Map<Character, String> codigos) {
        StringBuilder bits = new StringBuilder();
        for (char c : texto.toCharArray()) {
            bits.append(codigos.get(c));
        }
        return bits.toString();
    }

    // ─── DESCOMPRESION ─────────────────────────────────────────────

    static String descomprimir(String bits, Nodo raiz) {
        StringBuilder resultado = new StringBuilder();
        Nodo actual = raiz;

        for (char bit : bits.toCharArray()) {
            // navegar el arbol segun cada bit
            actual = (bit == '0') ? actual.izquierda : actual.derecha;

            // si llega a una hoja, encontramos un caracter
            if (actual.esHoja()) {
                resultado.append(actual.caracter);
                actual = raiz; // volver a la raiz para el siguiente caracter
            }
        }

        return resultado.toString();
    }

    // ─── UTILIDAD: IMPRIMIR EL ARBOL ───────────────────────────────

    static void imprimirArbol(Nodo nodo, String prefijo, boolean esUltimo) {
        if (nodo == null) return;

        String rama = prefijo + (esUltimo ? "└── " : "├── ");
        String info = nodo.esHoja()
            ? "'" + nodo.caracter + "' (freq=" + nodo.frecuencia + ")"
            : "[" + nodo.frecuencia + "]";

        System.out.println(rama + info);

        String nuevoPrefijo = prefijo + (esUltimo ? "    " : "│   ");
        imprimirArbol(nodo.izquierda, nuevoPrefijo, false);
        imprimirArbol(nodo.derecha,   nuevoPrefijo, true);
    }

    // ─── DEMO ──────────────────────────────────────────────────────

    public static void main(String[] args) {
        String[] ejemplos = {
            "ABABABAB",
            "aaaaaaaaaaaa",
            "Hola mundo, hola mundo, hola mundo!",
            "the quick brown fox jumps over the lazy dog"
        };

        for (String original : ejemplos) {
            System.out.println("=".repeat(55));
            System.out.println("original   : " + original);

            // construir arbol y tabla de codigos
            Map<Character, Integer> frecuencias = contarFrecuencias(original);
            Nodo raiz = construirArbol(frecuencias);
            Map<Character, String> codigos = generarCodigos(raiz);

            // comprimir
            String bits = comprimir(original, codigos);

            // descomprimir y verificar
            String recuperado = descomprimir(bits, raiz);

            // estadisticas
            int bitsOriginales   = original.length() * 8;
            int bitsComprimidos  = bits.length();
            double ratio         = 100.0 * bitsComprimidos / bitsOriginales;

            System.out.println("bits       : " + bits);
            System.out.println("recuperado : " + recuperado);
            System.out.printf ("compresion : %d bits → %d bits (%.1f%%)%n",
                bitsOriginales, bitsComprimidos, ratio);
            System.out.println("ok         : " + original.equals(recuperado));

            // tabla de codigos ordenada por longitud
            System.out.println("tabla de codigos:");
            codigos.entrySet().stream()
                .sorted(Comparator.comparingInt(e -> e.getValue().length()))
                .forEach(e -> System.out.printf(
                    "  '%c' (freq=%2d) -> %s%n",
                    e.getKey(), frecuencias.get(e.getKey()), e.getValue()
                ));

            // arbol visual
            System.out.println("arbol:");
            imprimirArbol(raiz, "", true);
        }
    }
}