2 façons de compresser des informations dans des fichiers. Compression par encodage série. Transmission d'e-mails

Bonne journée.
Aujourd'hui, je veux aborder le sujet de la compression de données sans perte. Malgré le fait qu'il y avait déjà des articles sur Habré consacrés à certains algorithmes, je voulais en parler un peu plus en détail.
je vais essayer de donner comme description mathématique, et une description sous la forme habituelle, afin que chacun puisse trouver quelque chose d'intéressant pour lui-même.

Dans cet article, j'aborderai les bases de la compression et les principaux types d'algorithmes.

Compression. Est-ce nécessaire à notre époque ?

Bien sûr que oui. Bien entendu, nous comprenons tous que nous avons désormais accès à la fois à des supports de stockage à grand volume et à des canaux de transmission de données à grande vitesse. Cependant, dans le même temps, les volumes d'informations transmises augmentent. Si, il y a quelques années, nous regardions des films de 700 mégaoctets qui tiennent sur un seul disque, les films en qualité HD peuvent aujourd'hui prendre des dizaines de gigaoctets.
Bien sûr, il n'y a pas beaucoup d'avantages à compresser tout et tout le monde. Mais il existe encore des situations dans lesquelles la compression est extrêmement utile, voire nécessaire.

• Envoi de documents par e-mail(en particulier de gros volumes de documents utilisant des appareils mobiles)
• Lors de la publication de documents sur des sites Web, la nécessité d'économiser du trafic
• Économie espace disque dans les cas où le remplacement ou l'ajout de moyens de stockage est difficile. Par exemple, cela se produit dans les cas où il n'est pas facile d'éliminer un budget pour les dépenses en capital et où il n'y a pas assez d'espace disque.

Bien sûr, vous pouvez penser à bien d'autres situations dans lesquelles la compression sera utile, mais ces quelques exemples nous suffisent.

Toutes les méthodes de compression peuvent être divisées en deux grands groupes : la compression avec perte et la compression sans perte. La compression sans perte est utilisée lorsque les informations doivent être restaurées avec une précision binaire. Cette approche est la seule possible lors de la compression, par exemple, de données textuelles.
Dans certains cas, cependant, une récupération précise des informations n'est pas requise et les algorithmes qui implémentent la compression avec perte sont autorisés, ce qui, contrairement à la compression sans perte, est généralement plus facile à implémenter et fournit un degré d'archivage plus élevé.

Passons donc aux algorithmes de compression sans perte.

Méthodes de compression sans perte polyvalentes

En général, il existe trois options de base sur lesquelles les algorithmes de compression sont construits.
Premier groupe méthodes - transformation de flux. Cela suppose la description des nouvelles données non compressées entrantes à travers les données déjà traitées. Dans ce cas, aucune probabilité n'est calculée, le codage des caractères est effectué uniquement sur la base des données déjà traitées, comme, par exemple, dans les méthodes LZ (du nom d'Abraham Lempel et Jacob Ziv). Dans ce cas, la deuxième occurrence et les suivantes d'une certaine sous-chaîne déjà connue du codeur sont remplacées par des références à sa première occurrence.

Deuxième groupe Les méthodes sont des méthodes de compression statistique. À leur tour, ces méthodes sont divisées en adaptatives (ou rationalisées) et en blocs.
Dans la première version (adaptative), les probabilités de nouvelles données sont calculées à partir de données déjà traitées lors de l'encodage. Ces méthodes incluent des variantes adaptatives des algorithmes de Huffman et Shannon-Fano.
Dans le second cas (bloc), les statistiques de chaque bloc de données sont calculées séparément et ajoutées au bloc le plus compressé. Il s'agit notamment des versions statiques des méthodes de codage Huffman, Shannon-Fano et arithmétique.

Troisième groupe Les méthodes sont des méthodes dites de conversion de blocs. Les données entrantes sont divisées en blocs, qui sont ensuite transformés dans leur intégralité. Dans le même temps, certaines méthodes, en particulier celles basées sur la permutation de blocs, peuvent ne pas conduire à une réduction significative (voire aucune) de la quantité de données. Cependant, après un tel traitement, la structure des données est considérablement améliorée et la compression ultérieure par d'autres algorithmes est plus efficace et plus rapide.

Principes généraux sur lesquels repose la compression des données

Toutes les méthodes de compression de données sont basées sur un principe logique simple. Si nous imaginons que les éléments les plus courants sont codés avec des codes plus courts et les moins courants avec des codes plus longs, il faudra alors moins d'espace pour stocker toutes les données que si tous les éléments étaient représentés par des codes de même longueur.
La relation exacte entre les fréquences des éléments et les longueurs de code optimales est décrite dans le théorème de codage de source de Shannon, qui définit la limite de compression sans perte maximale et l'entropie de Shannon.

Un peu de maths

Si la probabilité d'occurrence d'un élément s i est égale à p (s i), alors il sera plus avantageux de représenter cet élément - log 2 p (s i) en bits. Si pendant le codage, il est possible d'obtenir que la longueur de tous les éléments soit réduite à log 2 p (si) bits, alors la longueur de la séquence codée entière sera minimale pour toutes les méthodes de codage possibles. De plus, si la distribution de probabilité de tous les éléments F = (p (s i)) est inchangée et que les probabilités des éléments sont mutuellement indépendantes, alors la longueur moyenne des codes peut être calculée comme suit

Cette valeur est appelée l'entropie de la distribution de probabilité F, ou l'entropie de la source à un instant donné.
Cependant, généralement la probabilité d'apparition d'un élément ne peut pas être indépendante, au contraire, elle dépend de certains facteurs. Dans ce cas, pour chaque nouvel élément codé si, la distribution de probabilité F prendra une certaine valeur F k, c'est-à-dire pour chaque élément F = F k et H = H k.

En d'autres termes, on peut dire que la source est dans l'état k, ce qui correspond à un certain ensemble de probabilités p k (si) pour tous les éléments si.

Par conséquent, en tenant compte de cet amendement, nous pouvons exprimer la longueur moyenne des codes comme

Où P k est la probabilité de trouver une source dans l'état k.

Ainsi, à ce stade, nous savons que la compression est basée sur le remplacement d'éléments fréquents par des codes courts, et vice versa, et nous savons également déterminer la longueur moyenne des codes. Mais qu'est-ce que le code, le codage, et comment cela se passe-t-il ?

Encodage sans mémoire

Les codes sans mémoire sont les codes les plus simples sur la base desquels la compression de données peut être effectuée. Dans le code sans mémoire, chaque caractère du vecteur de données codé est remplacé par un mot de code provenant d'un ensemble préfixé de séquences ou de mots binaires.
À mon avis, ce n'est pas la définition la plus compréhensible. Examinons ce sujet un peu plus en détail.

Qu'un peu d'alphabet soit donné , composé d'un certain nombre (fini) de lettres. Appelons chaque suite finie de caractères de cet alphabet (A = a 1, a 2, ..., a n) mot, et le nombre n est la longueur de ce mot.

Qu'un autre alphabet soit également donné ... De même, désignons un mot de cet alphabet par B.

Introduisons deux autres notations pour l'ensemble de tous les mots non vides de l'alphabet. Soit le nombre de mots non vides dans le premier alphabet, et - dans le second.

Soit aussi une application F, qui assigne à chaque mot A du premier alphabet un mot B = F (A) du second. Alors le mot B s'appellera code mot A, et le passage du mot d'origine à son code s'appellera codage.

Puisqu'un mot peut aussi être constitué d'une lettre, on peut identifier la correspondance entre les lettres du premier alphabet et les mots correspondants du second :
un 1<->B 1
un 2<->B 2
…
un<->Bn

Cette correspondance est appelée schème, et sont notés .
Dans ce cas, les mots B 1, B 2, ..., B n appellent codes élémentaires, et le type d'encodage avec leur aide est codage alphabétique... Bien sûr, la plupart d'entre nous ont rencontré ce genre de codage, même sans savoir tout ce que j'ai décrit ci-dessus.

Nous avons donc défini les concepts alphabet, mot, code, et codage... Présentons maintenant le concept préfixe.

Laissez le mot B avoir la forme B = B "B" ". Alors B" est appelé le début, ou préfixe mot B, et B "" est sa fin. Il s'agit d'une définition assez simple, mais il convient de noter que pour tout mot B, un certain mot vide ("espace") et le mot B lui-même peuvent être considérés à la fois comme des débuts et des fins.

Ainsi, nous nous rapprochons de la définition des codes sans mémoire. La dernière définition que nous devons comprendre est l'ensemble de préfixes. Le schéma ∑ a la propriété de préfixe si pour tout 1≤i, j≤r, i ≠ j, le mot B i n'est pas un préfixe du mot B j.
En termes simples, un ensemble de préfixes est un ensemble fini dans lequel aucun élément n'est le préfixe (ou le début) d'un autre élément. Un exemple simple un tel ensemble est, par exemple, un alphabet ordinaire.

Nous avons donc trouvé les définitions de base. Alors, comment se passe l'encodage réel sans mémoire ?
Il se déroule en trois étapes.

1. Un alphabet de Ψ symboles du message original est compilé, et les symboles de l'alphabet sont triés par ordre décroissant de leur probabilité d'occurrence dans le message.
2. Chaque symbole a i de l'alphabet Ψ est associé à un certain mot B i de l'ensemble de préfixes .
3. Chaque caractère est codé, suivi de la combinaison des codes en un seul flux de données, qui sera le résultat de la compression.

L'un des algorithmes canoniques qui illustre cette méthode est l'algorithme de Huffman.

Algorithme de Huffman

L'algorithme de Huffman utilise la fréquence d'occurrence des mêmes octets dans le bloc de données d'entrée et affecte les blocs fréquents à des chaînes de bits plus courtes, et vice versa. Ce code est minimalement redondant. Considérons le cas où, indépendamment de flux d'entrée, l'alphabet du flux de sortie se compose de seulement 2 caractères - zéro et un.

Tout d'abord, lors du codage avec l'algorithme de Huffman, nous devons construire un circuit ∑. Cela se fait comme suit:

1. Toutes les lettres de l'alphabet d'entrée sont classées par ordre décroissant de probabilités. Tous les mots de l'alphabet du flux de sortie (c'est-à-dire avec quoi nous allons encoder) sont initialement considérés comme vides (rappelons que l'alphabet du flux de sortie n'est constitué que de caractères (0,1)).
2. Deux symboles a j-1 et a j du flux d'entrée, qui ont les probabilités d'occurrence les plus faibles, sont combinés en un "pseudo-symbole" avec la probabilité pégal à la somme des probabilités des symboles qu'il contient. Puis on ajoute 0 au début du mot B j-1, et 1 au début du mot B j, qui seront par la suite les codes des caractères a j-1 et a j, respectivement.
3. On retire ces symboles de l'alphabet du message d'origine, mais on ajoute le pseudo-symbole généré à cet alphabet (bien entendu, il faut l'insérer dans l'alphabet au bon endroit, en tenant compte de sa probabilité).

Les étapes 2 et 3 sont répétées jusqu'à ce qu'il ne reste plus qu'un pseudo-caractère dans l'alphabet, contenant tous les caractères originaux de l'alphabet. Dans ce cas, puisqu'à chaque étape et pour chaque caractère, le mot correspondant B i change (en ajoutant un ou zéro), alors à l'issue de cette procédure, un certain code B i correspondra à chaque symbole initial de l'alphabet a je.

Pour une meilleure illustration, considérons un petit exemple.
Supposons que nous ayons un alphabet composé de seulement quatre caractères - (a 1, a 2, a 3, a 4). Supposons également que les probabilités d'occurrence de ces symboles soient respectivement p 1 = 0,5 ; p2 = 0,24 ; p3 = 0,15 ; p 4 = 0,11 (la somme de toutes les probabilités est évidemment égale à un).

Alors, construisons un schéma pour un alphabet donné.

1. Nous combinons les deux caractères avec les probabilités les plus faibles (0,11 et 0,15) en un pseudo-caractère p".
2. Combinez les deux caractères avec la probabilité la plus faible (0,24 et 0,26) dans le pseudo-caractère p "".
3. Supprimez les caractères concaténés et insérez le pseudo-caractère résultant dans l'alphabet.
4. Enfin, nous combinons les deux symboles restants pour obtenir le sommet de l'arbre.

Si vous faites une illustration de ce processus, vous obtenez quelque chose comme ceci :

Comme vous pouvez le voir, chaque fois que nous fusionnons, nous attribuons les codes 0 et 1 aux caractères fusionnés.
De cette façon, lorsque l'arbre est construit, nous pouvons facilement obtenir le code pour chaque caractère. Dans notre cas, les codes ressembleront à ceci :

Un 1 = 0
un 2 = 11
un 3 = 100
un 4 = 101

Étant donné qu'aucun de ces codes n'est le préfixe d'un autre (c'est-à-dire que nous avons le fameux ensemble de préfixes), nous pouvons identifier de manière unique chaque code dans le flux de sortie.
Ainsi, nous avons réussi à ce que le caractère le plus fréquent soit encodé par le code le plus court, et vice versa.
Si nous supposons qu'au départ un octet a été utilisé pour stocker chaque caractère, nous pouvons calculer de combien nous avons réussi à réduire les données.

Supposons que nous ayons une chaîne de 1000 caractères à l'entrée, dans laquelle le caractère a 1 apparaît 500 fois, 2 - 240, 3 - 150 et 4 - 110 fois.

Initialement chaîne donnée occupé 8000 bits. Après encodage, on obtient une chaîne de longueur ∑p i l i = 500 * 1 + 240 * 2 + 150 * 3 + 110 * 3 = 1760 bits. Ainsi, nous avons réussi à compresser les données par un facteur de 4,54, en dépensant en moyenne 1,76 bits pour encoder chaque caractère du flux.

Permettez-moi de vous rappeler que selon Shannon, la longueur moyenne des codes est. En substituant nos probabilités dans cette équation, nous obtenons la longueur de code moyenne égale à 1,75496602732291, ce qui est très, très proche de notre résultat.
Cependant, il convient de garder à l'esprit qu'en plus des données elles-mêmes, nous devons stocker la table d'encodage, ce qui augmentera légèrement la taille finale des données encodées. De toute évidence, dans différents cas, différentes variantes de l'algorithme peuvent être utilisées - par exemple, il est parfois plus efficace d'utiliser à l'avance un tableau donné probabilités, et parfois - il faut le composer dynamiquement, en passant par les données compressibles.

Conclusion

Ainsi, dans cet article, j'ai essayé de parler des principes généraux selon lesquels la compression sans perte se produit, et j'ai également considéré l'un des algorithmes canoniques - l'encodage de Huffman.
Si l'article est du goût de la communauté habro, alors j'écrirai volontiers une suite, car il y a encore beaucoup de choses intéressantes liées à la compression sans perte ; ce sont à la fois des algorithmes classiques et des transformations de données préliminaires (par exemple, la transformation de Burrows-Wheeler), et, bien sûr, des algorithmes spécifiques pour compresser l'audio, la vidéo et les images (le sujet le plus intéressant, à mon avis).

Littérature

• Vatolin D., Ratushnyak A., Smirnov M., Yukin V. Méthodes de compression de données. Le dispositif des archiveurs, compression d'images et de vidéos ; ISBN 5-86404-170-X ; 2003 r.
• D. Salomon. Compression de données, d'images et de sons ; ISBN 5-94836-027-X ; 2004

Principes de compression de l'information

Toute méthode de compression d'informations est basée sur un modèle de source d'informations, ou, plus précisément, un modèle de redondance. En d'autres termes, pour compresser des informations, certaines informations sont utilisées sur le type d'informations compressées - sans aucune information sur les informations, aucune hypothèse ne peut être faite sur la transformation qui réduira le volume du message. Ces informations sont utilisées dans le processus de compression et de décompression. Le modèle de redondance peut également être construit ou paramétré lors de la phase de compression. Les méthodes qui permettent de modifier le modèle de redondance des informations en fonction des données d'entrée sont appelées adaptatives. Les algorithmes non adaptatifs sont généralement des algorithmes étroitement spécifiques utilisés pour travailler avec des caractéristiques bien définies et inchangées. L'écrasante majorité des algorithmes suffisamment universels sont adaptatifs à un degré ou à un autre.

Toute méthode de compression d'informations comprend deux conversions inverses l'une de l'autre :

• conversion de compression;
• conversion d'extension.

La transformation de compression fournit un message compressé à partir de l'original. La décompression garantit que le message d'origine (ou son approximation) est obtenu à partir du message compressé.

Toutes les méthodes de compression sont divisées en deux classes principales

• aucune perte,
• avec des pertes.

La différence fondamentale entre les deux est que la compression sans perte permet de reconstruire avec précision le message d'origine. La compression avec perte vous permet d'obtenir uniquement une approximation du message d'origine, c'est-à-dire différent de l'original, mais avec quelques erreurs prédéterminées. Ces erreurs doivent être déterminées par un autre modèle - le modèle du récepteur, qui détermine quelles données et avec quelle précision sont présentées au récepteur, et lesquelles sont acceptables à rejeter.

Caractéristiques et applicabilité de l'algorithme de compression

Ratio de compression

Le taux de compression est la principale caractéristique de l'algorithme de compression, qui exprime la principale qualité appliquée. Il est défini comme le rapport entre la taille des données non compressées et compressées, c'est-à-dire :

k = S o / S c,

où k- ratio de compression, S o est la taille des données non compressées, et S c - la taille du compressé. Ainsi, plus le taux de compression est élevé, meilleur est l'algorithme. Ça devrait être noté:

• si k= 1, alors l'algorithme ne compresse pas, c'est-à-dire qu'il reçoit un message de sortie d'une taille égale à celui d'entrée ;
• si k < 1, то алгоритм порождает при сжатии сообщение большего размера, нежели несжатое, то есть, совершает «вредную» работу.

La situation avec k < 1 вполне возможна при сжатии. Невозможно получить алгоритм сжатия без потерь, который при любых данных образовывал бы на выходе данные меньшей или равной длины. Обоснование этого факта заключается в том, что количество различных сообщений длиной m Motif : E : le bit est exactement 2 m... Ensuite, le nombre de messages différents de longueur inférieure ou égale à m(s'il y a au moins un message de longueur plus courte) sera inférieur à 2 m... Cela signifie qu'il est impossible de faire correspondre sans ambiguïté tous les messages originaux à un message compressé : soit certains des messages originaux n'auront pas de représentation compressée, soit plusieurs messages originaux correspondront au même message compressé, ce qui signifie qu'ils ne peuvent pas être distingués.

Le taux de compression peut être soit un taux constant (certains algorithmes de compression pour le son, les images, etc., par exemple, loi A, loi μ, ADPCM), soit variable. Dans le second cas, il peut être déterminé soit pour un message précis, soit évalué selon certains critères :

• moyenne (généralement sur certains ensembles de données de test) ;
• maximum (cas de la meilleure compression) ;
• minimale (compression dans le pire des cas) ;

ou un autre. Le taux de compression avec perte dans ce cas dépend fortement de l'erreur de compression admissible ou de son qualité, qui agit généralement comme un paramètre de l'algorithme.

Tolérance aux pertes

Le principal critère de distinction entre les algorithmes de compression est la présence ou l'absence des pertes décrites ci-dessus. En général, les algorithmes de compression sans perte sont polyvalents dans le sens où ils peuvent être appliqués à tout type de données, tandis que l'utilisation de la compression avec perte doit être justifiée. Certains types de données ne tolèrent aucun type de perte :

• des données symboliques, un changement dans lequel entraîne inévitablement un changement dans leur sémantique : programmes et leurs codes sources, tableaux binaires, etc.
• données vitales, dont les modifications peuvent entraîner des erreurs critiques : par exemple, obtenues à partir d'équipements de mesure médicaux ou de dispositifs de contrôle d'aéronefs, d'engins spatiaux, etc.
• données soumises à plusieurs reprises à la compression et à la décompression : fichiers graphiques, sonores, vidéo de travail.

Cependant, la compression avec perte vous permet d'atteindre des taux de compression beaucoup plus élevés en éliminant les informations insignifiantes qui ne se compressent pas bien. Ainsi, par exemple, l'algorithme de compression audio sans perte FLAC permet dans la plupart des cas de compresser l'audio de 1,5 à 2,5 fois, tandis que l'algorithme Vorbis avec perte, en fonction du paramètre de qualité défini, peut compresser jusqu'à 15 fois tout en conservant une qualité sonore acceptable.

Configuration système requise pour l'algorithme

Différents algorithmes peuvent nécessiter différentes quantités de ressources système informatique sur lesquels sont effectués :

• mémoire vive (pour les données intermédiaires);
• mémoire permanente (pour le code de programme et les constantes) ;
• temps processeur.

En général, ces exigences dépendent de la complexité et de "l'intelligence" de l'algorithme. En règle générale, plus l'algorithme est performant et polyvalent, plus il sollicite la machine. Cependant, dans des cas spécifiques, des algorithmes simples et compacts peuvent être plus performants. Les exigences du système déterminent leurs qualités de consommateur : moins un algorithme est exigeant, plus il peut fonctionner sur un système simple et donc compact, fiable et bon marché.

Étant donné que les algorithmes de compression et de décompression fonctionnent par paires, le rapport Configuration requise pour eux. Vous pouvez souvent compliquer un algorithme, vous pouvez grandement simplifier l'autre. Ainsi, nous pouvons avoir trois options :

L'algorithme de compression est beaucoup plus gourmand en ressources que l'algorithme de décompression. Il s'agit de la relation la plus courante et elle s'applique principalement dans les cas où des données compressées seront utilisées plusieurs fois. Les exemples incluent les lecteurs audio et vidéo numériques. Les algorithmes de compression et de décompression ont des exigences à peu près égales. L'option la plus acceptable pour une ligne de communication, lorsque la compression et la décompression se produisent une fois à ses deux extrémités. Par exemple, il peut s'agir de téléphonie. L'algorithme de compression est nettement moins exigeant que l'algorithme de décompression. Un cas assez exotique. Il peut être utilisé dans les cas où l'émetteur est un appareil ultra-portable, où la quantité de ressources disponibles est très critique, par exemple, un vaisseau spatial ou un grand réseau distribué de capteurs, ou il peut s'agir de décompresser des données nécessaires dans un très faible pourcentage de cas, par exemple, l'enregistrement de caméras de vidéosurveillance.

voir également

Fondation Wikimédia. 2010.

Voyez ce qu'est « Compression d'informations » dans d'autres dictionnaires :

compression d'informations- consolidation des informations - [L.G. Sumenko. Le dictionnaire anglais russe des technologies de l'information. M.: GP TsNIIS, 2003.] Thèmes technologies de l'information en général Synonymes compactage de l'information FR réduction de l'information ...

COMPRESSION DES INFORMATIONS- (compression de données) présentation des informations (données) en moins de bits que l'original. Basé sur l'élimination de la redondance. Distinguer S. et. sans perte d'informations et avec la perte de certaines informations insignifiantes pour les tâches à résoudre. À… … Dictionnaire encyclopédique de psychologie et de pédagogie

compression adaptative sans perte- - [L.G. Sumenko. Le dictionnaire anglais russe des technologies de l'information. Moscou : GP TsNIIS, 2003.] Thèmes technologies de l'information en général EN compression de données adaptative sans perteALDC ... Guide du traducteur technique

compression / compression d'informations- - [L.G. Sumenko. Le dictionnaire anglais russe des technologies de l'information. M.: GP TsNIIS, 2003.] Thèmes technologies de l'information en général EN compactage ... Guide du traducteur technique

compression d'informations numériques- - [L.G. Sumenko. Le dictionnaire anglais russe des technologies de l'information. M. : GP TsNIIS, 2003.] Thèmes technologies de l'information en général compression EN ... Guide du traducteur technique

Le son est une simple onde, et signal numérique est une représentation de cette vague. Ceci est obtenu en mémorisant l'amplitude Signal analogique plusieurs fois en une seconde. Par exemple, dans un CD ordinaire, un signal est mémorisé 44100 fois dans ... ... Wikipedia

Un processus qui réduit la quantité de données en réduisant la redondance. La compression de données consiste à compacter des blocs de données de taille standard. Une distinction est faite entre la compression avec perte et sans perte. En anglais : Données ...... Vocabulaire financier

compression de carte numérique- Traitement de l'information cartographique numérique afin d'en réduire le volume, y compris l'élimination de la redondance dans la précision requise de sa présentation. [GOST 28441 99] Thèmes cartographie numérique Termes généraux méthodes et technologies ... ... Guide du traducteur technique

Le but du cours : développer l'attention, l'intelligence, susciter l'intérêt pour le sujet.
Matériel : ordinateurs, disques de laboratoire, Logiciel, cartes avec une tâche de test.

Pendant les cours

1. Partie organisationnelle.
2. Actualisation des connaissances de base.
3. Apprendre du nouveau matériel
4. Sécurisation du nouveau matériel.
5. Devoirs.
6. Résumer la leçon.

Apprendre du nouveau matériel

1. Qu'est-ce que l'archivage. Notion de compression de données.
2. Les principaux types de programmes d'archivage.
3. Programme-archiveur WIN-RAR.
4. Comment ajouter un fichier à l'archive, ainsi que l'extraire de l'archive.

Avec le développement technologies de l'information la question de savoir comment stocker les données s'est rapidement posée. Depuis les années 40 du XXe siècle, les scientifiques ont développé des méthodes de présentation des données, dans lesquelles l'espace sur les supports d'information serait utilisé de manière plus économique. Le résultat est une technologie de compression et d'archivage des données (sauvegarde).

L'archivage des données est la fusion de plusieurs fichiers ou répertoires en un seul fichier d'archive.

Compression des données - réduction de la taille des fichiers originaux en éliminant les informations redondantes.

Pour accomplir ces tâches, il existe des programmes d'archivage qui fournissent compression de données : notamment archivage de fichiers. À l'aide d'algorithmes spéciaux, les archiveurs suppriment toutes les informations redondantes des fichiers et, lors des opérations de décompression inverse, ils restaurent les informations dans leur forme d'origine. La taille fichier compressé deux à dix fois moins que le fichier d'origine. Dans ce cas, la compression et la restauration des informations s'effectuent sans perte. La compression sans perte est pertinente lorsque vous travaillez avec des fichiers texte et programme, dans des tâches de cryptographie. Il existe également des techniques de compression avec perte.

Le taux de compression dépend du type de fichiers et du programme d'archivage. Surtout rétrécir fichiers texte, encore moins - les fichiers audio et vidéo.

Archivage des fichiers. Tâches

Jusqu'à présent, nous avons parlé d'un objectif de l'archivage des données - une utilisation plus économique des supports de stockage. Cependant, grâce à l'archivage, vous pouvez effectuer toute une série de tâches :
1. Réduire le volume des fichiers (important non seulement pour économiser de l'espace sur le support, mais aussi pour transférer rapidement des fichiers sur le réseau).
2. Sauvegarde sur un support externe pour stocker des informations importantes.

3. Archivage lors du cryptage des données afin de réduire la probabilité de casser le cryptosystème.

Le processus d'écriture d'informations dans un fichier d'archive est appelé archivage.
Extraction de fichiers de l'archive - décompression.

Les premiers programmes d'archivage sont apparus au milieu des années 80. Ils se concentraient sur le travail dans MS-DOC et prenaient en charge les formats d'archives populaires : ARC, ICE, ARJ, ZIP et RAR, etc. Il y avait également un groupe d'archiveurs qui emballait les données dans des archives auto-extractibles - des fichiers avec des extensions. ee ,. com. Des archiveurs résidents ont été créés pour compresser l'intégralité du disque. Ils ont permis d'augmenter l'efficacité de l'utilisation de l'espace disque en créant de gros fichiers d'archive - des « compressions » de disque.

Travailler avec des archives est devenu beaucoup plus pratique avec l'avènement des versions Windows et Windows des archiveurs. Des anciens formats d'archives parmi Utilisateurs Windows ARJ, ZIP - les programmes qui décompressent les fichiers ont vraiment pris racine. Les fichiers d'archives de grande taille peuvent se trouver sur plusieurs disquettes (volumes). De telles archives sont appelées multivolumes.

Tom est composant archives multivolumes.

Des dizaines de programmes d'archivage sont désormais utilisés, qui diffèrent par la liste des fonctions et des paramètres de fonctionnement, mais les meilleurs d'entre eux ont à peu près les mêmes caractéristiques. Nous savons que l'emballage et le déballage des fichiers sont effectués par le même programme, mais dans certains cas, il est effectué différents programmes, par exemple, le programme RKZIP compresse les fichiers et RKUNZIP décompresse les fichiers.
Les programmes d'archivage vous permettent de créer de telles archives, pour l'extraction à partir desquelles vous n'avez besoin d'aucun programme, car les fichiers d'archive contiennent un programme auto-extractible. Ces archives sont appelées archives SFX.

Placer des fichiers dans une archive : Démarrez Programmes WINRAR ou en tant que raccourci sur le bureau.

Archiveur universel WINRAR

L'archiveur WINRAR est également destiné à l'archivage de fichiers. Il possède une interface graphique pratique et prend en charge la technologie Drag and Drop. Le logiciel WINRAR vous permet de travailler non seulement avec des archives fichiers rar, mais aussi avec d'autres formats d'archives : zip, cab, arj, lzh. WINRAR est lancé par l'un des voies possibles fourni dans Windows. Lancement du programme à l'aide du menu principal du bouton Démarrer Programmes WINRAR WINRAR ou à l'aide d'un raccourci sur le bureau.

Enquête de test sur les bases de l'utilisation des disques.
Devoirs.
Leçon d'introspection.

Pour accomplir ces tâches, il existe des programmes d'archivage qui assurent à la fois l'archivage et la compression des données.À l'aide d'algorithmes spéciaux, les archiveurs suppriment toutes les informations redondantes des fichiers et, lors des opérations de décompression inversée, restaurent les informations dans leur forme d'origine. La taille du fichier compressé est de deux à dix fois inférieure à celle du fichier d'origine.

De nos jours, de nombreux utilisateurs réfléchissent à la manière dont le processus de compression des informations est effectué afin d'économiser de l'espace libre sur le disque dur, car c'est l'un des plus des moyens efficaces utilisation de l'espace utilisable dans n'importe quel lecteur. Assez souvent, les utilisateurs modernes confrontés à un manque d'espace libre sur un disque doivent supprimer toutes les données afin de libérer l'espace nécessaire, tandis que les utilisateurs plus avancés utilisent le plus souvent la compression de données afin de réduire leur volume.

Cependant, beaucoup ne savent même pas comment s'appelle le processus de compression d'informations, sans parler des algorithmes utilisés et de ce que donne l'application de chacun d'eux.

Faut-il compresser les données ?

La compression des données est assez importante aujourd'hui et est nécessaire pour tout utilisateur. Bien sûr, à notre époque, presque tout le monde peut acheter des périphériques de stockage de données avancés qui permettent d'utiliser une assez grande quantité d'espace libre, ainsi que des canaux à haut débit pour diffuser des informations.

Cependant, dans ce cas, vous devez bien comprendre qu'au fil du temps, la quantité de données à transférer augmente également. Et s'il y a littéralement dix ans, le volume de 700 Mo était considéré comme la norme pour un film ordinaire, aujourd'hui les films réalisés en qualité HD peuvent avoir des volumes égaux à plusieurs dizaines de gigaoctets, sans parler de l'espace libre occupé par des films de haute qualité. au format Blu-ray.

Quand la compression des données est-elle nécessaire ?

Bien sûr, vous ne devez pas vous attendre à ce que le processus de compression d'informations vous apporte beaucoup d'avantages, mais il existe un certain nombre de situations dans lesquelles certaines méthodes de compression d'informations sont extrêmement utiles et même nécessaires :

• Transfert de certains documents par e-mail. Cela est particulièrement vrai dans les situations où vous devez transférer des informations en gros volumes à l'aide de divers appareils mobiles.
• Souvent le procédé de compression d'informations afin de réduire l'espace qu'elles occupe est utilisé lors de la publication de certaines données sur différents sites lorsqu'il est nécessaire d'économiser du trafic ;
• Économisez de l'espace libre sur votre disque dur lorsqu'il n'y a aucun moyen de remplacer ou d'ajouter de nouveaux supports de stockage. En particulier, la situation la plus courante est lorsqu'il existe certaines restrictions sur le budget disponible, mais qu'il n'y a pas assez d'espace disque libre.

Bien sûr, en plus de ce qui précède, il y a aussi nombre énorme diverses situations dans lesquelles le processus de compression de l'information peut être requis afin de réduire son volume, cependant, ce sont de loin les plus courantes.

Comment compresser les données ?

Aujourd'hui, il existe une grande variété de méthodes de compression d'informations, mais elles sont toutes divisées en deux groupes principaux - il s'agit de la compression avec certaines pertes, ainsi que de la compression sans perte.

L'utilisation du dernier groupe de méthodes est pertinente lorsque les données doivent être récupérées avec une précision extrêmement élevée, jusqu'à un bit. Cette approche est la seule pertinente dans le cas où un certain document texte est compressé.

Dans le même temps, il convient de noter que dans certaines situations, la récupération la plus précise des données compressées n'est pas nécessaire. Par conséquent, il est possible d'utiliser de tels algorithmes dans lesquels les informations sur le disque sont compressées avec certaines pertes. L'avantage de la compression avec perte est que cette technologie est beaucoup plus simple à mettre en œuvre et offre également le plus haut degré d'archivage possible.

La compression avec perte

Les informations avec pertes offrent une meilleure compression d'un ordre de grandeur, tout en maintenant une qualité d'information suffisante. Dans la plupart des cas, l'utilisation de tels algorithmes est effectuée pour compresser des données analogiques, telles que toutes sortes d'images ou de sons. Dans de telles situations, les fichiers décompressés peuvent être très différents des informations d'origine, mais ils sont pratiquement impossibles à distinguer de l'œil ou de l'oreille humaine.

Compression sans perte

Les algorithmes de compression sans perte fournissent la récupération de données la plus précise, éliminant toute perte de fichiers compressés. Cependant, vous devez bien comprendre le fait que dans ce cas, une compression de fichier moins efficace est fournie.

Méthodes génériques

Entre autres choses, il y a une certaine série méthodes universelles par lequel un processus efficace de compression de l'information est effectué afin de réduire l'espace qu'elle occupe. En général, il n'y a que trois technologies principales :

• Transformation de flux. Dans ce cas, la description des nouvelles informations non compressées entrantes est effectuée à travers les fichiers déjà traités, alors qu'aucune probabilité n'est calculée, mais les caractères sont codés en fonction uniquement des fichiers qui ont déjà subi un certain traitement.
• Compression statistique. Ce processus de compression d'informations afin de réduire l'espace qu'il occupe sur le disque est divisé en deux sous-catégories - les méthodes adaptatives et par blocs. La version adaptative permet de calculer les probabilités de nouveaux fichiers sur la base d'informations qui ont déjà été traitées lors du processus d'encodage. En particulier, ces méthodes devraient également inclure diverses variantes adaptatives des algorithmes de Shannon-Fano et Huffman. L'algorithme de bloc prévoit un calcul séparé de chaque bloc d'informations avec un ajout ultérieur au bloc le plus compressé.
• Bloquer la transformation. Les informations entrantes sont divisées en plusieurs blocs, puis une transformation holistique a lieu. Il faut dire que certaines méthodes, notamment celles basées sur la permutation de plusieurs blocs, peuvent in fine conduire à une diminution importante de la quantité d'informations compressibles. Cependant, il faut bien comprendre qu'après un tel traitement, une amélioration significative se produit finalement, de sorte que la compression ultérieure via d'autres algorithmes est beaucoup plus facile et plus rapide.

Copier la compression

L'un des composants les plus importants Réserver une copie est-ce que l'appareil doit être déplacé vers nécessaire à l'utilisateur informations. Plus vous déplacez de données, plus vous aurez besoin d'un appareil volumineux. Cependant, si vous envisagez de compresser des données, il est peu probable que dans ce cas, le problème du manque d'espace libre reste pertinent pour vous.

Pourquoi est-ce nécessaire ?

La possibilité de compresser les informations tout en réduisant considérablement le temps nécessaire à la copie fichiers requis et en même temps réaliser des économies effectives d'espace libre sur le disque. En d'autres termes, lors de l'utilisation de la compression, les informations seront copiées de manière beaucoup plus compacte et rapide, et vous pourrez économiser votre argent et vos finances, ce qui était nécessaire pour acheter un disque plus gros. Entre autres, en compressant les informations, vous réduisez également le temps qui sera nécessaire pour transporter toutes les données vers le serveur ou les copier sur le réseau.

La compression des données pour la sauvegarde peut être effectuée dans un ou plusieurs fichiers - dans ce cas, tout dépendra du programme que vous utilisez et des informations que vous compressez.

Lorsque vous choisissez un utilitaire, assurez-vous de vérifier dans quelle mesure le programme que vous avez choisi peut compresser les données. Cela dépend du type d'informations, à la suite de quoi l'efficacité de la compression des documents texte peut être supérieure à 90%, tandis que l'efficacité ne dépassera pas 5%.

Comme mentionné ci-dessus, l'une des tâches importantes préparation préliminaire chiffrer les données est de réduire leur redondance et d'aligner les schémas statistiques de la langue utilisée. L'élimination partielle de la redondance est obtenue en compressant les données.

Compression des informations est le processus de conversion du message original d'un système de code à un autre, à la suite de quoi taille du message... Les algorithmes conçus pour compresser les informations peuvent être divisés en deux grands groupes : ceux qui implémentent la compression sans perte (compression réversible) et ceux qui implémentent la compression avec perte (compression irréversible).

Compression réversible implique une récupération de données absolument précise après décodage et peut être utilisé pour compresser n'importe quelle information. Elle conduit toujours à une diminution du volume du flux d'informations de sortie sans modifier son contenu d'informations, c'est-à-dire sans perdre structure d'informations... De plus, à partir du flux de sortie, en utilisant l'algorithme de récupération ou de décompression, vous pouvez obtenir l'entrée, et le processus de récupération est appelé décompression ou décompression, et ce n'est qu'après le processus de décompression que les données peuvent être traitées conformément à leur format interne. La compression sans perte est utilisée pour le texte, les fichiers exécutables, le son et les graphiques de haute qualité.

Compression irréversible a généralement un taux de compression beaucoup plus élevé que le codage sans perte, mais permet quelques écarts des données décodées par rapport à l'original. Dans la pratique, il existe un large éventail de problèmes pratiques dans lesquels le respect de l'exigence de restauration précise des informations d'origine après décompression n'est pas obligatoire. Ceci s'applique notamment à la compression d'informations multimédias : images sonores, photo ou vidéo. Par exemple, les formats multimédia JPEG et MPEG, qui utilisent une compression irréversible, sont largement utilisés. La compression irréversible n'est généralement pas utilisée en conjonction avec le cryptage cryptographique, car la principale exigence d'un système cryptographique est l'identité des données décryptées avec celles d'origine. Cependant, lors de l'utilisation de technologies multimédias, les données présentées dans forme numérique sont souvent compressés de manière irréversible avant d'être envoyés à un système cryptographique pour le cryptage. Une fois les informations transférées au consommateur et décryptées, les fichiers multimédias sont utilisés sous une forme compressée (c'est-à-dire qu'ils ne sont pas restaurés).

Examinons de plus près certaines des méthodes les plus courantes de compression de données réversible.

L'approche et l'algorithme simples les plus connus pour compresser les informations de manière réversible sont le codage de longueur d'exécution (RLE). L'essence des méthodes de cette approche est de remplacer des chaînes ou des séries d'octets répétés par un remplisseur d'octets de codage et un compteur du nombre de leurs répétitions. Le problème avec toutes les méthodes analogues est uniquement de déterminer la manière dont l'algorithme de décompression pourrait distinguer la série codée dans le flux d'octets résultant des autres - et non des séquences d'octets codées. La solution au problème est généralement obtenue en plaçant des étiquettes au début des chaînes codées. De telles étiquettes peuvent être des valeurs de bits caractéristiques dans le premier octet de l'exécution codée, les valeurs du premier octet de l'exécution codée. L'inconvénient de la méthode RLE est le taux de compression plutôt faible ou le coût d'encodage des fichiers avec un petit nombre de séries et, pire encore, avec un petit nombre d'octets répétés dans une série.

Avec un codage uniforme des informations, le même nombre de bits est affecté à un message, quelle que soit la probabilité de son apparition. Dans le même temps, il est logique de supposer que la longueur totale des messages transmis diminuera si les messages fréquents sont codés avec des mots de code courts, et les rares - avec des mots plus longs. Les problèmes qui se posent dans ce cas sont liés à la nécessité d'utiliser codes de longueur variable... Il existe de nombreuses approches pour créer de tels codes.

L'une des méthodes les plus utilisées en pratique est celle des dictionnaires, dont les principaux représentants sont les algorithmes des familles Ziv et Lempel. Leur idée principale est que les fragments du flux d'entrée ("phrases") sont remplacés par un pointeur vers l'endroit où ils sont déjà apparus dans le texte. Dans la littérature, de tels algorithmes sont appelés algorithmes Compression LZ.

Cette méthode s'adapte rapidement à la structure du texte et peut encoder des mots fonctionnels courts, car ils y apparaissent très souvent. De nouveaux mots et expressions peuvent également être formés à partir de parties de mots déjà rencontrés. Le décodage du texte compressé est effectué directement - il y a un simple remplacement du pointeur par une phrase toute faite du dictionnaire vers laquelle il pointe. En pratique, la méthode LZ permet d'obtenir une bonne compression, sa propriété importante est le travail très rapide du décodeur.

Une autre approche pour compresser l'information est Code de Huffman, dont l'encodeur et le décodeur ont une implémentation matérielle assez simple. L'idée de l'algorithme est la suivante : connaissant les probabilités d'occurrence de caractères dans un message, on peut décrire la procédure de construction de codes de longueur variable constitués d'un nombre entier de bits. Les symboles sont plus susceptibles d'être attribués à plus de codes courts, tandis que les caractères moins courants sont plus longs. Cela permet d'obtenir une réduction de la longueur moyenne du mot de code et une efficacité de compression plus élevée. Les codes de Huffman ont un préfixe unique (le début du mot de code), qui leur permet d'être décodés de manière unique, malgré leur longueur variable.

La procédure de synthèse pour le code de Huffman classique suppose la présence d'informations a priori sur les caractéristiques statistiques de la source du message. En d'autres termes, le développeur doit être conscient des probabilités d'occurrence de certains symboles à partir desquels des messages sont formés. Considérons la synthèse du code de Huffman à l'aide d'un exemple simple.

p (S 1) = 0,2, p (S 2) = 0,15, p (S 3) = 0,55, p (S 4) = 0,1... Trions les symboles par ordre décroissant de probabilité d'occurrence et présentons-les sous forme de tableau (Fig. 14.3, a).

La procédure de synthèse de code comprend trois étapes principales. A la première étape, les lignes du tableau sont repliées : deux lignes correspondant aux symboles avec les probabilités d'occurrence les plus faibles sont remplacées par une avec la probabilité totale, après quoi le tableau est à nouveau réordonné. La convolution se poursuit jusqu'à ce qu'il n'y ait qu'une seule ligne dans le tableau avec une probabilité totale égale à un (Fig. 14.3, b).

Riz. 14.3.

À la deuxième étape, un arbre de code est construit à l'aide d'un tableau réduit (Fig. 14.4, a). L'arbre est construit à partir de la dernière colonne du tableau.

Riz. 14.4.

La racine de l'arbre forme l'unité dans la dernière colonne. Dans l'exemple considéré, cette unité est formée des probabilités 0,55 et 0,45, représentées par deux nœuds d'arbre associés à la racine. Le premier d'entre eux correspond au symbole S 3 et, par conséquent, aucun autre branchement de ce nœud ne se produit.

Le deuxième nœud, étiqueté avec une probabilité de 0,45, se connecte à deux nœuds du troisième niveau, avec des probabilités de 0,25 et 0,2. La probabilité 0,2 correspond au symbole S 1 et la probabilité 0,25, à son tour, est formée des probabilités 0,15 d'apparition du symbole S 2 et 0,1 d'apparition du symbole S 4.

Les bords reliant les nœuds individuels de l'arbre de code sont numérotés 0 et 1 (par exemple, les bords gauches sont 0 et les bords droits sont 1). A la troisième étape finale, une table est construite dans laquelle les symboles sources et les mots de code Huffman correspondants sont comparés. Ces mots de code sont formés en lisant les nombres qui marquent les bords qui forment un chemin de la racine de l'arbre au symbole correspondant. Pour l'exemple considéré, le code de Huffman prendra la forme indiquée dans le tableau de droite (Fig. 14.4, b).

Cependant, l'algorithme de Huffman classique présente un inconvénient important. Pour récupérer le contenu du message compressé, le décodeur doit connaître la table de fréquence utilisée par le codeur. Par conséquent, la longueur du message compressé est augmentée de la longueur de la table de fréquences à envoyer devant les données, ce qui peut annuler tous les efforts de compression du message.

Une autre variante codage Huffman statique consiste à visualiser le flux d'entrée et à construire un encodage basé sur les statistiques collectées. Cela nécessite deux passages dans le fichier - un pour la visualisation et la collecte d'informations statistiques, le second pour l'encodage. Dans le codage statique de Huffman, les symboles d'entrée (chaînes de bits de différentes longueurs) sont associés à des chaînes de bits de longueur variable - leurs codes. La longueur du code de chaque symbole est prise proportionnelle au logarithme binaire de sa fréquence, pris avec le signe opposé. Et l'ensemble commun de tous les différents symboles rencontrés constitue l'alphabet du flux.

Il existe une autre méthode - adaptative ou codage dynamique de Huffman... Le sien principe général consiste à modifier le schéma de codage en fonction de la nature des changements dans le flux d'entrée. Cette approche a un algorithme à une passe et ne nécessite pas de stocker des informations sur l'encodage utilisé sous une forme explicite. Le codage adaptatif peut donner un taux de compression plus élevé que le codage statique, car les changements dans les fréquences du flux d'entrée sont mieux pris en compte. Lors de l'utilisation du codage de Huffman adaptatif, la complexité de l'algorithme consiste en la nécessité d'ajuster en permanence l'arbre et les codes des caractères de l'alphabet de base en fonction des statistiques changeantes du flux d'entrée.

Les méthodes de Huffman donnent une vitesse assez élevée et modérée bonne qualité compression. Cependant, le codage de Huffman a une redondance minimale, à condition que chaque caractère soit codé dans l'alphabet de code de caractère avec une chaîne distincte de deux bits - (0, 1). Le principal inconvénient cette méthode est la dépendance du taux de compression sur la proximité des probabilités des symboles à 2 à un certain degré négatif, ce qui est dû au fait que chaque symbole est codé avec un nombre entier de bits.

Une solution complètement différente est offerte par codage arithmétique... Cette méthode est basée sur l'idée de convertir un flux d'entrée en un seul nombre à virgule flottante. Le codage arithmétique est une technique de compactage sans perte de caractères alphabétiques d'entrée, à condition que la distribution de fréquence de ces caractères soit connue.

La séquence de caractères requise estimée lorsqu'elle est compressée par la méthode de codage arithmétique est considérée comme une fraction binaire de l'intervalle)