alf.htm

来自「code to compress data usin huffman algor」· HTM 代码 · 共 224 行 · 第 1/2 页

<ol>
<li>Se crean varios 谩rboles, uno por cada uno de los s铆mbolos del alfabeto, consistiendo cada uno de los 谩rboles en un nodo sin hijos, y etiquetado cada uno con su s铆mbolo asociado y su frecuencia de aparici贸n.</li>
<li>Se toman los dos 谩rboles de menor frecuencia, y se unen creando un nuevo 谩rbol. La etiqueta de la ra铆z ser谩 la suma de las frecuencias de las ra铆ces de los dos 谩rboles que se unen, y cada uno de estos 谩rboles ser谩 un hijo del nuevo 谩rbol. Tambi茅n se etiquetan las dos ramas del nuevo 谩rbol: con un 0 la de la izquierda, y con un 1 la de la derecha.</li>
<li>Se repite el paso 2 hasta que s贸lo quede un 谩rbol.</li>
</ol>
<p>Con este 谩rbol se puede conocer el c贸digo asociado a un s铆mbolo, as铆 como obtener el s铆mbolo asociado a un determinado c贸digo.</p>
<p>Para obtener el c贸digo asociado a un s铆mbolo se debe proceder del siguiente modo:</p>
<ol>
<li>Comenzar con un c贸digo vac铆o</li>
<li>Iniciar el recorrido del 谩rbol en la hoja asociada al s铆mbolo</li>
<li>Comenzar un recorrido del 谩rbol hacia arriba</li>
<li>Cada vez que se suba un nivel, a帽adir al c贸digo la etiqueta de la rama que se ha recorrido</li>
<li>Tras llegar a la ra铆z, invertir el c贸digo</li>
<li>El resultado es el c贸digo Huffman deseado</li>
</ol>
<p>Para obtener un s铆mbolo a partir de un c贸digo se debe hacer as铆:</p>
<ol>
<li>Comenzar el recorrido del 谩rbol en la ra铆z de 茅ste</li>
<li>Extraer el primer s铆mbolo del c贸digo a descodificar</li>
<li>Descender por la rama etiquetada con ese s铆mbolo</li>
<li>Volver al paso 2 hasta que se llegue a una hoja, que ser谩 el s铆mbolo asociado al c贸digo</li>
</ol>
<p>En la pr谩ctica, casi siempre se utiliza el 谩rbol para obtener todos los c贸digos de una sola vez; luego se guardan en tablas y se descarta el 谩rbol.</p>
<p><a name="Ejemplo_de_uso" id="Ejemplo_de_uso"></a></p>
<h3><span class="editsection">[<a href="/w/index.php?title=Algoritmo_de_Huffman&amp;action=edit&amp;section=2" title="Editar secci贸n: Ejemplo de uso">editar</a>]</span> <span class="mw-headline">Ejemplo de uso</span></h3>
<p>La tabla describe el alfabeto a codificar, junto con las frecuencias de sus s铆mbolos. En el gr谩fico se muestra el 谩rbol construido a partir de este alfabeto siguiendo el algoritmo descrito.</p>
<div class="thumb tright">
<div class="thumbinner" style="width:182px;"><a href="/wiki/Imagen:ArbolCodigoHuffman.png" class="image" title="脕rbol para construir el c贸digo Huffman del ejemplo"><img alt="脕rbol para construir el c贸digo Huffman del ejemplo" src="http://upload.wikimedia.org/wikipedia/commons/thumb/d/d8/ArbolCodigoHuffman.png/180px-ArbolCodigoHuffman.png" width="180" height="157" border="0" class="thumbimage" /></a>
<div class="thumbcaption">
<div class="magnify"><a href="/wiki/Imagen:ArbolCodigoHuffman.png" class="internal" title="Aumentar"><img src="/skins-1.5/common/images/magnify-clip.png" width="15" height="11" alt="" /></a></div>
脕rbol para construir el c贸digo Huffman del ejemplo</div>
</div>
</div>
<table class="prettytable">
<tr>
<th>S铆mbolo</th>
<th>Frecuencia</th>
</tr>
<tr>
<td>A</td>
<td>0,15</td>
</tr>
<tr>
<td>B</td>
<td>0,30</td>
</tr>
<tr>
<td>C</td>
<td>0,20</td>
</tr>
<tr>
<td>D</td>
<td>0,05</td>
</tr>
<tr>
<td>E</td>
<td>0,15</td>
</tr>
<tr>
<td>F</td>
<td>0,05</td>
</tr>
<tr>
<td>G</td>
<td>0,10</td>
</tr>
</table>
<p>Se puede ver con facilidad cu谩l es el c贸digo del s铆mbolo <b>E</b>: subiendo por el 谩rbol se recorren ramas etiquetadas con <b>1</b>, <b>1</b> y <b>0</b>; por lo tanto, el c贸digo es <b>011</b>. Para obtener el c贸digo de <b>D</b> se recorren las ramas <b>0</b>, <b>1</b>, <b>1</b> y <b>1</b>, por lo que el c贸digo es <b>1110</b>.</p>
<p>La operaci贸n inversa tambi茅n es f谩cil de realizar: dado el c贸digo <b>10</b> se recorren desde la ra铆z las ramas <b>1</b> y <b>0</b>, obteni茅ndose el s铆mbolo <b>C</b>. Para descodificar <b>010</b> se recorren las ramas <b>0</b>, <b>1</b> y <b>0</b>, obteni茅ndose el s铆mbolo <b>A</b>.</p>
<div class="visualClear"></div>
<p><a name="Limitaciones" id="Limitaciones"></a></p>
<h2><span class="editsection">[<a href="/w/index.php?title=Algoritmo_de_Huffman&amp;action=edit&amp;section=3" title="Editar secci贸n: Limitaciones">editar</a>]</span> <span class="mw-headline">Limitaciones</span></h2>
<p>Para poder utilizar el algoritmo de Huffman es necesario conocer de antemano las frecuencias de aparici贸n de cada s铆mbolo, y su eficiencia depende de lo pr贸ximas a las frecuencias reales que sean las estimadas. Algunas implementaciones del algoritmo de Huffman son <a href="/wiki/Algoritmos_Adaptativos" title="Algoritmos Adaptativos" class="mw-redirect">adaptativas</a>, actualizando las frecuencias de cada s铆mbolo conforme recorre el texto.</p>
<p>La eficiencia de la codificaci贸n de Huffman tambi茅n depende del balance que exista entre los hijos de cada nodo del 谩rbol, siendo m谩s eficiente conforme menor sea la diferencia de frecuencias entre los dos hijos de cada nodo.</p>
<p><b>Ejemplos:</b></p>
<ul>
<li>La <a href="/wiki/Sistema_binario" title="Sistema binario">codificaci贸n binaria</a> es un caso particular de la codificaci贸n de Huffman que ocurre cuando todos los s铆mbolos del alfabeto tienen la misma frecuencia. Se tiene pues que la codificaci贸n binaria es la m谩s eficiente para cualquier n煤mero de s铆mbolos equiprobables.</li>
<li>El algoritmo de Huffman aplicado sobre un alfabeto de dos s铆mbolos asignar谩 siempre un 1 al primero y un 0 al segundo, independientemente de la frecuencia de aparici贸n de dichos s铆mbolos. En este caso nunca se realiza compresi贸n de los datos, mientras que otros algoritmos s铆 podr铆an conseguirlo.</li>
</ul>
<p>Una manera de resolver este problema consiste en agrupar los s铆mbolos en palabras antes de ejecutar el algoritmo. Por ejemplo, si se tiene la cadena de longitud 64</p>
<pre>
 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB
</pre>
<p>El algoritmo de Huffman aplicado 煤nicamente a los s铆mbolos devuelve el c贸digo:</p>
<pre>
 1111111111111111111111111111111111111111111111111111111111111110
</pre>
<p>Tambi茅n de longitud 64. Sin embargo, si antes de utilizar el algoritmo, se agrupan los s铆mbolos en las palabras <b>"AA"</b>, <b>"AB"</b> y <b>"B"</b> (que se codifican como 1, 01 y 00), el algoritmo devuelve la siguiente cadena:</p>
<pre>
 111111111111111111111111111111101
</pre>
<p>que tiene longitud 32, la mitad que si no se hubiera agrupado. Si observa el 谩rbol de Huffman, se puede comprobar que la diferencia de frecuencias entre las ramas del 谩rbol es menor que en el caso anterior.</p>
<p><a name="Variaciones_del_algoritmo" id="Variaciones_del_algoritmo"></a></p>
<h2><span class="editsection">[<a href="/w/index.php?title=Algoritmo_de_Huffman&amp;action=edit&amp;section=4" title="Editar secci贸n: Variaciones del algoritmo">editar</a>]</span> <span class="mw-headline">Variaciones del algoritmo</span></h2>
<p><a name="C.C3.B3digos_Huffman_n-arios" id="C.C3.B3digos_Huffman_n-arios"></a></p>
<h3><span class="editsection">[<a href="/w/index.php?title=Algoritmo_de_Huffman&amp;action=edit&amp;section=5" title="Editar secci贸n: C贸digos Huffman n-arios">editar</a>]</span> <span class="mw-headline">C贸digos Huffman <i>n</i>-arios</span></h3>
<p>Es posible crear c贸digos de Huffman ternarios, cuaternarios, y, en general, <i>n</i>-arios. Para ello s贸lo es necesario realizar dos modificaciones al algoritmo:</p>
<ol>
<li>Los 谩rboles a crear tendr谩n tantos hijos como s铆mbolos posibles puedan aparecer en los c贸digos Huffman. Por ejemplo, si es ternario se crear谩n 谩rboles con tres hijos; si es cuaternario, con cuatro.</li>
<li>Si se expresa como <i>s</i> el n煤mero de s铆mbolos en el alfabeto a codificar, y <i>n</i> el n煤mero de s铆mbolos que aparecen en el c贸digo Huffman, entonces <i>s</i>-1 debe ser m煤ltiplo de <i>n</i>-1. Es decir, para un c贸digo ternario, <i>s</i> debe valer 3, 5, 7, etc. Si esta condici贸n no se cumple, entonces se deben a帽adir s铆mbolos "nulos" con frecuencia 0, que servir谩n s贸lo como relleno a la hora de construir el 谩rbol.</li>
</ol>
<p><a name="V.C3.A9ase_tambi.C3.A9n" id="V.C3.A9ase_tambi.C3.A9n"></a></p>
<h2><span class="editsection">[<a href="/w/index.php?title=Algoritmo_de_Huffman&amp;action=edit&amp;section=6" title="Editar secci贸n: V茅ase tambi茅n">editar</a>]</span> <span class="mw-headline">V茅ase tambi茅n</span></h2>
<ul>
<li><a href="/wiki/Codificaci%C3%B3n_Huffman" title="Codificaci贸n Huffman">Codificaci贸n Huffman</a></li>
<li><a href="http://mmengineer.blogspot.com/2007/11/algoritmo-de-compresion-huffman-php.html" class="external text" title="http://mmengineer.blogspot.com/2007/11/algoritmo-de-compresion-huffman-php.html" rel="nofollow">Huffman en PHP.</a></li>
</ul>
<p><a name="Referencias" id="Referencias"></a></p>
<h2><span class="editsection">[<a href="/w/index.php?title=Algoritmo_de_Huffman&amp;action=edit&amp;section=7" title="Editar secci贸n: Referencias">editar</a>]</span> <span class="mw-headline">Referencias</span></h2>
<div class="listaref references-small">
<ol class="references">
<li id="cite_note-0"><a href="#cite_ref-0" title="">鈫