Quel est le concept derrière la compression zip?

Question

Quel est le concept derrière la compression zip? Je peux comprendre le concept de supprimer l'espace vide, etc., mais il est probable que quelque chose doit être ajouté pour dire combien/où cet espace libre doit être ajouté lors de la décompression?

Quel est le processus de base pour compresser un flux d'octets?

Answer 1

Un bon point de départ serait de rechercher le schéma de compression Huffman. L'idée de base derrière huffman est que dans un fichier donné, certains octets apparaissent plus fréquemment que d'autres (dans un fichier texte, plusieurs octets n'apparaîtront pas du tout). Plutôt que de dépenser 8 bits pour encoder chaque octet, pourquoi ne pas utiliser une séquence de bits plus courte pour coder les caractères les plus communs, et des séquences plus longues pour coder les caractères moins communs (ces séquences sont déterminées en créant un arbre de Huffman). Une fois que vous maîtrisez l'utilisation de ces arbres pour encoder/décoder les fichiers en fonction de la fréquence des caractères, imaginez que vous commencez à travailler sur la fréquence des mots - au lieu d'encoder "ils" comme une séquence de 4 caractères, pourquoi ne pas être un seul caractère en raison de sa fréquence, lui permettant d'être assigné sa propre feuille dans l'arbre de Huffman. C'est plus ou moins la base de ZIP et d'autres types de compression sans perte - ils recherchent des "mots" communs (séquences d'octets) dans un fichier (y compris des séquences de 1 byte) et utilisent un arbre pour les encoder. Le fichier zip doit alors seulement inclure les informations de l'arborescence (une copie de chaque séquence et le nombre de fois qu'elle apparaît) pour permettre la reconstruction de l'arborescence et le décodage du reste du fichier.

Suivi:

Pour mieux répondre à la question initiale, l'idée derrière la compression sans perte est pas tant de supprimer l'espace vide, mais pour enlever redundent informations.

Si vous créiez une base de données pour stocker des paroles de musique, vous trouveriez beaucoup d'espace pour stocker le chœur qui se répète plusieurs fois. Au lieu d'utiliser tout cet espace, vous pouvez simplement placer le mot CHORUS avant la première instance des lignes de chorus, et ensuite chaque fois que le refrain doit être répété, utilisez simplement CHORUS comme un espace réservé (en fait c'est à peu près l'idée derrière LZW compression - dans LZW chaque ligne de la chanson aurait un nombre montré avant elle.Si une ligne se répète plus tard dans la chanson, plutôt que d'écrire toute la ligne seulement le nombre est montré)

Answer 2

Le concept entre la compression est fondamentalement statistique. Si vous avez une série d'octets, la probabilité que l'octet N soit X dépend en pratique de la distribution de la valeur des octets précédents 0..N-1. Sans compression, vous allouez 8 bits pour chaque valeur possible X. Avec la compression, les quantités d'octets allouées pour chaque valeur X dépendent du hasard estimé p (N, X). Par exemple, avec une séquence "aaaa", un algorithme de compression peut attribuer une valeur élevée à p (5, a) et des valeurs inférieures à p (5, b). Quand p (X) est haut, la chaîne binaire attribuée à X sera courte, quand p (X) est bas, une chaîne binaire longue est utilisée. De cette manière, si p (N, X) est une bonne estimation, la chaîne de bits moyenne sera plus courte que 8 bits.

Answer 3

Le concept de base est qu'au lieu d'utiliser huit bits pour représenter chaque octet, vous utilisez des représentations plus courtes pour des octets ou des séquences d'octets plus fréquents.

Par exemple, si votre fichier est constitué uniquement de 0x41 octet (A) seize fois répétées, alors au lieu de représenter comme la séquence 8 bits 01000001 raccourcissent à la séquence 1 bits 0. Ensuite, le fichier peut être représenté par 0000000000000000 (seize 0 s).Ainsi, le fichier de l'octet 0x41 répété seize fois peut être représenté par le fichier constitué de l'octet 0x00 répété deux fois.

donc ce que nous avons ici est que ce fichier (0x41 répété seize fois) les bits 01000001 ne véhiculent pas d'informations supplémentaires sur le bit 0. Donc, dans ce cas, nous jetons les bits étrangers pour obtenir une représentation plus courte.

C'est l'idée de base derrière la compression.

Comme autre exemple, considérons le modèle de huit octets

0x41 0x42 0x43 0x44 0x45 0x46 0x47 0x48 

et maintenant le répéter 2048 fois. Une façon de suivre l'approche ci-dessus est de représenter les octets en utilisant trois bits.

000 0x41 
001 0x42 
010 0x43 
011 0x44 
100 0x45 
101 0x46 
110 0x47 
111 0x48 

Maintenant, nous pouvons représenter le motif d'octets ci-dessus par 00000101 00111001 01110111 (ce qui est le modèle à trois octets 0x05 0x39 0x77) répété 2048 fois.

Mais une approche encore mieux est de représenter le motif d'octets

0x41 0x42 0x43 0x44 0x45 0x46 0x47 0x48 

par le bit unique 0. Ensuite, nous pouvons représenter le modèle d'octets ci-dessus par 0 répété 2048 fois qui devient l'octet 0x00 répété 256 fois. Maintenant, nous avons seulement besoin de stocker le dictionnaire

0 -> 0x41 0x42 0x43 0x44 0x45 0x46 0x47 0x48 

et le motif de l'octet 0x00 répété 256 fois et nous compresserait les fichier de 16384 octets (modulo le dictionnaire) 256 octets.

Voilà, en un mot, comment fonctionne la compression. Toute l'affaire revient à trouver des représentations courtes et efficaces des octets et des séquences d'octets dans un fichier donné. C'est l'idée simple, mais les détails (trouver la représentation) peuvent être assez difficiles.

Voir par exemple:

1. Data compression
2. Run length encoding
3. Huffman compression
4. Shannon-Fano coding
5. LZW