07 14 2020 Algoritmos de compresion - MatRJ08/Portafolio_DatosII GitHub Wiki
Se reduce la cantidad de bits de la información original
Tipos
Compresión sin perdida: elimina los bits redundantes
Con perdida: elimina información innecesaria
Aritmética: Los símbolos son codificados con menos bits que la forma original
Con perdida
La info original no se conserva y no puede ser regenerada
Método de compresión donde se utilizan aproximaciones inexactas para representar la info
Los buenos algoritmos hacen que el usuario no note la diferencia tan fácilmente
Se usa para audio, video e imagen
Sin perdida
Identificay elimina info redundante
No se pierde info
Ejemplos
- Huffman Code
- LZ77
- LZ78
- LZW
Huffman Code
Asigna un código binario de menor tamaño posible a símbolos que se repiten mayormente en la info original
Construye un Arbol Binario, asigna códigos a los diferentes símbolos de la representación
Los simbolos mas repetidos usan los códigos mas pequeños
Pasos
- Conteo de símbolos
- Ordenar símbolos según su probabilidad de aparecer en la representación original. Se ordena de menor a mayor
- Se seleccionan dos nodos (L,R) de la lista con la probabilidad mínima
- Se crea un nuevo nodo (F), y se acomoda en la lista según la suma de sus probabilidades
- Se puede hacer de manera que asigne un 0 a la izq y un 1 a la der. O que el algoritmo sepa que al recorrer un movimiento a la izq es 0 y der 1
- Estos pasos se repiten hasta formar un árbol con un solo padre
Los códigos se almacenan junto con los datos comprimidos
Pasos Descompresión
Lee la data comprimida moviendo a izq o derecha según sea un 1 o 0, hasta llegar a un hoja y lee la tabla con los códigos, luego se devuelve a la raíz