Quel est le concept derrière la compression zip? Je peux comprendre le concept d'élimination de l'espace vide, etc., mais il faut probablement ajouter quelque chose pour dire combien / où cet espace libre doit être ajouté pendant la décompression?
Quel est le processus de base pour compresser un flux d'octets?
3 Réponses :
Un bon endroit pour commencer 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, alors d'autres (dans un fichier plaint de nombreux octets n'apparaîtront pas du tout). Plutôt, passez à 8 bits pour encoder chaque octet, pourquoi ne pas utiliser une séquence de bits plus courte pour coder les caractères les plus courants et une séquence plus longue pour coder les caractères moins courants (ces séquences sont déterminées en créant un arbre de Huffman).
Une fois que vous avez reçu une poignée sur l'utilisation de ces arbres pour encoder / décoder des fichiers en fonction de la fréquence de caractères, imaginez que vous commencez ensuite à travailler sur la fréquence de mot - au lieu d'encoder "ils" comme une séquence de 4 caractères, pourquoi ne pas le considérer à Soyez un seul caractère en raison de sa fréquence, ce qui lui permet d'attribuer sa propre feuille dans l'arbre Huffman. Ceci est plus ou moins la base du zip et une autre compression de type sans perte - ils recherchent des "mots" communs (séquences d'octets) dans un fichier (y compris des séquences de seulement 1 octet si suffisamment communs) et utilisez un arbre pour les coder. Le fichier zip doit alors inclure l'info de l'arborescence (une copie de chaque séquence et le nombre de fois qu'il apparaît) pour permettre à l'arborescence d'être reconstruit et le reste du fichier à décoder.
Suivi:
Pour mieux répondre à la question initiale, l'idée de la compression sans perte n'est pas tellement de supprimer l'espace vide, mais de supprimer Si vous avez créé une base de données pour stocker des paroles de musique, vous trouverez que beaucoup d'espace étaient utilisés pour stocker le choeur 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, puis chaque fois que le choeur doit être répété, il suffit d'utiliser le chorus comme un porte-lieu (en fait c'est à peu près l'idée. Derrière la compression LZW - en LZW, chaque ligne de la chanson aurait un numéro affichée avant. Si une ligne se répète plus tard dans la chanson, écrivez plutôt la ligne complète que le numéro est affiché)
Excellent moyen de fournir un résumé de la réponse avec des liens vers une lecture ultérieure plutôt que de simplement envoyer le OP au wiki / Google.
Plus de compression de base est probablement la compression rle, mais elle n'explique pas grand chose sur les types les plus avancés.
En tant que ressource supplémentaire, vous pouvez ajouter un lien ou mentionner la sécurité maintenant! Podcast. Dans l'épisode n ° 205, Steve Gibson discute de la théorie de Compersion et de la façon dont elle a évolué au fil du temps. Voici un lien vers la transcription: GRC.com/sn/sn-205.txt < / a>
En fait, vous n'avez même pas besoin de stocker l'arbre, si vous utilisez une compression dynamique de Huffman. Lorsque vous codez, commencez avec un arbre par défaut. Ensuite, vous encodez un seul caractère / mot en l'utilisant, mettez à jour l'arborescence en fonction de la fréquence des caractères / mots que vous avez déjà lus et traitez le caractère / mot suivant jusqu'à la fin de l'entrée. Lorsque vous décodez, vous commencez avec le même arborescence initial et mettez-le à la mettre à jour en fonction de l'entrée.
Pour la précision des sceptes - zip est (généralement) non basé sur LZW, mais plutôt LZ77 + (non dynamique) Huffman basé. LZ77 est l'algorithme de compression, qui élimine les séquences répétées de lettres ("Oh Baby Baby" comme un "bébé" redondant de celui-ci), tandis que Huffman est un codage efficace sur la sortie de la LZ77.
Le concept entre la compression est essentiellement statistique. Si vous avez une série d'octets, les chances d'octet n étant X dans la pratique dépend de la répartition 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 des chances estimées P (n, x).
Par exemple, étant donné une séquence "AAAA", un algorithme de compression peut affecter une valeur élevée à P (5, A) et à des valeurs inférieures à P (5, B). Lorsque P (x) est élevé, le bitstring assigné à X sera court, lorsque P (x) est basse un long bits de bits longs. De cette manière, si p (n, x) est une bonne estimation, le bitstring moyen sera plus court que 8 bits.
Le concept de base est que, 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équemment ou des séquences d'octets.
Par exemple, si votre fichier est composé uniquement de l'octet 0x41 ( donc ce que nous avons Voici que pour ce fichier ( C'est l'idée principale de la compression. comme un autre exemple, considérez le motif de huit octets < / p> et maintenant le répéter 2048 fois. Un moyen de suivre l'approche ci-dessus consiste à représenter les octets en utilisant trois bits. Nous pouvons représenter le motif d'octet ci-dessus par mais une approche encore meilleure est de représenter le motif d'octet par le seul bit et le modèle d'octet que, en un mot, c'est comment fonctionne la compression. Toute l'activité se présente pour 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: A ) répété seize fois seize fois, puis au lieu de le représenter comme la séquence 8 bits 01000001 raccourcissez-la sur la séquence 1 bit 0 . Ensuite, le fichier peut être représenté par 0000000000000000 (seize 0 s). Alors alors 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. 0x41 répété seize fois) The Bits 01000001 Ne transmettez aucune information supplémentaire sur le bit 0 . Donc, dans ce cas, nous jetons les morceaux étrangers pour obtenir une représentation plus courte. 00000101 00111001 01110111 ( Ceci est le modèle de trois octets 0x05 0x39 0x77 ) répété 2048 fois. 0 . Ensuite, nous pouvons représenter le modèle d'octet ci-dessus par 0 répété 2048 fois qui devient l'octet 0x00 répété 256 fois. Nous n'avons maintenant besoin que de stocker le dictionnaire 0x00 répété 256 fois et nous avons compressé le fichier de 16 384 octets à (modulo le Dictionnaire) 256 octets.
Cela me semble que vous avez besoin d'aller à Wikipedia et de faire de la lecture.
Facile! Convertir en binaire et retirez les zéros
HOWSTFUMWORKS.COM/FILE-Compprimer.htm
@skaffman Oui, mais Spolsky veut donc être l'endroit canonique pour aller pour des questions de programmation, il est donc approprié de le demander ici. Je ne prévoie pas d'écrire un algorithme de compression, je m'intéressais juste à la manière dont les fondamentaux de ce fonctionnement fonctionnent. Maintenant oui. Donc, quelqu'un d'autre qui est intéressé et le demande alors?
Juste Google, lisez les réponses Wiki, RTFM ne sont jamais la bonne réponse (ou commentaire).
@John Nolan - Vous obtenez de meilleurs ratios de compression si vous supprimez celles à la place. Mais laissez les TWOS, ce sont importants.