Examen Parcial - 75.06. Organización de Datos

Cátedra: Servetto
Fecha: Segundo Cuatrimestre 2008
Día: 04/03/2009
Módulo: Compresión

Responder Verdadero o Falso, justificando en ambos casos la respuesta:

1. La exclusión en PPMC predice qué símbolos es improbable que ocurran. Un símbolo excluído será un símbolo que se predice que no ocurra, pero si falla la predicción y ocurre, se deberán emitir bits extra.
2. Si se intenta comprimir una fuente aleatoria, ningún compresor Run Length obtendrá buenos resultados.
3. Si se intenta comprimir una fuente aleatoria, ningún compresor obtendrá buenos resultados salvo que se le aplique un pre-procesamiento como BS+MTF, que mejorará la entropía del archivo y eso permitirá que algunos compresores aprovechen esta mejora para comprimir más.
4. El algoritmo MTF no obtiene buenos resultados para archivos con mala localidad.
5. Los algoritmos puramente estadísticos mejoran el nivel de compresión cuanta más localidad tienen los datos de entrada.
6. Para iguales datos de entrada, el nivel de compresión alcanzado por Huffman estático es siempre peor que el nivel de compresión alcanzado por un compresor aritmético estático de orden 0.

Comprimir “ALALALASARAS” con LZ78, suponiendo que en la compresión no hace falta hacer clearing. Mostrar la descompresión y explicar los pasos de ésta.

Explique los pasos para realizar una compresión de Huffman con el manejo eficiente del árbol. Dé un ejemplo.