Saltar a contenido

Compresión

Definición: alfabeto

Un alfabeto es un conjunto de símbolos. Por ejemplo:

  • \(\texttt{\{A, B, C, D\}}\)
  • \(\texttt{\{0, 1\}}\)
  • \(\texttt{\{} \spades, \hearts, \diamonds, \clubs\texttt{\}}\)

Definición: cadena

Una cadena es una secuencia de símbolos de un alfabeto. Por ejemplo:

  • \(\texttt{ABACADA}\)
  • \(\texttt{011011000001}\)
  • \(\hearts\hearts\diamonds\spades\)

Introducción

  1. Queremos almacenar una cadena de longitud \(n\) sobre el alfabeto \(\texttt{\{A, B, C, D\}}\). ¿Cuántos bits vamos a necesitar?
Solución

El alfabeto está formado por 4 símbolos. Por lo tanto, podemos codificar cada símbolo usando 2 bits (\(\texttt{A} \to \texttt{00}\), \(\texttt{B} \to \texttt{01}\), \(\texttt{C} \to \texttt{10}\), \(\texttt{D} \to \texttt{11}\)). Así, una cadena de \(n\) símbolos necesitará \(2n\) bits.

  1. Una cadena de longitud \(n\) sobre un alfabeto de \(k\) símbolos se puede codificar con \(n \times \lceil \log_2 k \rceil\) bits. ¿Por qué?
Solución

Con \(b\) bits se pueden formar \(2^b\) cadenas distintas. El menor \(b\) entero tal que \(2^b > k\) es \(\lceil \log_2 k \rceil\) bits. Por lo tanto, con \(n \times \lceil \log_2 k \rceil\) bits se puede codificar una cadena de longitud \(n\).

  1. Este método básico no es óptimo. ¿Por qué?
Solución

Si el número de símbolos del alfabeto (\(k\)) no es una potencia de 2, \(\lceil \log_2 k \rceil\) bits dan lugar a más de \(k\) combinaciones. Es decir, estamos usando más bits de los estrictamente necesarios.

Run-length encoding (RLE)

  1. Codifica con el método básico la cadena \(\texttt{CCCCCCABDCCCCCCCCC}\).
Solución

Con la regla anterior, \(\texttt{101010101010000111101010101010101010}\).

RLE

La mayoría de cadenas que encontramos en el mundo real tienen baja entropía, es decir, contienen secuencias predecibles o repeticiones. Esto se puede aprovechar para desarrollar métodos de codificación más eficientes.

Un ejemplo es RLE, en el que se añade un conteo a cada letra, lo que permite acortar las secuencias repetidas. Usando bloques de 6 bits, los cuatro primeros indicarán el número de veces que aparece el símbolo, mientras que los últimos dos bits indicarán el símbolo. Así, la secuencia \(\texttt{AAA}\) se codificará como \(\texttt{0011-00}\).

  1. Descodifica la cadena \(\texttt{010101001111}\) usando RLE.
Solución

\(\texttt{BBBBBDDD}\)

  1. Codifica la secuencia del ejercicio 4 usando RLE. ¿Es más o menos eficiente que el método básico?
Solución

\(\texttt{0110-10 0001-00 0001-01 0001-11 1001-10}\)

Este método usa 30 bits, mientras que antes usamos 36.

  1. Escribe una cadena en el alfabeto \(\texttt{\{A, B, C, D\}}\) que requiera \(n\) bits con el método básico, pero menos de \(n/2\) bits usando RLE.
Solución

Por ejemplo, la cadena de longitud 15 \(\texttt{AAA}\cdots\texttt{AAA}\), formada únicamente por el símbolo \(\texttt{A}\). Requiere 30 bits con el método básico, pero solamente 6 con RLE: \(\texttt{1111-00}\).

  1. Escribe una cadena en el alfabeto \(\texttt{\{A, B, C, D\}}\) que requiera \(n\) bits con el método básico, pero más de \(2n\) bits usando RLE.
Solución

Por ejemplo, la cadena \(\texttt{ABCD}\) requiere 8 bits con el método básico y 6 · 4 = 24 con RLE.

  1. ¿Cuándo es RLE más eficiente que el método básico y cuándo lo es menos?
Solución

RLE es más eficiente cuando hay secuencias largas formadas por el mismo caracter, mientras que el método básico es más eficiente cuando no hay repeticiones. Más concretamente (y suponiendo que no hay ninguna secuencia de más de 15 símbolos iguales consecutivos) RLE necesita \(6m\) bits, donde \(m\) es el número de bloques de letras (por ejemplo, \(\texttt{AAAABBDCCC}\) tiene 4 bloques). En cambio, cualquier cadena de longitud \(n\) necesita \(2n\) bits con el método básico. Siempre que \(6m<2n\), RLE será más eficiente, y viceversa.

  1. ¿Cómo podemos mejorar RLE para que los símbolos no repetidos no ocupen tanto espacio?
Solución

Una posible solución es la siguiente:

  • Codificar símbolos únicos directamente: \(\texttt{ABCD}\) se convierte en \(\texttt{00 01 10 11}\)
  • Indicar secuencias más largas con dos copias del símbolo y la longitud de la secuencia: \(\texttt{BBBBB}\) se convierte en \(\texttt{01 01 0101}\)

Así, el descodificador, siempre que encontrara dos símbolos iguales seguidos, sabría que los 4 bits siguientes indican la longitud de la secuencia.

  1. Dada la cadena \(\texttt{DCBA-DCBA-CDCDCDCD-DCBA-DCBA}\):

    • ¿Cuántos bits son necesarios para codificarla con el método básico?
    • ¿Y con RLE?
    • ¿Y con RLE modificado?
Solución
  • Método básico: \(2 \times 24 = 48\) bits
  • RLE: \(6 \times 23 = 138\) bits (hay dos \(\texttt{D}\) seguidas)
  • RLE modificado: \(2 \times 22 + 6 \times 1 = 50\) bits

Un paso más allá…

Aunque la cadena del ejemplo anterior contiene repeticiones evidentes (\(\texttt{DCBA}\), \(\texttt{CD}\)), los algoritmos que hemos visto hasta ahora no son capaces de aprovecharlas, ya que solo pueden usar repeticiones de un mismo símbolo, pero no de subsecuencias.

Códigos LZ

La familia de códigos LZ1 pueden aprovechar subsecuencias repetidas para comprimir una cadena. Son la base de la mayoría de algoritmos de compresión modernos como DEFLATE, usado en los formatos ZIP, PNG y gzip.

La idea fundamental en estos algoritmos es representar subsecuencias repetidas como punteros a partes anteriores de la cadena. Los punteros tiene la forma \(\texttt{<p,l>}\), donde \(\texttt{p}\) es la posición de la cadena y \(\texttt{l}\) su longitud.

Ejemplo

La cadena \(\texttt{ABRACADABRA}\) se puede codificar como \(\texttt{ABRACAD<7,4>}\). El puntero \(\texttt{<7,4>}\) dice que debemos buscar 7 posiciones hacia atrás y copiar 4 símbolos desde esa posición.

Un detalle importante

El puntero hace referencia a la cadena descodificada, no a la codificada. Esto permite usar códigos como \(\texttt{A<1,9>}\), que se descodificaría como \(\texttt{AAAAAAAAAA}\). Piensa que la cadena descodificada se escribe símbolo a símbolo y se lee de la misma manera.

  1. Codifica usando este método.

    • \(\texttt{AAAAABBBBCCCDD}\)
    • \(\texttt{ABACADAEA}\)
    • \(\texttt{ABCBCBBCBCB}\)
    • \(\texttt{ABBABAABBAABABBA}\)
    • \(\texttt{DCBA-DCBA-CDCDCDCD-DCBA-DCBA}\)
Solución

Suponiendo que un puntero solo es eficiente si \(l > 1\), tenemos:

  • \(\texttt{A<1,4>B<1,3>C<1,2>DD}\)
  • \(\texttt{ABACADAEA}\) (la única repetición son las \(\texttt{A}\))
  • \(\texttt{ABC<2,3><5,5>}\)
  • \(\texttt{ABBABAAB<4,4><12,4>}\) (habría que ver cuál es la longitud mínima para la que resulta más eficiente usar un puntero que escribir directamente)
  • Una primera compresión nos daría \(\texttt{DCBA<4,8>CD<2,6>DCBA<4,8>}\). Pero podemos aprovechar que el final es idéntico al principio y lograr una mayor compresión: \(\texttt{DCBA<4,8>CD<2,6><16,8>}\).

  1. Descodifica:

    • \(\texttt{ABCD<4,4>}\)
    • \(\texttt{ACB<3,7>}\)
    • \(\texttt{B<1,4>CB<2,5>}\)
    • \(\texttt{B<1,4>C<2,6>}\)
    • \(\texttt{D<1,3>ACB<4,7><12,5>}\)
Solución
  • \(\texttt{ABCDABCD}\)
  • \(\texttt{ACBACBACBA}\)
  • \(\texttt{BBBBBCBCBCBC}\)
  • \(\texttt{BBBBBCBCBCBC}\)
  • \(\texttt{DDDDACBDACBDACDDACB}\)

RLE \(\subset\) LZ

LZ es una generalización del método RLE que vimos anteriormente. LZ puede comprimir cualquier repetición de un mismo símbolo, pero además permite comprimir repeticiones de subsecuencias. Lo que antes codificamos como \(\texttt{00-1001}\) es lo mismo que \(\texttt{A<1,9>}\).

Faltan detalles…

Faltaría analizar cómo representar en binario una cadena comprimida con LZ. Es decir, cómo representar los símbolos \(\texttt{<}\), \(\texttt{>}\) o la coma. También faltaría analizar el algoritmo de compresión que convierte una cadena sobre un alfabeto en una cadena binaria comprimida con LZ.

Códigos Huffman

Como vimos en el problema 2, si usamos el alfabeto \(\texttt{\{A, B, C, D, E\}}\), podemos codificar cualquier cadena de longitud \(n\) usando \(3n\) bits, ya que con 3 bits podemos representar \(2^3=8\) combinaciones distintas. Pero solo necesitamos representar 5 símbolos, así que de algún modo estamos desperdiciando bits.

v2

Podemos mejorar esta codificación así:

  • \(\texttt{A} \to \texttt{00}\)
  • \(\texttt{B} \to \texttt{01}\)
  • \(\texttt{B} \to \texttt{10}\)
  • \(\texttt{D} \to \texttt{110}\)
  • \(\texttt{E} \to \texttt{111}\)
  1. Codifica la secuencia \(\texttt{CABDECE}\) y descodifica \(\texttt{110011001111}\).
Solución
  • \(\texttt{CABDECE} \to \texttt{10 00 01 110 111 10 111}\)
  • \(\texttt{110011001111} = \texttt{110 01 10 01 111} \to \texttt{DBCBE}\)
  1. ¿Cuántos bits por símbolo usa de media este método?
Solución
\[ \frac{2+2+2+3+3}{5} = \frac{12}{5} = 2{,}4 \]

v3

Considera ahora esta codificación:

  • \(\texttt{A} \to \texttt{00}\)
  • \(\texttt{B} \to \texttt{01}\)
  • \(\texttt{B} \to \texttt{10}\)
  • \(\texttt{D} \to \texttt{110}\)
  • \(\texttt{E} \to \texttt{11}\)
  1. ¿En qué cambia con respecto al anterior? Descodifica la cadena \(\texttt{1100110}\). ¿Qué observas?
Solución

El código para \(\texttt{E}\) pasa a ser \(\texttt{11}\). El problema es que ahora el código para \(\texttt{E}\) está contenido en el código para \(\texttt{D}\), lo que genera ambigüedad. ¡La cadena puede dar lugar a dos resultados distintos! Todo depende de cómo agrupemos los bits:

  • \(\texttt{110 01 10} \to \texttt{DBC}\)
  • \(\texttt{11 00 110} \to \texttt{EAD}\)

Árboles binarios

La codificación anterior (v2) se puede visualizar como un árbol binario completo, es decir, un árbol en el que cada nodo tiene 0 o 2 hijos.

graph TD
    R((" ")) --0--> L0((" "))
    R --1--> R0((" "))
    L0 --0--> L1[A]
    L0 --1--> R1[B]
    R0 --0--> L3[C]
    R0 --1--> R3((" "))
    R3 --0--> L5[D]
    R3 --1--> R5[E]

Definición: codificación prefijo

Una codificación prefijo o sin prefijos (prefix-free) es aquella en la que ningún símbolo tiene un código que sea prefijo de otro. (Por ejemplo, v2 es una codificación sin prefijos, mientras que v3 no lo es.)

  1. Demuestra que un árbol binario completo siempre genera una codificación prefijo.
Solución

Los códigos corresponden a hojas del árbol, es decir, a nodos sin hijos.

  1. Descodifica \(\texttt{110111001001110110}\) usando el árbol anterior.
Solución

\(\texttt{110 111 00 10 01 110 110} \to \texttt{DEACBDD}\)

  1. Codifica \(\texttt{ABDECBE}\) usando el árbol. ¿Cuántos bits ahorramos comparado con un esquema básico de 3 bits por símbolo?
Solución

Se obtiene \(\texttt{00 01 110 111 10 01 111}\) y ahorramos 4 bits, uno por cada \(\texttt{D}\) o \(\texttt{E}\).

  1. Antes hemos usado 18 bits para codificar \(\texttt{DEACBDD}\). Esto ya es una mejora frente a los \({3 \times 7 = 21}\) bits que necesitaría una codificación básica. Diseña un árbol que codifique la cadena de forma aún más eficiente, es decir, usando menos de 18 bits.
Solución

La idea clave es asignar un código corto a los símbolos más frecuentes, en este caso la \(\texttt{D}\). Así, podemos intercambiar las posiciones de \(\texttt{D}\) y \(\texttt{A}\) en el árbol anterior, lo que nos dará un código de longitud \(2+3+3+2+2+2+2=16\) bits: \(\texttt{00 111 110 10 01 00 00}\).

graph TD
    R((" ")) --0--> L0((" "))
    R --1--> R0((" "))
    L0 --0--> L1[D]
    L0 --1--> R1[B]
    R0 --0--> L3[C]
    R0 --1--> R3((" "))
    R3 --0--> L5[A]
    R3 --1--> R5[E]

Otra posibilidad es desequilibrar el árbol, dando a \(\texttt{D}\) un código de 1 bit. Con este árbol necesitamos solamente \(1+3+3+3+3+1+1=15\) bits: \(\texttt{0 111 100 110 101 0 0}\).

graph TD
    R((" ")) --0--> L0[D]
    R --1--> R0((" "))
    R0 --0--> L3((" "))
    R0 --1--> R3((" "))
    L3 --0--> L4[A]
    L3 --1--> R4[B]    
    R3 --0--> L5[C]
    R3 --1--> R5[E]
  1. Ahora haz lo contrario y diseña un árbol que codifique la cadena \(\texttt{DEACBDD}\) de manera menos eficiente.
Solución

La \(\texttt{D}\) es el símbolo más frecuente, así que colocándolo al fondo del árbol se obtiene un código poco eficiente. En este caso, la cadena codificada requeriría \(4+4+1+3+2+4+4=22\) bits: \(\texttt{1110 1111 0 110 10 1110 1110}\).

graph TD
    R((" ")) --0--> L0[A]
    R --1--> R0((" "))
    R0 --0--> L1[B]
    R0 --1--> R1((" "))
    R1 --0--> L2[C]
    R1 --1--> R2((" "))
    R2 --0--> L3[D]
    R2 --1--> R3[E]

Buscar la eficiencia

Construir una codificación sin prefijos es fácil, pero hallar la codificación más eficiente para un mensaje dado es más complicado.

Referencias

  1. Los algoritmos de compresión sin pérdida LZ77 y LZ78 fueron creados por Abraham Lempel y Jacob Ziv en 1977 y 1978. Posteriormente, estos algoritmos han servido de base para variantes como LZW, LZSS, LZMA y otros. ↩