Compresion de datos

Introducción:

Datos → Procesamiento → Información

Dato = característica (dimensión) + valor (medida) || Información = datos interpretados.

La información toma valores entre 0 y 1 → probabilidad p de recibir información i.

Dentro de una fuente F, recibimos el símbolo Fi, que tenía probabilidad pi → I (F = Fi) = - log(pi) → para calcular la entropía hay que tener en cuenta labase en la que se quieren representar los caracteres (generalmente en base 2, por lo que hay que tomar el -log2(pi)).

Si se tiene mucha información sobre algo, el peso de información sobre eso, es bajo.
n
La entropia es el peso de toda fuente F → H (F) = pi * I (F = Fi)
i = 1

Entropía: la entropía se puede considerar como la cantidad de información promedioque contienen los símbolos usados. Los símbolos con menor probabilidad son los que aportan mayor información; por ejemplo, si se considera como sistema de símbolos a las palabras en un texto, palabras frecuentes como "que", "el", "a" aportan poca información, mientras que palabras menos frecuentes como "corren", "niño", "perro" aportan más información. Si de un texto dado borramos un "que",seguramente no afectará a la comprensión y se sobreentenderá, no siendo así si borramos la palabra "niño" del mismo texto original. Cuando todos los símbolos son igualmente probables (distribución de probabilidad plana), todos aportan información relevante y la entropía es máxima.


Algoritmos de Codificación
- Son algoritmos para modificar la representación de una fuente.
- La representaciónresultante es sin pérdida de información.
- Generan códigos prefijos.
- Para permitir la descompresión pueden necesitar información de control extra.

Clasificación según la forma de reconocer la redundancia
1)- Estadísticos
1.1)- Algoritmo de Huffman
1.2)- Algoritmo aritmético
2)- No estadísticos
2.1)- Algoritmo Lz77
2.2)- Algoritmo Lz78/W
3)- Predictores
3.1)- Algoritmo Aritmético deOrden mayor a 0
3.2)- Algoritmo PPMC
4)- Híbridos
4.1)- Half coding
4.2)- LZHuff
4.3)- LZP

Clasificación según la forma de procesar los datos
- Estático
- Dinámico

1)- Estadísticos:

1.1)- Algoritmo de Huffman (estadístico):
- Árbol de generación de códigos.
- Los códigos son de longitud variable.
- El camino desde la raiz hacia las hojas define el código que reemplazará alcaracter.
- Se generan en función de las veces que aparece un caracter en el archivo (frecuencia); cuanto más aparece, más cerca de la raíz está y códigos más cortos de reemplazo tiene para ahorrar más espacio.
- Como se basa en la frecuencia solamente, es un compresor Estadístico.









A = 000, B = 001, C = 01, D = 1
En el árbol anterior, la letra que más aparece es la D, y laque menos aparece es la A (código más corto y más largo respectivamente).


1.1.1)- Método estático: la tabla de frecuencia de simbolos, debe almacenarse en el archivo para la descompresión.
- Se utiliza una lista con par (simbolo,frecuencia), ordenada por frecuencia.
- Se unen los nodos con menor frecuencia, para generar el nodo padre.
- El nodo padre que se cree en cada paso, tendrá comohijo izquierdo al primero de la lista y derecho al segundo.
- En caso de tener la misma frecuencia, los de menor cantidad de agrupados van primeros en la tabla; en caso de tener la misma cantidad de agrupados, por orden alfabético.

Comprimir y descomprimir: F (fuente) = JERRYRICE

Codificación: C = 010 | E = 00 | I = 011 | J = 100 | R = 11 | Y = 101
Representación:100-00-11-11-101-11-011-010-00 → (9 * 8) = 72 bits representados en 22 bits (igualmente falta sumar lo que ocupa la tabla) → es bueno para archivos grandes.
La entropia en este caso es: J: 1 * (-log2 (1/9)) + E: 2 * (-log2 (2/9)) + R: 3 * (-log2 (3/9)) +
Y: 1 * (-log2 (1/9)) + I: 1 * (-log2 (1/9)) + C: 1 * (-log2 (1/9)) = 21, 76 bits.

Para recuperar la fuente, el descompresor debe armar el mismo árbol a partir...