traductor que imagen funciona example decodificar como btoa atob compression data-compression lossless-compression

compression - que - ¿Por qué los datos codificados en base64 se comprimen tan mal?



btoa javascript (3)

Hace poco estaba comprimiendo algunos archivos y noté que los datos codificados en base64 parecen comprimirse realmente mal. Aquí hay un ejemplo:

  • Archivo original: 429,7 MiB
  • comprimir a través de xz -9 :
    13,2 MiB / 429,7 MiB = 0,031 4,9 MiB/s 1:28
  • base64 y comprime via xz -9 :
    26,7 MiB / 580,4 MiB = 0,046 2,6 MiB/s 3:47
  • base64 el archivo xz comprimido original:
    17,8 MiB en casi ningún tiempo = el esperado aumento de 1.33x en tamaño

Entonces, lo que se puede observar es que:

  • xz comprime muy bien ☺
  • Los datos codificados en base64 no se comprimen bien, es 2 veces más grande que el archivo comprimido no codificado
  • base64-then-compress es significativamente peor y más lento que compress-then-base64

¿Cómo puede ser esto? Base64 es un algoritmo reversible sin pérdidas, ¿por qué afecta tanto a la compresión? (Intenté con gzip también, con resultados similares).

Sé que no tiene sentido basar 64-luego-comprimir un archivo, pero la mayoría de las veces uno no tiene control sobre los archivos de entrada, y hubiera pensado que desde la densidad de información real (o como se llame) ) de un archivo codificado en base64 sería casi idéntico a la versión no codificada, y por lo tanto sería comprimible de manera similar.

La compresión es necesariamente una operación que actúa sobre múltiples bits. No hay ganancia posible al tratar de comprimir un "0" y "1" individual. Aun así, la compresión normalmente funciona en un conjunto limitado de bits a la vez. El algoritmo LZMA en xz no va a considerar todos los 3.6 mil millones de bits a la vez. Se ve en cadenas mucho más pequeñas (<273 bytes).

Ahora observe lo que hace la codificación de base-64: Reemplaza una palabra de 3 bytes (24 bits) por una palabra de 4 bytes, utilizando solo 64 de los 256 valores posibles. Esto te da el crecimiento x1.33.

Ahora está bastante claro que este crecimiento debe hacer que algunas subcadenas crezcan más allá del tamaño máximo de subcadena del codificador. Esto hace que ya no se compriman como una única subcadena, sino como dos subcadenas de hecho.

Como tiene mucha compresión (97%), aparentemente tiene la situación de que las subcadenas de entrada muy largas se comprimen como un todo. esto significa que también tendrá muchas subcadenas en base 64 expandidas más allá de la longitud máxima que el codificador puede manejar.

La mayoría de los algoritmos de compresión genéricos funcionan con una granularidad de un byte .

Consideremos la siguiente cadena:

"XXXXYYYYXXXXYYYY"

  • Un algoritmo de codificación de longitud de carrera dirá: "eso es 4 ''X'', seguido de 4 ''Y'', seguido de 4 ''X'', seguido de 4 ''Y''"
  • Un algoritmo de Lempel-Ziv dirá: "Esa es la cadena ''XXXXYYYY'', seguida de la misma cadena: entonces reemplacemos la segunda cadena con una referencia a la primera".
  • Un algoritmo de codificación de Huffman dirá: "Sólo hay 2 símbolos en esa cadena, por lo que puedo usar solo un bit por símbolo".

Ahora vamos a codificar nuestra cadena en Base64. Esto es lo que obtenemos:

"WFhYWFlZWVlYWFhYWVlZWQ=="

Todos los algoritmos ahora dicen: "¿Qué tipo de desorden es ese?" . Y no es probable que comprimen esa cuerda muy bien.

Como recordatorio, Base64 básicamente trabaja por recodificación de grupos de 3 bytes en (0 ... 255) en grupos de 4 bytes en (0 ... 63):

Input bytes : aaaaaaaa bbbbbbbb cccccccc 6-bit repacking: 00aaaaaa 00aabbbb 00bbbbcc 00cccccc

Cada byte de salida se transforma en un carácter ASCII imprimible. Por convención, estos caracteres son (aquí con una marca cada 10 caracteres):

0 1 2 3 4 5 6 ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/

Por ejemplo, nuestra cadena de ejemplo comienza con un grupo de tres bytes igual a 0x58 en hexadecimal (código ASCII del carácter "X"). O en binario: 01011000. Apliquemos la codificación Base64:

Input bytes : 0x58 0x58 0x58 As binary : 01011000 01011000 01011000 6-bit repacking : 00010110 00000101 00100001 00011000 As decimal : 22 5 33 24 Base64 characters: ''W'' ''F'' ''h'' ''Y'' Output bytes : 0x57 0x46 0x68 0x59

Básicamente, el patrón "3 veces el byte 0x58" que era obvio en el flujo de datos original ya no es obvio en el flujo de datos codificado porque hemos dividido los bytes en paquetes de 6 bits y los hemos mapeado a nuevos bytes que ahora parecen se inpredecible.

O en otras palabras: hemos roto la alineación de bytes original en la que se basan la mayoría de los algoritmos de compresión.

Cualquiera que sea el método de compresión utilizado, generalmente tiene un impacto severo en el rendimiento del algoritmo. Es por eso que siempre debes comprimir primero y codificar segundo.

Esto es aún más cierto para el cifrado: comprimir primero, cifrar segundo.

EDITAR - Una nota sobre LZMA

Como notó MSalters, LZMA, que está utilizando xz, está trabajando en flujos de bits en lugar de flujos de bytes.

Aún así, este algoritmo también sufrirá de la codificación Base64 de una manera que es esencialmente consistente con mi descripción anterior:

Input bytes : 0x58 0x58 0x58 As binary : 01011000 01011000 01011000 (see above for the details of Base64 encoding) Output bytes : 0x57 0x46 0x68 0x59 As binary : 01010111 01000110 01101000 01011001

Incluso trabajando a nivel de bits, es mucho más fácil reconocer un patrón en la secuencia binaria de entrada que en la secuencia binaria de salida.