La entropía explicada

En 1948, un ingeniero de los Bell Labs, Claude Shannon, se hizo una pregunta que nadie había planteado con precisión: ¿cuánta información contiene un mensaje? Su respuesta fue un número, medido en bits, que no depende de lo que significa un mensaje sino de lo sorprendente que es. Ese número, la entropía, fija los límites de todo programa de compresión, de toda conexión de red y de todo dispositivo de almacenamiento, y explica por qué algunos textos se reducen a una fracción de su tamaño mientras que otros no se dejan comprimir en absoluto.

Barras de probabilidades de letras que se desvanecen de las más comunes a las más raras, con la curva de entropía que baja a medida que se conoce más contexto
Barras de probabilidades de letras que se desvanecen de las más comunes a las más raras, con la curva de entropía que baja a medida que se conoce más contexto

La información es sorpresa

La idea de Shannon fue medir la información por lo inesperado que es un mensaje, no por lo que significa. Si ya conoces la respuesta, oírla no te dice nada; si podía ser una cosa entre mil, te dice mucho. Un mensaje que señala una de dos posibilidades igual de probables lleva un bit. Una de cuatro requiere dos bits, una de ocho, tres bits, y en general una de N posibilidades igual de probables requiere log₂ N bits. Por tanto, un símbolo que aparece con probabilidad p lleva −log₂ p bits: cuanto más raro es, más te dice.

La fórmula de Shannon

La entropía es la información media por símbolo: H = −Σ p log₂ p, sumada sobre todos los símbolos, cada uno con su probabilidad p. Para una moneda equilibrada, H es 1 bit. Para una moneda que sale cara el 90 % de las veces es solo 0,47 bits, porque el resultado no suele sorprender. La entropía es máxima cuando todos los símbolos son igual de probables, log₂ n bits para n símbolos, y nula cuando un símbolo es seguro. Shannon eligió el nombre por consejo de John von Neumann, porque la misma fórmula aparece en física, donde la entropía mide el desorden.

Claude Shannon, que en 1948, en Bell Labs, precisó cuánta información contiene un mensaje y la midió en bits.
Claude Shannon, que en 1948, en Bell Labs, precisó cuánta información contiene un mensaje y la midió en bits.

El límite de la compresión

El teorema de codificación de fuente de Shannon dice que ningún código sin pérdida puede usar, de media, menos bits por símbolo que la entropía de la fuente, y que los códigos pueden acercarse a ella tanto como se quiera. La codificación de Huffman, inventada por David Huffman en 1952 cuando era estudiante, asigna códigos cortos a los símbolos frecuentes y largos a los raros, y se queda a menos de un bit por símbolo de la entropía; la codificación aritmética se acerca todavía más. La entropía no es, por tanto, solo una descripción, sino un límite infranqueable: un archivo de bytes aleatorios, con 8 bits de entropía por byte, no se puede comprimir en absoluto.

David Huffman, fotografiado como profesor de la Universidad de California en Santa Cruz. Como estudiante de posgrado en el MIT, en 1951 halló su código óptimo en un trabajo para el curso de Robert Fano.
David Huffman, fotografiado como profesor de la Universidad de California en Santa Cruz. Como estudiante de posgrado en el MIT, en 1951 halló su código óptimo en un trabajo para el curso de Robert Fano.

Contexto y redundancia

Las letras de un texto no son independientes. En inglés, después de Q viene U, después de un punto una mayúscula, y una palabra que empieza por INFORMA casi seguro continúa con TION. Tener en cuenta los símbolos anteriores da la entropía condicional, que es menor que la entropía de los símbolos contados uno a uno. La diferencia es la redundancia: la parte del mensaje que se podría haber predicho. Los programas de compresión como ZIP, que usa el método deflate, buscan cadenas repetidas y las sustituyen por referencias cortas, y los compresores modernos predicen cada símbolo a partir de su contexto.

¿Cuánta información hay en el inglés?

Contada letra por letra, con las frecuencias del inglés, una letra lleva unos 4,1 bits, frente a 4,7 para letras elegidas al azar. En 1951 Shannon fue más allá: mostró a varias personas el comienzo de un texto y les pidió que adivinaran la letra siguiente, contando cuántos intentos necesitaban. A partir de sus respuestas estimó que el inglés lleva solo entre 0,6 y 1,3 bits por letra. Dicho de otro modo, cerca de tres cuartas partes del inglés escrito son redundancia, y por eso un texto al que le faltan letras normalmente se puede seguir leyendo.

Aleatoriedad y contraseñas

La entropía también mide la imprevisibilidad, de la que depende la seguridad. Una clave o contraseña elegida de forma uniforme entre N posibilidades tiene log₂ N bits de entropía, y un atacante tiene que probar de media aproximadamente la mitad. Una contraseña aleatoria de 12 letras tomadas de las 26 minúsculas tiene unos 56 bits; una palabra común tiene muchos menos, por larga que sea. Los generadores de números aleatorios se ponen a prueba comprobando que su salida tiene la entropía completa de una fuente aleatoria, y los sistemas operativos recogen entropía de las fluctuaciones de temporización para inicializarlos.

Dónde aparece la entropía

La entropía decide cuántos bits necesita una llamada telefónica, una foto o una transmisión de vídeo, y cuánto puede acercarse un módem o una conexión Wi-Fi a la capacidad de su canal. Los biólogos la usan para medir la información del ADN, donde cuatro bases pueden llevar como máximo 2 bits cada una, y la diversidad de un ecosistema. En aprendizaje automático, los árboles de decisión eligen la pregunta que más reduce la entropía, y la pérdida de entropía cruzada entrena la mayoría de las redes neuronales. Los lingüistas comparan los idiomas por su entropía por carácter y por palabra.

Explórala

Abre la calculadora de entropía para medir cualquier texto por caracteres, palabras o bytes. Compara un párrafo con letras, bits, dígitos y ADN aleatorios, mira la sorpresa de cada símbolo, cuánta información contiene el texto frente a su tamaño almacenado, y cómo bajan los bits por símbolo a medida que se conoce más contexto, junto a lo que consigue realmente ZIP.

Preguntas frecuentes

¿Por qué la entropía se mide en bits?

Porque Shannon usó logaritmos en base 2, de modo que una elección de sí o no entre dos opciones iguales cuenta como una unidad. Con el logaritmo natural la unidad es el nat, unos 1,44 bits, y con base 10 el hartley, unos 3,32 bits; los usan los físicos y algunos estadísticos.

¿Puede un texto tener más entropía que el log₂ de su alfabeto?

No. Con n símbolos distintos, la entropía es como máximo log₂ n bits por símbolo, y solo se alcanza cuando todos son igual de frecuentes. Cualquier desequilibrio, y cualquier previsibilidad debida al contexto, la reduce.

¿La entropía de la teoría de la información es la misma que la de la física?

Las fórmulas tienen la misma forma: Boltzmann y Gibbs escribieron la entropía física como una suma sobre las probabilidades de los estados microscópicos de un sistema. El significado está relacionado, ya que ambas miden cuánto no se sabe, y desde entonces los físicos han demostrado que borrar un bit de información debe liberar una pequeña cantidad de calor.

¿Por qué no sirve de nada comprimir un archivo ya comprimido?

Un buen compresor elimina la mayor parte de la redundancia, así que su salida es casi aleatoria, con casi 8 bits de entropía por byte. No queda nada que eliminar, y volver a comprimirlo suele hacerlo un poco más grande por la sobrecarga del propio compresor.

¿Listo para probarlo?

Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.

Abrir la calculadora de entropía