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 compresión de información pueden ingresar su propia codificación (diferente para diferentes archivos) y asignar una determinada tabla (diccionario) al archivo comprimido, a partir de la cual el programa de descompresión aprende cómo Este archivo ciertos caracteres o sus grupos están codificados. 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 métodosRLE (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, recibiremos 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 decenas de veces. 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 grupos. personajes 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 solo 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 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 de 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 una palabra de código no puede ser inferior a uno, mientras que la entropía de un 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 en el texto de idioma en Inglés Si nos encontramos con la letra q, entonces 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 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 la mayor cantidad posible de gráficos en un volumen 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 de suma importancia.

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. EN Últimamente Se están realizando intensas investigaciones en el campo de la llamada transformada wavelet (o transformada wavelet). Basados ​​en principios matemáticos sofisticados, los codificadores wavelet proporcionan 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 sencilla que JPEG. Aunque los algoritmos de compresión wavelet todavía están en etapa inicial 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 utilizados 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 (subimágenes de rango) 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 utiliza ningún algoritmo de optimización, será necesario enumerar y comparar todos los fragmentos de imágenes posibles 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 debe ser triturado (para ello se deben instalar varias lentes). 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 (aunque sólo sea debido a la baja velocidad de archivo de este último), pero en el campo de las aplicaciones multimedia, en juegos de computadora su uso está completamente justificado.

ARCHIVADORES

Compresión de información es el proceso de transformar la información almacenada en un archivo reduciendo la redundancia de datos. La finalidad de este proceso es reducir el volumen ocupado por los datos.

Archivo de archivo es un archivo especialmente creado que contiene uno o más archivos en forma comprimida.

Índice de compresión: Kc =Vc /Vo *100%

kc- índice de compresión, vc– volumen del archivo comprimido, vo– tamaño del archivo inicial.

La relación de compresión depende de:

1) el programa utilizado - archivador,

2) método de compresión,

3) tipo de archivo fuente: texto, gráfico, vídeo, sonido, etc.

Los programas que empaquetan y descomprimen archivos se llaman archivadores. Los más comunes son: ARJ, ZIP, RAR. La extensión de los archivos comprimidos coincide con el nombre del archivador utilizado para crearlos.

Los archivadores le permiten crear archivos de almacenamiento autoextraíbles, es decir. Para descomprimirlos, no es necesario iniciar el programa de archivado, porque ellos mismos contienen un programa de desembalaje. Estos archivos se llaman archivos SFX.
(Autoextraíble). La extensión de dichos archivos es *.EXE.

Principios de compresión de información.

Hay caracteres repetidos en cualquier texto. Es posible especificar un carácter y el número de repeticiones. La eficiencia de este algoritmo es aún mayor cuando se aplica a archivos gráficos. Si miras el monitor, puedes ver muchos puntos repetidos del mismo color. El formato de archivo gráfico PCX se basa en este principio de compresión de información. Los archivadores modernos resaltan no solo caracteres repetidos, sino también cadenas de caracteres y palabras individuales.

Si el texto no utiliza todos los caracteres del alfabeto de la PC, para codificarlos puede utilizar un byte, 8 bits o un número menor. Este principio se utiliza en los aparatos de telégrafo, donde sólo se utilizan letras mayúsculas rusas; para representarlas bastan 5 bits, lo que permite escribir tres caracteres en dos bytes.

3. El siguiente principio utiliza el patrón de que las letras aparecen en el texto con diferentes frecuencias. Por ejemplo, en este texto el espacio es el carácter más común; los símbolos “a” y “y” son muy comunes. Estos caracteres que aparecen con frecuencia se pueden representar como una secuencia corta de bits, mientras que otros caracteres se pueden codificar como una secuencia más larga. Por ejemplo:

4. Físicamente, la PC asigna espacio para colocar archivos en el disco en grupos, en bloques de 4 kB. Es imposible destacar menos. Por ejemplo, si un archivo tiene un tamaño de 8193 bytes (8 kB y 1 byte), ocupará físicamente 16 kB o 16384 bytes. Combinar un grupo de archivos en uno le permite ahorrar estos restos. Esto proporciona grandes ahorros al empaquetar archivos pequeños.

En total, al colocar archivos por separado, no se utilizan 6 kB, que es el 100% del contenido de los archivos. En el segundo caso, quedan 2 kB, el 33%, sin utilizar.

zip del archivador

Empacar archivos pkzip [claves]<имя архива>[rutas de archivos]

Llaves: -rp Archivar con subdirectorios manteniendo la estructura.

S PWD protección de contraseña de archivo (PWD)

A agregar archivos para archivar

M mover archivos para archivar

V ver el contenido del archivo

Si se están archivando todos los archivos en un directorio, entonces es necesario especificar la máscara *.*

Descomprimiendo archivos pkunzip [interruptores]<имя архива>[nombres de archivos]

Claves: -d descomprimir con subdirectorios preservando la estructura

Contraseña de archivo SPWD (PWD)

Archivador arj

arj<команда>[llaves]<имя архива>[nombres de archivos]

Para el archivador arj, un archivo realiza operaciones de descompresión y empaquetado.

Equipos: a archivar

e descomprimir sin preservar la estructura del directorio

X desembalaje preservando la estructura

l ver el contenido del archivo

m mover archivos para archivar

d eliminar archivos del archivo

Claves: -r empaquetar con subdirectorios preservando la estructura

V desglose del archivo en volúmenes con un volumen de vol (si se especifica)

el tamaño de los disquetes estándar (360, 720, 1200, 1440) se indica en kilobytes, el tamaño de los disquetes no estándar se indica en bytes

V se indica al descomprimir un archivo de varios volúmenes

GRAMO PWD contraseña de archivo ( PWD)

Empacar archivos

Descomprimir archivos

©2015-2019 sitio
Todos los derechos pertenecen a sus autores. Este sitio no reclama autoría, pero proporciona uso gratuito.
Fecha de creación de la página: 2016-08-08

GORKOFF 24 de febrero de 2015 a las 11:41

Métodos de compresión de datos.

• Algoritmos

Mi supervisor y yo estamos preparando una pequeña monografía sobre procesamiento de imágenes. Decidí presentar a la comunidad habra un capítulo dedicado a los algoritmos de compresión de imágenes. Como es difícil incluir un capítulo completo en una sola publicación, decidí dividirlo en tres publicaciones:
1. Métodos de compresión de datos;
2. Compresión de imágenes sin pérdidas;
3. Compresión de imágenes con pérdida.
A continuación puedes leer el primer post de la serie.

Actualmente, existe una gran cantidad de algoritmos de compresión sin pérdidas, que se pueden dividir en dos grandes grupos:
1. Algoritmos de flujo y diccionario. Este grupo incluye algoritmos de las familias RLE (codificación de longitud de ejecución), LZ*, etc.. Una característica de todos los algoritmos de este grupo es que la codificación no utiliza información sobre las frecuencias de los símbolos en el mensaje, sino información sobre las secuencias encontradas. previamente.
2. Algoritmos de compresión estadística (entropía). Este grupo de algoritmos comprime la información aprovechando las frecuencias irregulares con las que aparecen los diferentes caracteres en un mensaje. Los algoritmos de este grupo incluyen algoritmos aritméticos y de codificación de prefijos (utilizando árboles secantes de Shannon-Fanno, Huffman).
Los algoritmos para convertir información se pueden clasificar en un grupo separado. Los algoritmos de este grupo no comprimen información directamente, pero su uso simplifica enormemente la compresión adicional utilizando algoritmos de flujo, diccionario y entropía.

Algoritmos de flujo y diccionario

Codificación de longitud de ejecución

Run-Length Encoding (RLE) es uno de los algoritmos de compresión de datos más simples y comunes. En este algoritmo, una secuencia de caracteres repetidos se reemplaza por un carácter y el número de veces que se repite.
Por ejemplo, la cadena "AAAAAA", que requiere almacenar 5 bytes (suponiendo que se asigne un byte para almacenar un carácter), se puede reemplazar por "5A", que consta de dos bytes. Evidentemente, este algoritmo es más eficaz cuanto más larga sea la serie de repeticiones.

La principal desventaja de este algoritmo es su eficiencia extremadamente baja en secuencias de caracteres que no se repiten. Por ejemplo, si consideramos la secuencia "ABABAB" (6 bytes), después de aplicar el algoritmo RLE se convertirá en "1A1B1A1B1A1B" (12 bytes). Existen varios métodos para resolver el problema de los caracteres que no se repiten.

El método más simple es la siguiente modificación: el byte que codifica el número de repeticiones debe almacenar información no solo sobre el número de repeticiones, sino también sobre su presencia. Si el primer bit es 1, los siguientes 7 bits indican el número de repeticiones del carácter correspondiente, y si el primer bit es 0, los siguientes 7 bits indican el número de caracteres que se deben tomar sin repetición. Si codificamos “ABABAB” usando esta modificación, obtendremos “-6ABABAB” (7 bytes). Es obvio que la técnica propuesta puede aumentar significativamente la eficiencia del algoritmo RLE en secuencias de caracteres que no se repiten. La implementación del enfoque propuesto se muestra en el Listado 1:

1. tipo
2. función RLEEncode(InMsg: ShortString): TRLEEncodedString;
3. MatchFl: booleano;
4. MatchCount: shortint;
5. Cadena codificada: TRLEEncodedString;
6. N, i: byte;
7. comenzar
8. norte:=0;
9. SetLength(EncodedString, 2 * longitud(InMsg));
10. mientras que longitud (InMsg) >= 1 hacer
11. comenzar
12. MatchFl : = (longitud(InMsg) > 1 ) y (InMsg[ 1 ] = InMsg[ 2 ] ) ;
13. Conteo de coincidencias: = 1;
14. mientras (MatchCount<= 126 ) and (MatchCount < length(InMsg) ) and ((InMsg[ MatchCount] = InMsg[ MatchCount + 1 ] ) = MatchFl) do
15. Conteo de coincidencias: = Conteo de coincidencias + 1;
16. si MatchFl entonces
17. comenzar
18. N:=N+2;
19. Cadena codificada[ N - 2 ] : = MatchCount + 128;
20. Cadenacodificada[ N - 1 ] : = orden ( InMsg[ 1 ] ) ;
21. demás
22. comenzar
23. si MatchCount<>longitud (InMsg) entonces
24. MatchCount: = MatchCount - 1;
25. N : = N + 1 + MatchCount;
26. Cadena codificada[ N - 1 - MatchCount] : = - MatchCount + 128;
27. para i: = 1 para MatchCount hacer
28. Cadenacodificada[ N - 1 - MatchCount + i] : = ord (InMsg[ i] );
29. fin ;
30. eliminar(InMsg, 1, MatchCount);
31. fin ;
32. EstablecerLongitud(Cadena codificada, N);
33. RLEEncode := Cadena codificada;
34. fin ;

Decodificar un mensaje comprimido es muy simple y se reduce a un solo paso a través del mensaje comprimido; consulte el Listado 2:

1. tipo
2. TRLEEncodedString = matriz de bytes;
3. función RLEDecode(InMsg: TRLEEncodedString): ShortString;
4. RepetirContador: shortint;
5. i, j: palabra;
6. Mensaje de salida: cadena corta;
7. comenzar
8. Mensaje de salida: = "";
9. yo:= 0;
10. mientras yo< length(InMsg) do
11. comenzar
12. RepetirContador: = InMsg[ i] - 128;
13. yo: = yo + 1;
14. si RepetirContar< 0 then
15. comenzar
16. RepetirCuenta := abs (RepetirCuenta);
17. para j: = i a i + RepetirCount - 1 hacer
18. Mensaje de salida: = Mensaje de salida + chr (Mensaje de entrada[j]);
19. yo : = yo + RepetirCuenta;
20. demás
21. comenzar
22. para j: = 1 para repetirCount hacer
23. Mensaje de salida: = Mensaje de salida + chr (Mensaje de entrada[i]);
24. yo: = yo + 1;
25. fin ;
26. fin ;
27. RLEDecode := Mensaje de salida;
28. fin ;

El segundo método para aumentar la eficiencia del algoritmo RLE es utilizar algoritmos de transformación de información que no comprimen los datos directamente, sino que los llevan a una forma más conveniente para la compresión. Como ejemplo de dicho algoritmo, consideraremos la permutación BWT, que lleva el nombre de los inventores de la transformada de Burrows-Wheeler. Esta permutación no cambia los caracteres en sí, solo cambia su orden en la cadena, mientras que las subcadenas repetidas después de aplicar la permutación se recopilan en grupos densos, que se comprimen mucho mejor usando el algoritmo RLE. La conversión directa de BWT se reduce a los siguientes pasos:
1. Agregar a la cadena original un carácter especial de fin de línea que no aparece en ningún otro lugar;
2. Obtener todas las permutaciones cíclicas de la cadena original;
3. Clasificar las cadenas recibidas en orden lexicográfico;
4. Devolver la última columna de la matriz resultante.
Una implementación de este algoritmo se muestra en el Listado 3.

1. constante
2. EOMsg = "|" ;
3. función BWTEncode(InMsg: ShortString): ShortString;
4. Mensaje de salida: cadena corta;
5. Último carácter: ANSIChar;
6. N, i: palabra ;
7. comenzar
8. MensajeEnt : = MensajeEnt + MensajeEnt;
9. N : = longitud(InMsg);
10. ShiftTable[ 1 ] : = EnMsg;
11. para i : = 2 a N hacer
12. comenzar
13. Últimocarácter: = EnMsg[ N];
14. EnMsg: = LastChar + copiar(InMsg, 1, N - 1);
15. ShiftTable[i] : = InMsg;
16. fin ;
17. Ordenar(ShiftTable);
18. Mensaje de salida: = "";
19. para i : = 1 a N hacer
20. Mensaje de salida: = Mensaje de salida + ShiftTable[i] [N];
21. BWTEncode:= Mensaje de salida;
22. fin ;

La forma más sencilla de explicar esta transformación es con un ejemplo concreto. Tomemos la cadena "PIÑA" y acordemos que el final del carácter de la cadena será el carácter "|". Todas las permutaciones cíclicas de esta cadena y el resultado de su clasificación lexicográfica se dan en la tabla. 1.

Aquellos. El resultado de una conversión directa es la cadena "|NNAAAC". Es fácil ver que esta cadena se comprime mucho mejor que la original mediante el algoritmo RLE, porque contiene largas subsecuencias de letras repetidas.
Se puede lograr un efecto similar utilizando otras transformaciones, pero la ventaja de la transformación BWT es que es reversible, aunque la transformación inversa es más complicada que la directa. Para restaurar la cadena original, debe realizar los siguientes pasos:
Cree una matriz vacía de tamaño n*n, donde n es el número de caracteres del mensaje codificado;
Llene la columna vacía más a la derecha con el mensaje codificado;
Ordenar las filas de la tabla en orden lexicográfico;
Repita los pasos 2 y 3 siempre que haya columnas vacías;
Devuelve la cadena que termina con el carácter de fin de línea.

Implementar la conversión inversa no es difícil a primera vista y una de las opciones de implementación se muestra en el Listado 4.

1. constante
2. EOMsg = "|" ;
3. función BWTDecode(InMsg: ShortString): ShortString;
4. Mensaje de salida: cadena corta;
5. ShiftTable: matriz de ShortString;
6. N, i, j: palabra;
7. comenzar
8. Mensaje de salida: = "";
9. N : = longitud(InMsg);
10. EstablecerLongitud(ShiftTable, N + 1);
11. para i : = 0 a N hacer
12. Tabla de cambios[i] : = "" ;
13. para i : = 1 a N hacer
14. comenzar
15. para j := 1 a N hacer
16. ShiftTable[ j] : = InMsg[ j] + ShiftTable[ j] ;
17. Ordenar(ShiftTable);
18. fin ;
19. para i : = 1 a N hacer
20. si ShiftTable[i] [N] = EOMsg entonces
21. Mensaje de salida: = ShiftTable[i];
22. eliminar (Mensaje de salida, N, 1);
23. BWTDecode := Mensaje de salida;
24. fin ;

Pero en la práctica, la eficiencia depende del algoritmo de clasificación elegido. Los algoritmos triviales con complejidad cuadrática obviamente tendrán un impacto muy negativo en el rendimiento, por lo que se recomienda utilizar algoritmos eficientes.

Después de ordenar la tabla obtenida en el séptimo paso, debe seleccionar una fila de la tabla que termine con el carácter “|”. Es fácil ver que esta es la única línea. Eso. Analizamos la transformación BWT usando un ejemplo específico.

En resumen, podemos decir que la principal ventaja del grupo de algoritmos RLE es la simplicidad y la velocidad de operación (incluida la velocidad de decodificación), y la principal desventaja es la ineficiencia en conjuntos de caracteres que no se repiten. El uso de permutaciones especiales aumenta la eficiencia del algoritmo, pero también aumenta en gran medida el tiempo de ejecución (especialmente la decodificación).

Compresión de diccionario (algoritmos LZ)

El grupo de algoritmos de diccionario, a diferencia de los algoritmos del grupo RLE, codifica no el número de repeticiones de caracteres, sino secuencias de caracteres encontradas previamente. Mientras se ejecutan los algoritmos considerados, se crea dinámicamente una tabla con una lista de secuencias ya encontradas y sus códigos correspondientes. Esta tabla a menudo se denomina diccionario y el grupo correspondiente de algoritmos se denomina diccionario.

La versión más simple del algoritmo del diccionario se describe a continuación:
Inicialice el diccionario con todos los caracteres que aparecen en la cadena de entrada;
Busque en el diccionario la secuencia más larga (S) que coincida con el comienzo del mensaje codificado;
Imprima el código de la secuencia encontrada y elimínelo del comienzo del mensaje codificado;
Si no se llega al final del mensaje, lea el siguiente carácter y agregue Sc al diccionario, vaya al paso 2. En caso contrario, salga.

Por ejemplo, el diccionario recién inicializado para la frase “CUCKOOKOOKUSHONKOOKUPILAKAHOOD” se muestra en la Tabla. 3:

Durante el proceso de compresión, el diccionario se complementará con secuencias que se encuentran en el mensaje. El proceso de actualización del diccionario se muestra en la tabla. 4.

Al describir el algoritmo, se omitió deliberadamente una descripción de la situación en la que el diccionario está completamente lleno. Dependiendo de la variante del algoritmo, es posible un comportamiento diferente: borrar total o parcialmente el diccionario, dejar de llenar el diccionario o expandir el diccionario con el correspondiente aumento en la capacidad del código. Cada uno de estos enfoques tiene ciertas desventajas. Por ejemplo, detener la reposición del diccionario puede llevar a una situación en la que el diccionario almacene secuencias que ocurren al comienzo de la cadena que se está comprimiendo, pero que no ocurren posteriormente. Al mismo tiempo, limpiar el diccionario puede provocar la eliminación de secuencias frecuentes. La mayoría de las implementaciones utilizadas, al llenar el diccionario, comienzan a monitorear el nivel de compresión y, cuando disminuye por debajo de cierto nivel, el diccionario se reconstruye. A continuación, consideraremos la implementación más simple que deja de actualizar el diccionario cuando está lleno.

Primero, definamos un diccionario como un registro que almacena no solo las subcadenas encontradas, sino también la cantidad de subcadenas almacenadas en el diccionario:

Las subsecuencias encontradas anteriormente se almacenan en la matriz de Palabras y su código son los números de subsecuencia en esta matriz.
También definiremos las funciones de buscar en el diccionario y agregar al diccionario:

1. constante
2. MAX_DICT_LENGTH = 256;
3. función FindInDict(D: TDictionary; str: ShortString): entero;
4. r:entero;
5. i:entero;
6. fl:booleano;
7. comenzar
8. r : = - 1 ;
9. si D. WordCount > 0 entonces
10. comenzar
11. yo := D. Conteo de palabras ;
12. fl := falso ;
13. mientras que (no fl) y (i >= 0 ) lo hacen
14. comenzar
15. yo : = yo - 1 ;
16. fl : = D. Palabras [ i] = str;
17. fin ;
18. fin ;
19. si fl entonces
20. r := yo;
21. FindInDict: = r;
22. fin ;
23. procedimiento AddToDict(var D: TDictionary; str: ShortString);
24. comenzar
25. si D. Conteo de palabras< MAX_DICT_LENGTH then
26. comenzar
27. D. Conteo de palabras: = D. Conteo de palabras + 1;
28. SetLength(D. Palabras, D. WordCount);
29. D. Palabras [ D. WordCount - 1 ] : = cadena;
30. fin ;
31. fin ;

Usando estas funciones, el proceso de codificación según el algoritmo descrito se puede implementar de la siguiente manera:

1. función LZWEncode(InMsg: ShortString): TEncodedString;
2. Mensaje de salida: TEncodedString;
3. tmpstr: cadena corta;
4. D: TDiccionario;
5. yo, N: byte;
6. comenzar
7. EstablecerLongitud(OutMsg, length(InMsg));
8. norte:=0;
9. InitDict(D);
10. mientras que longitud (InMsg) > 0 hacer
11. comenzar
12. tmpstr : = EnMsg[ 1 ] ;
13. mientras (FindInDict(D, tmpstr) >= 0 ) y (longitud(InMsg) > longitud(tmpstr) hacen
14. tmpstr : = tmpstr + InMsg[ longitud(tmpstr) + 1 ] ;
15. si FindInDict(D, tmpstr)< 0 then
16. eliminar(tmpstr, longitud(tmpstr), 1);
17. OutMsg[ N] : = FindInDict(D, tmpstr);
18. N:=N+1;
19. eliminar(InMsg, 1, longitud(tmpstr));
20. si longitud (InMsg) > 0 entonces
21. AddToDict(D, tmpstr + InMsg[ 1 ] );
22. fin ;
23. EstablecerLongitud(Mensaje de salida, N);
24. LZWEncode:= Mensaje de salida;
25. fin ;

El resultado de la codificación será la cantidad de palabras en el diccionario.
El proceso de decodificación se reduce a la decodificación directa de códigos, y no es necesario transferir el diccionario creado, basta con que durante la decodificación el diccionario se inicialice de la misma forma que durante la codificación. Luego, el diccionario se restaurará por completo directamente durante el proceso de decodificación concatenando la subsecuencia anterior y el símbolo actual.

El único problema es posible en la siguiente situación: cuando es necesario decodificar una subsecuencia que aún no está en el diccionario. Es fácil ver que esto sólo es posible cuando es necesario extraer una subcadena que debe agregarse en el paso actual. Esto significa que la subcadena satisface el patrón cSc, es decir Comienza y termina con el mismo personaje. En este caso, cS es la subcadena agregada en el paso anterior. La situación considerada es la única en la que es necesario decodificar una línea que aún no se ha agregado. Considerando lo anterior, podemos proponer la siguiente opción para decodificar una cadena comprimida:

1. función LZWDecode(InMsg: TEncodedString): ShortString;
2. D: TDiccionario;
3. OutMsg, tmpstr: ShortString;
4. yo: byte;
5. comenzar
6. Mensaje de salida: = "";
7. tmpstr: = "";
8. InitDict(D);
9. para i: = 0 a longitud (InMsg) - 1 hacer
10. comenzar
11. si InMsg[ i] >= D. WordCount entonces
12. tmpstr : = D. Palabras [ InMsg[ i - 1 ] ] + D. Palabras [ InMsg[ i - 1 ] ] [ 1 ]
13. demás
14. tmpstr : = D. Palabras [ InMsg[ i] ] ;
15. Mensaje de salida : = Mensaje de salida + tmpstr;
16. si i > 0 entonces
17. AddToDict(D, D. Palabras [ InMsg[ i - 1 ] ] + tmpstr[ 1 ] );
18. fin ;
19. LZWDecode:= Mensaje de salida;
20. fin ;

Las ventajas de los algoritmos de diccionario incluyen su mayor eficiencia de compresión en comparación con RLE. Sin embargo, debe entenderse que el uso real de estos algoritmos implica algunas dificultades de implementación.

Codificación de entropía

Codificación utilizando árboles de Shannon-Fano

El algoritmo de Shannon-Fano es uno de los primeros algoritmos de compresión desarrollados. El algoritmo se basa en la idea de representar caracteres más frecuentes mediante códigos más cortos. Además, los códigos obtenidos utilizando el algoritmo de Shannon-Fano tienen la propiedad de prefijo: es decir ningún código es el comienzo de ningún otro código. La propiedad de prefijo garantiza que la codificación sea uno a uno. El algoritmo para construir códigos Shannon-Fano se presenta a continuación:
1. Divida el alfabeto en dos partes, cuyas probabilidades totales de los símbolos estén lo más cerca posible entre sí.
2. Agregue 0 al código de prefijo de la primera parte de los caracteres, agregue 1 al código de prefijo de la segunda parte de los caracteres.
3. Para cada parte (que contenga al menos dos caracteres), realice de forma recursiva los pasos 1 a 3.
A pesar de su comparativa simplicidad, el algoritmo de Shannon-Fano no está exento de inconvenientes, el más importante de los cuales es la codificación no óptima. Aunque la partición en cada paso es óptima, el algoritmo no garantiza un resultado óptimo en su conjunto. Considere, por ejemplo, la siguiente cadena: "AAABVGDEJ". El correspondiente árbol de Shannon-Fano y los códigos obtenidos en base a él se presentan en la Fig. 1:

Sin utilizar codificación, el mensaje ocupará 40 bits (siempre que cada carácter esté codificado con 4 bits), y utilizando el algoritmo de Shannon-Fano 4*2+2+4+4+3+3+3=27 bits. El volumen de mensajes disminuyó un 32,5%, pero a continuación mostraremos que este resultado se puede mejorar significativamente.

Codificación con árboles de Huffman

El algoritmo de codificación de Huffman, desarrollado varios años después del algoritmo de Shannon-Fano, también tiene la propiedad de prefijo y, además, una redundancia mínima demostrada, lo que determina su distribución extremadamente amplia. Para obtener códigos Huffman, utilice el siguiente algoritmo:
1. Todos los caracteres del alfabeto se representan como nodos libres y el peso del nodo es proporcional a la frecuencia del carácter en el mensaje;
2. Del conjunto de nodos libres, se seleccionan dos nodos con peso mínimo y se crea un nuevo nodo (padre) con un peso igual a la suma de los pesos de los nodos seleccionados;
3. Los nodos seleccionados se eliminan de la lista libre y el nodo principal creado en base a ellos se agrega a esta lista;
4. Se repiten los pasos 2 y 3 hasta que haya más de un nodo en la lista libre;
5. Según el árbol construido, a cada carácter del alfabeto se le asigna un código de prefijo;
6. El mensaje se codifica con los códigos recibidos.

Consideremos el mismo ejemplo que en el caso del algoritmo de Shannon-Fano. El árbol de Huffman y los códigos obtenidos para el mensaje “AAAABVGDEJ” se presentan en la Fig. 2:

Es fácil calcular que el volumen del mensaje codificado será de 26 bits, que es menor que en el algoritmo de Shannon-Fano. Por separado, vale la pena señalar que debido a la popularidad del algoritmo de Huffman en este momento Existen muchas variantes de la codificación Huffman, incluida la codificación adaptativa, que no requiere transmisión de frecuencias de símbolos.
Entre las desventajas del algoritmo de Huffman, una parte importante son los problemas asociados con la complejidad de la implementación. El uso de símbolos de variables reales para almacenar frecuencias está asociado con una pérdida de precisión, por lo que en la práctica se suelen utilizar variables enteras, pero como El peso de los nodos principales crece constantemente y, tarde o temprano, se produce un desbordamiento. Por tanto, a pesar de la simplicidad del algoritmo, su correcta implementación todavía puede causar algunas dificultades, especialmente para alfabetos grandes.

Codificación con árboles de funciones secantes

La codificación mediante funciones secantes es un algoritmo desarrollado por los autores que permite obtener códigos de prefijo. El algoritmo se basa en la idea de construir un árbol, cada nodo del cual contiene una función secante. Para describir el algoritmo con más detalle, es necesario introducir varias definiciones.
Una palabra es una secuencia ordenada de m bits (el número m se llama capacidad de palabra).
Un literal secante es un par con la forma valor dígito-dígito. Por ejemplo, el literal (4,1) significa que el bit 4 de la palabra debe ser 1. Si se cumple la condición del literal, entonces el literal se considera verdadero; de lo contrario, es falso.
Una secante de k bits es un conjunto de k literales. Si todos los literales son verdaderos, entonces la función secante en sí es verdadera; de lo contrario, es falsa.

El árbol está construido de manera que cada nodo divida el alfabeto en partes lo más cercanas posible. En la Fig. La Figura 3 muestra un ejemplo de un árbol secante:

Un árbol de funciones secantes en el caso general no garantiza una codificación óptima, pero proporciona una velocidad extremadamente alta debido a la simplicidad de las operaciones en los nodos.

Codificación aritmética

La codificación aritmética es una de las más formas efectivas Compresión de información. A diferencia del algoritmo de Huffman, la codificación aritmética permite codificar mensajes con una entropía inferior a 1 bit por carácter. Porque La mayoría de los algoritmos de codificación aritmética están protegidos por patentes; a continuación sólo se describirán las ideas básicas.
Supongamos que el alfabeto en uso contiene N símbolos a_1,…,a_N, con frecuencias p_1,…,p_N, respectivamente. Entonces el algoritmo de codificación aritmética se verá así:
Tome ) como medio intervalo de trabajo)