Compresion Flashcards
Se omite: - entropia conjunta y condicional - informacion mutua - entropia relativa - entropia cruzada
Defina complejidad de Kolmogorov
complejidad de Kolmogorov: K(x)
Sea x un string, K(x) es igual a la cantidad de bits minimos que debe tener un programa que genera x.
Defina dato aleatorio
Sea x un string, se dice que x es random/aleatorio si y sólo si K(x) = |x|. Es decir que la complejidad del string es
igual a la longitud del mismo.
Propiedades de complejidad de Kolmogorov
- K(x) ≥ 0
- K(x) ≤ |x|
- K(xy) ≤ K(x) + K(y)
- K(xy) ≥ K(x), K(y)
- K(xy) = K(yx)
- K(xx) = K(x)
- K(xy) + K(z) ≤ K(xz) + K(yz)
Defina Distancia de Kolmogorov
KD(x, y) = K(xy) − min{K(x), K(y)}
```
La normalizada:
N KD(x, y) =
K(xy) − min{K(x), K(y)})/
(max{K(x), K(y)}
~~~
Por que se dice que K(x) es intractable?
Suponiendo que K(x) es computable, se quiere un programa que genere todos los strings posibles en binario (0,1,10,11,100,101,…) hasta encontrar el primero cuya complejidad es de 200Mb para poder imprimirlo y luego
finalizar el programa.
El programa ocupa menos de 200Mb y es capaz de generar un string x cuya complejidad es mayor o igual a 200Mb y esto es un absurdo porque tendrı́amos dos
complejidades para el mismo string x (una que es menor a 200Mb, y otra que es mayor o igual a 200Mb). En consecuencia, queda demostrado que K(x) no puede existir ya que si existiera entonces nuestro este programa invalida su definición.
Como se soluciona el hecho de que K(x) es intractable?
Como K(x) es la longitud en bits del programa mas chico que genera x podemos aproximar K(x) por el mejor resultado posible de aplicar un compresor de datos a x, es decir, C(x). De esta forma, el mejor compresor posible existente hasta la fecha, permite determinar la complejidad de un string. Todas las propiedades de K(x) se mantienen con algunos cuidados especiales para C(x). En consecuencia, se puede definir la Distancia Normalizada de Compresión.
Defina Distancia normalizada de compresion.
N CD(x, y) =
C(xy) − min{C(x), C(y)}/
max{C(x), C(y)}Puede un archivo comprimirse por partes? Por que?
cuando se comprimen dos archivos concatenados x e y, los compresores aprenden del archivo x y en base a lo aprendido podrán comprimir bien o mal al archivo y. El problema que se presenta es que esto no siempre es cierto. Por ejemplo, cuando se usan compresores que trabajan por bloques, el compresor puede no aprender lo suficiente del archivo x antes de comprimir y entonces el cálculo de NCD podrı́a verse afectado. En principio se exigirá que para calcular NCD el compresor no trabaje de a bloques sino que trabaje procesando a los archivos en su totalidad.
Que es la entropia? Que representa? En que unidades se mide?
La entropia es una forma basada en probabilidades de medir la complejidad de un string o archivo, es decir, otra forma de aproximar a K(x).
La entropı́a puede entenderse de diferentes formas. Por un lado es una longitud promedio, es decir la longitud promedio en bits de los códigos usados para representar un mensaje. Por otro lado, es una medida de la cantidad de información representada en la fuente. Si queremos representar a una fuente en la menor longitud posible tenemos que minimizar su entropı́a.
Se mide en bits.
Como se define matematicamente la entropia?
La entropia se calcula como la sumatoria de productos entre la probabilidad y longitud de cada uno de los codigos posibles.
Cual es la longitud optima de un codigo?
l_i = - log2(p_i)
Es posible que un compresor pueda comprimir cualquier archivo? Justifique
Es sencillo demostrar que no existe un compresor que pueda comprimir cualquier tipo de datos y esto se logra mediante el llamado ”counting argument” o ”pigeonhole principle”. Sin perder generalidad, si existieran solo archivos de 3 bits entonces solo habrı́a 8 archivos posibles: 000,001,010,011,100,101,110 y 111. Si un compresor comprime cualquier archivo entonces podrı́a comprimir cada uno de estos archivos en 2 bits, pero solo existen 4 archivos de 2 bits: 00,01,10 y 11. Por lo tanto, dos o mas de los archivos de 3 bits se comprimen en el mismo archivo de 2 bits lo cual implica que será imposible descomprimirlos. Este argumento se extiende fácilmente a ”n” bits que es lo mismo que pensar en cualquier archivo. Existen menos archivos comprimidos que archivos posibles por lo tanto no puede haber una relación 1 a 1 entre ambos lo cual demuestra que ciertos archivos no podrı́an descomprimirse.
Otra forma simple de entender el counting argument es pensar que un algoritmo capaz de comprimir cualquier archivo puede aplicarse recursivamente a la salida del compresor de forma tal que cualquier archivo podrá quedar comprimido finalmente en un bit lo cual es totalmente absurdo.
En que se basa la compresion estadistica?
Se basa en, para un archivo, calcular cuantas veces aparece cada caracter.
Describa el problema de frecuenci cero.
Para introducir a este problema se puede analizar el siguiente ejemplo: al utilizar un modelo de orden 1 como el Huffman estático, cada caracter se codifica en función del anterior. Si el caracter anterior fuera una Q entonces es muy probable que el próximo sea una U. La primera vez que se da esta situación la probabilidad de la U será 1/256. Suponiendo que siempre luego de Q viene otra U, la segunda vez que aparezca una U su probabilidad será 2/257, luego 3/258, 4/259, etc. Dicho esto, se quiere remarcar que el compresor puede tardar mucho tiempo en aprender que la U tiene una alta probabilidad de ocurriencia en el contexto de la Q. A este problema se lo conoce como el problema de frecuencia cero ya que su origen se debe a que en el contexto Q no se puede tener caracteres con frecuencia 0 ya que si estos ocurrieran no se podrı́an representar. Al inicializar todo en frecuencia 1, el compresor necesitarı́a de un archivo muy grande para tener tiempo de aprender y comprimir eficientemente. Es decir que tanto los métodos estáticos como los dinámicos necesitan de archivos cada vez mas grandes para funcionar con un orden cada vez mayor.
El problema de frecuencia cero se puede resolver en compresores dinámicos de la forma en que lo hace el algoritmo PPMC que se verá más adelante luego de introducir el concepto de compresión aritmética.
Cual es la idea de la Compresion aritmetica?
La idea es aproxima lo mejor posible lal ong. estimada por la entropia.
Un compresor aritmético es capaz de comprimir los mensajes de una fuente en una cantidad no-entera de bits y gracias a esta capacidad los compresores aritméticos son óptimos dada una cierta distribución de probabilidades siendo los que mejor aproximan a la longitud ideal de los códigos que es − log_2 P_i .
Que es lo que determina la long. del archivo comprimido en un compresor aritmetico?
Un compresor aritmético transforma un archivo en un número en el intervalo [0, 1), la precisión de este número determina la longitud del archivo comprimido.
Que es lo que determina la long. del archivo comprimido en un compresor aritmetico?
Un compresor aritmético transforma un archivo en un número en el intervalo [0, 1), la precisión de este número determina la longitud del archivo comprimido.
Caracteristicas de PPM (Prediction by partial matching).
- usa varios modelos a la vez, siendo el primero el modelo -1, luego el 0, 1, …
- es necesario fijar un nivel maximo.
- el modelo de orden -1 tiene todos los caracteres posibles mas el EOF, y nunca se actualiza.
- la frecuancia de ESC es igual a la cantidad de caracteres que hay en el modelo.
- solamente se actualizan los modelos que se utilizan y esto se hace luego de haber comprimido cada caracter.
- es uno de los que mas comprime (suele ser el ganador para textos).
En que es imbatible la flia. LZ de compresores? Por que es importante?
En descompresion. Esto es muy importante porque uan vez que los datos estan comprimidos, su lectura es tan eficiente que puede llegar a casi no haber diferencia entre leerlo comprimido o descomprimido, lo que significa que en lectura no hay degradacion de performance en tiempo de lectura, teniendo el beneficio de haber optimizado el aspecto espacial de almacenamiento.
Explique LZ77.
En LZSS se usa un bit para distinguir repeticiones de no-repeticiones. Cada vez que se comprime un caracter del archivo se busca hacia atrás hasta una cierta cantidad máxima de caracteres llamada ventana en busca de repeticiones. Si se encuentra una repetición entonces se emite un bit en 1 seguido de la posición de la repetición en la ventana y la longitud de la misma. Cuando no se encuentran repeticiones se emite un bit en 0 y luego el caracter en cuestión en 8 bits (es decir, sin comprimir).
Es LZ77 adecuado para aproximar la complejidad de un string?
Notar que las limitaciones en el tamaño de la máxima longitud representable y el tamaño de la ventana hacen que LZSS no sea un compresor adecuado para aproximarnos a la complejidad de un string y por lo tanto no es usable en el cálculo de la distancia normalizada de compresión. (LZMA sı́ lo es y pertenece a la misma familia que LZSS).
Que parametros hay que ajustar en LZ77?
En principio entonces hay que fijar dos parámetros: la longitud de la ventana en la que se buscan las repeticiones y la longitud mı́nima de un match (podrı́a no tener sentido buscar matches de longitud 1).
Explique lazy parsing en LZ77 y sus consecuencias.
El mecanismo de parsing de LZSS es de tipo ”lazy” es decir que siempre que se encuentra un match lo reemplazamos por un offset y una longitud. Curiosamente esto no siempre es óptimo ya que podrı́a ser mejor ignorar un match para luego poder encontrar un match mas largo.
Explique Deflate.
Tambien conocido como LzHuf, deflate modela el archivo de igual forma que LZ77, o sea que se basa en matches, y codifica las posiciones y tamanos de los matches.
La codificación del modelo es lo que cambia en DEFLATE. Para empezar se utiliza un árbol de Huffman dinámico en donde conviven los 256 caracteres posibles y además todas las longitudes posibles desde LMIN hasta LMAX. Este árbol se utilizará para codificar los caracteres literales cuando no hay un match y para las longitudes cuando hay un match. Cada vez que se emite un caracter literal hay que actualizar el árbol incrementando su frecuencia. Cuando hay un match se emite su longitud en base al código de la misma en el árbol y a continuación su posición en la ventana en una cierta cantidad de bits que se puede fijar mediante otro árbol de Huffman o bien de forma fija. Luego, se actualiza la frecuencia de la longitud en el árbol y se sigue comprimiendo el resto de los caracteres.
