GORKOFF 24 febrero 2015 a las 11:41

Métodos de compresión de datos

• Algoritmos

Mi supervisor y yo estamos preparando una breve monografía sobre procesamiento de imágenes. Decidí presentar a la corte de la comunidad habra un capítulo sobre algoritmos de compresión de imágenes. Como es difícil incluir un capítulo completo en una 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 imagen con pérdida.
Puedes leer la primera publicación de la serie a continuación.

En este 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 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 la frecuencia de los símbolos en el mensaje, sino información sobre las secuencias. encontrado antes.
2. Algoritmos de compresión estadística (entropía). Este grupo de algoritmos comprime la información utilizando las frecuencias desiguales con las que aparecen diferentes caracteres en un 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 destacar como un grupo separado. Los algoritmos de este grupo no comprimen información directamente, pero su aplicación simplifica enormemente la compresión adicional utilizando algoritmos de transmisión, 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 "AAAAA", que requiere 5 bytes para almacenar (suponiendo que se asigne un byte para almacenar un carácter), se puede reemplazar por "5A", que consta de dos bytes. Obviamente, este algoritmo es más eficiente cuanto más larga es 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), luego 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 7 bits siguientes indican el número de repeticiones del carácter correspondiente, y si el primer bit es 0, los 7 bits siguientes indican el número de caracteres a tomar sin repetición. Si codificamos "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. function RLEEncode(InMsg: ShortString) : TRLEEncodedString;
3. MatchFl: booleano;
4. Contador de coincidencias: entero corto;
5. CadenaCodificada: TRLECadenaCodificada;
6. N, yo: bytes;
7. comenzar
8. N:=0;
9. SetLength(EncodedString, 2 * length(InMsg) ) ;
10. while length(InMsg) >= 1 hacer
11. comenzar
12. MatchFl : = (longitud(InMsg) > 1 ) and (InMsg[ 1 ] = InMsg[ 2 ] ) ;
13. Contador de coincidencias := 1 ;
14. while (Número de coincidencias<= 126 ) and (MatchCount < length(InMsg) ) and ((InMsg[ MatchCount] = InMsg[ MatchCount + 1 ] ) = MatchFl) do
15. Número de coincidencias: = Número de coincidencias + 1;
16. si MatchFl entonces
17. comenzar
18. norte: = norte + 2;
19. CadenaCodificada[ N - 2 ] : = MatchCount + 128 ;
20. EncodedString[ N - 1 ] : = ord (InMsg[ 1 ] ) ;
21. demás
22. comenzar
23. si MatchCount<>longitud (InMsg) entonces
24. Número de coincidencias: = Número de coincidencias - 1;
25. N := N + 1 + Número de coincidencias;
26. EncodedString[ N - 1 - MatchCount] : = - MatchCount + 128 ;
27. for i := 1 to MatchCount do
28. EncodedString[ N - 1 - MatchCount + i] : = ord (InMsg[ i] ) ;
29. fin ;
30. eliminar(InMsg, 1 , MatchCount) ;
31. fin ;
32. EstablecerLongitud(CadenaCodificada, N) ;
33. RLEncode := CadenaCodificada;
34. fin ;

La decodificación de un mensaje comprimido es muy simple y se reduce a una sola pasada a través del mensaje comprimido, consulte el Listado 2:

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

El segundo método para mejorar 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 convierten a una forma que es más conveniente para la compresión. Como ejemplo de dicho algoritmo, consideraremos una 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í, sino que 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 transformación directa de BWT se reduce a una secuencia de los siguientes pasos:
1. Agregar a la cadena de origen un carácter especial de final de línea que no aparece en ningún otro lugar;
2. Obtener todas las permutaciones cíclicas de la cadena original;
3. Ordenar las cadenas recibidas en orden lexicográfico;
4. Devolver 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. Mensaje de Salida: Cadena Corta;
5. ÚltimoCarácter: ANSICarácter;
6. N, i: palabra;
7. comenzar
8. MensajeEntrada := MensajeEntrada + 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 + copy(InMsg, 1 , N - 1 ) ;
15. ShiftTable[i] := InMsg;
16. fin ;
17. Ordenar(ShiftTable) ;
18. MensajeSalida := "" ;
19. para i := 1 a N hacer
20. OutMsg : = OutMsg + ShiftTable[ i] [ N] ;
21. BWTEncode := MensajeSalida;
22. fin ;

La forma más fácil de explicar esta transformación es con un ejemplo específico. Tomemos la cadena "piña" y aceptemos que el símbolo "|" será el final de la cadena. Todas las permutaciones cíclicas de esta cadena y el resultado de su clasificación lexicográfica se dan en la Tabla. una.

Aquellos. el resultado de la conversión directa será la cadena "|NNAAAC". Es fácil ver que esta cadena es mucho mejor que la original, está comprimida por el algoritmo RLE, porque contiene largas subsecuencias de letras repetidas.
Se puede lograr un efecto similar usando otras transformaciones, pero la ventaja de la transformación BWT es que es reversible, sin embargo, 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 un carácter de fin de línea.

La implementación de la transformación inversa no es difícil a primera vista, y una de las implementaciones 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. MensajeSalida := "" ;
9. N := longitud(InMsg) ;
10. EstablecerLongitud(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 (Mensaje de salida, N, 1);
23. BWTDecode := MensajeSalida;
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 una fila de la tabla que termine con el símbolo "|". Es fácil ver que esta es la única línea. Ese. hemos considerado la transformación BWT en un ejemplo específico.

Resumiendo, 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 considerablemente 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 encontrados anteriormente. Durante la operación de los algoritmos en consideración, se crea dinámicamente una tabla con una lista de secuencias ya encontradas y sus códigos correspondientes. Esta tabla a menudo se llama diccionario, y el grupo correspondiente de algoritmos se llama diccionario.

La versión más simple del algoritmo del diccionario se describe a continuación:
Inicialice el diccionario con todos los caracteres que se encuentran 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, en la Tabla se muestra un diccionario recién inicializado para la frase "CUCKOOCOOKOOHOOD". 3:

Durante el proceso de compresión, el diccionario se complementará con las secuencias encontradas en el mensaje. El proceso de actualización del diccionario se da en la Tabla. 4.

Al describir el algoritmo, se omitió deliberadamente la descripción de la situación cuando el diccionario está completamente lleno. Dependiendo de la variante del algoritmo, es posible un comportamiento diferente: borrado total o parcial del diccionario, finalización del llenado del diccionario o expansión del diccionario con el correspondiente aumento en la capacidad de 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 almacena secuencias que ocurren al comienzo de la cadena comprimida, pero que no ocurren después. Al mismo tiempo, borrar el diccionario puede resultar en la eliminación de secuencias frecuentes. La mayoría de las implementaciones utilizadas, al llenar el diccionario, comienzan a rastrear el grado 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 reponer el diccionario cuando está lleno.

Primero, definimos 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 Palabras, y su código son los números de las subsecuencias en esta matriz.
También definimos la búsqueda de diccionario y agregamos funciones de diccionario:

1. constante
2. MAX_DICT_LENGTH = 256;
3. function FindInDict(D: TDictionary; str: ShortString) : integer ;
4. r: entero
5. yo: entero;
6. fl: booleano;
7. comenzar
8. r := - 1 ;
9. si D. WordCount > 0 entonces
10. comenzar
11. i := D.ContadorPalabras ;
12. fl := falso ;
13. mientras que (no fl) y (i >= 0 ) sí
14. comenzar
15. yo := yo - 1 ;
16. fl:=D.Palabras[i]=str;
17. fin ;
18. fin ;
19. si entonces
20. r :=i;
21. BuscarEnDict := r;
22. fin ;
23. procedimiento AddToDict(var D: TDictionary; str: ShortString) ;
24. comenzar
25. si D.ContadorPalabras< MAX_DICT_LENGTH then
26. comenzar
27. D.CuentaPalabras := D.CuentaPalabras + 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 de acuerdo con el algoritmo descrito se puede implementar de la siguiente manera:

1. function LZWEncode(InMsg: ShortString) : TEncodedString;
2. OutMsg: TEncodedString;
3. tmpstr: cadena corta;
4. D: TDiccionario;
5. yo, N: bytes;
6. comenzar
7. SetLength(OutMsg, length(InMsg) ) ;
8. N:=0;
9. DictInic(D) ;
10. while length(InMsg) > 0 do
11. comenzar
12. tmpstr := InMsg[ 1 ] ;
13. while (FindInDict(D, tmpstr) >= 0 ) y (longitud(InMsg) > longitud(tmpstr) )
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. norte: = norte + 1;
19. eliminar (InMsg, 1, longitud (tmpstr));
20. si longitud (InMsg) > 0 entonces
21. AddToDict(D, tmpstr + InMsg[ 1 ] ) ;
22. fin ;
23. EstablecerLongitud(MensajeSalida, N) ;
24. LZWEncode := MensajeSalida;
25. fin ;

El resultado de la codificación será el número 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 el diccionario se inicialice durante la decodificación de la misma manera que durante la codificación. Luego, el diccionario se restaurará por completo directamente en el proceso de decodificación al concatenar la subsecuencia anterior y el carácter 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 es posible solo en el caso de que sea necesario extraer una subcadena que debe agregarse en el paso actual. Y 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 cadena que aún no se ha agregado. Dado lo anterior, podemos ofrecer 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. MensajeSalida := "" ;
7. tmpstr := "" ;
8. DictInic(D) ;
9. for i := 0 to length(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. MensajeSalida := MensajeSalida + tmpstr;
16. si i > 0 entonces
17. AddToDict(D, D. Palabras [ InMsg[ i - 1 ] ] + tmpstr[ 1 ] ) ;
18. fin ;
19. LZWDecode := MensajeSalida;
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 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 con códigos más cortos. En este caso, los códigos obtenidos mediante el algoritmo de Shannon-Fano tienen la propiedad de prefijo: i.e. 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 de Shannon-Fano se presenta a continuación:
1. Divida el alfabeto en dos partes, cuyas probabilidades totales de 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 símbolos, agregue 1 al código de prefijo de la segunda parte de los símbolos.
3. Para cada parte (que tiene al menos dos caracteres), realice recursivamente los pasos 1-3.
A pesar de su relativa 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 el resultado óptimo en su conjunto. Considere, por ejemplo, la siguiente cadena: "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 (siempre que cada carácter esté codificado con 4 bits), y usando el algoritmo de Shannon-Fano 4*2+2+4+4+3+3+3=27 bits. El volumen de mensajes disminuyó en un 32,5%, pero a continuación se muestra que este resultado puede mejorar significativamente.

Codificación con árboles de Huffman

El algoritmo de codificación de Huffman, desarrollado unos años después del algoritmo de Shannon-Fano, también tiene la propiedad de prefijo y, además, la redundancia mínima comprobada, esta es la razón de su distribución extremadamente amplia. Para obtener los códigos de Huffman se utiliza el siguiente algoritmo:
1. Todos los símbolos del alfabeto se representan como nodos libres, siendo el peso del nodo proporcional a la frecuencia del símbolo en el mensaje;
2. Del conjunto de nodos libres, se seleccionan dos nodos con un 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. Los pasos 2 y 3 se repiten hasta que haya más de un nodo en la lista libre;
5. Con base en 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.

Considere el mismo ejemplo que en el caso del algoritmo de Shannon-Fano. El árbol de Huffman y los códigos recibidos 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 otra parte, cabe señalar que, debido a la popularidad del algoritmo de Huffman, actualmente existen 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 que, en la práctica, se suelen utilizar variables enteras, pero, dado que el peso de los nodos principales crece constantemente, tarde o temprano se produce 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 secantes

La codificación mediante funciones secantes es un algoritmo desarrollado por los autores que permite obtener códigos prefijos. 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 la palabra).
El literal secante es un par de valor de bit. Por ejemplo, el literal (4,1) significa que 4 bits de la palabra deben ser iguales a 1. Si la condición del literal es verdadera, 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 operación 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 permite que los mensajes se codifiquen 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, a continuación solo se describirán las ideas principales.
Supongamos que en el alfabeto utilizado existen N caracteres a_1,…,a_N, con frecuencias p_1,…,p_N, respectivamente. Entonces el algoritmo de codificación aritmética se verá así:
Como medio intervalo de trabajo, tome )