Pourquoi les données encodées en base64 se compressent-elles si mal?

Question

J'ai été récemment compresser certains fichiers, et j'ai remarqué que des données codées en base64 semble compresser vraiment mauvais. Voici un exemple:

• Fichier d'origine: 429,7 MiB
• compresser via xz -9:
  13,2 MiB / 429,7 MiB = 0,031 4,9 MiB/s 1:28
• base64 et compresser via xz -9:
  26,7 MiB / 580,4 MiB = 0,046 2,6 MiB/s 3:47
• base64 origine compressé xz fichier:
  17,8 MiB dans presque pas de temps = attendus 1.33x augmentation de la taille

Donc ce qui peut être observé, c'est que:

• xz comprime vraiment bon
• des données codées en base64 ne compresse pas bien, il est 2 fois plus grande que la forme non codée fichier compressé
• base64-puis-compresse est bien pire et plus lents que les compresser-puis-base64

Comment cela peut-il être? Base64 est une compression sans perte, réversible algorithme, pourquoi elle affecte la compression autant? (J'ai essayé avec gzip ainsi, avec des résultats similaires).

Je sais que ça n'a pas de sens pour base64-puis-compresser un fichier, mais la plupart du temps on n'a pas de contrôle sur les fichiers d'entrée, et j'aurais pensé que, puisque l'information réelle de la densité (ou peu importe son nom) d'un fichier codé en base64 serait presque identique à la non-codées version, et donc de faire de même compressible.

Answer 1

La plupart des génériques des algorithmes de compression de travailler avec un un octet de granularité.

Considérons la chaîne suivante:

"XXXXYYYYXXXXYYYY"

• Une course-Longueur-algorithme de Codage va dire: "c'est 4 'X', 4 'Y', 4 'X', 4 'Y'"
• Un Lempel-Ziv algorithme va dire: "C'est la chaîne de caractères "XXXXYYYY", suivie par la même chaîne: donc, nous allons remplacer la 2e corde avec une référence à la 1ère."
• Un codage de Huffman algorithme va dire: "Il y a seulement 2 symboles dans cette chaîne, donc je ne peux utiliser qu'un seul bit par symbole."

Maintenant, nous allons coder notre chaîne en Base64. Voici ce que nous obtenons:

"WFhYWFlZWVlYWFhYWVlZWQ=="

Tous les algorithmes sont en train de dire: "Quel genre de gâchis, c'est qui?". Et ils ne sont pas susceptibles de comprimer cette chaîne très bien.

Pour rappel, en Base64 fonctionne essentiellement par le ré-encodage des groupes de 3 octets (0...255) en groupes de 4 octets (0...63):

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

Chaque octet de sortie est ensuite transformé en une version imprimable des caractères ASCII. Par convention, ces personnages sont (ici avec une marque tous les 10 caractères):

0         1         2         3         4         5         6
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/

Par exemple, notre exemple de chaîne commence avec un groupe de trois octets égal à 0x58 en hexadécimal (code ASCII du caractère "X"). Ou en binaire: 01011000. Nous allons appliquer le codage 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

Fondamentalement, le modèle "3 fois l'octet 0x58" qui était évident dans l'original flux de données n'est pas évident de plus lors de l'encodage du flux de données parce que nous avons brisé les octets en 6 bits paquets et les mappé à nouveau octets qui semblent désormais être aléatoire.

Ou en d'autres termes: nous avons cassé l'origine alignement d'octets que la plupart des algorithmes de compression dépendent.

Quelle que soit la méthode de compression est utilisé, il a généralement un impact sévère sur l'algorithme de la performance. C'est pourquoi vous devriez toujours compresser d'abord et encoder de la seconde.

C'est encore plus vrai pour le chiffrement: compresser d'abord, chiffrer seconde.

MODIFIER - UNE note sur LZMA

Comme MSalters remarqué, LZMA -- qui xz est à l'aide de -- est de travailler sur les flux de bits plutôt que de flux d'octets.

Encore, cet algorithme ne souffrent également de l'encodage Base64 dans un chemin qui est essentiellement compatible avec ma description précédente:

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

Même en travaillant au niveau du bit, il est beaucoup plus facile de reconnaître un schéma de l'entrée binaire de la séquence que dans la sortie binaire de la séquence.

Answer 2

La Compression est nécessairement une opération qui agit sur plusieurs bits. Il n'y a pas de gain possible en essayant de comprimer un individu "0" et "1". De même, la compression fonctionne généralement sur un ensemble limité de bits à la fois. L'algorithme LZMA en xz ne va pas tenir compte de tous les 3,6 milliards de bits à la fois. Il ressemble à cordes bien plus petites (<273 octets).

Maintenant, regardez ce que l'encodage base 64: Il remplace un 3 octets (24 bits) mot de 4 octets mot, à l'aide de seulement 64 de 256 valeurs possibles. Cela vous donne la x1.33 croissance.

Maintenant, il est assez clair que cette croissance est à cause de certains sous-chaînes dépasser le maximum de la sous-chaîne de la taille de l'encodeur. Cela les conduit à être plus compressé que d'un seul sous-chaîne, mais comme deux sous-chaînes en effet.

Comme vous avez un lot de compression (97%), vous apparemment, la situation est très long d'entrée de sous-chaînes sont compressés dans son ensemble. cela signifie que vous aurez également de nombreux sous-chaînes de base-64 élargi passé, la longueur maximale du codeur peut traiter.

Answer 3

Ce n'est pas Base64. ses besoins en mémoire des bibliothèques "Les préréglages 7-9 sont comme le préréglage 6 mais utilisent des dictionnaires plus gros et ont des besoins en mémoire de compresseur et de décompresseur plus élevés." https://tukaani.org/xz/xz-javadoc/org/tukaani/xz/LZMA2Options.html