{"id":16733,"date":"2022-08-23T12:52:10","date_gmt":"2022-08-23T11:52:10","guid":{"rendered":"https:\/\/complex-systems-ai.com\/?page_id=16733"},"modified":"2022-09-06T10:37:53","modified_gmt":"2022-09-06T09:37:53","slug":"codage-de-huffman","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/algoritmico\/huffman-codificacion\/","title":{"rendered":"Codificaci\u00f3n Huffman"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"16733\" class=\"elementor elementor-16733\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-8126e71 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"8126e71\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-c21415e\" data-id=\"c21415e\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-968936c elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"968936c\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Algor\u00edtmico<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-bf10e73\" data-id=\"bf10e73\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-883d283 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"883d283\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/es\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Pagina de inicio<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-c0fbf73\" data-id=\"c0fbf73\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-f73e561 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"f73e561\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/fr.wikipedia.org\/wiki\/Codage_de_Huffman\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-b0b416e elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"b0b416e\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-a782604\" data-id=\"a782604\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-6395dbe elementor-widget elementor-widget-heading\" data-id=\"6395dbe\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contenido<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Tabla de contenido alternativo\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Palanca<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewbox=\"0 0 24 24\" version=\"1.2\" baseprofile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/huffman-codificacion\/#Codage-de-Huffman\" >Codificaci\u00f3n Huffman<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/huffman-codificacion\/#Arbre-de-Huffman\" >\u00e1rbol de huffman<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/huffman-codificacion\/#Algorithme-de-Huffman\" >algoritmo de Huffman<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/huffman-codificacion\/#Codage-et-decodage\" >Codificaci\u00f3n y decodificaci\u00f3n<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/huffman-codificacion\/#Exemple\" >Ejemplo<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/huffman-codificacion\/#Correction-de-lexemple\" >Correcci\u00f3n del ejemplo<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Codage-de-Huffman\"><\/span>Codificaci\u00f3n Huffman<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-02f1ea2 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"02f1ea2\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-c5e7056\" data-id=\"c5e7056\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-e7766a0 elementor-widget elementor-widget-text-editor\" data-id=\"e7766a0\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p><span style=\"font-weight: 400;\">La codificaci\u00f3n Huffman es un m\u00e9todo ampliamente utilizado en la compresi\u00f3n de datos. Se utiliza para codificar un texto en binario, utilizando para cada letra un n\u00famero de bits en funci\u00f3n del n\u00famero de veces que aparece la letra: cuanto m\u00e1s aparece la letra, menor es el n\u00famero de bits. Por lo tanto, el n\u00famero total de bits utilizados para codificar el texto se reduce en comparaci\u00f3n con la codificaci\u00f3n ASCII est\u00e1ndar que utiliza ocho bits para cada letra.<\/span><\/p><p><span style=\"font-weight: 400;\">Cuando se trata de transmitir informaci\u00f3n en un canal no ruidoso, el objetivo prioritario es minimizar el tama\u00f1o de la representaci\u00f3n de la informaci\u00f3n: este es el problema de la compresi\u00f3n de datos. El c\u00f3digo de Huffman (1952) es un c\u00f3digo \u00f3ptimo de longitud variable, es decir tal que la longitud media de un texto codificado es m\u00ednima. Se observan as\u00ed reducciones de tama\u00f1o del orden de 20 a 90%.<\/span><\/p><p><span style=\"font-weight: 400;\">El c\u00f3digo binario asociado con cada letra est\u00e1 definido por un <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/arboles-y-arboles\/\">\u00e1rbol binario<\/a>. Las hojas del \u00e1rbol corresponden a las letras del alfabeto. Los nodos internos no contienen informaci\u00f3n. El camino tomado para llegar a una hoja desde la ra\u00edz define el c\u00f3digo de la letra en esta hoja: izquierda 0, derecha 1. Por ejemplo:<\/span><\/p><p><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter wp-image-16736 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman1.png\" alt=\"codificaci\u00f3n huffman \u00e1rbol huffman codificaci\u00f3n decodificaci\u00f3n\" width=\"735\" height=\"188\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman1.png 735w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman1-300x77.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman1-18x5.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman1-600x153.png 600w\" sizes=\"(max-width: 735px) 100vw, 735px\" \/><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-81a4fc5 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"81a4fc5\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-adc2dcf\" data-id=\"adc2dcf\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-2357e1c elementor-widget elementor-widget-heading\" data-id=\"2357e1c\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Arbre-de-Huffman\"><\/span>\u00e1rbol de huffman<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-db488cd elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"db488cd\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-8979d98\" data-id=\"8979d98\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-2440e15 elementor-widget elementor-widget-text-editor\" data-id=\"2440e15\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p><span style=\"font-weight: 400;\">Cuando se conoce el texto a codificar, es posible optimizar el \u00e1rbol binario utilizado para acortar los c\u00f3digos de las letras m\u00e1s frecuentes. Esto es lo que hace el algoritmo de Huffman: comienza contando el n\u00famero de ocurrencias de cada car\u00e1cter en el texto. Por ejemplo, en la oraci\u00f3n:<\/span><\/p><p><img decoding=\"async\" class=\"alignnone wp-image-16737 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman2.png\" alt=\"codificaci\u00f3n huffman \u00e1rbol huffman codificaci\u00f3n decodificaci\u00f3n\" width=\"753\" height=\"126\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman2.png 753w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman2-300x50.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman2-18x3.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman2-600x100.png 600w\" sizes=\"(max-width: 753px) 100vw, 753px\" \/><\/p><p><span style=\"font-weight: 400;\">A partir de estas frecuencias, el algoritmo inicializa un \u00e1rbol por car\u00e1cter, teniendo como peso el n\u00famero de apariciones del car\u00e1cter:<\/span><\/p><p><img decoding=\"async\" class=\"alignnone wp-image-16738 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman3.png\" alt=\"codificaci\u00f3n huffman \u00e1rbol huffman codificaci\u00f3n decodificaci\u00f3n\" width=\"746\" height=\"84\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman3.png 746w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman3-300x34.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman3-18x2.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman3-600x68.png 600w\" sizes=\"(max-width: 746px) 100vw, 746px\" \/><\/p><p><span style=\"font-weight: 400;\">En cada iteraci\u00f3n, el algoritmo selecciona los dos \u00e1rboles con los pesos m\u00e1s bajos y los ensambla para formar los dos hijos de un \u00e1rbol binario cuyo peso es la suma de los dos \u00e1rboles. Cuando se atan varios \u00e1rboles por el menor peso, el \u00e1rbol seleccionado entre ellos puede ser cualquiera. As\u00ed, en la primera iteraci\u00f3n, podr\u00edamos obtener:<\/span><\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-16739 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman4.png\" alt=\"codificaci\u00f3n huffman \u00e1rbol huffman codificaci\u00f3n decodificaci\u00f3n\" width=\"727\" height=\"117\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman4.png 727w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman4-300x48.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman4-18x3.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman4-600x97.png 600w\" sizes=\"(max-width: 727px) 100vw, 727px\" \/><\/p><p><span style=\"font-weight: 400;\">y despu\u00e9s de cuatro iteraciones m\u00e1s:<\/span><\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-16740 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman5.png\" alt=\"codificaci\u00f3n huffman \u00e1rbol huffman codificaci\u00f3n decodificaci\u00f3n\" width=\"758\" height=\"155\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman5.png 758w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman5-300x61.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman5-18x4.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman5-600x123.png 600w\" sizes=\"(max-width: 758px) 100vw, 758px\" \/><\/p><p><span style=\"font-weight: 400;\">Cuando solo queda un \u00e1rbol, el algoritmo ha terminado.<\/span><\/p><p><span style=\"font-weight: 400;\">Aqu\u00ed hay un ejemplo de construcci\u00f3n del \u00e1rbol de Huffman para comprender mejor el proceso. En este ejemplo hemos colocado las letras en orden ascendente a diferencia del ejemplo anterior:<\/span><\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-16742 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman7.png\" alt=\"codificaci\u00f3n huffman \u00e1rbol huffman codificaci\u00f3n decodificaci\u00f3n\" width=\"360\" height=\"775\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman7.png 360w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman7-139x300.png 139w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman7-6x12.png 6w\" sizes=\"(max-width: 360px) 100vw, 360px\" \/><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-47c5910 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"47c5910\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-af6146f\" data-id=\"af6146f\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-292d0a1 elementor-widget elementor-widget-heading\" data-id=\"292d0a1\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Algorithme-de-Huffman\"><\/span>algoritmo de Huffman<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-ea54251 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"ea54251\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-6a4d639\" data-id=\"6a4d639\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-ddb578a elementor-widget elementor-widget-text-editor\" data-id=\"ddb578a\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p><span style=\"font-weight: 400;\">M\u00e1s formalmente, el algoritmo de Huffman es el siguiente:<\/span><\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-16741 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman6.png\" alt=\"codificaci\u00f3n huffman \u00e1rbol huffman codificaci\u00f3n decodificaci\u00f3n algoritmo huffman\" width=\"742\" height=\"381\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman6.png 742w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman6-300x154.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman6-18x9.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman6-600x308.png 600w\" sizes=\"(max-width: 742px) 100vw, 742px\" \/><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-66f00e5 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"66f00e5\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-05023d2\" data-id=\"05023d2\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-32eeef9 elementor-widget elementor-widget-heading\" data-id=\"32eeef9\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Codage-et-decodage\"><\/span>Codificaci\u00f3n y decodificaci\u00f3n<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-682052f elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"682052f\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-c819f50\" data-id=\"c819f50\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-f3e8ff6 elementor-widget elementor-widget-text-editor\" data-id=\"f3e8ff6\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p><span style=\"font-weight: 400;\">Podemos reescribir el \u00e1rbol en forma de matriz. La codificaci\u00f3n de una letra est\u00e1 ligada al camino recorrido en el \u00e1rbol hasta la letra deseada. Tome la siguiente tabla:<\/span><\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-16743 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman8.png\" alt=\"\" width=\"703\" height=\"67\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman8.png 703w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman8-300x29.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman8-18x2.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman8-700x67.png 700w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman8-600x57.png 600w\" sizes=\"(max-width: 703px) 100vw, 703px\" \/><\/p><p><span style=\"font-weight: 400;\">Este tipo de c\u00f3digo se dice prefijo, lo que significa que ning\u00fan c\u00f3digo es el prefijo de otro (el c\u00f3digo de A es 10 y ning\u00fan otro c\u00f3digo comienza con 10, el c\u00f3digo de B es 001 y ning\u00fan otro c\u00f3digo no comienza con 001 ). Esta propiedad permite que los caracteres se separen sin ambig\u00fcedades.<\/span><\/p><p><span style=\"font-weight: 400;\">Atenci\u00f3n, aqu\u00ed todo lleva a creer que la tabla propuesta no es la \u00f3ptima. De hecho, hay 8 caracteres, por lo que usando binario, podr\u00edamos usar 3 bits para codificar todos los caracteres (2^<\/span><span style=\"font-weight: 400;\">3<\/span><span style=\"font-weight: 400;\"> = 8 posibilidades).\u00a0<\/span><\/p><p><span style=\"font-weight: 400;\">Aqu\u00ed, la suma de los bits de letras codificados es 2+3+3+4+2+4+4+4 = 26 bits, o un promedio de 26\/8 = 3,25 bits por car\u00e1cter. Pero en realidad lo que contar\u00e1 no es la media, sino la media ponderada en frecuencia como veremos en el ejercicio de ejemplo.<\/span><\/p><p><span style=\"font-weight: 400;\">Usando la matriz, es posible codificar un mensaje (aqu\u00ed el + es una concatenaci\u00f3n):<\/span><\/p><p><span style=\"font-weight: 400;\">CACHE=000+10+000+1111+01=00010000111101.<\/span><\/p><p><span style=\"font-weight: 400;\">Por tanto, tenemos un mensaje de 14 bits en lugar de 5*3=15 bits, lo que corresponde a una reducci\u00f3n de memoria para el almacenamiento de texto de (15-14)\/15 = 6,61 TP2T. Aunque en promedio la codificaci\u00f3n es m\u00e1s grande, \u00a1de hecho tenemos una reducci\u00f3n en el espacio de memoria utilizado!<\/span><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-c3663ab elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"c3663ab\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-4f6625c\" data-id=\"4f6625c\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-2d81e45 elementor-widget elementor-widget-heading\" data-id=\"2d81e45\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exemple\"><\/span>Ejemplo<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-5347db7 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"5347db7\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-61c76c9\" data-id=\"61c76c9\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-ba76fe0 elementor-widget elementor-widget-text-editor\" data-id=\"ba76fe0\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p><span style=\"font-weight: 400;\">1) Buscamos codificar cada letra de este alfabeto mediante una secuencia de d\u00edgitos binarios.<\/span><\/p><p><span style=\"font-weight: 400;\">a) Cuantos bits se necesitan para codificar cada una de las 8 letras del alfabeto.<\/span><\/p><p><span style=\"font-weight: 400;\">b) \u00bfCu\u00e1l es la longitud en bytes de un mensaje de 1000 caracteres basado en este alfabeto?<\/span><\/p><p><span style=\"font-weight: 400;\">2) Proporcione un c\u00f3digo de tama\u00f1o fijo para cada car\u00e1cter del alfabeto de 8 letras.<\/span><\/p><p><span style=\"font-weight: 400;\">3) Consideremos ahora la siguiente codificaci\u00f3n, siendo variable la longitud del c\u00f3digo de cada car\u00e1cter.<\/span><\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-16743 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman8.png\" alt=\"\" width=\"703\" height=\"67\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman8.png 703w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman8-300x29.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman8-18x2.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman8-700x67.png 700w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman8-600x57.png 600w\" sizes=\"(max-width: 703px) 100vw, 703px\" \/><\/p><p><span style=\"font-weight: 400;\">a) Utilizando la tabla anterior, dar el c\u00f3digo de mensaje: CACHE.<\/span><\/p><p><span style=\"font-weight: 400;\">b) Cu\u00e1l es el mensaje correspondiente al c\u00f3digo 001101100111001.<\/span><\/p><p><span style=\"font-weight: 400;\">4) En un texto, cada uno de los 8 caracteres tiene un n\u00famero diferente de ocurrencias. Esto se resume en la siguiente tabla, construida a partir de texto de 1000 caracteres.<\/span><\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-16744 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman9.png\" alt=\"codificaci\u00f3n huffman \u00e1rbol huffman codificaci\u00f3n decodificaci\u00f3n\" width=\"700\" height=\"64\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman9.png 700w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman9-300x27.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman9-18x2.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman9-600x55.png 600w\" sizes=\"(max-width: 700px) 100vw, 700px\" \/><\/p><p><span style=\"font-weight: 400;\">a) Usando el c\u00f3digo de tama\u00f1o fijo propuesto en la pregunta 2, \u00bfcu\u00e1l es la longitud en bits del mensaje que contiene los 1000 caracteres enumerados en la tabla anterior?<\/span><\/p><p><span style=\"font-weight: 400;\">b) Usando el c\u00f3digo de la pregunta 3, \u00bfcu\u00e1l es la longitud del mismo mensaje en bits?<\/span><\/p><p>5) <span style=\"font-weight: 400;\">Realiza el \u00e1rbol de Huffman optimizando el espacio de memoria. Vuelva a hacer las preguntas 3 y 4 con el nuevo \u00e1rbol.<\/span><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-17c74d5 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"17c74d5\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-53f5399\" data-id=\"53f5399\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-4062ca1 elementor-widget elementor-widget-heading\" data-id=\"4062ca1\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Correction-de-lexemple\"><\/span>Correcci\u00f3n del ejemplo<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-6b8de51 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"6b8de51\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-b04187d\" data-id=\"b04187d\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-235e266 elementor-widget elementor-widget-text-editor\" data-id=\"235e266\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p><span style=\"font-weight: 400;\">1a \u2013 Para codificar las 8 letras se necesitan 3 bits porque 2<\/span><span style=\"font-weight: 400;\">3<\/span><span style=\"font-weight: 400;\"> = 8.<\/span><\/p><p><span style=\"font-weight: 400;\">1b \u2013 1000 caracteres corresponden a 1000*3 = 3000 bits. Dividimos por 8 para tener el n\u00famero de bytes = 375.<\/span><\/p><p><span style=\"font-weight: 400;\">2 \u2013 Como con 3 bits hay 8 posibilidades, asignaremos cada posibilidad a un car\u00e1cter como:<\/span><\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-16745 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman10.png\" alt=\"codificaci\u00f3n huffman \u00e1rbol huffman codificaci\u00f3n decodificaci\u00f3n\" width=\"700\" height=\"70\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman10.png 700w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman10-300x30.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman10-18x2.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman10-600x60.png 600w\" sizes=\"(max-width: 700px) 100vw, 700px\" \/><\/p><p><span style=\"font-weight: 400;\">3a \u2013 Lo vimos en el texto CACHE est\u00e1 codificado por 00010000111101.<\/span><\/p><p><span style=\"font-weight: 400;\">3b \u2013 Leemos los bits de izquierda a derecha, en cuanto la lectura da una letra la escribimos y empezamos a buscar de nuevo en la tabla el car\u00e1cter correspondiente.<\/span><\/p><p><span style=\"font-weight: 400;\">0 no da nada, 00 no da nada, 001 da una B. 1 no da nada, 10 da una A, y as\u00ed sucesivamente. La \u00faltima palabra es BADGE.<\/span><\/p><p><span style=\"font-weight: 400;\">4a \u2013 La longitud ser\u00eda 1000*3 = 3000 bits.\u00a0<\/span><\/p><p><span style=\"font-weight: 400;\">4b \u2013 Para saber la longitud con la tabla de codificaci\u00f3n, multiplicaremos para cada car\u00e1cter su frecuencia por su longitud de codificaci\u00f3n: 240*2 + 140*3 + 160*3 + 51*4 + 280*2 + 49*4 + 45* 4 + 35*4. Eso es 2660 bits con una reducci\u00f3n de (3000-2660)\/3000 = 11% (que realmente no es terrible...).<\/span><\/p><p>5 \u2013\u00a0<span style=\"font-weight: 400;\">Despu\u00e9s de realizar el m\u00e9todo de Huffman, obtienes el siguiente \u00e1rbol:<\/span><\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-16746 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman11.png\" alt=\"codificaci\u00f3n huffman \u00e1rbol huffman codificaci\u00f3n decodificaci\u00f3n\" width=\"574\" height=\"426\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman11.png 574w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman11-300x223.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/huffman11-16x12.png 16w\" sizes=\"(max-width: 574px) 100vw, 574px\" \/><\/p><p><span style=\"font-weight: 400;\">Al final, era la mesa que ya se proporcionaba antes, \u00a1as\u00ed que ya era \u00f3ptima!<\/span><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>","protected":false},"excerpt":{"rendered":"<p>Algorithms Wiki home page Codificaci\u00f3n Huffman La codificaci\u00f3n Huffman es un proceso ampliamente utilizado en la compresi\u00f3n de datos. Se utiliza para codificar... <\/p>","protected":false},"author":1,"featured_media":0,"parent":1062,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-16733","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/16733","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/comments?post=16733"}],"version-history":[{"count":3,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/16733\/revisions"}],"predecessor-version":[{"id":17143,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/16733\/revisions\/17143"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/1062"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/media?parent=16733"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}