2 formas de comprimir información en archivos. Compresión por codificación de series. Transmisión de correo electrónico

Buen día.
Hoy quiero tocar el tema de la compresión de datos sin pérdidas. A pesar de que ya había artículos sobre Habré dedicados a algunos algoritmos, quería hablar de esto con un poco más de detalle.
Trataré de dar como descripción matemática, así como una descripción en la forma habitual, para que todos puedan encontrar algo interesante para ellos.

En este artículo, tocaré los fundamentos de la compresión y los principales tipos de algoritmos.

Compresión. ¿Es necesario en nuestro tiempo?

Por supuesto que sí. Por supuesto, todos entendemos que ahora tenemos acceso tanto a medios de almacenamiento de gran volumen como a canales de transmisión de datos de alta velocidad. Sin embargo, al mismo tiempo, aumentan los volúmenes de información transmitida. Si hace unos años veíamos películas de 700 megabytes que caben en un disco, hoy las películas en calidad HD pueden ocupar decenas de gigabytes.
Por supuesto, no hay mucho beneficio de comprimir todo y todo. Pero todavía hay situaciones en las que la compresión es extremadamente útil, si no necesaria.

• Envío de documentos por Email(especialmente grandes volúmenes de documentos que utilizan dispositivos móviles)
• Al publicar documentos en sitios web, la necesidad de ahorrar tráfico
• Ahorro Espacio del disco en los casos en que sea difícil la sustitución o la adición de medios de almacenamiento. Por ejemplo, esto sucede en los casos en los que no es fácil eliminar un presupuesto para gastos de capital y no hay suficiente espacio en disco.

Por supuesto, puede pensar en muchas más situaciones en las que la compresión será útil, pero estos pocos ejemplos son suficientes para nosotros.

Todos los métodos de compresión se pueden dividir en dos grandes grupos: compresión con pérdida y compresión sin pérdida. La compresión sin pérdida se utiliza cuando la información debe restaurarse con precisión de bits. Este enfoque es el único posible al comprimir, por ejemplo, datos de texto.
En algunos casos, sin embargo, no se requiere una recuperación precisa de la información y se permiten algoritmos que implementan la compresión con pérdida, que, a diferencia de la compresión sin pérdida, suelen ser más fáciles de implementar y proporcionan un mayor grado de archivo.

Entonces, pasemos a considerar los algoritmos de compresión sin pérdidas.

Métodos versátiles de compresión sin pérdidas

En general, existen tres opciones básicas sobre las que se construyen los algoritmos de compresión.
Primer grupo métodos - transformación de flujo. Esto implica describir nuevos datos entrantes sin comprimir a través de los ya procesados. En este caso, no se calculan probabilidades, la codificación de caracteres se realiza solo sobre la base de los datos que ya se han procesado, como, por ejemplo, en los métodos LZ (nombrados en honor a Abraham Lempel y Jacob Ziv). En este caso, la segunda y otras apariciones de una determinada subcadena ya conocida por el codificador se reemplazan con referencias a su primera ocurrencia.

Segundo grupo Los métodos son métodos de compresión estadística. A su vez, estos métodos se dividen en adaptativos (o de flujo) y en bloque.
En la primera versión (adaptativa), el cálculo de probabilidades para nuevos datos se basa en datos que ya se han procesado durante la codificación. Estos métodos incluyen versiones adaptativas de los algoritmos de Huffman y Shannon-Fano.
En el segundo caso (bloque), las estadísticas de cada bloque de datos se calculan por separado y se agregan al bloque más comprimido. Esto incluye versiones estáticas de Huffman, Shannon-Fano y métodos de codificación aritmética.

Tercer grupo Los métodos son los llamados métodos de conversión de bloques. Los datos entrantes se dividen en bloques, que luego se transforman en su totalidad. Al mismo tiempo, es posible que algunos métodos, especialmente los basados ​​en la permutación de bloques, no produzcan una reducción significativa (o incluso ninguna) en la cantidad de datos. Sin embargo, después de dicho procesamiento, la estructura de los datos mejora significativamente y la compresión posterior por otros algoritmos es más exitosa y rápida.

Principios generales en los que se basa la compresión de datos

Todos los métodos de compresión de datos se basan en un principio lógico simple. Si imaginamos que los elementos más comunes están codificados con códigos más cortos y los menos comunes con códigos más largos, entonces se necesitará menos espacio para almacenar todos los datos que si todos los elementos estuvieran representados por códigos de la misma longitud.
La relación exacta entre las frecuencias de los elementos y las longitudes óptimas del código se describe en el llamado teorema de codificación de fuente de Shannon, que define el límite máximo de compresión sin pérdidas y la entropía de Shannon.

Un poco de matematicas

Si la probabilidad de ocurrencia de un elemento s i es igual ap (s i), entonces será más ventajoso representar este elemento - log 2 p (s i) en bits. Si durante la codificación es posible lograr que la longitud de todos los elementos se reduzca a log 2 p (s i) bits, entonces la longitud de toda la secuencia codificada será mínima para todos los métodos de codificación posibles. Además, si la distribución de probabilidad de todos los elementos F = (p (s i)) es invariable, y las probabilidades de los elementos son mutuamente independientes, entonces la longitud promedio de los códigos se puede calcular como

Este valor se denomina entropía de la distribución de probabilidad F, o entropía de la fuente en un momento dado.
Sin embargo, normalmente la probabilidad de aparición de un elemento no puede ser independiente, al contrario, depende de algunos factores. En este caso, para cada nuevo elemento codificado s i, la distribución de probabilidad F tomará algún valor F k, es decir, para cada elemento F = F k y H = H k.

En otras palabras, podemos decir que la fuente está en el estado k, que corresponde a un cierto conjunto de probabilidades p k (s i) para todos los elementos s i.

Por tanto, teniendo en cuenta esta enmienda, podemos expresar la longitud media de los códigos como

Donde P k es la probabilidad de encontrar una fuente en el estado k.

Entonces, en esta etapa, sabemos que la compresión se basa en reemplazar elementos que ocurren con frecuencia con códigos cortos, y viceversa, y también sabemos cómo determinar la longitud promedio de los códigos. Pero, ¿qué es el código, la codificación y cómo sucede?

Codificación sin memoria

Los códigos sin memoria son los códigos más simples sobre cuya base se puede realizar la compresión de datos. En el código sin memoria, cada carácter del vector de datos codificados se reemplaza por una palabra de código de un conjunto de prefijos de secuencias o palabras binarias.
En mi opinión, esta no es la definición más clara. Consideremos este tema con un poco más de detalle.

Que se le dé un poco de alfabeto , que consta de un cierto número (finito) de letras. Llamemos a cada secuencia finita de símbolos de este alfabeto (A = a 1, a 2, ..., a n) palabra y el número n es la longitud de esta palabra.

Que también se dé otro alfabeto ... De manera similar, denotemos una palabra en este alfabeto como B.

Introduzcamos dos notación más para el conjunto de todas las palabras no vacías del alfabeto. Sea el número de palabras no vacías en el primer alfabeto y - en el segundo.

Démosle también un mapeo F, que asigna a cada palabra A del primer alfabeto alguna palabra B = F (A) del segundo. Entonces la palabra B se llamará código palabra A, y la transición de la palabra original a su código se llamará codificación.

Dado que una palabra también puede constar de una letra, podemos identificar la correspondencia entre las letras del primer alfabeto y las palabras correspondientes del segundo:
un 1<->B 1
un 2<->B 2
…
un<->B n

Esta correspondencia se llama esquema, y se denotan por ∑.
En este caso, las palabras B 1, B 2, ..., B n llaman códigos elementales, y el tipo de codificación con su ayuda es codificación alfabética... Por supuesto, la mayoría de nosotros nos hemos encontrado con este tipo de codificación, incluso sin saber todo lo que describí anteriormente.

Entonces, hemos definido los conceptos alfabeto, palabra, código, y codificación... Ahora presentamos el concepto prefijo.

Deje que la palabra B tenga la forma B = B "B" ". Entonces B" se llama el principio, o prefijo palabra B, y B "" es su final. Esta es una definición bastante simple, pero debe tenerse en cuenta que para cualquier palabra B, tanto una palabra vacía ʌ ("espacio"), como la palabra B en sí, pueden considerarse principios y finales.

Entonces, nos acercamos a comprender la definición de códigos sin memoria. La última definición que nos queda por entender es el conjunto de prefijos. El esquema ∑ tiene la propiedad de prefijo si para cualquier 1≤i, j≤r, i ≠ j, la palabra B i no es un prefijo de la palabra B j.
En pocas palabras, un conjunto de prefijos es un conjunto finito en el que ningún elemento es un prefijo (o comienzo) de cualquier otro elemento. Un simple ejemplo tal conjunto es, por ejemplo, un alfabeto ordinario.

Entonces, descubrimos las definiciones básicas. Entonces, ¿cómo ocurre la codificación real sin memoria?
Se desarrolla en tres etapas.

1. Se compila un alfabeto de Ψ símbolos del mensaje original y los símbolos del alfabeto se clasifican en orden descendente de su probabilidad de aparición en el mensaje.
2. Cada símbolo a i del alfabeto Ψ está asociado con una determinada palabra B i del conjunto de prefijos Ω.
3. Cada carácter se codifica, seguido de la combinación de los códigos en un flujo de datos, que será el resultado de la compresión.

Uno de los algoritmos canónicos que ilustran este método es el algoritmo de Huffman.

Algoritmo de Huffman

El algoritmo de Huffman utiliza la frecuencia de aparición de bytes idénticos en el bloque de datos de entrada y asigna bloques que ocurren con frecuencia a cadenas de bits más cortas y viceversa. Este código es mínimo, redundante. Considere el caso cuando, independientemente de flujo de entrada, el alfabeto del flujo de salida consta de solo 2 caracteres: cero y uno.

En primer lugar, al codificar con el algoritmo de Huffman, necesitamos construir un circuito ∑. Esto se hace de la siguiente manera:

1. Todas las letras del alfabeto de entrada están ordenadas en orden descendente de probabilidades. Todas las palabras del alfabeto del flujo de salida (es decir, lo que codificaremos) se consideran inicialmente vacías (recuerde que el alfabeto del flujo de salida consta solo de caracteres (0,1)).
2. Dos símbolos a j-1 y a j del flujo de entrada, que tienen las probabilidades más bajas de ocurrencia, se combinan en un "pseudo-símbolo" con la probabilidad pag igual a la suma de las probabilidades de los símbolos incluidos en él. Luego sumamos 0 al comienzo de la palabra B j-1, y 1 al comienzo de la palabra B j, que posteriormente serán los códigos de los caracteres a j-1 y a j, respectivamente.
3. Eliminamos estos símbolos del alfabeto del mensaje original, pero agregamos el pseudo-símbolo generado a este alfabeto (por supuesto, debe insertarse en el alfabeto en el lugar correcto, teniendo en cuenta su probabilidad).

Los pasos 2 y 3 se repiten hasta que solo queda 1 pseudo carácter en el alfabeto, que contiene todos los caracteres originales del alfabeto. En este caso, dado que en cada paso y para cada carácter, la palabra correspondiente B i cambia (agregando uno o cero), luego de la finalización de este procedimiento, un cierto código B i corresponderá a cada símbolo inicial del alfabeto a I.

Para una mejor ilustración, considere un pequeño ejemplo.
Supongamos que tenemos un alfabeto que consta de solo cuatro caracteres (un 1, un 2, un 3, un 4). Supongamos también que las probabilidades de aparición de estos símbolos son, respectivamente, p 1 = 0,5; p 2 = 0,24; p 3 = 0,15; p 4 = 0.11 (la suma de todas las probabilidades es obviamente igual a uno).

Entonces, construyamos un esquema para un alfabeto dado.

1. Combinamos los dos caracteres con las probabilidades más bajas (0,11 y 0,15) en un pseudo carácter p ".
2. Combine los dos caracteres con la probabilidad más baja (0,24 y 0,26) en el pseudo carácter p "".
3. Elimine los caracteres concatenados e inserte el pseudo carácter resultante en el alfabeto.
4. Finalmente, combinamos los dos símbolos restantes para obtener la parte superior del árbol.

Si hace una ilustración de este proceso, obtendrá algo como esto:

Como puede ver, cada vez que nos fusionamos, asignamos los códigos 0 y 1 a los caracteres fusionados.
De esta manera, cuando se construye el árbol, podemos obtener fácilmente el código para cada carácter. En nuestro caso, los códigos se verán así:

A 1 = 0
a 2 = 11
a 3 = 100
a 4 = 101

Dado que ninguno de estos códigos es un prefijo de otro (es decir, obtuvimos el notorio conjunto de prefijos), podemos identificar de forma única cada código en el flujo de salida.
Entonces, hemos logrado que el carácter más frecuente sea codificado por el código más corto y viceversa.
Si asumimos que inicialmente se usó un byte para almacenar cada carácter, entonces podemos calcular cuánto logramos reducir los datos.

Suponga que en la entrada tenemos una cadena de 1000 caracteres, en la que el carácter 1 aparece 500 veces, 2 - 240, 3 - 150 y 4 - 110 veces.

Inicialmente cadena dada ocupado 8000 bits. Después de la codificación, obtenemos una cadena de longitud ∑p i l i = 500 * 1 + 240 * 2 + 150 * 3 + 110 * 3 = 1760 bits. Entonces, logramos comprimir los datos 4.54 veces, gastando un promedio de 1.76 bits para codificar cada carácter del flujo.

Permítanme recordarles que, según Shannon, la longitud promedio de los códigos es. Sustituyendo nuestras probabilidades en esta ecuación, obtenemos la longitud promedio del código igual a 1.75496602732291, que está muy, muy cerca de nuestro resultado.
Sin embargo, debe tenerse en cuenta que además de los datos en sí, necesitamos almacenar la tabla de codificación, lo que aumentará ligeramente el tamaño final de los datos codificados. Obviamente, en diferentes casos, se pueden usar diferentes variaciones del algoritmo; por ejemplo, a veces es más eficiente usarlo de antemano. una mesa dada probabilidades y, a veces, es necesario componerlo dinámicamente, pasando a través de los datos comprimibles.

Conclusión

Entonces, en este artículo intenté hablar sobre los principios generales por los cuales se produce la compresión sin pérdidas, y también consideré uno de los algoritmos canónicos: la codificación de Huffman.
Si el artículo es del agrado de la comunidad habro, con mucho gusto escribiré una secuela, ya que todavía hay muchas cosas interesantes relacionadas con la compresión sin pérdidas; estos son tanto algoritmos clásicos como transformaciones de datos preliminares (por ejemplo, la transformación de Burrows-Wheeler) y, por supuesto, algoritmos específicos para comprimir audio, video e imágenes (el tema más interesante, en mi opinión).

Literatura

• Vatolin D., Ratushnyak A., Smirnov M., Yukin V. Métodos de compresión de datos. El dispositivo de archivadores, compresión de imágenes y videos; ISBN 5-86404-170-X; 2003 r.
• D. Salomon. Compresión de datos, imágenes y sonido; ISBN 5-94836-027-X; 2004

Principios de compresión de información

Cualquier método de compresión de información se basa en el modelo de fuente de información o, más específicamente, en el modelo de redundancia. En otras palabras, para comprimir información, se usa cierta información sobre qué tipo de información se está comprimiendo; sin tener ninguna información sobre la información, no se puede hacer absolutamente ninguna suposición sobre qué transformación reducirá el volumen del mensaje. Esta información se utiliza en el proceso de compresión y descompresión. El modelo de redundancia también se puede construir o parametrizar durante la etapa de compresión. Los métodos que permiten cambiar el modelo de redundancia de información en función de los datos de entrada se denominan adaptativos. Los no adaptativos suelen ser algoritmos muy específicos que se utilizan para trabajar con características bien definidas y sin cambios. La inmensa mayoría de los algoritmos suficientemente universales son adaptables en un grado u otro.

Cualquier método de compresión de información incluye dos conversiones inversas entre sí:

• conversión de compresión;
• conversión de expansión.

La transformación de compresión proporciona un mensaje comprimido del original. La descompresión asegura que el mensaje original (o su aproximación) se obtenga del comprimido.

Todos los métodos de compresión se dividen en dos clases principales

• sin pérdida,
• con pérdidas.

La diferencia fundamental entre los dos es que la compresión sin pérdidas brinda la capacidad de reconstruir con precisión el mensaje original. La compresión con pérdida le permite obtener solo una aproximación del mensaje original, es decir, diferente del original, pero dentro de algunos errores predeterminados. Estos errores deben ser determinados por otro modelo: el modelo del receptor, que determina qué datos y con qué precisión se presentan al receptor y cuáles son aceptables para descartar.

Características y aplicabilidad del algoritmo de compresión

Índice de compresión

La relación de compresión es la característica principal del algoritmo de compresión, que expresa la calidad principal de la aplicación. Se define como la relación entre el tamaño de los datos sin comprimir y los datos comprimidos, es decir:

k = S o / S C,

dónde k- índice de compresión, S o es el tamaño de los datos sin comprimir, y S c - el tamaño del comprimido. Por tanto, cuanto mayor sea la relación de compresión, mejor será el algoritmo. Se debería notar:

• si k= 1, entonces el algoritmo no comprime, es decir, recibe un mensaje de salida con un tamaño igual al de entrada;
• si k < 1, то алгоритм порождает при сжатии сообщение большего размера, нежели несжатое, то есть, совершает «вредную» работу.

La situación con k < 1 вполне возможна при сжатии. Невозможно получить алгоритм сжатия без потерь, который при любых данных образовывал бы на выходе данные меньшей или равной длины. Обоснование этого факта заключается в том, что количество различных сообщений длиной norte Patrón: E: bit es exactamente 2 norte... Luego, el número de mensajes diferentes con una longitud menor o igual a norte(si hay al menos un mensaje de menor longitud) será menor que 2 norte... Esto significa que es imposible hacer coincidir inequívocamente todos los mensajes originales con uno comprimido: o algunos de los mensajes originales no tendrán una representación comprimida, o varios mensajes originales corresponderán al mismo comprimido, lo que significa que no se pueden distinguir.

La relación de compresión puede ser una relación constante (algunos algoritmos de compresión para sonido, imágenes, etc., por ejemplo, ley A, ley μ, ADPCM) o variable. En el segundo caso, puede determinarse para un mensaje específico o evaluarse según algunos criterios:

• promedio (generalmente sobre algún conjunto de datos de prueba);
• máximo (caso de la mejor compresión);
• mínima (compresión en el peor de los casos);

o alguna otra. La relación de compresión con pérdida en este caso depende en gran medida del error de compresión permisible o de su calidad, que suele actuar como parámetro del algoritmo.

Tolerancia a la pérdida

El criterio principal para distinguir entre algoritmos de compresión es la presencia o ausencia de pérdidas descritas anteriormente. En general, los algoritmos de compresión sin pérdidas son universales en el sentido de que pueden aplicarse a cualquier tipo de datos, mientras que el uso de la compresión con pérdidas debe estar justificado. Algunos tipos de datos no toleran ningún tipo de pérdida:

• datos simbólicos, cambio en el que inevitablemente se produce un cambio en su semántica: programas y sus códigos fuente, arrays binarios, etc.;
• datos vitales, cuyos cambios pueden dar lugar a errores críticos: por ejemplo, obtenidos de equipos de medición médica o dispositivos de control de aeronaves, naves espaciales, etc.
• datos sometidos repetidamente a compresión y descompresión: gráficos de trabajo, sonido, archivos de vídeo.

Sin embargo, la compresión con pérdida le permite lograr relaciones de compresión mucho más altas al descartar información insignificante que no se comprime bien. Entonces, por ejemplo, el algoritmo de compresión de audio sin pérdida FLAC, en la mayoría de los casos, le permite comprimir el audio entre 1,5 y 2,5 veces, mientras que el algoritmo de Vorbis con pérdida, según el parámetro de calidad establecido, puede comprimir hasta 15 veces manteniendo una calidad aceptable. .sonido.

Requisitos del sistema de algoritmos

Diferentes algoritmos pueden requerir diferentes cantidades de recursos sistema informático en las que se realizan:

• RAM (para datos intermedios);
• memoria permanente (para código de programa y constantes);
• tiempo de procesador.

En general, estos requisitos dependen de la complejidad y la "inteligencia" del algoritmo. Como tendencia general, cuanto mejor y más versátil es el algoritmo, más exigencias tiene en la máquina. Sin embargo, en casos específicos, los algoritmos simples y compactos pueden funcionar mejor. Los requisitos del sistema determinan sus cualidades de consumidor: cuanto menos exigente es un algoritmo, más sencillo y, por tanto, compacto, fiable y económico es el sistema en el que puede trabajar.

Dado que los algoritmos de compresión y descompresión funcionan en pares, la relación Requisitos del sistema a ellos. A menudo puede complicar un algoritmo, puede simplificar enormemente el otro. Así, podemos tener tres opciones:

El algoritmo de compresión es mucho más exigente con los recursos que el algoritmo de descompresión. Esta es la relación más común y se aplica principalmente en los casos en los que los datos comprimidos una vez se utilizarán varias veces. Los ejemplos incluyen reproductores de audio y video digital. Los algoritmos de compresión y descompresión tienen requisitos aproximadamente iguales. La opción más aceptable para una línea de comunicación, cuando la compresión y descompresión ocurren una vez en sus dos extremos. Por ejemplo, puede ser telefonía. El algoritmo de compresión es significativamente menos exigente que el algoritmo de descompresión. Un caso bastante exótico. Se puede utilizar en casos donde el transmisor es un dispositivo ultraportátil, donde la cantidad de recursos disponibles es muy crítica, por ejemplo, una nave espacial o una gran red distribuida de sensores, o puede estar desempaquetando datos que se requieren en un porcentaje muy pequeño de casos, por ejemplo, grabación de cámaras CCTV.

ver también

Fundación Wikimedia. 2010.

Vea qué es "Compresión de información" en otros diccionarios:

compresión de información- consolidación de la información - [L.G. Sumenko. El Diccionario Inglés Ruso de Tecnología de la Información. M.: GP TsNIIS, 2003.] Temas tecnologías de la información en general Sinónimos compactación de información ES reducción de información ...

COMPRIMIR INFORMACIÓN- (compresión de datos) presentación de información (datos) en menos bits que el original. Basado en eliminar la redundancia. Distinguir S. y. sin pérdida de información y con la pérdida de alguna información insignificante para las tareas que se están resolviendo. PARA… … Diccionario enciclopédico de psicología y pedagogía

compresión adaptativa sin pérdidas- - [L.G. Sumenko. El Diccionario Inglés Ruso de Tecnología de la Información. M.: GP TsNIIS, 2003.] Temas tecnologías de la información en general EN compresión adaptativa sin pérdida de datosALDC ... Guía del traductor técnico

compresión / compresión de información- - [L.G. Sumenko. El Diccionario Inglés Ruso de Tecnología de la Información. M.: GP TsNIIS, 2003.] Temas tecnologías de la información en general Compactación EN ... Guía del traductor técnico

compresión de información digital- - [L.G. Sumenko. El Diccionario Inglés Ruso de Tecnología de la Información. M.: GP TsNIIS, 2003.] Temas tecnologías de la información en general compresión EN ... Guía del traductor técnico

El sonido es una onda simple y señal digital es una representación de esta ola. Esto se logra memorizando la amplitud Señal analoga varias veces en un segundo. Por ejemplo, en un CD ordinario, una señal se memoriza 44100 veces en ... ... Wikipedia

Un proceso que reduce la cantidad de datos al reducir la redundancia. La compresión de datos implica la compactación de fragmentos de datos de tamaño estándar. Se hace una distinción entre compresión con pérdida y sin pérdida. En inglés: Data ... ... Vocabulario financiero

compresión de mapas digitales- Procesamiento de información cartográfica digital con el fin de reducir su volumen, incluyendo la eliminación de redundancias dentro de la precisión requerida de su presentación. [GOST 28441 99] Temas cartografía digital Generalización de términos métodos y tecnologías ... ... Guía del traductor técnico

El propósito de la lección: desarrollar la atención, la inteligencia, fomentar el interés por el tema.
Equipo: computadoras, discos de laboratorio, apropiados software, tarjetas con una tarea de prueba.

Durante las clases

1. Parte organizativa.
2. Actualización de conocimientos básicos.
3. Aprendiendo material nuevo
4. Asegurar material nuevo.
5. Tarea.
6. Resumiendo la lección.

Aprendiendo material nuevo

1. Qué es archivar. Concepto de compresión de datos.
2. Los principales tipos de programas de archivo.
3. Programa el archivador WIN-RAR.
4. Cómo agregar un archivo al archivo, así como extraerlo del archivo.

Con desarrollo tecnologías de la información La cuestión de cómo almacenar los datos surgió con fuerza. Desde los años 40 del siglo XX, los científicos han estado desarrollando métodos para presentar datos, en los que el espacio en los soportes de información se utilizaría de forma más económica. El resultado es una tecnología de compresión y archivo de datos (copia de seguridad).

El archivo de datos es la fusión de varios archivos o directorios en un solo archivo.

Compresión de datos: reduce el tamaño de los archivos originales al eliminar la información redundante.

Para realizar estas tareas, existen programas de archivo que proporcionan compresión de datos: en particular, archivo de archivos. Utilizando algoritmos especiales, los archivadores eliminan toda la información redundante de los archivos y, durante las operaciones de desempaquetado inverso, restauran la información en su forma original. El tamaño archivo comprimido de dos a diez veces menos que el archivo original. En este caso, la compresión y restauración de la información se produce sin pérdida. La compresión sin pérdida es relevante cuando se trabaja con archivos de texto y de programa, en tareas de criptografía. También existen técnicas de compresión con pérdida.

La relación de compresión depende del tipo de archivo y del programa de archivado. Sobre todo encogerse archivos de texto y menos aún: archivos de audio y video.

Archivar archivos. Tareas

Hasta ahora, hemos estado hablando de un propósito de archivar datos: más económico que usar medios de almacenamiento. Sin embargo, al utilizar el archivo, puede realizar una amplia gama de tareas:
1. Reducir el volumen de archivos (importante no solo para ahorrar espacio en los medios, sino también para transferir archivos rápidamente a través de la red).
2. Realización de copias de seguridad en medios externos para almacenar información importante.

3. Archivar al cifrar datos para reducir la probabilidad de romper el criptosistema.

El proceso de escribir información en un archivo de almacenamiento se denomina archivado.
Extrayendo archivos del archivo - descomprimiendo.

Los primeros programas de archivo aparecieron a mediados de la década de 1980. Se centraron en trabajar en MS-DOC y admitieron formatos de archivo populares: ARC, ICE, ARJ, ZIP y RAR, etc. También había un grupo de archivadores que empaquetaban datos en archivos autoextraíbles: archivos con. eхе,. vamos. Se crearon archivadores residentes para comprimir todo el disco. Hicieron posible aumentar la eficiencia de la utilización del espacio en disco mediante la creación de grandes archivos de almacenamiento: "compresiones" de disco.

Trabajar con archivos se ha vuelto mucho más conveniente con la llegada de las versiones de Windows y Windows de los archivadores. De formatos de archivo anteriores entre Usuarios de Windows ARJ, ZIP: los programas que descomprimen archivos realmente se han arraigado. Los archivos de almacenamiento de gran tamaño se pueden ubicar en varios disquetes (volúmenes). Estos archivos se denominan multivolumen.

Tom es componente archivo multivolumen.

Actualmente se utilizan decenas de programas de archivo, que difieren en la lista de funciones y parámetros operativos, pero los mejores tienen aproximadamente las mismas características. Sabemos que empaquetar y desempaquetar archivos lo realiza el mismo programa, pero en algunos casos esto se hace diferentes programas por ejemplo, el programa RKZIP empaqueta archivos y RKUNZIP descomprime los archivos.
Los programas de archivo le permiten crear dichos archivos, para extraerlos, de los cuales no necesita ningún programa, ya que los archivos de almacenamiento contienen un programa autoextraíble. Estos archivos se denominan archivos SFX.

Colocación de archivos en un archivo: inicie Programas WINRAR o como acceso directo en el escritorio.

Archivador universal WINRAR

El archivador WINRAR también está diseñado para archivar archivos. Tiene una interfaz gráfica conveniente y es compatible con la tecnología de arrastrar y soltar. El software WINRAR le permite trabajar no solo con archivos archivos rar, pero también con otros formatos de archivo: zip, cab, arj, lzh. WINRAR es lanzado por cualquiera de formas posibles proporcionado en Windows. Ejecutando el programa usando el menú principal del botón Inicio Programas WINRAR WINRAR o usando un acceso directo en el escritorio.

Encuesta de prueba sobre los conceptos básicos del trabajo con discos.
Tarea.
Lección de introspección.

Para lograr estas tareas, existen programas de archivo que proporcionan tanto archivo como compresión de datos. Utilizando algoritmos especiales, los archivadores eliminan toda la información redundante de los archivos y, durante las operaciones de desempaquetado inverso, restauran la información en su forma original. El tamaño del archivo comprimido es de dos a diez veces menor que el del archivo original.

Hoy en día, muchos usuarios están pensando en cómo se lleva a cabo el proceso de compresión de información con el fin de ahorrar espacio libre en el disco duro, porque este es uno de los más medios eficaces uso del espacio utilizable en cualquier unidad. Muy a menudo, los usuarios modernos que se enfrentan a una falta de espacio libre en la unidad tienen que eliminar cualquier dato para liberar el espacio necesario, mientras que los usuarios más avanzados suelen utilizar la compresión de datos para reducir su volumen.

Sin embargo, muchos ni siquiera saben cómo se llama el proceso de compresión de información, sin mencionar qué algoritmos se utilizan y qué da la aplicación de cada uno de ellos.

¿Deberías comprimir datos?

La compresión de datos es bastante importante hoy en día y es necesaria para cualquier usuario. Por supuesto, en nuestro tiempo, casi todo el mundo puede comprar dispositivos de almacenamiento de datos avanzados que brinden la capacidad de utilizar una cantidad suficientemente grande de espacio libre, además de estar equipados con canales de transmisión de información de alta velocidad.

Sin embargo, en este caso, debe comprender correctamente que con el tiempo, la cantidad de datos que deben transferirse también aumenta. Y si literalmente hace diez años, el volumen de 700 MB se consideraba estándar para una película ordinaria, hoy las películas realizadas en calidad HD pueden tener volúmenes equivalentes a varias decenas de gigabytes, sin mencionar cuánto espacio libre ocupan las películas de alta calidad. .en formato Blu-ray.

¿Cuándo es necesaria la compresión de datos?

Por supuesto, no debe esperar que el proceso de compresión de información le brinde muchos beneficios, pero hay una serie de situaciones en las que algunos métodos de compresión de información son extremadamente útiles e incluso necesarios:

• Transferencia de determinados documentos por correo electrónico. Esto es especialmente cierto para aquellas situaciones en las que necesita transferir información en grandes volúmenes utilizando varios dispositivos móviles.
• A menudo, el proceso de comprimir información para reducir el espacio que ocupa se utiliza cuando se publican ciertos datos en varios sitios cuando es necesario para ahorrar tráfico;
• Ahorre espacio libre en su disco duro cuando no haya forma de reemplazar o agregar nuevos medios de almacenamiento. En particular, la situación más común es cuando existen ciertas restricciones en el presupuesto disponible, pero no hay suficiente espacio libre en disco.

Por supuesto, además de lo anterior, también hay numero enorme Varias situaciones en las que el proceso de compresión de información puede ser necesario para reducir su volumen, sin embargo, estas son, con mucho, las más comunes.

¿Cómo se pueden comprimir los datos?

Hoy en día, existe una amplia variedad de métodos para comprimir información, pero todos se dividen en dos grupos principales: compresión con ciertas pérdidas, así como compresión sin pérdida.

El uso del último grupo de métodos es relevante cuando los datos deben recuperarse con una precisión extremadamente alta, hasta un bit. Este enfoque es el único relevante en el caso de que un determinado documento de texto esté comprimido.

Al mismo tiempo, vale la pena señalar el hecho de que en algunas situaciones no es necesaria la recuperación más precisa de los datos comprimidos, por lo tanto, es posible utilizar tales algoritmos en los que la información en el disco se comprime con ciertas pérdidas. La ventaja de la compresión con pérdida es que esta tecnología es mucho más fácil de implementar y también proporciona el mayor nivel posible de archivo.

Compresión con pérdida

La información con pérdida proporciona una mejor compresión en un orden de magnitud, al tiempo que mantiene una calidad de información suficiente. En la mayoría de los casos, el uso de este tipo de algoritmos se lleva a cabo para comprimir datos analógicos, como todo tipo de imágenes o sonidos. En tales situaciones, los archivos descomprimidos pueden ser bastante diferentes de la información original, pero son prácticamente indistinguibles del ojo u oído humanos.

Compresión sin perdidas

Los algoritmos de compresión sin pérdida proporcionan la recuperación de datos más precisa, eliminando cualquier pérdida de archivos comprimidos. Sin embargo, al mismo tiempo, debe comprender correctamente el hecho de que, en este caso, se proporciona una compresión de archivos no tan efectiva.

Métodos genéricos

Entre otras cosas, hay una serie determinada métodos universales, mediante el cual se lleva a cabo un eficaz proceso de compresión de información con el fin de reducir el espacio que ocupa. En general, solo hay tres tecnologías principales:

• Conversión de flujo. En este caso, la descripción de la nueva información entrante sin comprimir se realiza a través de los archivos ya procesados, mientras que no se calculan probabilidades, sino que los caracteres se codifican en base únicamente a aquellos archivos que ya han pasado por un determinado procesamiento.
• Compresión estadística. Este proceso de comprimir información para reducir el espacio que ocupa en el disco se divide en dos subcategorías: métodos adaptativos y de bloques. La versión adaptativa permite calcular las probabilidades de archivos nuevos en función de la información que ya se ha procesado durante el proceso de codificación. En particular, estos métodos también deberían incluir varias variantes adaptativas de los algoritmos de Shannon-Fano y Huffman. El algoritmo de bloque proporciona un cálculo separado de cada bloque de información con la posterior adición al bloque más comprimido.
• Transformación de bloques. La información entrante se divide en varios bloques y luego se lleva a cabo una transformación integral. Cabe decir que ciertos métodos, especialmente los basados ​​en la permutación de varios bloques, pueden conducir en última instancia a una reducción significativa en la cantidad de información comprimible. Sin embargo, debe entenderse correctamente que después de dicho procesamiento, finalmente se produce una mejora significativa, como resultado de lo cual la compresión posterior a través de otros algoritmos es mucho más fácil y rápida.

Compresión de copia

Uno de los componentes más importantes Reserva copia es el dispositivo al que moverse necesario por el usuario información. Cuantos más datos mueva, más voluminoso será el dispositivo que necesitará utilizar. Sin embargo, si va a llevar a cabo el proceso de compresión de datos, entonces, en este caso, es poco probable que el problema de la falta de espacio libre siga siendo relevante para usted.

¿Por qué es necesario?

La capacidad de comprimir información al tiempo que reduce significativamente el tiempo que se necesitará para copiar archivos requeridos y al mismo tiempo lograr ahorros efectivos en espacio libre en la unidad. En otras palabras, al utilizar la compresión, la información se copiará de forma mucho más compacta y rápida, y podrá ahorrar su dinero y sus finanzas, que eran necesarios para comprar una unidad más grande. Entre otras cosas, al comprimir la información, también reduce el tiempo que será necesario para transportar todos los datos al servidor o copiarlos a través de la red.

La compresión de datos para la copia de seguridad se puede llevar a cabo en uno o varios archivos; en este caso, todo dependerá del programa que utilice y de la información que comprima.

Al elegir una utilidad, asegúrese de ver cuánto puede comprimir los datos el programa elegido. Depende del tipo de información, por lo que la eficiencia de la compresión de documentos de texto puede ser superior al 90%, mientras que la eficiencia no superará el 5%.

Como se mencionó anteriormente, una de las tareas importantes preparación preliminar el cifrado de datos es para reducir su redundancia y alinear los patrones estadísticos del lenguaje utilizado. La eliminación parcial de la redundancia se logra comprimiendo los datos.

Compresión de información es el proceso de convertir el mensaje original de un sistema de código a otro, como resultado de lo cual tamaño del mensaje... Los algoritmos diseñados para comprimir información se pueden dividir en dos grandes grupos: los que implementan la compresión sin pérdidas (compresión reversible) y los que implementan la compresión con pérdidas (compresión irreversible).

Compresión reversible implica una recuperación de datos absolutamente precisa después de la decodificación y se puede utilizar para comprimir cualquier información. Siempre conduce a una disminución en el volumen del flujo de información de salida sin cambiar su contenido de información, es decir, sin perder estructura de la información... Además, desde el flujo de salida, utilizando el algoritmo de recuperación o descompresión, puede obtener la entrada, y el proceso de recuperación se llama descompresión o descompresión, y solo después del proceso de descompresión los datos son adecuados para su procesamiento de acuerdo con su formato interno. La compresión sin pérdida se utiliza para texto, archivos ejecutables, audio y gráficos de alta calidad.

Compresión irreversible generalmente tiene una relación de compresión mucho más alta que la codificación sin pérdidas, pero permite algunas desviaciones de los datos decodificados del original. En la práctica, existe una amplia gama de problemas prácticos en los que el cumplimiento del requisito de restauración precisa de la información original después de la descompresión no es obligatorio. Esto, en particular, se aplica a la compresión de información multimedia: imágenes de sonido, fotos o videos. Por ejemplo, los formatos multimedia JPEG y MPEG, que utilizan compresión irreversible, se utilizan ampliamente. La compresión irreversible generalmente no se usa junto con el cifrado criptográfico, ya que el principal requisito para un criptosistema es la identidad de los datos descifrados con el original. Sin embargo, cuando se utilizan tecnologías multimedia, los datos presentados en forma digital a menudo se comprimen de forma irreversible antes de enviarse a un sistema criptográfico para su cifrado. Una vez que la información se transfiere al consumidor y se descifra, los archivos multimedia se utilizan en forma comprimida (es decir, no se restauran).

Echemos un vistazo más de cerca a algunos de los métodos más comunes de compresión de datos reversible.

El método y algoritmo simple más famoso para la compresión reversible de información es Run Length Encoding (RLE). La esencia de los métodos de este enfoque es reemplazar cadenas o series de bytes repetidos con un relleno de bytes de codificación y un contador del número de sus repeticiones. El problema con todos los métodos análogos es solo determinar la forma en que el algoritmo de desempaquetado podría distinguir la serie codificada en el flujo de bytes resultante de otras secuencias de bytes no codificadas. La solución al problema generalmente se logra colocando etiquetas al comienzo de las cadenas codificadas. Dichas etiquetas pueden ser valores de bits característicos en el primer byte de la ejecución codificada, los valores del primer byte de la ejecución codificada. La desventaja del método RLE es la relación de compresión bastante baja o el costo de codificar archivos con una pequeña cantidad de series y, lo que es peor, con una pequeña cantidad de bytes repetidos en una serie.

Con una codificación uniforme de la información, se asigna el mismo número de bits a un mensaje, independientemente de la probabilidad de que ocurra. Al mismo tiempo, es lógico suponer que la longitud total de los mensajes transmitidos disminuirá si los mensajes frecuentes se codifican con palabras clave cortas y las raras, con palabras más largas. Los problemas que surgen en este caso están asociados a la necesidad de utilizar códigos de longitud variable... Hay muchos enfoques para construir dichos códigos.

Uno de los más utilizados en la práctica son los métodos de diccionario, cuyos principales representantes son los algoritmos de las familias Ziv y Lempel. Su idea principal es que los fragmentos del flujo de entrada ("frases") se reemplazan por un puntero al lugar donde ya han aparecido en el texto. En la literatura, estos algoritmos se denominan algoritmos. Compresión LZ.

Este método se adapta rápidamente a la estructura del texto y puede codificar palabras funcionales cortas, ya que aparecen con mucha frecuencia en él. También se pueden formar nuevas palabras y frases a partir de partes de palabras encontradas anteriormente. La decodificación del texto comprimido se realiza directamente: hay un simple reemplazo del puntero con una frase preparada del diccionario a la que apunta. En la práctica, el método LZ logra una buena compresión, su propiedad importante es el trabajo muy rápido del decodificador.

Otro enfoque para comprimir información es Código Huffman, cuyo codificador y decodificador tienen una implementación de hardware bastante simple. La idea del algoritmo es la siguiente: conociendo las probabilidades de aparición de caracteres en un mensaje, se puede describir el procedimiento para construir códigos de longitud variable que constan de un número entero de bits. Es más probable que se asignen más símbolos que códigos cortos, mientras que los caracteres menos comunes son más largos. Esto logra una reducción en la longitud promedio de la palabra de código y una mayor eficiencia de compresión. Los códigos de Huffman tienen un prefijo único (el comienzo de la palabra de código), que les permite ser decodificados de forma única, a pesar de su longitud variable.

El procedimiento de síntesis del código clásico de Huffman asume la presencia de información a priori sobre las características estadísticas de la fuente del mensaje. En otras palabras, el desarrollador debe conocer las probabilidades de aparición de ciertos símbolos a partir de los cuales se forman los mensajes. Consideremos la síntesis del código de Huffman usando un ejemplo simple.

p (S 1) = 0,2, p (S 2) = 0,15, p (S 3) = 0,55, p (S 4) = 0,1... Clasifiquemos los símbolos en orden descendente de probabilidad de ocurrencia y presentémoslos en forma de tabla (figura 14.3, a).

El procedimiento de síntesis de código consta de tres etapas principales. En la primera etapa, las filas de la tabla se pliegan: dos filas correspondientes a los símbolos con las probabilidades más bajas de ocurrencia se reemplazan por una con la probabilidad total, después de lo cual la tabla se reordena nuevamente. La convolución continúa hasta que solo hay una fila en la tabla con una probabilidad total igual a uno (figura 14.3, b).

Arroz. 14.3.

En la segunda etapa, se construye un árbol de código usando una tabla colapsada (Fig. 14.4, a). El árbol se construye a partir de la última columna de la tabla.

Arroz. 14.4.

La raíz del árbol forma la unidad en la última columna. En el ejemplo en consideración, esta unidad se forma a partir de las probabilidades de 0,55 y 0,45, representadas como dos nodos de árbol asociados con la raíz. El primero de ellos corresponde al símbolo S 3 y, por tanto, no se produce ninguna otra ramificación de este nodo.

El segundo nodo, etiquetado con una probabilidad de 0,45, se conecta a dos nodos del tercer nivel, con probabilidades de 0,25 y 0,2. La probabilidad 0.2 corresponde al símbolo S 1, y la probabilidad 0.25, a su vez, se forma a partir de las probabilidades 0.15 de la aparición del símbolo S 2 y 0.1 de la aparición del símbolo S 4.

Los bordes que conectan los nodos individuales del árbol de código se numeran 0 y 1 (por ejemplo, los bordes izquierdos son 0 y los bordes derechos son 1). En la tercera y última etapa, se construye una tabla en la que se comparan los símbolos fuente y las palabras de código de Huffman correspondientes. Estas palabras de código se forman leyendo los números que marcan los bordes que forman un camino desde la raíz del árbol hasta el símbolo correspondiente. Para el ejemplo en consideración, el código de Huffman tomará la forma que se muestra en la tabla de la derecha (Fig. 14.4, b).

Sin embargo, el algoritmo clásico de Huffman tiene un inconveniente importante. Para recuperar el contenido del mensaje comprimido, el decodificador debe conocer la tabla de frecuencias utilizada por el codificador. En consecuencia, la longitud del mensaje comprimido aumenta con la longitud de la tabla de frecuencias que se enviará delante de los datos, lo que puede anular todos los esfuerzos para comprimir el mensaje.

Otra variante codificación estática de Huffman consiste en ver el flujo de entrada y construir una codificación basada en las estadísticas recopiladas. En este caso, se requieren dos pasadas a través del archivo: una para ver y recopilar información estadística, la segunda para codificar. En la codificación estática de Huffman, los símbolos de entrada (cadenas de bits de diferentes longitudes) se asocian con cadenas de bits de longitud variable: sus códigos. La longitud del código de cada símbolo se toma proporcional al logaritmo binario de su frecuencia, tomado con el signo opuesto. Y el conjunto común de todos los diferentes símbolos encontrados constituye el alfabeto de la secuencia.

Hay otro método: adaptativo o codificación dinámica de Huffman... Su principio general es cambiar el esquema de codificación dependiendo de la naturaleza de los cambios en el flujo de entrada. Este enfoque tiene un algoritmo de un solo paso y no requiere almacenar información sobre la codificación utilizada de forma explícita. La codificación adaptativa puede dar una relación de compresión más alta que la codificación estática, ya que los cambios en las frecuencias del flujo de entrada se tienen más en cuenta. Cuando se utiliza la codificación adaptativa de Huffman, la complejidad del algoritmo consiste en la necesidad de ajustar constantemente el árbol y los códigos de los caracteres del alfabeto básico de acuerdo con las estadísticas cambiantes del flujo de entrada.

Los métodos de Huffman dan una velocidad bastante alta y moderada buena calidad compresión. Sin embargo, la codificación de Huffman tiene una redundancia mínima, siempre que cada carácter esté codificado en el alfabeto del código de caracteres con una cadena separada de dos bits - (0, 1). El principal inconveniente este método es la dependencia de la relación de compresión de la proximidad de las probabilidades de los símbolos a 2 en algún grado negativo, lo que se debe al hecho de que cada símbolo está codificado con un número entero de bits.

Una solución completamente diferente es ofrecida por codificación aritmética... Este método se basa en la idea de convertir un flujo de entrada en un único número de coma flotante. La codificación aritmética es una técnica que permite el empaquetado sin pérdidas de los caracteres del alfabeto de entrada, siempre que se conozca la distribución de frecuencia de estos caracteres.

La secuencia de caracteres requerida estimada cuando se comprime mediante el método de codificación aritmética se considera como una fracción binaria del intervalo)