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 .
