GORKOFF 24 de febrero de 2015 a las 11:41 AM

Métodos de compresión de datos

• Algoritmos

Mi asesor científico y yo estamos preparando una pequeña monografía sobre procesamiento de imágenes. Decidí enviar un capítulo sobre algoritmos de compresión de imágenes al juicio de HabraSociety. Como es difícil encajar todo un capítulo en el marco de una publicación, decidí dividirlo en tres publicaciones:
1. Métodos de compresión de datos;
2. Compresión de imágenes sin pérdida;
3. Compresión de imágenes con pérdida.
A continuación puede leer la primera publicación de la serie.

Por el momento, hay una gran cantidad de algoritmos de compresión sin pérdidas, que se pueden dividir condicionalmente en dos grandes grupos:
1. Algoritmos de flujo y diccionario. Este grupo incluye algoritmos de la RLE (codificación de longitud de ejecución), LZ * y otras familias. La peculiaridad de todos los algoritmos de este grupo es que la codificación no utiliza información sobre las frecuencias de los caracteres en el mensaje, sino información sobre las secuencias. que se encontraron antes.
2. Algoritmos de compresión estadística (entropía). Este grupo de algoritmos comprime la información utilizando la irregularidad de las frecuencias con las que aparecen diferentes caracteres en el mensaje. Los algoritmos de este grupo incluyen algoritmos aritméticos y de codificación de prefijos (usando Shannon-Fanno, Huffman, árboles secantes).
Los algoritmos de transformación de información se pueden distinguir en un grupo separado. Los algoritmos de este grupo no comprimen directamente la información, pero su aplicación simplifica enormemente la compresión adicional utilizando algoritmos de flujo, diccionario y entropía.

Algoritmos de transmisión y diccionario

Ejecutar codificación de longitud

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 "AAAAA", que requiere 5 bytes para almacenar (asumiendo que se asigna un byte para almacenar un carácter), se puede reemplazar con "5A", que consta de dos bytes. Obviamente, cuanto más larga sea la serie de repetición, más eficiente será este algoritmo.

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), luego de aplicar el algoritmo RLE se convertirá en "1A1B1A1B1A1B" (12 bytes). Existen varios métodos para abordar 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 deben tomarse sin repetición. Si codifica "ABABAB" usando esta modificación, obtenemos "-6ABABAB" (7 bytes). Obviamente, la técnica propuesta puede mejorar 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. escribe
2. función RLEEncode (InMsg: ShortString): TRLEEncodedString;
3. MatchFl: booleano;
4. MatchCount: shortint;
5. EncodedString: TRLEEncodedString;
6. N, i: byte;
7. comenzar
8. N: = 0;
9. SetLength (EncodedString, 2 * longitud (InMsg));
10. while length (InMsg)> = 1 hacer
11. comenzar
12. MatchFl: = (longitud (InMsg)> 1) y (InMsg [1] = InMsg [2]);
13. MatchCount: = 1;
14. while (MatchCount<= 126 ) and (MatchCount < length(InMsg) ) and ((InMsg[ MatchCount] = InMsg[ MatchCount + 1 ] ) = MatchFl) do
15. MatchCount: = MatchCount + 1;
16. si MatchFl entonces
17. comenzar
18. N: = N + 2;
19. EncodedString [N - 2]: = MatchCount + 128;
20. EncodedString [N - 1]: = ord (InMsg [1]);
21. demás
22. comenzar
23. si MatchCount<>length (InMsg) luego
24. MatchCount: = MatchCount - 1;
25. N: = N + 1 + MatchCount;
26. EncodedString [N - 1 - MatchCount]: = - MatchCount + 128;
27. para i: = 1 para MatchCount hacer
28. EncodedString [N - 1 - MatchCount + i]: = ord (InMsg [i]);
29. fin;
30. eliminar (InMsg, 1, MatchCount);
31. fin;
32. SetLength (EncodedString, N);
33. RLEEncode: = EncodedString;
34. fin;

Decodificar un mensaje comprimido es muy simple y se reduce a una sola pasada sobre el mensaje comprimido, vea el Listado 2:

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

El segundo método para aumentar la eficiencia del algoritmo RLE es el uso de algoritmos de transformación de información que no comprimen directamente los datos, sino que los llevan a una forma más conveniente para la compresión. Como ejemplo de un algoritmo de este tipo, consideraremos una permutación de 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 con el algoritmo RLE. La conversión directa de BWT se reduce a la secuencia de los siguientes pasos:
1. Agregar un carácter especial de final de línea a la cadena original, que no se encuentra en ningún otro lugar;
2. Obtener todas las permutaciones cíclicas de la cadena original;
3. Clasificación de las líneas recibidas en orden lexicográfico;
4. Devolviendo la última columna de la matriz resultante.
La implementación de este algoritmo se muestra en el Listado 3.

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

La forma más sencilla de explicar esta transformación es con un ejemplo específico. Tomemos la cadena "ANANAS" y acordamos que el carácter de final de línea será el símbolo "|". Todas las permutaciones cíclicas de esta línea y el resultado de su clasificación lexicográfica se muestran en la Tabla. una.

Aquellos. el resultado de la conversión directa será la cadena "| ННААС". Es fácil ver que esta cadena es mucho mejor que la original; está comprimida por el algoritmo RLE, ya que contiene subsecuencias largas de letras repetidas.
Se puede lograr un efecto similar con la ayuda de otras transformaciones, pero la ventaja de la transformada BWT es que es reversible, sin embargo, la transformada inversa es más difícil que la directa. Para restaurar la cadena original, debe hacer lo siguiente:
Cree una matriz n * n vacía, donde n es el número de caracteres en el mensaje codificado;
Llene la columna vacía más a la derecha con el mensaje codificado;
Ordene las filas de la tabla en orden lexicográfico;
Repita los pasos 2-3 hasta que haya columnas vacías;
Devuelve la línea que termina con el carácter de final de línea.

A primera vista, la transformación inversa es sencilla y una de las opciones se muestra en el Listado 4.

1. constante
2. EOMsg = "|" ;
3. función BWTDecode (InMsg: ShortString): ShortString;
4. OutMsg: ShortString;
5. ShiftTable: matriz de ShortString;
6. N, i, j: palabra;
7. comenzar
8. OutMsg: = "";
9. N: = longitud (InMsg);
10. SetLength (ShiftTable, N + 1);
11. para i: = 0 a N hacer
12. ShiftTable [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. OutMsg: = ShiftTable [i];
22. eliminar (OutMsg, N, 1);
23. BWTDecode: = OutMsg;
24. fin;

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

Después de ordenar la tabla obtenida en el séptimo paso, es necesario seleccionar de la tabla una fila que termine con el carácter "|". Es fácil ver que esta es la única línea. Ese. Examinamos 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 los 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 las secuencias de caracteres encontradas anteriormente. Durante el funcionamiento de los algoritmos considerados, se crea dinámicamente una tabla con una lista de secuencias encontradas previamente 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;
Emita el código de la secuencia encontrada y elimínelo del principio 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. De lo contrario, salga.

Por ejemplo, el vocabulario recién inicializado para la frase "CUCKOOKUCHONKUPILACAPUCHON" se muestra en la Tabla. 3:

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

Al describir el algoritmo, se omitió deliberadamente la descripción de la situación en la que el diccionario está lleno por completo. Dependiendo de la variante del algoritmo, es posible un comportamiento diferente: vaciado total o parcial del diccionario, detener el llenado del diccionario o expandir el diccionario con un aumento correspondiente en el ancho del código. Cada uno de estos enfoques tiene ciertas desventajas. Por ejemplo, detener la finalización del diccionario puede llevar a una situación en la que el diccionario almacena secuencias que ocurren al principio de la cadena comprimida, pero que no ocurren más tarde. Al mismo tiempo, borrar el diccionario puede eliminar secuencias frecuentes. La mayoría de las implementaciones utilizadas, al completar el diccionario, comienzan a rastrear la relación de compresión, y cuando cae por debajo de cierto nivel, el diccionario se reconstruye. A continuación, consideraremos la implementación más simple que deja de reponer el diccionario cuando está lleno.

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

Las subsecuencias encontradas anteriormente se almacenan en la matriz de palabras y sus códigos son los números de subsecuencias en esta matriz.
También definimos las funciones para 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. i: = D. WordCount;
12. fl: = falso;
13. mientras que (no fl) y (i> = 0) 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. WordCount< MAX_DICT_LENGTH then
26. comenzar
27. D. WordCount: = D. WordCount + 1;
28. SetLength (D. Palabras, D. WordCount);
29. D. Palabras [D. WordCount - 1]: = str;
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. OutMsg: TEncodedString;
3. tmpstr: ShortString;
4. D: TDiccionario;
5. i, N: byte;
6. comenzar
7. SetLength (OutMsg, longitud (InMsg));
8. N: = 0;
9. InitDict (D);
10. while length (InMsg)> 0 do
11. comenzar
12. tmpstr: = InMsg [1];
13. mientras que (FindInDict (D, tmpstr)> = 0) y (length (InMsg)> length (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. SetLength (OutMsg, N);
24. LZWEncode: = OutMsg;
25. fin;

El resultado de la codificación serán los números de palabras en el diccionario.
El proceso de decodificación se reduce al descifrado directo de códigos, si bien 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á completamente directamente durante el proceso de decodificación mediante la concatenación de 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 solo es posible cuando es necesario extraer una subcadena para agregarla en el paso actual. Esto significa que la subcadena coincide con el patrón cSc, es decir comienza y termina con el mismo carácter. Además, cS es la subcadena agregada en el paso anterior. La situación considerada es la única cuando es necesario decodificar una línea que aún no se ha agregado. Teniendo en cuenta lo anterior, podemos sugerir la siguiente opción para decodificar una cadena comprimida:

1. función LZWDecode (InMsg: TEncodedString): ShortString;
2. D: TDiccionario;
3. OutMsg, tmpstr: ShortString;
4. i: byte;
5. comenzar
6. OutMsg: = "";
7. tmpstr: = "";
8. InitDict (D);
9. para i: = 0 a la longitud (InMsg) - 1 do
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. OutMsg: = OutMsg + tmpstr;
16. si i> 0 entonces
17. AddToDict (D, D. Palabras [InMsg [i - 1]] + tmpstr [1]);
18. fin;
19. LZWDecode: = OutMsg;
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 está asociado con algunas dificultades de implementación.

Codificación de entropía

Codificación con árboles Shannon-Fano

El algoritmo 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 utilizando códigos más cortos. Además, los códigos obtenidos mediante el algoritmo de Shannon-Fano tienen la propiedad de prefijo: es decir, ningún código es el comienzo de cualquier otro código. La propiedad del prefijo asegura 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, las probabilidades totales de los símbolos en los que 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 (en la que hay al menos dos caracteres), realice de forma recursiva los pasos 1-3.
A pesar de su simplicidad comparativa, el algoritmo de Shannon-Fano no está exento de inconvenientes, el más significativo 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 línea: "AAAABVGDEZH". El árbol de Shannon-Fano correspondiente y los códigos derivados de él se muestran en la Fig. una:

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

Codificación con árboles de Huffman

El algoritmo de codificación de Huffman, desarrollado pocos años después del algoritmo de Shannon-Fano, también posee la propiedad de prefijo y, además, la redundancia mínima probada, por eso precisamente está tan extendido. Para obtener códigos de Huffman, se utiliza el siguiente algoritmo:
1. Todos los símbolos del alfabeto se representan como nodos libres, mientras que el peso del nodo es proporcional a la frecuencia del símbolo en el mensaje;
2. Del conjunto de nodos libres, se seleccionan dos nodos con el 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 padre creado en base a ellos se agrega a esta lista;
4. Los pasos 2-3 se repiten hasta que haya más de un nodo en la lista libre;
5. Según el árbol construido, se asigna un código de prefijo a cada carácter del alfabeto;
6. El mensaje está codificado con los códigos recibidos.

Considere el mismo ejemplo que en el caso del algoritmo Shannon-Fano. El árbol de Huffman y los códigos obtenidos para el mensaje "AAAABVGDEZH" se muestran en la Fig. 2:

Es fácil calcular que el tamaño del mensaje codificado será de 26 bits, que es menor que en el algoritmo de Shannon-Fano. Por separado, cabe señalar que debido a la popularidad del algoritmo de Huffman, en este momento hay muchas opciones para la codificación de Huffman, incluida la codificación adaptativa, que no requiere la 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 variables reales para almacenar las frecuencias de los símbolos está asociado con una pérdida de precisión; por lo tanto, en la práctica, a menudo se usan variables enteras, pero como el peso de los nodos padres crece constantemente, tarde o temprano ocurre un desbordamiento. Por lo tanto, a pesar de la simplicidad del algoritmo, su correcta implementación aún 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 denomina longitud de palabra).
El literal secante es un par del tipo de valor de descarga-descarga. Por ejemplo, literal (4,1) significa que los 4 bits de la palabra deben ser 1. Si se cumple la condición 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í misma es verdadera; de lo contrario, es falsa.

El árbol está construido para que cada nodo divida el alfabeto en las partes más cercanas posibles. En la Fig. 3 muestra un ejemplo de un árbol secante:

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

Codificación aritmética

La codificación aritmética es una de las formas más eficientes de comprimir información. A diferencia del algoritmo de Huffman, la codificación aritmética le permite codificar mensajes con una entropía de menos de 1 bit por símbolo. Porque la mayoría de los algoritmos de codificación aritmética están protegidos por patentes, solo las ideas básicas se describirán a continuación.
Supongamos que en el alfabeto utilizado hay 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í:
Tomar como medio intervalo de trabajo)