La idea: algoritmos voraces
Un algoritmo voraz toma en cada paso la decisión que se ve mejor en ese momento y nunca la deshace. No siempre funciona, pero en estos tres problemas está demostrado que llega a la solución óptima.
Algoritmos voraces · Compresión de Huffman y Árbol de Expansión Mínima
LIBRO CARGADO
Busca un libro en Gutenberg o sube un .txt para comenzar.
Elige un libro de Project Gutenberg o sube un archivo .txt para construir el árbol, ver los códigos y medir cuánto se ahorra.
Haz clic en un carácter para ver su camino en el árbol.
| Carácter | Unicode | Frecuencia | Probabilidad | Código Huffman | Bits |
|---|
Reconstruye el texto recorriendo el árbol bit por bit: 0 = izquierda, 1 = derecha; al llegar a una hoja se escribe su carácter.
El texto reconstruido aparecerá aquí…| # | Arista | Peso | Decisión |
|---|
Un algoritmo voraz toma en cada paso la decisión que se ve mejor en ese momento y nunca la deshace. No siempre funciona, pero en estos tres problemas está demostrado que llega a la solución óptima.
Un .txt guarda cada carácter con 8 bits, aunque unos aparezcan muchísimo más que otros.
Huffman da códigos cortos a los caracteres frecuentes y largos a los raros.
0, derecha = 1..mc, que también guarda la tabla de frecuencias).Ningún código es el inicio de otro (código prefijo), por eso no hay ambigüedad al decodificar.
Construir el árbol cuesta O(n log n) con n = caracteres distintos.
Conectar todos los nodos de un grafo con el menor costo total y sin ciclos.
O(E log E).O(E log V).Los dos siempre llegan al mismo peso mínimo; la página lo comprueba al terminar.
Se cuentan las palabras vacías de cada idioma (artículos, preposiciones, conjunciones: de, la, que, the, and, der, und…). Forman casi la mitad de cualquier texto, así que el idioma con más coincidencias es el del libro. Las letras propias (ñ, ç, ß, ã) suman un poco más. Antes se quita el encabezado de Gutenberg, que siempre está en inglés.
Los algoritmos están escritos en Python (carpetas huffman/, mst/ e idioma/)
y se ejecutan en tu navegador con Pyodide. JavaScript solo dibuja la interfaz.
El buscador consulta gutenberg.org a través de un pequeño servidor (Cloudflare Worker),
porque Gutenberg no permite que otras páginas lean sus libros directamente.
Procesando…