Quel est le processus de compression de données. Codage avec les arbres de Shannon Fano. Déplacer et copier des fichiers et des dossiers compressés

Lecture numéro 4. Compresser des informations

Principes d'informations de compression

Le but de la compression des données est de fournir une représentation compacte des données générées par la source, pour leur économie plus économique et leur transmission par des canaux de communication.

Passons une taille de fichier 1 (un) mégaoctet. Nous devons obtenir un fichier plus petit de celui-ci. Rien de compliqué - Lancement de l'archiveur, par exemple, WinZip et aboutit, par exemple, un fichier de 600 kilo-octets. Où sont les 424 kilo-octets restants?

La compression des informations est l'une des façons de coder. En général, les codes sont divisés en trois grands groupes - codes de compression (codes effectifs), codes résistants au bruit et codes cryptographiques. Les codes conçus pour compresser des informations sont divisés, à son tour, sur des codes sans code de perte et de perte. La codage sans perte implique une récupération de données absolument précise après décodage et peut être utilisée pour compresser toutes les informations. Le codage de perte est généralement un degré de compression beaucoup plus élevé que le codage sans perte, mais permet des écarts de données décodées de la source.

Types de compression

Toutes les méthodes d'informations de compression peuvent être divisées en deux grandes classes non cycles: compression avec perte Information et compression sans perte informations.

Compression sans perte d'informations.

Ces méthodes de compression sont intéressées par nous d'abord, car elles sont elles qu'ils sont utilisés dans le transfert de documents et programmes de texte, lors de la publication d'un client effectué par le travail effectué ou lors de la création de copies de sauvegarde des informations stockées sur un ordinateur.

Les méthodes de compression de cette classe ne peuvent pas permettre la perte d'informations. Ils ne sont donc basés que sur l'élimination de sa redondance, et les informations ont presque toujours la redondance (cependant, si quelqu'un ne l'a plus compliqué). S'il n'y avait pas de redondance, il n'y aurait rien à compresser.

Voici un exemple simple. En russe, 33 lettres, dix chiffres et plus d'une douzaine de marques de ponctuation et d'une demi-douzaine de caractères spéciaux. Pour le texte enregistré seulement avec des lettres majuscules russes (Comme dans les télégrammes et les radiogrammes), il suffirait de soixante valeurs différentes. Cependant, chaque caractère est généralement codé par octet, qui contient 8 bits et peut exprimer 256 codes différents. C'est la première base de la redondance. Pour notre texte "télégraphique", ce serait suffisant pour six bits sur un symbole.

Voici un autre exemple. En caractères de codage internationaux Ascii. Pour encoder n'importe quel symbole, la même quantité de bits (8) est donnée, tandis que tout le monde a longtemps et qu'il est bien connu que les symboles les plus courants ont du sens à encoder moins de caractères. Ainsi, par exemple, dans l'alphabet de morse, les lettres "E" et "T", qui sont souvent codées, sont codées par un signe (respectivement, ceci est un point et un tableau de bord). Et de telles lettres rares, comme "Yu" (- -) et "C" (- - -) sont codées par quatre signes. Le codage inefficace est la deuxième base pour la redondance. Programmes qui compressent des informations peuvent entrer leur codage (différent pour différents fichiers) et attribuez une certaine table (dictionnaire) à un fichier compressé, à partir duquel le programme de déballage apprend à ce fichier Ceux ou d'autres personnages ou leurs groupes sont codés. Les algorithmes basés sur les informations de transcodage sont appelés hafman algorithmes.

La présence de fragments répétés est la troisième base de redondance. Dans les textes, il est rare, mais dans les tables et dans le graphique, la répétition des codes est un phénomène courant. Par exemple, si le numéro 0 est répété vingt fois de suite, il n'a aucun sens de mettre vingt-octets zéro. Au lieu de cela, ils mettent un zéro et un coefficient 20. Ces algorithmes basés sur la révélation de répétitions sont appelés méthodesRle. (COURS. Longueur. Codage).

Les grandes séquences répétitives des mêmes octets sont des illustrations graphiques particulièrement différentes, mais pas photographique (il existe de nombreux points de bruit et de points voisins diffèrent de manière significative dans les paramètres) et ceux que les artistes peignent la couleur "lisse" comme dans les films animés.

Compression avec perte d'informations.

La compression avec perte d'informations signifie qu'après déballage des archives compactées, nous recevrons un document quelque peu différent de celui au tout début. Il est clair que plus le degré de compression est grand, plus la valeur de perte est grande et vice versa.

Bien entendu, de tels algorithmes ne sont pas applicables aux documents texte, aux tables de base de données et en particulier aux programmes. Des distorsions mineures dans un simple texte non formaté peuvent être survécues, mais la distorsion d'au moins un bit dans le programme le rendra absolument inutilisable.

Dans le même temps, il existe des matériaux dans lesquels il vaut la peine de sacrifier quelques pour cent des informations pour obtenir une compression de dizaines de fois. Ceux-ci incluent des illustrations photographiques, des séquences vidéo et des compositions musicales. La perte d'informations dans la compression et le déballage subséquent dans de tels matériaux est perçue comme l'apparition d'un "bruit" supplémentaire. Mais depuis lors, lors de la création de ces matériaux, un certain "bruit" est toujours présent, sa légère augmentation ne semble pas toujours cruciale, et les gains de la taille donnent une énorme (10-15 fois de musique, à 20-30 fois sur la photo et séquences vidéo).

Les algorithmes de compression avec perte d'informations comprennent de tels algorithmes bien connus tels que JPEG et MPEG. L'algorithme JPEG est utilisé lors de la compression des images photo. Les fichiers graphiques compressés par cette méthode ont une extension JPG. Les algorithmes MPEG sont utilisés lors de la vidéo compressée et de la musique. Ces fichiers peuvent avoir des extensions différentes, selon le programme spécifique, mais les plus célèbres sont.mpg pour la vidéo I.MRZ pour la musique.

Les algorithmes de compression avec perte d'informations s'appliquent uniquement aux tâches de consommation. Cela signifie, par exemple, que si la photo est transmise à la vue et que la musique de lecture, alors ces algorithmes peuvent être appliqués. S'ils sont transmis pour un traitement ultérieur, par exemple, pour l'édition, aucune perte d'informations dans le matériau source n'est inacceptable.

L'ampleur de la perte admissible de la compression est généralement possible de contrôler. Cela vous permet d'expérimenter et d'atteindre un rapport optimal de taille / de qualité. Dans des illustrations photographiques destinées à la lecture à l'écran, une perte de 5% des informations est généralement non critique et peut, dans certains cas, peut être autorisée à 20-25%.

Algorithmes de compression sans perte d'informations

Code Shannon-Fano

Pour un raisonnement ultérieur, il sera commode de soumettre notre fichier original Avec du texte comme source de caractères qui apparaissent à sa sortie. Nous ne savons pas à l'avance quel symbole sera le suivant, mais nous savons que la lettre "A" apparaîtra avec la probabilité de P1, la probabilité de P2 -Buva "B", etc.

Dans le cas le plus simple, nous examinerons tous les symboles de texte indépendants de l'autre, c'est-à-dire La probabilité de l'apparition du symbole suivant ne dépend pas de la valeur du symbole précédent. Bien sûr, pour un texte significatif, ce n'est pas le cas, mais maintenant nous envisageons une situation très simplifiée. Dans ce cas, l'approbation est vraie "Le symbole porte plus d'informations, moins probable apparaître."

Imaginons le texte, dont l'alphabet ne comprend que 16 lettres: A, B, B, G, D, E, Z, Z et, K, L, M, N, O, P, R. Chacun de ces Les panneaux peuvent coder avec seulement 4 bits: de 0000 au 1111. Imaginez maintenant que les probabilités de l'apparition de ces caractères sont distribuées comme suit:

La somme de ces probabilités est naturellement unie. Nous divisons ces caractères en deux groupes de sorte que la probabilité totale des caractères de chaque groupe soit ~ 0.5 (fig.). Dans notre exemple, ce seront des groupes personnages A-in-in et M. Les cercles sur la figure, indiquant des groupes de symboles, sont appelés sommets ou nœuds (nœuds) et la conception elle-même de ces nœuds est un arbre binaire (arbre B). Nous attribuons votre code à chaque nœud, indiquant un numéro de nœud 0 et l'autre numéro 1.

Encore une fois, nous cassons le premier groupe (A-B) en deux sous-groupes de sorte que leurs probabilités totales soient aussi proches les unes des autres. Ajouter au code du premier numéro de sous-groupe 0 et au deuxième code - chiffre 1.

Nous répéterons cette opération jusqu'à ce que chaque sommet de notre "arbre" reste un personnage. L'arbre complet de notre alphabet aura 31 nœuds.

Les codes de symboles (nœuds de bois extrêmes droit) ont les codes de longueur inégale. Donc, la lettre A ayant une probabilité p \u003d 0,2 pour notre texte imaginaire est codée avec seulement deux bits et la lettre P (non représentée sur la figure), ayant la probabilité p \u003d 0,013, est codée avec une combinaison à six bits.

Donc, le principe est évident - les symboles communs sont codés par un nombre plus petit de bits, rarement trouvé - grand. En conséquence, la quantité moyenne de bits sur le symbole sera égale

où NI est le nombre de bits codant pour le I-th Symbole, PI est la probabilité de l'apparition du Symbole Ième.

Code Huffman.

L'algorithme Huffman implémente élégamment l'idée générale du codage statistique à l'aide de jeux de préfixes et fonctionne comme suit:

1. Nous écrivons tous les symboles de l'alphabet afin d'augmenter ou de réduire la probabilité de leur apparition dans le texte.

2. Combinez constamment deux caractères avec les probabilités les plus petites de l'apparition de l'apparence dans un nouveau caractère composite, la probabilité que nous assumons égale à la somme des probabilités des composants de ses caractères. En fin de compte, nous construisons un arbre, dont chaque nœud a la probabilité totale de tous les nœuds en dessous.

3. Suivez la voie à chaque feuille de bois, marquant la direction à chaque noeud (par exemple, à droite - 1, gauche - 0). La séquence résultante donne un mot de code correspondant à chaque symbole (Fig.).

Construire un arbre de code pour la communication avec l'alphabet suivant:

Inconvénients des méthodes

La plus grande complexité avec les codes, comme suit la discussion précédente, est la nécessité d'avoir une table de probabilité pour chaque type de données compressibles. Ce n'est pas un problème s'il est connu que le texte anglais ou russe est compressé; Nous fournissons simplement une arborescence de code appropriée de codeur et de décodeur pour le texte anglais ou russe. Dans le cas général, lorsque la probabilité de symboles pour les données d'entrée est inconnue, les codes statiques de Huffman travaillent inefficacement.

La solution à ce problème est une analyse statistique des données codées effectuées lors de la première passe sur les données et la compilation est basée sur son codage. Réellement codage est effectué par la deuxième passe.

Un autre manque de codes est que la longueur du mot de code minimal pour eux ne peut être inférieure à une, tandis que l'entropie du message peut bien être 0,1 et 0,01 bits / lettre. Dans ce cas, le code devient considérablement redondant. Le problème est résolu en utilisant l'algorithme pour bloquer des blocs, mais la procédure de codage / décodage est compliquée et l'arborescence de code est considérablement étendue, ce qui doit finalement être enregistré avec le code.

Ces codes ne tiennent pas compte des relations entre les caractères présents dans presque tous les texte. Par exemple, si dans le texte sur langue Anglaise Nous sommes trouvés dans la lettre Q, nous pouvons dire avec confiance que la lettre que vous ira après.

Codage de groupe - Encodage de longueur d'analyse (rle) est l'un des algorithmes d'archivage les plus anciens et les plus simples. La compression dans la rle se produit en raison du remplacement des chaînes du même octet sur le "compteur, de la valeur". ("Rouge, rouge, ..., rouge" est écrit comme "n rouge").

L'une des implémentations de l'algorithme est la suivante: ils recherchent l'octet le plus fréquent, ils appellent le préfixe et remplacent les chaînes des mêmes symboles sur le triple "préfixe, compteur, valeur". Si cet octet est atteint dans le fichier source une ou deux fois de suite, il est remplacé par une paire de "préfixes, 1" ou "préfixe, 2". Il y a une paire non utilisée "préfixe, 0", qui peut être utilisée comme signe de la fin des données emballées.

Lors de l'encodage des fichiers EXE, vous pouvez rechercher et emballer la séquence de la forme AXAYAZAWAT ... qui se trouvent souvent dans les ressources (lignes de l'encodage Unicode).

Les parties positives de l'algorithme peuvent être attribuées à ce qu'elle ne nécessite pas de mémoire supplémentaire lorsque vous travaillez et est rapidement exécutée. L'algorithme est utilisé dans les formats de RCX, TIFF, NMR. Une caractéristique intéressante du codage de groupe dans PCX est que le degré d'archivage de certaines images ne peut être considérablement augmenté que en modifiant l'ordre des couleurs dans la palette d'images.

Le code LZW (Lempel-ZIV & Welch) est aujourd'hui l'un des codes de compression les plus courants sans perte. C'est à l'aide du code LZW qu'il y a une compression dans de tels formats graphiques que TIFF et GIF, avec l'aide de modifications LZW, il existe de très nombreux architons universels. Le fonctionnement de l'algorithme est basé sur la recherche dans le fichier d'entrée de séquences de symboles répétitives, codées par des combinaisons d'une longueur de 8 à 12 bits. Ainsi, la plus grande efficacité cet algorithme Il a sur des fichiers texte et des fichiers graphiques dans lesquels il existe de grandes sections monochromes ou des séquences répétées de pixels.

L'absence de pertes d'informations avec le codage LZW a conduit à la large distribution du format basé sur TIFF en fonction de celle-ci. Ce format n'impose aucune restriction sur la taille et la profondeur de la couleur de l'image et est répandue, par exemple, dans l'impression. Un autre format basé sur LZW - GIF est plus primitif - il vous permet de stocker des images avec une profondeur de couleur d'au plus 8 bits / pixels. Au début du fichier GIF, une palette est une table qui définit la correspondance entre l'index de couleur - le nombre compris entre 0 et 255 et la valeur de couleur true 24 bits.

Algorithmes de compression avec perte d'informations

L'algorithme JPEG a été développé par un groupe d'entreprises appelé groupe d'experts photographiques conjoints. L'objectif du projet était de créer une norme de compression très efficace pour les images noires et blanches et couleur, cet objectif et a été réalisé par des développeurs. JPEG trouve actuellement l'application la plus large dans laquelle un ratio de compression élevé est requis - par exemple, sur Internet.

Contrairement à l'algorithme JPEG coding LZW codant avec des pertes. L'algorithme de codage lui-même est basé sur une mathématique très complexe, mais en termes généraux, il peut être décrit comme suit: L'image est divisée en carrés 8 * 8 pixels, puis chaque carré est converti en une chaîne séquentielle de 64 pixels. Ensuite, chacune de ces chaînes est soumise à la soi-disant transformation DCT, qui est l'une des variétés de transformée de Fourier discrète. Il réside dans le fait que la séquence d'entrée de pixels peut être représentée comme la somme des composants sinusoïdaux et cosinus à plusieurs fréquences (les harmoniques soi-disant). Dans ce cas, nous ne devons connaître que les amplitudes de ces composants afin de restaurer la séquence d'intrants avec un degré de précision suffisant. Plus nous connaissons le nombre de composants harmoniques que nous connaissons, moins la différence entre l'originale et l'image comprimée sera. La plupart des encodeurs JPEG vous permettent de régler le rapport de compression. Ceci est très atteint façon simple: Plus le degré de compression est élevé, plus l'harmonique est petit, vous présentera chaque bloc de 64 pixels.

Bien entendu, la force de ce type de codage est un rapport de compression important tout en maintenant la profondeur de couleur d'origine. C'est cette propriété qui a conduit à sa large application sur Internet, où la diminution de la taille des fichiers est d'une importance primordiale dans les encyclopédies multimédias, où stockage est nécessaire pour être plus graphiques dans un volume limité.

La propriété négative de ce format n'est pas liée par tout moyen, une qualité d'image aggravée intrinsèquement inhérente. C'est ce triste fait qui ne lui permet pas d'être utilisé dans l'impression, où la qualité est placée à la tête du coin.

Cependant, le format JPEG n'est pas la limite de la perfection dans le désir de réduire la taille du fichier de destination. DANS dernièrement Des recherches intensives sont en cours dans le domaine de la transformation dite de l'ondelettes (ou de la transformation des éclaboussures). Sur la base des principes mathématiques les plus complexes, les codeurs d'ondelettes permettent d'obtenir une plus grande compression que JPEG, avec des pertes d'informations plus petites. Malgré la complexité des mathématiques de la transformation de l'ondelettes, dans la mise en œuvre du logiciel, il est plus facile que JPEG. Bien que les algorithmes de la compression d'ondelettes soient toujours au stade initial du développement, un avenir formidable est préparé.

Compression fractale

La compression d'image fractale est une algorithme de compression d'image avec des pertes basées sur l'utilisation de fonctions iconiques (IFS, en règle générale, à la suite de transformations affines) vers des images. Cet algorithme est connu dans cela dans certains cas, il permet d'obtenir des ratios de compression très élevés ( meilleurs exemples - Jusqu'à 1000 fois avec une capacité visuelle acceptable) pour de vraies photos d'objets naturels, qui n'est pas disponible pour d'autres algorithmes de compression d'image en principe. à cause de situation complexe Avec le brevet de répandre l'algorithme n'a pas reçu.

L'archivage des fractales est basé sur le fait que l'utilisation des coefficients système des fonctions RCD, l'image est prêchée sous une forme plus compacte. Avant d'examiner le processus d'archivage, nous analyserons comment IFS construit une image.

Strictement parlant, IFS est un ensemble de transformations affines tridimensionnelles qui ont traduit une image à une autre. La transformation est soumise à des points dans l'espace tridimensionnel (coordonnées x, à la coordonnée, à la luminosité).

La base de la méthode de codage fractale est la détection de parcelles de type ressemblant à l'image. Pour la première fois, la possibilité d'appliquer la théorie des systèmes de fonctions emblématiques (IFS) au problème de la compression d'image a été étudiée par Michael Barnsley et Alan Sloan. Ils ont breveté leur idée en 1990 et 1991. Jackwin (Jacquin) a introduit une méthode de codage fractale, qui utilise des blocs de sous-mode de domaine et de la plage (blocs de sous-mode de domaine et de la plage), blocs de blocs couvrant toute l'image. Cette approche est devenue la base de la plupart des méthodes de codage fractales utilisées aujourd'hui. Il a été amélioré par Juval Fisher (Yuval Fisher) et un certain nombre d'autres chercheurs.

Conformément à cette méthode, l'image est divisée en une pluralité de frères et sidissures de rang non alternatif (sous-pattes de plage) et définit un ensemble de handicaps de domaine qui se chevauchent (sous -ages de domaine). Pour chaque bloc de rang, l'algorithme de codage trouve l'unité de domaine la plus appropriée et une conversion affine qui traduit cette unité de domaine à ce bloc de rang. La structure d'image est affichée dans le système de bloc de rang, les blocs de domaine et les transformations.

L'idée est la suivante: Supposons que l'image d'origine soit un point fixe de certains affichages de compression. Ensuite, il est possible de se rappeler cet affichage au lieu de l'image elle-même et de la restaurer est suffisamment appliquée à plusieurs reprises cet écran sur n'importe quelle image de départ.

Sur le théorème de Banach, de telles itérations mènent toujours à un point fixe, c'est-à-dire à l'image d'origine. En pratique, toute la difficulté réside dans la recherche de l'affichage compressive le plus approprié et dans son stockage compact. En règle générale, les algorithmes de mappage (c'est-à-dire des algorithmes de compression) sont largement accablants et nécessitent des coûts de calcul importants. Dans le même temps, les algorithmes de restauration sont assez efficaces et rapides.

En bref, la méthode proposée par Barnesley peut être décrite comme suit. L'image est codée par plusieurs transformations simples (dans notre cas affine), c'est-à-dire qu'il est déterminé par les coefficients de ces transformations (dans notre cas A, B, C, D, F).

Par exemple, l'image de la courbe de Koch peut être codée par quatre transformations affines, nous le déterminons sans ambiguïté avec les 24 coefficients.

En conséquence, le point va certainement aller quelque part dans la zone noire sur l'image source. Ayant fait une telle opération plusieurs fois, nous remplissons tous les espaces noirs, restaurant ainsi la photo.

Les deux images les plus célèbres obtenues avec l'IFS: Triangle de Serpinsky et Fern Barnsley. Le premier est défini trois, et la seconde est cinq transformations affines (ou, dans notre terminologie, des lentilles). Chaque conversion est définie par des octets de lecture littéralement, tandis que l'image construite avec leur aide peut occuper plusieurs mégaoctets.

Il devient clair que l'archiver fonctionne et pourquoi il a besoin de tellement de temps. En fait, la compression fractale est la recherche de domaines autonomes dans l'image et la définition des paramètres des transformations affines pour eux.

Dans le pire des cas, si l'algorithme d'optimisation ne s'applique pas, il faudra un buste et une comparaison de tous les fragments possibles de l'image de différentes tailles. Même pour de petites images, lors de la prise de discret, nous obtenons le nombre astronomique des options désordonnées. Même une forte rétrécissement des classes de conversion, par exemple, en améliorant un certain nombre de fois, ne permettra pas de réaliser du temps acceptable. De plus, la qualité de l'image est perdue. La majorité écrasante des recherches dans le domaine de la compression fractale visait désormais à réduire le temps d'archivage nécessaire pour obtenir une image de haute qualité.

Pour un algorithme de compression fractale, ainsi que pour d'autres algorithmes de compression avec des pertes, les mécanismes sont très importants avec lesquels il sera possible d'ajuster le degré de compression et du degré de pertes. À ce jour, un ensemble important de telles méthodes a été développé. Premièrement, il est possible de limiter le nombre de transformations, en garantissant délibérément que le rapport de compression n'est pas inférieur à la valeur fixe. Deuxièmement, vous pouvez exiger cela dans une situation où la différence entre le fragment traité et la meilleure approximation sera supérieure à une certaine valeur seuil, ce fragment a été broyé nécessairement (plusieurs objectifs sont nécessairement démarrés). Troisièmement, il est possible d'interdire des fragments de fragments inférieurs à, par exemple, quatre points. En modifiant les valeurs de seuil et la priorité de ces conditions, vous pouvez contrôler de manière flexible le rapport de compression d'image: de la conformité de la télécommande, à n'importe quel rapport de compression.

Comparaison avec JPEG.

Aujourd'hui, l'algorithme d'archivage graphique le plus courant est JPEG. Comparez-le avec la compression fractale.

Premièrement, nous notons que les deux, et un autre algorithme fonctionnent avec des images en couleur de 8 bits (en gris) et 24 bits. Les deux sont des algorithmes de perte de compression et fournissent des coefficients d'archivage proches. Et l'algorithme fractal et JPEG a la possibilité d'augmenter le degré de compression en raison d'une augmentation des pertes. De plus, les deux algorithmes sont très bien parallèles.

Les différences commencent si nous considérons le temps dont vous avez besoin d'archiver / décompressez des algorithmes. Ainsi, l'algorithme fractal compresse des centaines et même des milliers de fois plus longtemps que JPEG. Déballage de l'image, au contraire, se produira 5 à 10 fois plus vite. Par conséquent, si l'image n'est compressée qu'une seule fois, et est transférée sur le réseau et est déballé à plusieurs reprises, il est plus rentable d'utiliser un algorithme fractal.

JPEG utilise la décomposition de l'image sur les fonctions de cosinus, de sorte que la perte de celui-ci (même pour les pertes minimales données) se manifeste par des vagues et du halo à la frontière des couleurs vives. C'est pour cet effet qu'il n'aime pas utiliser lors de la compression des images préparées pour une impression de haute qualité: cet effet peut être très perceptible.

L'algorithme fractal est ravi de cette pénurie. De plus, lors de l'impression d'images, chaque fois que vous devez effectuer l'opération d'échelle, car le dispositif d'impression du périphérique d'impression ne coïncide pas avec le raster d'image. Lors de la conversion, il peut également y avoir plusieurs effets désagréables avec lesquels vous pouvez vous battre ou réduire l'image de manière programmatique (pour des dispositifs d'impression bon marché tels que le laser ordinaire et imprimantes à jet d'encre), fournissant un dispositif d'impression avec son processeur, son disque dur et un ensemble de programmes de traitement d'image (pour des machines de photophonation coûteuses). Comme vous pouvez le deviner, avec l'utilisation d'un algorithme fractal, de tels problèmes ne se produisent pratiquement pas.

L'algorithme de fractal JPEG à l'autre, l'utilisation généralisée n'arrivera pas bientôt (au moins en raison de la vitesse d'archivage la plus basse), mais dans le domaine des applications multimédia, dans jeux d'ordinateur Son utilisation est assez justifiée.

De nos jours, de nombreux utilisateurs pensent comment le processus d'information de compression est effectué afin de sauvegarder l'espace libre sur Winchester, car c'est l'un des plus outils efficaces Utilisation de l'espace utile dans n'importe quel lecteur. Il suffit souvent d'utilisateurs modernes qui font face à une pénurie d'espace libre sur le lecteur, vous devez supprimer toutes les données, essayant de libérer l'endroit souhaité de cette manière, tandis que des utilisateurs plus avancés utilisent le plus souvent la compression de données afin de réduire son volume. .

Cependant, de nombreuses personnes ne savent même pas comment le processus de compression des informations est appelé, sans parler de quels algorithmes sont utilisés et ce qui donne l'utilisation de chacun d'eux.

Vaut-il la peine de comprimer les données?

La compression de données est importante aujourd'hui et nécessite un utilisateur. Bien sûr, à notre époque, presque tout le monde peut acquérir des dispositifs de stockage de données avancés, prévoyant la possibilité d'utiliser une quantité suffisamment grande d'espace libre, ainsi que des canaux de traduction d'informations à grande vitesse.

Cependant, il est nécessaire de comprendre correctement cela au fil du temps, la quantité de données à transmettre au fil du temps. Et si il y ait littéralement dix ans, un volume de 700 Mo a été considéré comme standard pour un film régulier, alors aujourd'hui des films fabriqués en qualité HD peuvent avoir des volumes égaux à plusieurs dizaines de gigaoctets, sans oublier combien d'espace libre sont des peintures de haute qualité. Dans Format Blu-ray.

Lorsque la compression des données est nécessaire?

Bien sûr, il ne vaut pas la peine d'être le fait que le processus d'informations de compression vous apportera beaucoup d'utilisation, mais il existe un certain nombre de situations dans lesquelles certaines des méthodes de compression d'informations sont extrêmement utiles et même nécessaires:

• Transfert de certains documents à travers e-mail. En particulier, cela concerne ces situations où vous devez transférer des informations dans un volume important à l'aide de divers appareils mobiles.
• Souvent, le processus de compression des informations afin de réduire l'endroit occupé par elle est utilisé lors de la publication de certaines données sur différents sites lorsque vous souhaitez économiser du trafic;
• Sauvegarder l'espace libre sur le disque dur lorsqu'il n'est pas possible de remplacer ou d'ajouter de nouveaux outils de stockage. En particulier, la situation la plus courante est celle lorsqu'il existe certaines restrictions dans le budget abordable, mais il manque gratuitement espace disque.

Bien sûr, en plus de ce qui précède, il y a encore nombre énorme Il peut y avoir des situations différentes dans lesquelles le processus d'informations de compression peut être nécessaire afin de réduire son volume, mais ils sont aujourd'hui les plus courants.

Comment puis-je comprimer les données?

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

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

Il convient de noter que dans certaines situations, il n'est pas nécessaire de maximiser la réduction des données comprimées, il est donc possible d'utiliser de tels algorithmes dans lesquels la compression des informations sur le disque est effectuée avec certaines pertes. L'avantage de la compression avec des pertes est qu'une telle technologie est beaucoup plus simple dans la mise en œuvre, et fournit également le degré d'archivage le plus élevé possible.

Compression avec pertes

Les informations avec pertes assurent une meilleure compression 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éballés peuvent différer assez fortement des informations d'origine, mais elles ne sont pratiquement pas distinctives pour l'œil humain ou l'oreille.

Compression sans perte

Les algorithmes d'informations de compression sans perte fournissent la récupération de données la plus précise, éliminant toute perte de fichiers compressibles. Cependant, il est nécessaire de comprendre correctement le fait que dans ce cas, il n'est pas assuré une compression de fichiers si efficace.

Méthodes universelles

Entre autres choses, il y a une certaine série méthodes universellesqui est effectué un processus efficace d'informations de compression afin de réduire l'endroit occupé par celui-ci. En général, vous pouvez attribuer uniquement trois technologies principales:

• Conversion de flux. Dans ce cas, une description des nouvelles informations non compressées entrantes est effectuée via des fichiers déjà traités et aucune probabilité n'est calculée, et les symboles codant en fonction des seuls fichiers déjà soumis à un certain traitement.
• Compression statistique. Ce processus d'informations de compression afin de réduire l'endroit occupé sur le disque est distribué en deux sous-catégories - des méthodes adaptatives et bloquantes. L'option adaptative prévoit le calcul de la probabilité pour les nouveaux fichiers en fonction des informations, qui ont déjà été traitées lors du processus de codage. 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, suivi de l'ajout au bloc comprimé lui-même.
• Convertir le bloc. Les informations entrantes sont distribuées à plusieurs blocs et se produisent ensuite une transformation holistique. Il convient de dire que certaines méthodes, en particulier celles fondées sur la permutation de plusieurs blocs, peuvent finalement conduire à une diminution significative du volume d'informations compressibles. Cependant, il est nécessaire de comprendre correctement qu'après avoir réalisé un tel traitement, il est finalement amélioré dans lequel la compression ultérieure à travers d'autres algorithmes est réalisée beaucoup plus simple et rapide.

Compression lors de la copie

L'un des composants les plus importants copie de la réserve est le dispositif pour lequel il va bouger nécessaire à l'utilisateur informations. La plus grande quantité de ces données sera déplacée, plus vous devez utiliser un périphérique volumétrique. Toutefois, si vous êtes implémenté un processus de compression de données, le problème du manque d'espace libre est peu susceptible de rester pertinent pour vous.

Pourquoi en avez-vous besoin?

La possibilité de compresser des informations lorsqu'il permet de réduire considérablement le temps que vous souhaitez copier les fichiers nécessaires, tout en réalisant des économies efficaces de l'espace libre sur le lecteur. En d'autres termes, lors de l'utilisation de la compression, les informations seront copiées beaucoup plus compactes et rapidement, et vous pouvez économiser votre argent et vos finances nécessaires pour acheter un lecteur plus volumineux. Entre autres choses, avoir des informations compressées, vous réduisez également le temps dont vous aurez besoin lors du transport de toutes les données sur le serveur ou de les copier via le réseau.

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

Lorsque vous choisissez un utilitaire, veillez à examiner comment le programme que vous avez choisi peut compresser des données. Cela dépend du type d'informations, par conséquent, l'efficacité de la compression des documents textuels peut être supérieure à 90%, alors qu'elle n'est efficace qu'au plus de 5%.

Avant de commencer le processus de compression d'un fichier ou d'un dossier, il est très important de comprendre tous les avantages reçus et démonter les méthodes de compression disponibles dans Windows 7:

• Compression des fichiers NTFS
• Dossiers de compression (zip).

La compression de données réduit la taille du fichier en minimisant ses données redondantes. DANS fichier texte. Avec des données redondantes, il existe souvent certains signes, tels qu'un symbole d'espace ou des voyelles générales (E et A), ainsi que des cordes de caractères. La compression de données crée une version compressée du fichier, minimisant ainsi ces données redondantes.

Ces deux méthodes de compression seront comparées ci-dessous. De plus, l'impact sera considéré divers fichiers et des dossiers sur l'action des fichiers et des dossiers compressés.

Déposer système NTFS Prend en charge la compression de fichier basée sur un fichier séparé. L'algorithme de compression de fichier ici est un algorithme de compression sans perte, cela signifie que lors de la compression et du déballage du fichier, les données ne sont pas perdues. Dans d'autres algorithmes de compression et de décompression ultérieure, une partie des données est perdue.

Compression NTFS disponible sur le système de fichiers NTFS disques dursIl a les limitations et fonctionnalités suivantes:

• Compression - attribut pour un fichier ou un dossier.
• Dossiers et fichiers sur le volume NTFS, ou comprimé, ou non.
• Les nouveaux fichiers créés dans un dossier compressé sont nettoyés par défaut.
• L'état d'un dossier compressé ne reflète pas nécessairement l'état de la compression des fichiers dans ce dossier. Par exemple, des dossiers peuvent être compressés sans compresser son contenu, et tout ou partie de fichiers d'un dossier compressé peut être impayé.
• Travailler avec des fichiers compressés NTFS sans les déballer, car ils sont déballés et compressés à nouveau sans intervention de l'utilisateur.
• Si le fichier compressé est ouvert, le système le décompresse automatiquement.
• Lors de la fermeture fichier Windows Encore une fois, il serre.
• Pour simplifier la reconnaissance, les noms de fichiers compressés NTFS et les dossiers sont affichés dans une autre couleur.
• Les fichiers et dossiers compressés NTFS restent sous une forme compressée, uniquement sur le volume NTFS.
• Les fichiers compressés NTFS ne peuvent pas être cryptés.
• Les octets de fichier compressés ne sont pas disponibles pour les applications; Ils ne voient que des données non compressées.
• Les applications qui opennent les fichiers compressés peuvent fonctionner avec eux comme non comprimé.
• Les fichiers compressés ne peuvent pas être copiés dans un autre système de fichiers.

Noter: Vous pouvez utiliser l'outil de ligne de commande de ligne de commande pour gérer la compression NTFS.

Déplacez et copiez des fichiers et des dossiers compressés.

Les fichiers et dossiers compressés déplacés ou copiés peuvent changer leur état de compression. Vous trouverez ci-dessous cinq situations dans lesquelles l'impact de la copie et du déplacement vers des fichiers et des dossiers compressés est pris en compte.

Copier dans la partition de la section NTFS.

Comment l'état du fichier ou du dossier compressé-t-il si vous le copiez dans la section NTFS? Lors de la copie d'un fichier ou d'un dossier dans le système de fichiers NTFS, une section, un fichier ou un dossier hérite de l'état de compression du dossier cible. Par exemple, si vous copiez un fichier ou un dossier compressé dans un dossier déballé, un fichier ou un dossier sera automatiquement déballé.

Déplacer dans la section NTFS.

Qu'advient-il de la compression ou du dossier de fichier lors de la déplacement de la section NTFS?

Lorsque vous déplacez un fichier ou un dossier dans la section NTFS, un fichier ou un dossier enregistre son état de compression initial. Par exemple, lors du déplacement d'un fichier ou d'un dossier compressé dans un dossier non compressé, le fichier reste compressé.

Copier ou se déplacer entre les sections NTFS.

Qu'advient-il d'un fichier ou d'un dossier compressé lors de la copie ou de la déplaçant entre les sections NTFS?

Lorsque vous déplacez le fichier ou le dossier entre les partitions NTFS, le fichier ou le dossier hérite de l'état de compression du dossier cible. Étant donné que Windows 7 examine le mouvement entre les sections en tant que copie avec une opération de suppression ultérieure, les fichiers héritent de l'état de compression du dossier cible.

Lors de la copie d'un fichier dans un dossier qui contient déjà un fichier avec le même nom, le fichier copié accepte l'attribut de compression du fichier cible, quel que soit l'état de compression du dossier.

Copier ou se déplacer entre les volumes de graisse et de NTFS.

Qu'advient-il de la compression de fichier copiée ou déplacée entre les volumes de graisse et de NTFS?

Les fichiers compressés copiés dans la section grasse ne sont pas comprimés, car les volumes de graisse ne prennent pas en charge la compression. Toutefois, si vous copiez ou déplacez des fichiers de la section FAT dans la section NTFS, ils héritent de l'attribut de compression du dossier auquel vous les copiez.

Lors de la copie de fichiers, système de fichiers NTFS calcule l'espace disque en fonction de la taille d'un fichier non compressé. Ceci est important car les fichiers pendant le processus de copie ne sont pas comprimés et le système devrait garantir suffisamment d'espace. Si vous essayez de copier un fichier compressé dans la section NTFS, vous n'avez pas d'espace libre pour un fichier non compressé, vous aurez un message d'erreur que vous avertiez la carence de l'espace disque pour le fichier.

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

Compresser des informations représente le processus de convertir le message source d'un système de code à un autre, qui diminue taille de message. Les algorithmes destinés à la compression des informations peuvent être divisés en deux grands groupes: mise en œuvre de compression sans perte (compression réversible) et mise en œuvre de compression avec pertes (compression irréversible).

Compression réversible Il implique une récupération de données absolument précise après décodage et peut être appliquée pour compresser toutes les informations. Cela conduit toujours à une diminution du volume du flux de sortie d'informations sans changer son informaticité, c'est-à-dire sans perte structure de l'information. De plus, à partir du flux de sortie, à l'aide d'un algorithme de restauration ou de décompression, vous pouvez obtenir l'entrée et le processus de récupération est appelé décompression ou déballage et seulement après le processus de déballage, les données conviennent au traitement conformément au format interne. La compression sans perte est appliquée sur des textes, des fichiers exécutables, un son de haute qualité et des graphiques.

Compression irréversible C'est généralement un degré de compression beaucoup plus élevé que le codage sans perte, mais permet des écarts de données décodées de la source. En pratique, il existe une large gamme de tâches pratiques, dans lesquelles la conformité à l'exigence de restauration précise des informations initiales après la décompression n'est pas requise. Ceci notamment référence à la compression des informations multimédia: Son, images photo ou vidéo. Par exemple, les formats d'informations multimédia JPEG et MPEG sont largement appliqués, qui utilisent une compression irréversible. La compression irréversible n'est généralement pas utilisée conjointement avec le cryptage cryptographique, car l'exigence principale du cryptosystème est l'identité des données déchiffrées de l'original. Cependant, lors de l'utilisation de technologies multimédias, les données présentées dans vidéo numérique, souvent exposé à une compression irréversible avant de servir dans le système cryptographique du cryptage. Après avoir transféré des informations sur le consommateur et le décryptage, les fichiers multimédia sont utilisés sous une forme compressée (c'est-à-dire non restaurée).

Considérez certains des moyens les plus courants de compression de données réversible.

L'approche et l'algorithme simple la plus connue et l'algorithme d'informations de compression sont réversibles - il s'agit du codage de la série de séquences (encodage de longueur d'exécution - rle). L'essence des méthodes de cette approche consiste à remplacer les chaînes ou la série d'octets répétés à un revenu d'octet codant et au nombre de leurs répétitions. Le problème de toutes les méthodes similaires n'est que dans la définition de la méthode, avec laquelle l'algorithme de déballage pourrait être distingué dans le flux résultant de la série codée par des octets d'autres séquences d'octets non codés. La solution au problème est généralement réalisée par l'expansion des étiquettes au début des chaînes codées. De telles étiquettes peuvent être des bits caractéristiques dans le premier pape de la série codée, les valeurs du premier octet de la série codée. L'inconvénient de la méthode rle est un rapport de compression relativement bas ou le coût des fichiers de codage avec un petit nombre de séries et, encore pire - avec un petit nombre d'octets répétitifs de la série.

Avec des informations d'encodage uniformes, le même bit est attribué au message, quelle que soit la probabilité de son apparence. Dans le même temps, il est logique de supposer que la longueur totale des messages transmises diminuera si des messages fréquents codés avec des mots de code abrégés et rarement rencontrés - plus longtemps. Les problèmes découlant de cela sont liés à la nécessité d'utiliser codes avec mot de code variable. Il existe de nombreuses approches pour construire de tels codes.

Certaines des méthodes de vocabulaire sont des méthodes de vocabulaire, dont les principaux représentants incluent les algorithmes de la famille et du lemplage de Ziva. Leur idée de base est que des fragments flux d'entrée ("phrases") sont remplacées par un pointeur à l'endroit où ils sont déjà apparus dans le texte. Dans la littérature, de tels algorithmes sont indiqués comme algorithmes Compression lz.

Une méthode similaire s'adapte rapidement à la structure du texte et peut encoder de courts mots fonctionnels, car ils apparaissent très souvent. Les nouveaux mots et expressions peuvent également être formés à partir de parties de mots précédemment rencontrés. Le décodage du texte comprimé est effectué directement, il existe un simple remplacement du pointeur à la phrase finie du dictionnaire à laquelle l'indique celui indiqué. En pratique, la méthode LZ est la bonne compression, sa propriété importante est très travail rapide Décodeur.

Une autre approche de la compression de l'information est code Huffman, le codeur et le décodeur dont ont une implémentation matérielle assez simple. L'idée de l'algorithme consiste à suivre: connaître les probabilités d'occurrence de caractères dans un message, vous pouvez décrire la procédure de construction de codes de longueur variable consistant en un nombre total de bits. Les symboles sont plus susceptibles d'être attribués plus codes courts, Alors que les caractères moins souvent rencontrés sont plus longs. Grâce à cela, une réduction de la longueur moyenne du mot de code et une plus grande efficacité de compression est obtenue. Les codes Huffman ont un préfixe unique (le début du mot code), ce qui vous permet de les décoder sans ambiguïté, malgré leur longueur variable.

La procédure de synthèse du code classique Khaffman assume la présence d'informations priori sur les caractéristiques statistiques de la source de message. En d'autres termes, le développeur doit connaître la probabilité de ceux-ci ou d'autres caractères, dont les messages sont formés. Considérez la synthèse du code de Huffman sur un exemple simple.

p (S 1) \u003d 0,2, P (S 2) \u003d 0,15, P (S 3) \u003d 0,55, P (S 4) \u003d 0,1. Trier les symboles en descendant la probabilité d'apparence et imaginez sous la forme d'une table (fig. 14.3, a).

La procédure de synthèse de code comprend trois étapes principales. Le premier déclencheur des rangées de la table se produit: deux rangées correspondant aux symboles avec les probabilités les plus petites de l'occurrence sont remplacées par une probabilité totale, après quoi la table est à nouveau réorganisée. La convolution continue jusqu'à une seule ligne avec une probabilité totale égale à une (figure 14.3, b) reste dans le tableau.

Figure. 14.3.

À la deuxième étape, le code de code est construit à l'aide d'une table pliée (figure 14.4, a). L'arbre est construit, en commençant par la dernière colonne de la table.

La racine de l'arbre forme une unité située dans la dernière colonne. Dans cet exemple, cette unité est formée à partir des probabilités de 0,55 et 0,45 représenté sous la forme de deux nœuds de l'arborescence associées à la racine. Le premier d'entre eux correspond au symbole S 3 et, donc, la nouvelle ramification de ce nœud ne se produit pas.

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

Côtes Connexion des nœuds d'arbre de code individuel, chiffres 0 et 1 chiffres (par exemple, côtes gauche - 0 et droite - 1). Dans la troisième étape finale, une table est construite dans laquelle les symboles de la source sont comparés et les codes du code Huffman. Ces mots de code sont formés à la suite de numéros de lecture marqués de nervures formant le chemin de la racine de l'arborescence au symbole correspondant. Pour l'exemple en considération, le code Huffman prendra la vue indiquée dans le tableau à droite (Fig. 14.4, B).

Cependant, l'algorithme Classic Huffman a un désavantage significatif. Pour restaurer le contenu du message compressé, le décodeur doit connaître la table de fréquence qui a apprécié le codeur. Par conséquent, la longueur du message compressé augmente par la longueur du tableau de fréquence, qui doit être envoyée à l'avance sur les données, qui peuvent ne pas être réduites sans effort pour compresser le message.

Une autre variante codage statique Huffman Il est d'afficher le flux d'entrée et le codage du bâtiment en fonction des statistiques collectées. Cela nécessite deux fichiers sur le fichier - un pour afficher et collecter des informations statistiques, la seconde est pour le codage. Dans le codage statique de Huffman, les symboles d'entrée (chaînes de bits de longueurs différentes) sont définis sur la correspondance de la chaîne de bits également des longueurs variables - leurs codes. La longueur du code de chaque symbole est prise par un logarithme binaire proportionnel de sa fréquence prise avec le signe opposé. Et l'ensemble total de tous les symboles rencontrés est l'alphabet de flux.

Il y a une autre méthode - adaptative ou codage dynamique de Huffman. Le sien principe général Il est de modifier le schéma de codage en fonction de la nature des changements de flux d'entrée. Une telle approche a un algorithme à une seule passe et ne nécessite pas la préservation des informations sur le codage utilisé explicitement. Le codage adaptatif peut donner un plus grand taux de compression par rapport à la statique, car les variations des fréquences du flux d'entrée sont plus entièrement prises en compte. Lors de l'utilisation d'un codage de Huffman adaptatif, la complication de l'algorithme consiste à ajuster constamment le bois et les codes des symboles de l'alphabet principal conformément aux statistiques modifiées du flux d'entrée.

Les méthodes Huffman donnent une vitesse élevée et modérément bonne qualité compression. Cependant, le codage de Huffman a une redondance minimale, à condition que chaque caractère soit codé dans l'alphabet du code de symbole par une chaîne séparée de deux bits - (0, 1). L'inconvénient principal cette méthode La dépendance du degré de compression de la proximité de la probabilité de symboles à 2 de manière négative, qui est due au fait que chaque caractère est codé par un bit entier.

Une solution complètement différente offre codage arithmétique. Cette méthode est basée sur l'idée de convertir le flux d'entrée en un seul point flottant. Le codage arithmétique est une méthode permettant aux caractères d'emballage de l'alphabet d'entrée sans perte, à condition que la distribution de fréquence de ces caractères soit connue.

La séquence estimée requise de symboles lorsque comprimé par la méthode de codage arithmétique est considérée comme une fraction binaire de l'intervalle)