Tabla de Contenidos

Ejercicios Compresión

  1. Defina los tipos de fuente que conoce según la naturaleza con la que es generada y con la relación entre los mensajes emitidos.
    • ¿Qué significa que una fuente es aleatoria?
    • ¿Qué significa que una fuente es estructurada?
    • Ejemplifique una fuente estructurada y una NO estructurada.
  2. Defina lo que entiende por código.
  3. ¿Cuándo un código es decodificable?
  4. Dado el siguiente esquema de codificación: 
    a=0
b=01
c=10

    Indique si un mensaje codificado por este esquema es decodificable. En caso de no serlo, dé un ejemplo de porqué no se cumple la decodificación.

  5. Supongamos ahora que al esquema anterior asignamos c=11.¿Es decodificable un mensaje, codificado por este nuevo esquema? ¿Qué problemática aparece aquí?
  6. Defina un esquema sencillo, donde cualquier mensaje pueda ser decodicado luego de codicarse, unívocamente.
  7. Enuncie la denfiición de entropía, en qué unidades se mide y dé su fórmula. Luego calcule la entropía de la siguiente fuente: 
    solonosotrospodemosliberarnuestrasmentes

    

  8. ¿Qué longitud debe cumplir al menos cualquier código? (Pista: Pensar en la definición de entropía)
  9. Dado un alfabeto de <tex>l_0,l_1,...,l_{n-1}</tex> donde el cardinal del alfabeto es <tex>N</tex>, <tex>C_n</tex> es el código prefijo correspondiente al caracter <tex>A_n</tex>, y <tex>L_n</tex> la longitud de <tex>C_n</tex>, se define la desigualdad de Kraft como: <tex> \sum_{i=0}^{n} 2^{-L_i} \leq 1 </tex>. Se demuestra que si un código cumple esta desigualdad, el mismo es prefijo.
    • De un ejemplo de un código donde no se cumpla la desigualdad y uno donde sí.
    • Dada la desigualdad de Kraft y además sabiendo la longitud mínima que debe cumplir un código (analizado en un ej. anterior), demuestre que un código es decodificable sólo si su longitud es mayor o igual que a la determinada por la entropía. (Pista: suponer que debemos agregar a longitud i-ésima, una longitud extra, llamada <tex>le_i</tex> y considerar para cada <tex>i</tex>, la misma longitud extra)
  10. ¿Es cierto que si se intenta comprimir una fuente aleatoria, ningún compresor Run Length obtendrá buenos resultados?

Huffman

  1. Dada la siguiente fuente: 
    pepitalapistolera
    • Calcule su entropía.
    • Comprimala y descomprimala con Huffman estático.
    • Compare lo calculado en a) con la cantidad de bits de b) y saque conclusiones.
  2. Sabiendo que la emisión de bits de una compresión realizada por un compresor Huffman Estático y su tabla son la siguientes: 
    Emisión: 01-110-101-111-00-100-111-110-01-00
Caracter Frecuencia
a 2
d 2
e 2
l 2
r 1
u 1

Descomprima la fuente, considerando que el orden de emisión fue 0 a izquierda y 1 a derecha y que el orden de los nodos hojas de izquierda a derecha es el siguiente: e-l-r-u-a-d.

  1. Dada la siguiente fuente: 
    pepitalapistolera
    • Calcule su entropía.
    • Comprimala y descomprimala con Huffman Dinámico.
    • Compare lo calculado en a) con la cantidad de bits de b) y saque conclusiones. Compare con el método estático.
  2. Utilizando el método de Huffman efuciente realice lo siguiente:
    • Comprima la fuente del inciso anterior.
    • Compare la cantidad de actualizaciones del árbol contra los 2 métodos anteriores, considerando cómo actualización del árbol, redistribución de sus nodos y no actualización de meta data.
    • Compare el resultado final contra la entropía de la fuente.
  3. Proponga si existe una fuente en donde:
    • Human estático comprime mejor que Huffman dinámico.
    • Human dinámico comprime mejor que Huffman dinámico.

Nota: Recuerde que para el caso de Huffman estático se debe considerar la tabla de frecuencias.

  1. Dada la siguiente fuente: 
    NOCOMPRARDOLARES
    • Comprima la misma con el método Estático.
    • Comprima la misma con el método Dinámico.
    • Comprima la misma con el método Dinámico eficiente.

Responda: ¿Cuál método elegiría, justificando su respuesta, para comprimir dicha fuente en tiempo real? Nota: Si decide no realizar algún ítem o paso justique porque no lo realiza y no lo haga.

Aritmético

  1. Dada la siguiente fuente: BAABCA
    • Calcule su entropía.
    • Comprímala y descomprímala con aritmético estático, utilizando precisión de: 8 bits, 3 bits, 2 bits.
    • ¿Cuál de las 3 precisiones es mejor? ¿Es esto siempre así? ¿Por qué?
    • Compare lo calculado en a) con la cantidad de bits de b) y saque conclusiones.
    • Compare contra compresión de Huffman estático.
  2. Responda V o F y justique.
    • Aritmético estático comprime siempre mejor que Human estático.
    • Los algoritmos puramente estadísticos mejoran el nivel de compresión cuanta más localidad tienen los datos de entrada.
  3. Dada la siguiente fuente: 'And when you gonna get some food Your brother got to be your enemy'
    • Comprimala y descomprimila con aritmético dinámico, utilizando precisión de 8 bits. (Considere achicar el diccionario de letras)
  4. Dada la fuente que contiene todos los caracteres del abecedario, en orden, indique que modo de compresor, comprimirá mejor, dinámico o estático.
  5. Indique los distintos modos de terminar compresión de un compresor aritmético (tanto dinámico como estático).
  6. Indique algorítmicamente, la descompresión de un compresor aritmético.
  7. Indique que significan los términos overflow y underflow. ¿Puede suceder que luego de resolver uno de ellos, suceda el otro o el mismo nuevamente? Ejemplique.

Lz77

  1. Explique su funcionamiento y responda:
    • ¿Cuáles son sus parámetros de ajuste?
    • ¿Cuáles son sus limitaciones?
  2. ¿En qué casos es bueno aplicarlo?
  3. Dada la siguiente fuente: AADAAABCDABCBCDAA
    • Calcule su entropía.
    • Comprímala y descomprímala con LZ, utilizando una ventana de 6 bytes donde:
      • 2 bytes corresponden a memoria y 4 bytes a inspección.
      • 3 bytes corresponden a memoria y 3 bytes a inspección.
      • 4 bytes corresponden a memoria y 2 bytes a inspección.
    • ¿Cuál de las 3 conguraciones es mejor? ¿Es esto siempre así? ¿Por qué?
    • Compare lo calculado en a) con la cantidad de bits de b) y saque conclusiones.
  4. Responda V o F y justique. En caso de ser F de un contraejemplo.
    • LZ77 comprime siempre mejor que el aritmético dinámico.
    • LZ77 comprime siempre peor que el aritmético estático.

Lz78

  1. Dada la siguiente fuente: PEP/PERSON/PEPERS/PERT
    • Calcule su entropía.
    • Comprímala y descomprímala con LZW.
    • ¿Por qué no es necesario guardar la tabla terminado el proceso de compresión?
    • Describa cuál es el caso particular de descompresión y cómo se resuelve.
    • ¿En qué consiste el método de clearing? ¿Es aplicable en este ejemplo? ¿Por qué?
  2. Descomprima con LZW lo siguiente: 
    A B 257 258 C 260

Aritmético dinámico

  1. Indique la principal problemática de trabajar con ordenes (referida al uso de recursos).
  2. Dada la fuente: 'SASASASASASASASABOOOORR', comprímala con Aritmético O(2).
  3. Descomprima la fuente del inciso anterior.
  4. Un día alguien le sugiere que para mejorar la distribución de probabilidades al comprimir, le conviene aumentar el órden. ¿Que respondería usted?

PPMC

  1. Dada la siguiente fuente: 
    REDEMPTIONSONG

    comprímala utilizando PPMC de O(2)(Sólo tabla).

  2. Descomprima la fuente del inciso anterior (Sólo tabla).
  3. Agregue al primer inciso, la emisión de bits con el aritmético, hasta que crea entender el proceso.
  4. Descomprima la emisión de bits, hasta que crea entender el proceso.
  5. Aumente el orden de compresión y verifique el exceso de ESC (máximo hasta O(8)).
  6. (Venenoso) Dado un PPMC de orden, con exclusión y EOF, realice lo siguiente:
    • Encuentre una fórmula para que la emisión de probabilidades de una fuente de N caracteres, que cumple que siempre se repite el mismo caracter (Fuente Ej: AAAAA, N=5).
    • Encuentre una fórmula, para la emisión de probabilidades de una fuente de N caracteres(dónde <tex>N</tex> es el abcedario completo), que cumple que están presentes todas las letras del abcedario una única vez en la fuente(Fuente Ej:ABCDE, N=5).
    • Encuentre una fórmula para la emisión de probabilidades de una fuente de N caracteres, dónde el abcedario a utilizar tiene un cardinal K y la fuente cumple que se dan los K caracteres al principio de la compresión(en cualquier orden), tal Que hay un match solo en ctx-1 y desde <tex>K+1</tex>, todos los matchs se dan en ctx0(Fuente Ej: FORTLAUDERDALE, K=9 y N=14).