Codigos de huffman
Páginas: 13 (3206 palabras)
Publicado: 3 de febrero de 2011
TRABAJO PRACTICO FINAL
Materia: Comunicaciones
Temas a desarrollar:
Códigos de Huffman.
Fundamentos teóricos
Construcción
Aplicaciones.
Alumno: Soledad Paolina
Introducción
En ciencias de la computación y teoría de la información, el código de Huffman es un algoritmo utilizado para la compresión de datos. Fue desarrollado por David A. Huffman[1] mientras era estudiantede doctorado en el Instituto Tecnológico de Massachusetts (MIT), y publicado en "A Method for the Construction of Minimum Redundancy Codes" en el año 1952.
El código de Huffman, también conocido como “codificación Huffman”, puede ser usado en casi cualquier aplicación, ya que es un sistema válido para la compresión y posterior transmisión de cualquier dato en formato digital, pudiendo aplicarsea faxes, modems, redes de computadoras y televisión.
Códigos de Huffman
Concepto del Algoritmo
Este algoritmo le asigna secuencias binarias (códigos) a los símbolos de un alfabeto de forma tal de utilizar la menor cantidad de bits posibles.
El algoritmo de Huffman define un código variable para cada carácter sin la necesidad de utilizar un código prefijo. De esta manera es posible queaquellos caracteres que son mas frecuentes dentro de un alfabeto se codifiquen con la menor cantidad de bits posibles mientras que aquellos que no sean tan frecuentes podrán tener una codificación un poco mas amplia, pero siempre tendiendo a ser la menor posible. Es obvio pensar que en el alfabeto del lenguaje castellano la letra a es usada con mucha mas frecuencia que la letra x. Este conceptose optimizaría si en lugar de aplicarlo a un alfabeto se aplicara a cada texto en particular, es decir, conocer con exactitud cuantas veces se repite un carácter dentro del texto para, de esa manera, darle un código variable que sea el menor posible para aquellos que se repitan con mayor frecuencia y, a medida que sea necesario, utilizar mas bits para codificar un carácter que la frecuencia con queel carácter se usa en el texto sea menor.
Para ello, Huffman hace uso de una tabla de frecuencias donde se guardan los caracteres empleados en el texto y la cantidad de veces que son utilizados y de un árbol binario como estructura de datos.
Fundamentos teóricos
Una de las formas de transmitir mensajes es transmitir en su lugar secuencias de símbolos. Si hay mayor cantidad de mensajes aser enviados que símbolos disponibles algunos mensajes deberán utilizar más de un símbolo. Si se asume que cada símbolo requiere la misma cantidad de tiempo para su transmisión, entonces el tiempo de transmisión (longitud) de un mensaje es directamente proporcional a la cantidad de símbolos asociados a él. En adelante, la secuencia de símbolos asociados a un determinado mensaje será llamada“código de mensaje”, la cantidad total de mensajes a transmitir será denominada “colección de mensajes” y al acuerdo entre transmisor y emisor con respecto al significado del código para cada mensaje de la colección será “colección de código”.
Para formalizar los requerimientos de una colección de código (es decir un mensaje que pueda ser interpretado tanto por transmisor como por receptor), lossímbolos codificados seran representados por números. Por lo tanto, si hay D tipos diferentes de símbolos a ser utilizados en la codificación estarán representados por 0, 1, 2..., (D-1). Por ejemplo, un código ternario se construirá utilizando los tres dígitos 0, 1 y 2 como símbolos codificadores.
Siendo N el número de mensajes en la colección y P(i) la probabilidad del mensaje ith, entonces:
[pic]La longitud de un mensaje, L(i), es el número de dígitos de código asignados a él. Por lo tanto la longitud promedio de un mensaje es:
[pic]
Huffman considero 2 restricciones básicas para una colección de código:
a) No habrá dos mensajes con igual combinación de dígitos.
b) Los códigos de mensaje serán construidos de manera tal que no será necesario agregar información...
Materia: Comunicaciones
Temas a desarrollar:
Códigos de Huffman.
Fundamentos teóricos
Construcción
Aplicaciones.
Alumno: Soledad Paolina
Introducción
En ciencias de la computación y teoría de la información, el código de Huffman es un algoritmo utilizado para la compresión de datos. Fue desarrollado por David A. Huffman[1] mientras era estudiantede doctorado en el Instituto Tecnológico de Massachusetts (MIT), y publicado en "A Method for the Construction of Minimum Redundancy Codes" en el año 1952.
El código de Huffman, también conocido como “codificación Huffman”, puede ser usado en casi cualquier aplicación, ya que es un sistema válido para la compresión y posterior transmisión de cualquier dato en formato digital, pudiendo aplicarsea faxes, modems, redes de computadoras y televisión.
Códigos de Huffman
Concepto del Algoritmo
Este algoritmo le asigna secuencias binarias (códigos) a los símbolos de un alfabeto de forma tal de utilizar la menor cantidad de bits posibles.
El algoritmo de Huffman define un código variable para cada carácter sin la necesidad de utilizar un código prefijo. De esta manera es posible queaquellos caracteres que son mas frecuentes dentro de un alfabeto se codifiquen con la menor cantidad de bits posibles mientras que aquellos que no sean tan frecuentes podrán tener una codificación un poco mas amplia, pero siempre tendiendo a ser la menor posible. Es obvio pensar que en el alfabeto del lenguaje castellano la letra a es usada con mucha mas frecuencia que la letra x. Este conceptose optimizaría si en lugar de aplicarlo a un alfabeto se aplicara a cada texto en particular, es decir, conocer con exactitud cuantas veces se repite un carácter dentro del texto para, de esa manera, darle un código variable que sea el menor posible para aquellos que se repitan con mayor frecuencia y, a medida que sea necesario, utilizar mas bits para codificar un carácter que la frecuencia con queel carácter se usa en el texto sea menor.
Para ello, Huffman hace uso de una tabla de frecuencias donde se guardan los caracteres empleados en el texto y la cantidad de veces que son utilizados y de un árbol binario como estructura de datos.
Fundamentos teóricos
Una de las formas de transmitir mensajes es transmitir en su lugar secuencias de símbolos. Si hay mayor cantidad de mensajes aser enviados que símbolos disponibles algunos mensajes deberán utilizar más de un símbolo. Si se asume que cada símbolo requiere la misma cantidad de tiempo para su transmisión, entonces el tiempo de transmisión (longitud) de un mensaje es directamente proporcional a la cantidad de símbolos asociados a él. En adelante, la secuencia de símbolos asociados a un determinado mensaje será llamada“código de mensaje”, la cantidad total de mensajes a transmitir será denominada “colección de mensajes” y al acuerdo entre transmisor y emisor con respecto al significado del código para cada mensaje de la colección será “colección de código”.
Para formalizar los requerimientos de una colección de código (es decir un mensaje que pueda ser interpretado tanto por transmisor como por receptor), lossímbolos codificados seran representados por números. Por lo tanto, si hay D tipos diferentes de símbolos a ser utilizados en la codificación estarán representados por 0, 1, 2..., (D-1). Por ejemplo, un código ternario se construirá utilizando los tres dígitos 0, 1 y 2 como símbolos codificadores.
Siendo N el número de mensajes en la colección y P(i) la probabilidad del mensaje ith, entonces:
[pic]La longitud de un mensaje, L(i), es el número de dígitos de código asignados a él. Por lo tanto la longitud promedio de un mensaje es:
[pic]
Huffman considero 2 restricciones básicas para una colección de código:
a) No habrá dos mensajes con igual combinación de dígitos.
b) Los códigos de mensaje serán construidos de manera tal que no será necesario agregar información...
Leer documento completo
Regístrate para leer el documento completo.