Capacidad de silencio para comprimir datos de documentos. Métodos de compresión de datos.

Los métodos de compresión de datos tienen una historia de desarrollo bastante larga, que comenzó mucho antes de la llegada de la primera computadora. Este artículo intentará ofrecer una breve descripción de las principales teorías, conceptos de ideas y sus implementaciones, sin pretender, sin embargo, que sean absolutamente completos. Se puede encontrar información más detallada, por ejemplo, en Krichevsky R.E. , Ryabko B.Ya. Witten I.H. , Rissanen J. , Huffman DA , Gallager R.G. , Knuth D.E. , Vitter J.S. etc.

La compresión de información es un problema que tiene una historia bastante larga, mucho más larga que la historia del desarrollo de la tecnología informática, que (la historia) generalmente transcurría paralela a la historia del desarrollo del problema de codificar y cifrar información. Todos los algoritmos de compresión operan en un flujo de entrada de información, cuya unidad mínima es un bit y la unidad máxima son varios bits, bytes o varios bytes. El propósito del proceso de compresión, por regla general, es obtener un flujo de salida de unidades de información más compacto a partir de algún flujo de entrada inicialmente no compacto mediante alguna transformación. Las principales características técnicas de los procesos de compresión y los resultados de su trabajo son:

El grado de compresión (índice de compresión) o la relación (proporción) de los volúmenes de las corrientes original y resultante;

La velocidad de compresión es el tiempo dedicado a comprimir una cierta cantidad de información de un flujo de entrada antes de obtener un flujo de salida equivalente;

La calidad de la compresión es un valor que muestra qué tan estrechamente se comprime el flujo de salida al aplicarle recompresión usando el mismo algoritmo u otro.

Existen varios enfoques diferentes para el problema de la compresión de información. Algunos tienen una base matemática teórica muy compleja, otros se basan en las propiedades del flujo de información y son algorítmicamente bastante simples. Cualquier enfoque y algoritmo que implemente la compresión o compresión de datos está diseñado para reducir el volumen del flujo de información de salida en bits mediante su transformación reversible o irreversible. Por tanto, en primer lugar, según el criterio relacionado con la naturaleza o formato de los datos, todos los métodos de compresión se pueden dividir en dos categorías: compresión reversible e irreversible.

Por compresión irreversible se entiende una transformación del flujo de datos de entrada en la que el flujo de salida, basado en un determinado formato de información, representa, desde cierto punto de vista, un objeto bastante similar en características externas al flujo de entrada, pero que difiere de él en volumen. El grado de similitud entre los flujos de entrada y salida está determinado por el grado de correspondencia de ciertas propiedades del objeto (es decir, información comprimida y no comprimida, de acuerdo con algún formato de datos específico) representado por un flujo de información determinado. Estos enfoques y algoritmos se utilizan para comprimir, por ejemplo, datos de archivos de gráficos rasterizados con un bajo grado de repetición de bytes en la secuencia. Este enfoque utiliza la propiedad estructural del formato de archivo gráfico y la capacidad de presentar una imagen gráfica con una calidad de visualización aproximadamente similar (para la percepción del ojo humano) de varias (o más bien n) formas. Por lo tanto, además del grado o magnitud de la compresión, en tales algoritmos surge el concepto de calidad, porque Dado que la imagen original cambia durante el proceso de compresión, la calidad puede entenderse como el grado de correspondencia entre la imagen original y la resultante, evaluado subjetivamente en función del formato de la información. En el caso de los archivos gráficos, esta correspondencia se determina visualmente, aunque también existen algoritmos y programas inteligentes correspondientes. La compresión irreversible no se puede utilizar en áreas donde es necesario tener una coincidencia exacta entre la estructura de información de los flujos de entrada y salida. Este enfoque se implementa en formatos populares para presentar información de vídeo y fotografías, conocidos como algoritmos JPEG y JFIF y formatos de archivo JPG y JIF.

La compresión reversible siempre conduce a una reducción en el volumen del flujo de información de salida sin cambiar su contenido de información, es decir, - sin pérdida de estructura de información. Además, a partir del flujo de salida, utilizando un algoritmo de reconstrucción o descompresión, se puede obtener la entrada, y el proceso de recuperación se denomina 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.

En los algoritmos reversibles, la codificación como proceso se puede ver desde un punto de vista estadístico, lo que es aún más útil, no sólo para construir algoritmos de compresión, sino también para evaluar su eficacia. Para todos los algoritmos reversibles existe un concepto de costo de codificación. El costo de codificación se refiere a la longitud promedio de una palabra de código en bits. La redundancia de codificación es igual a la diferencia entre el costo y la entropía de la codificación, y un buen algoritmo de compresión siempre debe minimizar la redundancia (recuerde que la entropía de la información es una medida de su desorden). El teorema fundamental de Shannon sobre la codificación de información dice que "el costo de la codificación no es siempre menor que la entropía de la fuente, aunque puede estar arbitrariamente cerca de ella". Por lo tanto, para cualquier algoritmo, siempre existe un cierto límite en el grado de compresión, determinado por la entropía del flujo de entrada.

Pasemos ahora directamente a las características algorítmicas de los algoritmos reversibles y consideremos los enfoques teóricos más importantes para la compresión de datos asociados con la implementación de sistemas de codificación y métodos de compresión de información.

Compresión por método de codificación en serie.

El enfoque y algoritmo simple más conocido para comprimir información de forma reversible es la codificación de longitud de ejecución (RLE). La esencia de los métodos de este enfoque es reemplazar cadenas o series de bytes repetidos o sus secuencias con un byte de codificación y un contador para el número de repeticiones. El problema con todos los métodos similares es sólo determinar la forma en que el algoritmo de descompresión podría distinguir una serie codificada de otras secuencias de bytes no codificadas en el flujo de bytes resultante. La solución al problema se suele conseguir colocando marcas al inicio de las cadenas codificadas. Dichas marcas pueden ser, por ejemplo, valores de bits característicos en el primer byte de una serie codificada, los valores del primer byte de una serie codificada, etc. Estos métodos, por regla general, son bastante efectivos para comprimir gráficos rasterizados (BMP, PCX, TIF, GIF), porque estos últimos contienen bastantes series largas de secuencias de bytes repetidas. 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, peor aún, con una pequeña cantidad de bytes repetidos en la serie.

Compresión sin utilizar el método RLE

El proceso de compresión de datos sin utilizar el método RLE se puede dividir en dos etapas: modelado y, de hecho, codificación. Estos procesos y sus algoritmos de implementación son bastante independientes y diversos.

Proceso de codificación y sus métodos.

La codificación generalmente significa procesar un flujo de caracteres (en nuestro caso, bytes o nibbles) en algún alfabeto, y las frecuencias de aparición de caracteres en el flujo son diferentes. El propósito de la codificación es convertir este flujo en un flujo de bits de longitud mínima, lo que se logra reduciendo la entropía del flujo de entrada teniendo en cuenta las frecuencias de los símbolos. La longitud del código que representa los caracteres del alfabeto del flujo debe ser proporcional a la cantidad de información en el flujo de entrada, y la longitud de los caracteres del flujo en bits no puede ser múltiplo de 8 o incluso variable. Si se conoce la distribución de probabilidad de las frecuencias de aparición de símbolos del alfabeto del flujo de entrada, entonces se puede construir un modelo de codificación óptimo. Sin embargo, debido a la existencia de una gran cantidad de formatos de archivos diferentes, la tarea se vuelve mucho más complicada. La distribución de frecuencia de los símbolos de datos se desconoce de antemano. En este caso, en general, se utilizan dos enfoques.

La primera es ver el flujo de entrada y construir una codificación basada en las estadísticas recopiladas (esto requiere dos pases a través del archivo: uno para ver y recopilar información estadística, el segundo para codificar, lo que limita un poco el alcance de dichos algoritmos, porque, en De esta manera, se elimina la posibilidad de la codificación sobre la marcha de un solo paso utilizada en los sistemas de telecomunicaciones, donde a veces se desconoce el volumen de datos y su retransmisión o análisis puede llevar un tiempo excesivamente largo). En este caso, el esquema estadístico de la codificación utilizada se escribe en el flujo de salida. Este método se conoce como codificación estática de Huffman.

Archivadores modernos

Programas especiales

Conferencia 6

Los Archivers son programas para crear archivos. Los archivos están diseñados para almacenar datos en una forma cómoda y compacta. Los datos suelen ser archivos y carpetas. Como regla general, los datos primero se comprimen o empaquetan. Por lo tanto, casi todos los archivadores son también programas de compresión de datos. Por otro lado, cualquier programa de compresión de datos puede considerarse un archivador. La eficiencia de la compresión es la característica más importante de los archivadores. El tamaño de los archivos creados depende de ello. Cuanto más pequeño sea el archivo, menos espacio se necesitará para almacenarlo. La transmisión requiere menos ancho de banda del canal de transmisión o lleva menos tiempo. Las ventajas de los archivos son obvias, considerando que el tamaño de los datos se reduce entre 2 y 5 veces.

La compresión de datos se utiliza mucho. Se podría decir en casi todas partes. Por ejemplo, los documentos PDF suelen contener información comprimida. Muchos archivos ejecutables EXE se comprimen con compresores especiales. Todo tipo de archivos multimedia (GIF, JPG, MP3, MPG) son una especie de archivos.

La principal desventaja de los archivos es la imposibilidad de acceder directamente a los datos. Primero deben extraerse del archivo o descomprimirse. La operación de descomprimir, al igual que empaquetar, requiere algunos recursos del sistema. Esta no es una operación instantánea. Por lo tanto, los archivos se utilizan principalmente con datos que se utilizan relativamente raramente. Por ejemplo, para almacenar copias de seguridad o archivos de instalación.

Actualmente existen muchos archivadores. Varían en prevalencia y eficacia. Algunos archivadores interesantes no son conocidos por una amplia gama de usuarios potenciales. De particular interés es la evaluación y comparación de la eficiencia de compresión de archivadores populares.

Se han desarrollado una gran cantidad de métodos diferentes, sus modificaciones y subtipos para la compresión de datos. Los archivadores modernos tienden a utilizar varios métodos simultáneamente. Podemos destacar algunos básicos.

Codificación de longitud de ejecución (RLE, abreviatura de codificación de longitud de ejecución)

Un método muy sencillo. Una serie secuencial de elementos de datos idénticos se reemplaza por dos caracteres: el elemento y el número de veces que aparece. Se utilizan ampliamente tanto métodos complementarios como intermedios. Como método independiente se utiliza, por ejemplo, en formato gráfico BMP.

Método de diccionario (LZ - abreviatura de Lempel Ziv - nombres de los autores)

El método más común. Se utiliza un diccionario que consta de secuencias de datos o palabras. Durante la compresión, estas palabras se reemplazan con sus códigos del diccionario. En la implementación más común, el propio bloque de datos de origen actúa como un diccionario.

El parámetro principal del método del diccionario es el tamaño del diccionario. Cuanto mayor sea el vocabulario, mayor será la eficiencia. Sin embargo, para datos heterogéneos, un tamaño excesivamente grande puede resultar perjudicial, ya que si el tipo de datos cambia bruscamente, el diccionario se llenará de palabras irrelevantes. Para que este método de compresión funcione eficazmente, se requiere memoria adicional. Aproximadamente un orden de magnitud mayor de lo necesario para los datos del diccionario original. Una ventaja significativa del método del diccionario es el procedimiento de descompresión sencillo y rápido. No se requiere memoria adicional. Esta característica es especialmente importante si se requiere un acceso rápido a los datos.

Método de entropía (Huffman - codificación Huffman, codificación aritmética - codificación aritmética)

En este método, los elementos de datos que ocurren con más frecuencia se codifican con un código más corto durante la compresión, y los elementos de datos que son menos comunes se codifican con un código más largo. Debido al hecho de que hay muchos más códigos cortos, el tamaño total es más pequeño que el original.

Ampliamente utilizado como método adicional. Como método independiente se utiliza, por ejemplo, en formato gráfico JPG.

Método de modelado de contexto (CM - abreviatura de modelado de contexto - modelado de contexto)

En este método, se construye un modelo de los datos fuente. Al comprimir el siguiente elemento de datos, este modelo produce su predicción o probabilidad. Según esta probabilidad, el elemento de datos se codifica mediante el método de entropía. Cuanto más se ajuste el modelo a los datos de origen, más precisas serán sus predicciones y más cortos se codificarán los elementos de datos.

Construir un modelo eficiente requiere mucha memoria. Al desembalar hay que construir exactamente el mismo modelo. Por lo tanto, los requisitos de velocidad y RAM para empaquetar y desempaquetar son casi los mismos. Actualmente, los métodos de modelado de contexto proporcionan la mejor relación de compresión, pero son extremadamente lentos.

PPM (PPM - Predicción por coincidencia parcial)

Este es un subtipo especial de modelado de contexto. La predicción se realiza en base a una cierta cantidad de datos anteriores. El parámetro principal es el orden del modelo, que establece este número de elementos. Cuanto mayor sea el orden del modelo, mayor será la relación de compresión, pero se requiere más RAM para almacenar los datos del modelo. Si no hay suficiente RAM, un modelo de este tipo con un pedido grande muestra malos resultados. El método PPM es especialmente eficaz para comprimir datos de texto.

Transformaciones previas o filtrado

Estos métodos no se utilizan para comprimir, sino para presentar información en una forma conveniente para una mayor compresión. Por ejemplo, los datos multimedia sin comprimir se caracterizan por cambios suaves en el nivel de la señal. Por lo tanto, para ellos se utiliza una transformación delta, cuando se toma un valor relativo en lugar de un valor absoluto. Hay filtros para texto, archivos ejecutables, bases de datos y otros.

Método de clasificación de bloques (BWT - abreviatura de Burrows Wheeler Transform - por el nombre de los autores)

Este es un tipo o grupo especial de transformaciones basadas en la clasificación. Casi cualquier dato puede estar sujeto a esta transformación. La clasificación se realiza en bloques, por lo que los datos primero se dividen en partes. El parámetro principal es el tamaño del bloque que se está ordenando. Para descomprimir datos, debe seguir casi los mismos pasos que al empaquetar. Por tanto, los requisitos de velocidad y RAM son casi los mismos. Los archivadores que utilizan este método suelen mostrar una alta velocidad y relación de compresión para los datos de texto.

Bloques continuos o modo continuo (Modo sólido - modo continuo)

En muchos métodos de compresión, la porción inicial de los datos o del archivo está mal codificada. Por ejemplo, en el método del diccionario el diccionario está vacío. En el método de modelado de contexto, no se construye un modelo. Cuando la cantidad de archivos es grande y su tamaño es pequeño, la relación de compresión general se degrada significativamente debido a estas secciones iniciales. Para evitar que esto suceda al pasar al siguiente archivo, se utiliza la información obtenida de archivos anteriores. Se puede lograr un efecto similar simplemente presentando los archivos fuente como un archivo contiguo.

Este método se utiliza en muchos archivadores y tiene un inconveniente importante. Para descomprimir un archivo arbitrario, también debe descomprimir los archivos que se encuentran al principio del archivo. Esto es necesario para completar correctamente el diccionario o construir un modelo. También existe una opción intermedia cuando se utilizan bloques continuos de tamaño fijo. Las pérdidas de compresión son mínimas, pero para extraer un único archivo ubicado al final de un archivo grande, solo necesita descomprimir un bloque contiguo, no todo el archivo.

Segmentación

En todos los métodos de compresión, al cambiar el tipo de datos, la transición en sí se codifica muy mal. El diccionario se vuelve irrelevante, el modelo se configura para otros datos. En estos casos, se utiliza la segmentación. Se trata de un desglose preliminar en partes homogéneas. Luego, estas partes se codifican individualmente o en grupos.

Principios de compresión de información.

La base de cualquier método de compresión de información es el modelo de fuente de información o, más específicamente, el modelo de redundancia. En otras palabras, para comprimir información, se utiliza cierta información sobre qué tipo de información se está comprimiendo; sin tener ninguna información sobre la información, es imposible hacer absolutamente ninguna suposición sobre qué tipo de 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 fase 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 algoritmos no adaptativos suelen ser muy específicos y se utilizan para trabajar con características bien definidas y sin cambios. La inmensa mayoría de algoritmos bastante universales son adaptativos en un grado u otro.

Cualquier método de compresión de información incluye dos transformaciones inversas:

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

La transformación de compresión garantiza que se obtenga un mensaje comprimido del mensaje 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 permite una reconstrucción precisa del mensaje original. La compresión con pérdida le permite obtener solo una cierta aproximación del mensaje original, es decir, diferente del original, pero dentro de los límites 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 presentados son importantes para el destinatario y cuáles pueden descartarse.

Características de los algoritmos de compresión y aplicabilidad.

Relación de compresión

La relación de compresión es la característica principal del algoritmo de compresión y expresa la principal calidad 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- relación de compresión, S o es el tamaño de los datos sin comprimir, y S c - tamaño de comprimido. Por tanto, cuanto mayor sea la relación de compresión, mejor será el algoritmo. Cabe señalar:

• Si k= 1, entonces el algoritmo no realiza compresión, 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. Entonces el número de mensajes diferentes con una longitud menor o igual a norte(si hay al menos un mensaje de menor longitud) será inferior a 2 norte. Esto significa que es imposible asignar de forma única todos los mensajes originales a uno comprimido: o algunos mensajes originales no tendrán una representación comprimida, o varios mensajes originales tendrán la misma representación comprimida y, por lo tanto, no podrán distinguirse.

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

• promedio (generalmente sobre algún conjunto de datos de prueba);
• máximo (caso de mejor compresión);
• mínimo (caso de peor compresión);

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

Tolerancia de pérdidas

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

• datos simbólicos, cuyo cambio conduce inevitablemente a un cambio en su semántica: programas y sus textos fuente, matrices binarias, etc.;
• datos vitales, cuyos cambios pueden provocar errores críticos: por ejemplo, obtenidos de equipos de medición médicos o dispositivos de control de aviones, naves espaciales, etc.
• datos que se comprimen y descomprimen repetidamente: archivos gráficos de trabajo, sonido y video.

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

Requisitos del sistema de algoritmos

Diferentes algoritmos pueden requerir diferentes cantidades de recursos del sistema informático en el que se ejecutan:

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

En general, estos requisitos dependen de la complejidad e inteligencia del algoritmo. Según la tendencia general, cuanto mejor y más universal sea el algoritmo, mayores serán las exigencias que plantea a 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 consumo: cuanto menos exigente sea el algoritmo, más simple y, por lo tanto, más compacto, confiable y económico será el sistema en el que podrá trabajar.

Dado que los algoritmos de compresión y descompresión funcionan en pares, la relación entre los requisitos del sistema y ellos también es importante. A menudo, al complicar un algoritmo, se puede simplificar significativamente otro. Entonces podemos tener tres opciones:

El algoritmo de compresión requiere muchos más recursos que el algoritmo de descompresión.

Esta es la proporción más común y se aplica principalmente en los casos en que los datos una vez comprimidos se utilizarán repetidamente. Un ejemplo son los reproductores de audio y vídeo digitales.

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 es cuando la compresión y descompresión se produce una vez en sus dos extremos. Por ejemplo, esto podría ser la 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 sea 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 pueden ser datos cuya descompresión se requiera en un porcentaje muy pequeño de casos, por ejemplo, grabación de cámaras de CCTV.

Ver también Fundación Wikimedia. 2010.

Vea qué es "compresión de información" en otros diccionarios: compresión de información - compactación de información - [L.G. Diccionario inglés-ruso sobre tecnologías de la información. M.: State Enterprise TsNIIS, 2003.] Temas tecnología de la información en general Sinónimos compactación de información EN reducción de información ...

COMPRESIÓN DE INFORMACIÓN- (compresión de datos) representación de información (datos) con un número menor de bits en comparación con el original. Basado en la eliminación de redundancias. Hay S. y. sin pérdida de información y con pérdida de alguna información que no es imprescindible para las tareas a resolver. A… … - compactación de información - [L.G. Diccionario inglés-ruso sobre tecnologías de la información. M.: State Enterprise TsNIIS, 2003.] Temas tecnología de la información en general Sinónimos compactación de información EN reducción de información ...

Diccionario enciclopédico de psicología y pedagogía. compresión de información adaptativa sin pérdidas - compactación de información - [L.G. Diccionario inglés-ruso sobre tecnologías de la información. M.: State Enterprise TsNIIS, 2003.] Temas tecnología de la información en general Sinónimos compactación de información EN reducción de información ...

- - [L.G. Diccionario inglés-ruso sobre tecnologías de la información. M.: State Enterprise TsNIIS, 2003.] Temas tecnología de la información en general EN compresión de datos adaptativa sin pérdidasALDC ...

Un proceso que reduce el volumen de datos al reducir la redundancia de datos. La compresión de datos se refiere a la disposición compacta de datos de tamaño estándar. Hay compresiones con pérdida y sin pérdida de información. En inglés: Datos... ... Diccionario financiero

compresión de información cartográfica digital- Procesamiento de información cartográfica digital con el fin de reducir su volumen, incluida la eliminación de redundancias dentro de la precisión requerida de su presentación. [GOST 28441 99] Temas cartografía digital Términos generales métodos y tecnologías... ... - compactación de información - [L.G. Diccionario inglés-ruso sobre tecnologías de la información. M.: State Enterprise TsNIIS, 2003.] Temas tecnología de la información en general Sinónimos compactación de información EN reducción de información ...

Conferencia número 4. Compresión de información

Principios de compresión de información.

El propósito de la compresión de datos es proporcionar una representación compacta de los datos generados por la fuente para que puedan almacenarse y transmitirse de manera más económica a través de canales de comunicación.

Tengamos un archivo de 1 (un) megabyte de tamaño. Necesitamos obtener un archivo más pequeño. Nada complicado: iniciamos un archivador, por ejemplo WinZip, y como resultado obtenemos, digamos, un archivo de 600 kilobytes de tamaño. ¿A dónde fueron los 424 kilobytes restantes?

Comprimir información es una de las formas de codificarla. En general, los códigos se dividen en tres grandes grupos: códigos de compresión (códigos efectivos), códigos resistentes al ruido y códigos criptográficos. Los códigos destinados a la compresión de información se dividen, a su vez, en códigos sin pérdida y códigos con pérdida. La codificación sin pérdidas implica una recuperación de datos absolutamente precisa después de la decodificación y puede usarse para comprimir cualquier información. La codificación con pérdida suele tener una relación de compresión mucho mayor que la codificación sin pérdida, pero permite cierta desviación de los datos decodificados del original.

Tipos de compresión

Todos los métodos de compresión de información se pueden dividir en dos grandes clases que no se superponen: compresión con pérdida información y compresión sin perdida información.

Compresión sin pérdida de información.

Estamos interesados ​​principalmente en estos métodos de compresión porque se utilizan al transferir documentos y programas de texto, al entregar el trabajo completo a un cliente o al crear copias de seguridad de la información almacenada en una computadora.

Los métodos de compresión de esta clase no pueden permitir la pérdida de información, por lo que se basan únicamente en eliminar su redundancia, y la información casi siempre tiene redundancia (aunque, a menos que alguien ya la haya comprimido antes). Si no hubiera redundancia, no habría nada que comprimir.

He aquí un ejemplo sencillo. El idioma ruso tiene 33 letras, diez números y aproximadamente una docena de signos de puntuación y otros caracteres especiales. Para el texto que está escrito sólo en letras rusas mayúsculas(como en los telegramas y radiogramas) sesenta significados diferentes serían suficientes. Sin embargo, cada carácter suele estar codificado por un byte, que contiene 8 bits y puede expresar 256 códigos diferentes. Ésta es la primera razón del despido. Para nuestro texto “telégrafo”, seis bits por carácter serían suficientes.

Aquí hay otro ejemplo. En codificación de caracteres internacional ASCII Se asigna el mismo número de bits (8) para codificar cualquier carácter, mientras que todo el mundo sabe desde hace mucho tiempo que tiene sentido codificar los caracteres que aparecen con más frecuencia con menos caracteres. Así, por ejemplo, en código Morse, las letras “E” y “T”, que aparecen con frecuencia, están codificadas con un carácter (un punto y un guión, respectivamente). Y letras tan raras como “Yu” (- -) y “C” (- -) están codificadas con cuatro caracteres. La codificación ineficiente es la segunda razón de la redundancia. Los programas que realizan la compresión de información pueden ingresar su propia codificación (diferente para diferentes archivos) y adjuntar una determinada tabla (diccionario) al archivo comprimido, a partir de la cual el programa de descompresión aprende cómo ciertos caracteres o sus grupos están codificados en este archivo. Los algoritmos basados ​​en la recodificación de información se denominan Algoritmos de Huffman.

La presencia de fragmentos repetidos es la tercera base de redundancia. Esto es poco común en los textos, pero en tablas y gráficos la repetición de códigos es común. Entonces, por ejemplo, si el número 0 se repite veinte veces seguidas, entonces no tiene sentido poner veinte bytes cero. En su lugar, pusieron un cero y un coeficiente de 20. Estos algoritmos basados ​​​​en la identificación de repeticiones se denominan metodosRLE (Correr Longitud Codificación).

Las ilustraciones gráficas se distinguen especialmente por grandes secuencias repetidas de bytes idénticos, pero no fotográficas (hay mucho ruido y los puntos vecinos difieren significativamente en los parámetros), sino aquellas que los artistas dibujan en colores "suaves", como en las películas animadas.

Compresión con pérdida de información.

La compresión con pérdida significa que después de descomprimir el archivo comprimido terminaremos con un documento ligeramente diferente al que teníamos al principio. Está claro que cuanto mayor sea la relación de compresión, mayor será la pérdida y viceversa.

Por supuesto, estos algoritmos no son aplicables a documentos de texto, tablas de bases de datos y, especialmente, a programas. Aún así es posible sobrevivir a distorsiones menores en texto simple sin formato, pero la distorsión de incluso un bit en el programa lo hará completamente inoperable.

Al mismo tiempo, hay materiales en los que vale la pena sacrificar un pequeño porcentaje de la información para obtener una compresión diez veces mayor. Estos incluyen ilustraciones fotográficas, vídeos y composiciones musicales. La pérdida de información durante la compresión y posterior descompresión de dichos materiales se percibe como la aparición de algún "ruido" adicional. Pero como todavía hay un cierto "ruido" al crear estos materiales, su ligero aumento no siempre parece crítico, y el aumento en el tamaño de los archivos es enorme (de 10 a 15 veces para música, de 20 a 30 veces para materiales de fotografía y video). .

Los algoritmos de compresión con pérdida incluyen algoritmos tan conocidos como JPEG y MPEG. El algoritmo JPEG se utiliza para comprimir imágenes fotográficas. Los archivos gráficos comprimidos con este método tienen una extensión JPG. Los algoritmos MPEG se utilizan para comprimir vídeos y música. Estos archivos pueden tener diferentes extensiones, dependiendo del programa específico, pero las más conocidas son .MPG para vídeo y .MPG para música.

Los algoritmos de compresión con pérdida se utilizan únicamente para tareas de consumo. Esto significa, por ejemplo, que si se transmite una fotografía para verla y música para reproducirla, se pueden utilizar algoritmos similares. Si se transfieren para su posterior procesamiento, por ejemplo para edición, no se aceptará ninguna pérdida de información en el material original.

Generalmente se puede controlar la cantidad de pérdida de compresión aceptable. Esto le permite experimentar y lograr la relación óptima tamaño/calidad. En las ilustraciones fotográficas destinadas a ser reproducidas en pantalla, la pérdida del 5% de la información no suele ser crítica y, en algunos casos, se puede tolerar entre el 20 y el 25%.

Algoritmos de compresión sin pérdida de información.

Código Shannon-Fano

Para una mayor discusión, será conveniente imaginar nuestro archivo de texto fuente como una fuente de caracteres que aparecen uno a la vez en su salida. No sabemos de antemano qué personaje será el siguiente, pero sabemos que con probabilidad p1 aparecerá la letra "a", con probabilidad p2 - la letra "b", etc.

En el caso más simple, consideraremos todos los caracteres del texto independientes entre sí, es decir. la probabilidad de que aparezca el siguiente símbolo no depende del valor del símbolo anterior. Por supuesto, esto no es cierto para un texto significativo, pero ahora estamos considerando una situación muy simplificada. En este caso, la afirmación “un símbolo contiene más información cuanto menor es la probabilidad de su aparición” es cierta.

Imaginemos un texto cuyo alfabeto consta de sólo 16 letras: A, B, C, D, D, E, F, Z, I, K, L, M, N, O, P, R. Cada uno de estos caracteres puede ser codificar con tan solo 4 bits: de 0000 a 1111. Ahora imagina que las probabilidades de aparición de estos caracteres se distribuyen de la siguiente manera:

La suma de estas probabilidades es, naturalmente, la unidad. Dividamos estos símbolos en dos grupos de modo que la probabilidad total de que haya símbolos en cada grupo sea ~0,5 (Figura). En nuestro ejemplo, estos serán los grupos de símbolos A-B y G-R. Los círculos en la figura que denotan grupos de caracteres se llaman vértices o nodos, y la estructura de estos nodos en sí se llama árbol binario (árbol B). Asignemos a cada nodo su propio código, designando un nodo con el número 0 y el otro con el número 1.

Dividamos nuevamente el primer grupo (A-B) en dos subgrupos para que sus probabilidades totales estén lo más cerca posible entre sí. Agreguemos el número 0 al código del primer subgrupo y el número 1 al código del segundo.

Repetiremos esta operación hasta que quede un símbolo en cada vértice de nuestro “árbol”. El árbol completo de nuestro alfabeto tendrá 31 nodos.

Los códigos de caracteres (los nodos más a la derecha del árbol) tienen códigos de longitud desigual. Así, la letra A, que tiene una probabilidad de p=0,2 para nuestro texto imaginario, está codificada con sólo dos bits, y la letra P (no mostrada en la figura), que tiene una probabilidad de p=0,013, está codificada con hasta una combinación de seis bits.

Entonces, el principio es obvio: los caracteres que aparecen con frecuencia se codifican con un número menor de bits y los que aparecen con poca frecuencia, con un número mayor. Como resultado, el número promedio de bits por símbolo será igual a

donde ni es el número de bits que codifican el i-ésimo carácter, pi es la probabilidad de que aparezca el i-ésimo carácter.

Código Huffman.

El algoritmo de Huffman implementa elegantemente la idea general de codificación estadística utilizando conjuntos de prefijos y funciona de la siguiente manera:

1. Anotamos todos los caracteres del alfabeto seguidos en orden de probabilidad creciente o decreciente de su aparición en el texto.

2. Combinamos secuencialmente dos símbolos con las probabilidades más bajas de aparición en un nuevo símbolo compuesto, cuya probabilidad suponemos es igual a la suma de las probabilidades de sus símbolos constituyentes. Al final, construiremos un árbol, cada nodo del cual tiene la probabilidad total de todos los nodos debajo de él.

3. Trazamos el camino hasta cada hoja del árbol, marcando la dirección a cada nodo (por ejemplo, a la derecha - 1, a la izquierda - 0). La secuencia resultante proporciona una palabra clave correspondiente a cada símbolo (Fig.).

Construyamos un árbol de códigos para un mensaje con el siguiente alfabeto:

Desventajas de los métodos.

El mayor desafío con los códigos, como sugiere la discusión anterior, es la necesidad de tener tablas de probabilidad para cada tipo de datos que se comprimen. Esto no es un problema si sabes que estás comprimiendo texto en inglés o ruso; simplemente proporcionamos al codificador y decodificador un árbol de códigos adecuado para el texto en inglés o ruso. En general, cuando se desconoce la probabilidad de los símbolos para los datos de entrada, los códigos estáticos de Huffman funcionan de manera ineficiente.

La solución a este problema es un análisis estadístico de los datos codificados, realizado durante el primer paso por los datos, y compilando un árbol de código basado en ellos. La codificación real se realiza en la segunda pasada.

Otra desventaja de los códigos es que la longitud mínima de la palabra clave para ellos no puede ser inferior a uno, mientras que la entropía del mensaje puede ser de 0,1 o 0,01 bits/letra. En este caso, el código se vuelve significativamente redundante. El problema se resuelve aplicando el algoritmo a bloques de caracteres, pero luego el procedimiento de codificación/decodificación se vuelve más complicado y el árbol de códigos se expande significativamente, que finalmente debe guardarse junto con el código.

Estos códigos no tienen en cuenta las relaciones entre personajes, que están presentes en casi cualquier texto. Por ejemplo, si encontramos la letra q en un texto en inglés, podemos decir con seguridad que la letra u vendrá después.

La codificación de longitud de ejecución (RLE) es uno de los algoritmos de archivo más antiguos y simples. La compresión en RLE se produce reemplazando cadenas de bytes idénticos con pares de "contador, valor". (“rojo, rojo,..., rojo” se escribe “N rojos”).

Una de las implementaciones del algoritmo es la siguiente: buscan el byte que ocurre con menos frecuencia, lo llaman prefijo y reemplazan cadenas de caracteres idénticos con tripletas "prefijo, contador, valor". Si este byte aparece en el archivo fuente una o dos veces seguidas, se reemplaza con el par "prefijo, 1" o "prefijo, 2". Queda un par de "prefijo, 0" sin usar, que puede usarse para indicar el final de los datos empaquetados.

Al codificar archivos exe, puede buscar y empaquetar secuencias como AxAyAzAwAt..., que a menudo se encuentran en recursos (cadenas Unicode)

Los aspectos positivos del algoritmo incluyen el hecho de que no requiere memoria adicional durante el funcionamiento y se ejecuta rápidamente. El algoritmo se utiliza en formatos PCX, TIFF, BMP. Una característica interesante de la codificación por lotes PCX es que el grado de archivo de algunas imágenes se puede mejorar significativamente simplemente cambiando el orden de los colores en la paleta de imágenes.

El código LZW (Lempel-Ziv & Welch) es uno de los códigos de compresión sin pérdidas más comunes en la actualidad. Es con la ayuda del código LZW que se realiza la compresión en formatos gráficos como TIFF y GIF; con la ayuda de modificaciones LZW, muchos archivadores universales realizan sus funciones; El funcionamiento del algoritmo se basa en buscar en el archivo de entrada secuencias repetidas de caracteres que están codificados en combinaciones de 8 a 12 bits de longitud. Por lo tanto, este algoritmo es más eficaz en archivos de texto y archivos gráficos que contienen grandes áreas de un solo color o secuencias repetidas de píxeles.

La ausencia de pérdida de información durante la codificación LZW ha llevado al uso generalizado del formato TIFF basado en ella. Este formato no impone ninguna restricción en cuanto al tamaño y la profundidad del color de la imagen y se utiliza ampliamente, por ejemplo, en la impresión. Otro formato basado en LZW, GIF, es más primitivo: permite almacenar imágenes con una profundidad de color de no más de 8 bits/píxel. Al principio del archivo GIF hay una paleta, una tabla que establece una correspondencia entre el índice de color, un número en el rango de 0 a 255, y el valor de color verdadero de 24 bits.

Algoritmos de compresión con pérdida

El algoritmo JPEG fue desarrollado por un grupo de empresas llamado Joint Photographic Experts Group. El objetivo del proyecto era crear un estándar de compresión altamente eficiente para imágenes en blanco y negro y en color, y los desarrolladores lograron este objetivo. Actualmente, JPEG se utiliza ampliamente cuando se requiere un alto grado de compresión, por ejemplo, en Internet.

A diferencia del algoritmo LZW, la codificación JPEG es una codificación con pérdida. El algoritmo de codificación en sí se basa en matemáticas muy complejas, pero en términos generales se puede describir de la siguiente manera: la imagen se divide en cuadrados de 8 * 8 píxeles y luego cada cuadrado se convierte en una cadena secuencial de 64 píxeles. A continuación, cada una de estas cadenas se somete a la denominada transformada DCT, que es una de las variedades de la transformada discreta de Fourier. Se basa en el hecho de que la secuencia de entrada de píxeles se puede representar como una suma de componentes sinusoidales y cosenos con múltiples frecuencias (los llamados armónicos). En este caso, sólo necesitamos conocer las amplitudes de estos componentes para poder reconstruir la secuencia de entrada con un grado suficiente de precisión. Cuantas más componentes armónicas conozcamos, menor será la discrepancia entre la imagen original y la comprimida. La mayoría de los codificadores JPEG le permiten ajustar el nivel de compresión. Esto se consigue de una forma muy sencilla: cuanto mayor sea el ratio de compresión, menos armónicos estarán representados por cada bloque de 64 píxeles.

Por supuesto, el punto fuerte de este tipo de codificación es la alta relación de compresión manteniendo al mismo tiempo la profundidad del color original. Es esta propiedad la que ha llevado a su uso generalizado en Internet, donde reducir el tamaño del archivo es de suma importancia, en enciclopedias multimedia, donde se requiere almacenar tantos gráficos como sea posible en un espacio limitado.

Una propiedad negativa de este formato es el deterioro inherente de la calidad de la imagen que no se puede eliminar de ninguna manera. Es este triste hecho el que no permite su uso en la impresión, donde la calidad es lo más importante.

Sin embargo, el formato JPEG no es el límite de la perfección en la búsqueda de reducir el tamaño del archivo final. Recientemente, se han llevado a cabo intensas investigaciones en el campo de la llamada transformada wavelet (o transformada wavelet). Los codificadores Wavelet, basados ​​en sofisticados principios matemáticos, permiten una mayor compresión que JPEG con menos pérdida de información. A pesar de la complejidad de las matemáticas de la transformada wavelet, su implementación de software es más simple que JPEG. Aunque los algoritmos de compresión wavelet aún se encuentran en sus primeras etapas de desarrollo, tienen un gran futuro por delante.

Compresión fractal

La compresión de imágenes fractales es un algoritmo de compresión de imágenes con pérdida basado en la aplicación de sistemas de funciones iterables (IFS, que normalmente son transformaciones afines) a las imágenes. Este algoritmo es conocido por el hecho de que en algunos casos permite obtener relaciones de compresión muy altas (los mejores ejemplos son hasta 1000 veces con una calidad visual aceptable) para fotografías reales de objetos naturales, lo cual es inaccesible a otros algoritmos de compresión de imágenes en principio. Debido a la difícil situación con las patentes, el algoritmo no se utilizó ampliamente.

El archivo fractal se basa en el hecho de que utilizando los coeficientes de un sistema de funciones iteradas, la imagen se presenta en una forma más compacta. Antes de analizar el proceso de archivado, veamos cómo IFS crea una imagen.

Estrictamente hablando, IFS es un conjunto de transformaciones afines 3D que transforman una imagen en otra. Los puntos en el espacio tridimensional (coordenada x, coordenada y, brillo) sufren transformación.

La base del método de codificación fractal es la detección de áreas autosemejantes en la imagen. La posibilidad de aplicar la teoría de sistemas de funciones iteradas (IFS) al problema de la compresión de imágenes fue explorada por primera vez por Michael Barnsley y Alan Sloan. Patentaron su idea en 1990 y 1991. Jacquin presentó un método de codificación fractal que utiliza sistemas de bloques de subimagen de dominio y rango, bloques de forma cuadrada que cubren toda la imagen. Este enfoque se convirtió en la base de la mayoría de los métodos de codificación fractal que se utilizan en la actualidad. Fue mejorado por Yuval Fisher y varios otros investigadores.

De acuerdo con este método, la imagen se divide en un conjunto de subimágenes de rango no superpuestas y se determina un conjunto de subimágenes de dominio superpuestas. Para cada bloque de clasificación, el algoritmo de codificación encuentra el bloque de dominio más adecuado y una transformación afín que traduce este bloque de dominio en un bloque de clasificación determinado. La estructura de la imagen se mapea en un sistema de bloques de clasificación, bloques de dominio y transformaciones.

La idea es la siguiente: supongamos que la imagen original es un punto fijo de algún mapeo de compresión. Luego, en lugar de la imagen en sí, de alguna manera puede recordar este mapeo y, para restaurarlo, basta con aplicar este mapeo repetidamente a cualquier imagen inicial.

Según el teorema de Banach, tales iteraciones siempre conducen a un punto fijo, es decir, a la imagen original. En la práctica, toda la dificultad radica en encontrar el mapeo de compresión más adecuado a partir de la imagen y almacenarlo de forma compacta. Normalmente, los algoritmos de búsqueda de mapeo (es decir, algoritmos de compresión) son de fuerza bruta y costosos desde el punto de vista computacional. Al mismo tiempo, los algoritmos de recuperación son bastante efectivos y rápidos.

Brevemente, el método propuesto por Barnsley se puede describir de la siguiente manera. La imagen está codificada mediante varias transformaciones simples (en nuestro caso, afines), es decir, está determinada por los coeficientes de estas transformaciones (en nuestro caso, A, B, C, D, E, F).

Por ejemplo, la imagen de la curva de Koch se puede codificar con cuatro transformaciones afines; la definiremos de forma única utilizando solo 24 coeficientes.

Como resultado, el punto definitivamente irá a algún lugar dentro del área negra de la imagen original. Habiendo realizado esta operación muchas veces, llenaremos todo el espacio negro, restaurando así la imagen.

Las dos imágenes más famosas obtenidas con IFS son el triángulo de Sierpinski y el helecho de Barnsley. La primera está dada por tres y la segunda por cinco transformaciones afines (o, en nuestra terminología, lentes). Cada transformación se especifica literalmente en unos pocos bytes, mientras que la imagen construida con su ayuda puede ocupar varios megabytes.

Queda claro cómo funciona el archivador y por qué lleva tanto tiempo. De hecho, la compresión fractal es la búsqueda de áreas autosemejantes en una imagen y la determinación de parámetros de transformación afines para ellas.

En el peor de los casos, si no se aplica un algoritmo de optimización, será necesario enumerar y comparar todos los posibles fragmentos de imagen de diferentes tamaños. Incluso para imágenes pequeñas, teniendo en cuenta la discreción, tenemos una cantidad astronómica de opciones para seleccionar. Incluso reducir drásticamente las clases de transformaciones, por ejemplo, escalando solo un cierto número de veces, no permitirá alcanzar un tiempo aceptable. Además, se pierde calidad de imagen. La gran mayoría de las investigaciones en el campo de la compresión fractal tienen como objetivo reducir el tiempo de archivo necesario para obtener una imagen de alta calidad.

Para el algoritmo de compresión fractal, al igual que para otros algoritmos de compresión con pérdida, los mecanismos mediante los cuales se pueden ajustar el grado de compresión y el grado de pérdida son muy importantes. Hasta la fecha, se ha desarrollado un conjunto bastante grande de estos métodos. En primer lugar, puede limitar el número de transformaciones, asegurándose conscientemente de que la relación de compresión no sea inferior a un valor fijo. En segundo lugar, se puede exigir que en una situación en la que la diferencia entre el fragmento procesado y su mejor aproximación esté por encima de un cierto valor umbral, este fragmento deba triturarse (se deben instalar varias lentes para ello). En tercer lugar, se puede prohibir la división de fragmentos de menos de, digamos, cuatro puntos. Al cambiar los valores de umbral y la prioridad de estas condiciones, puede controlar de manera muy flexible la relación de compresión de la imagen: desde la coincidencia bit a bit hasta cualquier nivel de compresión.

Comparación con JPEG

Hoy en día, el algoritmo de archivo de gráficos más común es JPEG. Comparémoslo con la compresión fractal.

Primero, tenga en cuenta que ambos algoritmos operan en imágenes a todo color de 8 bits (escala de grises) y 24 bits. Ambos son algoritmos de compresión con pérdida y proporcionan velocidades de archivo similares. Tanto el algoritmo fractal como JPEG tienen la capacidad de aumentar la relación de compresión aumentando las pérdidas. Además, ambos algoritmos están muy bien paralelizados.

Las diferencias comienzan cuando consideramos el tiempo que tardan los algoritmos en archivar/desarchivar. Por lo tanto, el algoritmo fractal comprime cientos e incluso miles de veces más que JPEG. Por el contrario, desempacar una imagen se realizará entre 5 y 10 veces más rápido. Por lo tanto, si la imagen se comprime solo una vez, pero se transmite a través de la red y se descomprime muchas veces, entonces es más rentable utilizar un algoritmo fractal.

JPEG utiliza la descomposición de la imagen en función del coseno, por lo que las pérdidas en ella (incluso con pérdidas mínimas especificadas) aparecen en ondas y halos en el borde de las transiciones de color nítidas. Precisamente por este efecto a la gente no le gusta utilizarlo al comprimir imágenes preparadas para impresión de alta calidad: allí este efecto puede resultar muy notorio.

El algoritmo fractal está libre de este inconveniente. Además, al imprimir una imagen, es necesario realizar una operación de escala cada vez, ya que la trama (o línea) del dispositivo de impresión no coincide con la trama de la imagen. Durante la conversión también pueden surgir varios efectos desagradables, que pueden combatirse escalando la imagen mediante programación (para dispositivos de impresión baratos, como impresoras láser y de inyección de tinta convencionales), o equipando el dispositivo de impresión con su propio procesador, disco duro y un conjunto. de programas de procesamiento de imágenes (para costosas máquinas de fotocomposición). Como se puede imaginar, cuando se utiliza un algoritmo fractal, estos problemas prácticamente no surgen.

La sustitución de JPEG por el algoritmo fractal de uso generalizado no se producirá pronto (al menos debido a la baja velocidad de archivo de este último), sin embargo, en el campo de las aplicaciones multimedia, en los juegos de ordenador, su uso está bastante justificado.

Un rasgo característico de la mayoría de los tipos de datos es su redundancia. El grado de redundancia de datos depende del tipo de datos.
Por ejemplo, para los datos de vídeo el grado de redundancia es varias veces mayor que para los datos gráficos y el grado de redundancia de los datos gráficos, a su vez, es mayor que el grado de redundancia de los datos de texto.

Otro factor El sistema de codificación adoptado influye en el grado de redundancia. Un ejemplo de sistemas de codificación serían los lenguajes de comunicación ordinarios, que no son más que sistemas de codificación de conceptos e ideas para expresar pensamientos. Por lo tanto, se ha establecido que codificar datos de texto en ruso proporciona, en promedio, entre un 20 y un 25% más de redundancia que codificar datos similares en inglés.

para el hombre redundancia datos a menudo atado Con calidad información, ya que la redundancia tiende a mejorar la comprensibilidad y percepción de la información. Sin embargo, cuando se trata de almacenar y transmitir información utilizando tecnología informática, Eso La redundancia juega un papel negativo., ya que conlleva un aumento en el costo de almacenar y transmitir información. Este problema adquiere especial relevancia en el caso de procesar grandes volúmenes de información con cantidades insignificantes de medios de almacenamiento. En este sentido, surge constantemente el problema de reducir la redundancia o la compresión de datos.

Si Los métodos de compresión de datos se aplican a archivos terminados., entonces a menudo se utiliza el término "archivo de datos" en lugar del término "compresión de datos", comprimido la versión de los datos se llama archivo, y software, que implementan métodos de compresión se denominan archivadores.

Dependiendo del objeto en el que se encuentren los datos a comprimir, existen:

· Compresión (archivo) de archivos: se utiliza para reducir el tamaño de los archivos al prepararlos para su transmisión a través de canales de comunicación o para su transporte en medios externos de pequeña capacidad;

· Compresión (archivo) de carpetas: se utiliza como medio para reducir el volumen de carpetas antes del almacenamiento a largo plazo, por ejemplo, durante la copia de seguridad;

· Compresión (compactación) de discos: se utiliza para aumentar la eficiencia en el uso del espacio en disco comprimiendo datos al escribirlos en un medio de almacenamiento (generalmente usando el sistema operativo).

Hay muchas prácticas algoritmos compresión de datos, pero todos se basan en tres Formas teóricas de reducir la redundancia de datos.

El primer método es cambiar contenido de datos,

· segundo - en cambio estructuras datos,

· tercero - en cambio simultáneo tanto la estructura como el contenido de los datos.

Si se produce compresión de datos cambiar su contenido, entonces método de compresión llamado irreversible, es decir, al restaurar (desarchivar) datos de un archivo, la información no se restaura por completo. Estos métodos suelen denominarse métodos de compresión con pérdidas de información controladas. Está claro que estos métodos sólo pueden utilizarse para tipos de datos para los cuales la pérdida de parte del contenido no da lugar a una distorsión significativa de la información. Estos tipos de datos incluyen datos de vídeo, audio y gráficos. Los métodos de compresión con pérdida controlada proporcionan una relación de compresión significativamente mayor, pero su esta prohibido referirse a datos de texto. Ejemplos de formatos de compresión con pérdida incluyen:

· JPEG - para datos gráficos;

· MPG - para datos de vídeo;

· MP3 - para datos de audio.

Si la compresión de datos solo ocurre cambio de estructura datos,
Eso método de compresión llamado reversible. En este caso, es posible restaurar la información completamente desde el archivo. Los métodos de compresión reversibles se pueden aplicar a cualquier tipo de datos, pero dan menos relación de compresión en comparación con los métodos de compresión irreversibles. Ejemplos de formatos de compresión sin pérdidas:

· GIF, TIFF - para datos gráficos;

· AVI - para datos de vídeo;

· ZIP, ARJ, RAR, CAB, LH - para tipos de datos arbitrarios.

hay muchos varios métodos prácticos de compresión sin pérdida de información, que tienden a tener diferente efectividad para diferentes tipos de datos y diferentes volúmenes. Sin embargo, estos métodos se basan en tres algoritmos teóricos:

· Algoritmo RLE (codificación de longitud de ejecución);

· algoritmos del grupo KWE (KeyWord Encoding);

· Algoritmo de Huffman.

algoritmo RLE

El algoritmo RLE se basa en la idea de identificar secuencias de datos repetidas y reemplazarlas con una estructura más simple que especifica el código de datos y el factor de repetición. Por ejemplo, supongamos la siguiente secuencia de datos que están sujetos a compresión:

1 1 1 1 2 2 3 4 4 4

El algoritmo RLE propone reemplazarlo por la siguiente estructura: 1 4 2 2 3 1 4 3, donde el primer número de cada par de números es el código de datos y el segundo es el factor de repetición. Si se asigna 1 byte para almacenar cada elemento de datos de la secuencia de entrada, entonces la secuencia completa ocupará 10 bytes de memoria, mientras que la secuencia de salida (versión comprimida) ocupará 8 bytes de memoria. Relación de compresión, que caracteriza el grado de compresión, se calcula mediante la fórmula.

Cómo menos el valor de la relación de compresión, el más eficiente método de compresión. Está claro que el algoritmo RLE dará un mejor efecto de compresión cuando la secuencia de datos repetida sea más larga. En el caso del ejemplo discutido anteriormente, si la secuencia de entrada se ve así: 1 1 1 1 1 1 3 4 4 4, entonces la relación de compresión será del 60%. En este sentido, se logra una mayor eficiencia del algoritmo RLE al comprimir datos gráficos (especialmente para imágenes monocromáticas).

Algoritmos del grupo KWE.

El algoritmo de compresión de palabras clave se basa en el principio de codificar unidades léxicas en grupos de bytes de longitud fija. Un ejemplo de elemento léxico sería una palabra ordinaria. En la práctica, se eligen secuencias repetidas de símbolos para que desempeñen el papel de unidades léxicas y se codifican mediante una cadena de símbolos (código) de menor longitud. El resultado de la codificación se coloca en una tabla, formando el llamado diccionario.

Existen bastantes implementaciones de este algoritmo, entre las cuales las más comunes son el algoritmo Lempel-Ziv (algoritmo LZ) y su modificación, el algoritmo Lempel-Ziv-Welch (algoritmo LZW). El diccionario de este algoritmo es una lista potencialmente infinita de frases. El algoritmo comienza con un diccionario casi vacío que contiene sólo una cadena codificada, la llamada cadena NULL. Al leer el siguiente carácter de la secuencia de datos de entrada, se agrega a la línea actual. El proceso continúa mientras la línea actual coincida con alguna frase del diccionario. Pero tarde o temprano la línea actual deja de corresponder a alguna frase del diccionario. En el punto donde la línea actual representa la última coincidencia del diccionario más el carácter del mensaje recién leído, el codificador produce un código que consta del índice de la coincidencia y el siguiente carácter que rompió la línea coincidente. Se agrega al diccionario una nueva frase, que consta del índice de coincidencia y el siguiente carácter. La próxima vez que esta frase aparezca en un mensaje, se puede utilizar para construir una frase más larga, lo que aumenta el grado de compresión de la información.

El algoritmo LZW se basa en una tabla de frases (diccionario) que reemplaza las cadenas de caracteres del mensaje comprimido en códigos de longitud fija. La tabla tiene la llamada propiedad de avance, es decir, para cada frase del diccionario que consta de una determinada frase w y el símbolo K, la frase w también se ingresa en el diccionario. Si todas las partes del diccionario están completamente completadas, la codificación deja de ser adaptativa (la codificación se basa en frases que ya existen en el diccionario).

Los algoritmos de compresión de este grupo son los más eficaz Para texto grandes volúmenes de datos y son ineficaces para archivos pequeños (debido a la necesidad de guardar el diccionario).

Algoritmo de Huffman

El algoritmo de Huffman se basa en la idea de codificación de grupos de bits. En primer lugar, se realiza un análisis de frecuencia de la secuencia de datos de entrada, es decir, se establece la frecuencia de aparición de cada carácter que se encuentra en la misma. Después de esto, los símbolos se ordenan según la frecuencia de aparición decreciente.

Principal idea es el siguiente: cuanto más a menudo aparece un símbolo, menos bits está codificado. El resultado de la codificación se ingresa en el diccionario requerido para la decodificación.