Codificación Shannon-Fano
¿Qué es el método de Shannon?
Se refiere a la probabilidad de aparición de cada símbolo en un mensaje, básicamente se utiliza para la compresión de datos.
Un poco de historia
Este método de codificación fue desarrollado por Claude Shannon en los laboratorios Bell y por Robert Fano en MIT (Massachussets Institute of Technology) en la década del 40 casi simultáneamente. La técnica fue propuesta por Claude Elwood Shannon, en “Una TeoríaMatemática de la Comunicación”, su artículo de 1948 introduciendo el campo de la teoría de la información. El método fue atribuido a Robert Fano, quien posteriormente lo publicó como uninforme técnico.
Propiedades Tablas de códigos
* Diferentes códigos, tienen diferentes tipos de bits
* Los códigos para símbolos con bajas probabilidades tienen más bits
* Los códigos para símbolos con altas probabilidades tienen menos bits
* Códigos de longitud diferente pueden ser unívocamente decodificados
¿Qué es la entropía?
* La entropía se refiere a la cantidad de bits necesarios para representar un símbolo
En un símbolo = - log2 (probabilidad)
En un mensaje = suma de la entropía de sus símbolos
Codificación de Huffman
La codificación Huffman es un algoritmo de compresión de datos sin pérdidas. La idea es asignar códigos de longitud variable a los caracteres de entrada; las longitudes de los códigos asignados se basan en las frecuencias de los caracteres correspondientes. El carácter más frecuente recibe el código más pequeño y el menos frecuente el más grande.
Los códigos de longitud variable asignados a los caracteres de entrada son códigos prefijados, lo que significa que los códigos (secuencias de bits) se asignan de tal manera que el código asignado a un carácter no es el prefijo del código asignado a cualquier otro carácter. Así es como la codificación Huffman se asegura de que no haya ambigüedad al decodificar el flujo de bits generado.
Entendamos los códigos de prefijo con un ejemplo de contador. Supongamos que hay cuatro caracteres a, b, c y d, y que sus correspondientes códigos de longitud variable son 00, 01, 0 y 1. Esta codificación provoca ambigüedad porque el código asignado a c es el prefijo de los códigos asignados a a y b. Si el flujo de bits comprimido es 0001, la salida descomprimida puede ser "cccd" o "ccb" o "acd" o "ab".
Hay principalmente dos partes principales en la codificación Huffman
1. Construir un árbol de Huffman a partir de los caracteres introducidos.
2. Recorrer el Árbol de Huffman y asignar códigos a los caracteres.
Pasos para construir el Árbol de Huffman:
La entrada es una matriz de caracteres únicos junto con su frecuencia de ocurrencia y la salida es el Árbol de Huffman.
1. Crea un nodo hoja para cada carácter único y construye un min heap de todos los nodos hoja (Min Heap se utiliza como cola de prioridad. El valor del campo de frecuencia se utiliza para comparar dos nodos en el min heap. Inicialmente, el carácter menos frecuente está en la raíz)
2. Extraer dos nodos con la frecuencia mínima del min heap.
3. Crear un nuevo nodo interno con una frecuencia igual a la suma de las frecuencias de los dos nodos. Hacer el primer nodo extraído como su hijo izquierdo y el otro nodo extraído como su hijo derecho. Añada este nodo a la pila mínima.
4. Repita los pasos#2 y #3 hasta que el montón contenga sólo un nodo. El nodo restante es el nodo raíz y el árbol está completo.
Sonríe Yahshua te ama
Comentarios
Publicar un comentario