archivo.htm

code to compress data usin huffman algorithm

<tr>
<td>
<div class="center">
<div class="thumb tnone">
<div class="thumbinner" style="width:352px;"><a href="/wiki/Imagen:Arbol_de_Huffman.svg" class="image" title="脕rbol de Huffman generado para las frecuencias de apariciones exactas del texto &quot;Esto es un ejemplo de arbol de Huffman&quot;. las frecuencias y c贸digos de cada car谩cter se muestran abajo. codificar esta frase usando este c贸digo requiere 156 bits, sin contar con el espacio para el 谩rbol."><img alt="脕rbol de Huffman generado para las frecuencias de apariciones exactas del texto &quot;Esto es un ejemplo de arbol de Huffman&quot;. las frecuencias y c贸digos de cada car谩cter se muestran abajo. codificar esta frase usando este c贸digo requiere 156 bits, sin contar con el espacio para el 谩rbol." src="http://upload.wikimedia.org/wikipedia/commons/thumb/2/2a/Arbol_de_Huffman.svg/350px-Arbol_de_Huffman.svg.png" width="350" height="121" border="0" class="thumbimage" /></a>
<div class="thumbcaption">
<div class="magnify"><a href="/wiki/Imagen:Arbol_de_Huffman.svg" class="internal" title="Aumentar"><img src="/skins-1.5/common/images/magnify-clip.png" width="15" height="11" alt="" /></a></div>
脕rbol de Huffman generado para las frecuencias de apariciones exactas del texto "Esto es un ejemplo de arbol de Huffman". las frecuencias y c贸digos de cada car谩cter se muestran abajo. codificar esta frase usando este c贸digo requiere 156 bits, sin contar con el espacio para el 谩rbol.</div>
</div>
</div>
</div>
</td>
</tr>
<tr>
<td>
<table>
<tr>
<td>
<table class="wikitable">
<tr>
<th>Car谩cter</th>
<th>Frecuencia</th>
<th>C贸digo</th>
</tr>
<tr>
<td>Espacio</td>
<td>8</td>
<td>00</td>
</tr>
<tr>
<td>E</td>
<td>6</td>
<td>100</td>
</tr>
<tr>
<td>N</td>
<td>3</td>
<td>1100</td>
</tr>
<tr>
<td>O</td>
<td>3</td>
<td>1110</td>
</tr>
<tr>
<td>U</td>
<td>3</td>
<td>0100</td>
</tr>
<tr>
<td>A</td>
<td>2</td>
<td>0101</td>
</tr>
<tr>
<td>D</td>
<td>2</td>
<td>1010</td>
</tr>
<tr>
<td>F</td>
<td>2</td>
<td>1011</td>
</tr>
<tr>
<td>L</td>
<td>2</td>
<td>0110</td>
</tr>
<tr>
<td>M</td>
<td>2</td>
<td>0111</td>
</tr>
<tr>
<td>S</td>
<td>2</td>
<td>11010</td>
</tr>
<tr>
<td>B</td>
<td>1</td>
<td>110110</td>
</tr>
<tr>
<td>H</td>
<td>1</td>
<td>110111</td>
</tr>
<tr>
<td>J</td>
<td>1</td>
<td>111100</td>
</tr>
<tr>
<td>P</td>
<td>1</td>
<td>111101</td>
</tr>
<tr>
<td>R</td>
<td>1</td>
<td>111110</td>
</tr>
<tr>
<td>T</td>
<td>1</td>
<td>111111</td>
</tr>
</table>
</td>
</tr>
</table>
</td>
</tr>
</table>
</div>
<p>En <a href="/wiki/Ciencias_de_la_computaci%C3%B3n" title="Ciencias de la computaci贸n">ciencias de la computaci贸n</a> y <a href="/wiki/Teor%C3%ADa_de_la_informaci%C3%B3n" title="Teor铆a de la informaci贸n">teor铆a de la informaci贸n</a>, la <i>codificaci贸n Huffman</i> es un <a href="/wiki/Algoritmo" title="Algoritmo">algoritmo</a> usado para <a href="/wiki/Compresi%C3%B3n_de_datos" title="Compresi贸n de datos">compresi贸n de datos</a>. El t茅rmino se refiere al uso de una tabla de c贸digos de longitud variable para codificar un determinado s铆mbolo (como puede ser un car谩cter en un archivo), donde la tabla ha sido rellenada de una manera espec铆fica bas谩ndose en la probabilidad estimada de aparici贸n de cada posible valor de dicho s铆mbolo. Fue desarrollado por <a href="/wiki/David_A._Huffman" title="David A. Huffman">David A. Huffman</a> mientras era estudiante de doctorado en el <a href="/wiki/MIT" title="MIT" class="mw-redirect">MIT</a>, y publicado en "A Method for the Construction of Minimum-Redundancy Codes". Huffman se hizo miembro del claustro del MIT tras su graduaci贸n y posteriormente fue miembro fundador del Departamento de ciencias de la computaci贸n en la <a href="/wiki/Universidad_de_California,_Santa_Cruz" title="Universidad de California, Santa Cruz">Universidad de California, Santa Cruz</a>.</p>
<p>La codificaci贸n Huffman usa un m茅todo espec铆fico para elegir la representaci贸n de cada s铆mbolo, que da lugar a un <a href="/wiki/C%C3%B3digo_prefijo" title="C贸digo prefijo">c贸digo prefijo</a> (es decir, la cadena de bits que representa a un s铆mbolo en particular nunca es prefijo de la cadena de bits de un s铆mbolo distinto) que representa los caracteres m谩s comunes usando las cadenas de bits m谩s cortas, y viceversa. Huffman fue capaz de dise帽ar el m茅todo de compresi贸n m谩s eficiente de este tipo: ninguna representci贸n alternativa de un conjunto de s铆mbolos de entrada produce una salida media m谩s peque帽a cuando las frecuencias de los s铆mbolos cocinciden con las usadas para crear el c贸digo. posteriormente se encontr贸 un m茅todo para llevar esto a cabo en un tiempo lineal si las probabilidades de los s铆mbolos de entrada (tambi茅n conocidas como "pesos") est谩n ordenadas.</p>
<p>Para un grupo de s铆mbolos con una distribuci贸n de probabilidad uniforme y un n煤mero de miembros que es potencia de dos, la codificaci贸n Huffman es equivalente a una codificaci贸n en bloque binaria, por ejemplo, la codificaci贸n <a href="/wiki/ASCII" title="ASCII">ASCII</a>. La codificaci贸n Huffman es un m茅todo para crear c贸digos prefijo tan extendido que el t茅rmino "codificaci贸n Huffman" es ampliamente usado como sin贸nimo de "c贸digo prejijo", incluso cuando dicho c贸digo no se ha producido con el algoritmo de Huffman.</p>
<p>Aunque la codificaci贸n de Huffman es 贸ptima para una codificaci贸n s铆mbolo a s铆mbolo dada una distribuci贸n de probabilidad, su optimalidad a veces puede verse accidentalmente exagerada. Por ejemplo, la codificaci贸n aritm茅tica y la codificaci贸n <a href="/wiki/LZW" title="LZW">LZW</a> normalmente ofrecen mayor capacidad de compresi贸n. Estos dos m茅todos pueden agrupar un n煤mero arbitrario de s铆mbolos para una codificaci贸n m谩s eficiente, y, en general, se adaptan a las estad铆sticas de entrada reales, y este 煤ltimo es 煤til cuando las probabilidades no se conocen de forma precisa o var铆an sinificativamente dentro del flujo de datos.</p>
<p><a name="Historia" id="Historia"></a></p>
<h2><span class="editsection">[<a href="/w/index.php?title=Codificaci%C3%B3n_Huffman&amp;action=edit&amp;section=2" title="Editar secci贸n: Historia">editar</a>]</span> <span class="mw-headline">Historia</span></h2>
<p>En 1951, a David Huffman y sus compa帽eros de clase de la asignatura 鈥淭eor铆a de la Informaci贸n鈥