====== Ejercicios Compresión ====== - 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. - Defina lo que entiende por **código**. - ¿Cuándo un código es decodificable? - 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. - Supongamos ahora que al esquema anterior asignamos c=11.¿Es decodificable un mensaje, codificado por este nuevo esquema? ¿Qué problemática aparece aquí? - Defina un esquema sencillo, donde cualquier mensaje pueda ser decodicado luego de codicarse, unívocamente. - 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 - ¿Qué longitud debe cumplir al menos cualquier código? (Pista: Pensar en la definición de entropía) - Dado un alfabeto de l_0,l_1,...,l_{n-1} donde el cardinal del alfabeto es N, C_n es el código prefijo correspondiente al caracter A_n, y L_n la longitud de C_n, se define la **desigualdad de Kraft** como: \sum_{i=0}^{n} 2^{-L_i} \leq 1 . 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 le_i y considerar para cada i, la misma longitud extra) - ¿Es cierto que si se intenta comprimir una fuente aleatoria, ningún compresor Run Length obtendrá buenos resultados? ===== Huffman ===== - 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. - 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. - 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. - 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. - 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. - 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 ===== - 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. - 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. - 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) - Dada la fuente que contiene todos los caracteres del abecedario, en orden, indique que modo de compresor, comprimirá mejor, dinámico o estático. - Indique los distintos modos de terminar compresión de un compresor aritmético (tanto dinámico como estático). - Indique algorítmicamente, la descompresión de un compresor aritmético. - 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 ===== - Explique su funcionamiento y responda: * ¿Cuáles son sus parámetros de ajuste? * ¿Cuáles son sus limitaciones? - ¿En qué casos es bueno aplicarlo? - 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. - 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 ===== - 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é? - Descomprima con LZW lo siguiente: A B 257 258 C 260 ===== Aritmético dinámico ===== - Indique la principal problemática de trabajar con ordenes (referida al uso de recursos). - Dada la fuente: 'SASASASASASASASABOOOORR', comprímala con Aritmético O(2). - Descomprima la fuente del inciso anterior. - 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 ===== - Dada la siguiente fuente: REDEMPTIONSONG comprímala utilizando PPMC de O(2)(Sólo tabla). - Descomprima la fuente del inciso anterior (Sólo tabla). - Agregue al primer inciso, la emisión de bits con el aritmético, hasta que crea entender el proceso. - Descomprima la emisión de bits, hasta que crea entender el proceso. - Aumente el orden de compresión y verifique el exceso de ESC (máximo hasta O(8)). - (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 N 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 K+1, todos los matchs se dan en ctx0(Fuente Ej: FORTLAUDERDALE, K=9 y N=14).