{"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\/en\/algorithmic\/huffman-coding\/","title":{"rendered":"Huffman coding"},"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\/en\/algorithmic\/\">\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\">Algorithmic<\/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\/en\/\">\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\">Home page<\/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\">Contents<\/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=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/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\/en\/algorithmic\/huffman-coding\/#Codage-de-Huffman\" >Huffman coding<\/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\/en\/algorithmic\/huffman-coding\/#Arbre-de-Huffman\" >Huffman tree<\/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\/en\/algorithmic\/huffman-coding\/#Algorithme-de-Huffman\" >Huffman&#039;s algorithm<\/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\/en\/algorithmic\/huffman-coding\/#Codage-et-decodage\" >Coding and decoding<\/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\/en\/algorithmic\/huffman-coding\/#Exemple\" >Example<\/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\/en\/algorithmic\/huffman-coding\/#Correction-de-lexemple\" >Correction of the example<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Codage-de-Huffman\"><\/span>Huffman coding<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;\">Huffman coding is a widely used method in data compression. It is used to encode a text in binary, using for each letter a number of bits depending on the number of times the letter is present: the more the letter appears, the smaller the number of bits. Thus, the total number of bits used to encode the text is reduced compared to standard ASCII encoding which uses eight bits for each letter.<\/span><\/p><p><span style=\"font-weight: 400;\">When it comes to transmitting information on a non-noisy channel, the priority objective is to minimize the size of the representation of the information: this is the problem of data compression. Huffman&#039;s code (1952) is an optimal variable length code, that is to say such that the average length of a coded text is minimal. Size reductions of the order of 20 to 90% are thus observed.<\/span><\/p><p><span style=\"font-weight: 400;\">The binary code associated with each letter is defined by a <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/trees-and-trees\/\">binary tree<\/a>. The leaves of the tree correspond to the letters of the alphabet. Internal nodes contain no information. The path taken to reach a leaf from the root defines the code of the letter on this leaf: left 0, right 1. For example:<\/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=\"huffman coding huffman tree encoding decoding\" 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>Huffman tree<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;\">When the text to be encoded is known, it is possible to optimize the binary tree used to shorten the codes of the most frequent letters. This is what Huffman&#039;s algorithm does: it begins by counting the number of occurrences of each character in the text. For example, in the sentence:<\/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=\"huffman coding huffman tree encoding decoding\" 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;\">From these frequencies, the algorithm initializes a tree per character, with the number of appearances of the character as weight:<\/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=\"huffman coding huffman tree encoding decoding\" 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;\">At each iteration, the algorithm selects the two trees with the lowest weights, and assembles them to form the two children of a binary tree whose weight is the sum of the two trees. When several trees are tied for the lowest weight, the tree selected among them can be any one. Thus, at the first iteration, we could obtain:<\/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=\"huffman coding huffman tree encoding decoding\" 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;\">and after four more iterations:<\/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=\"huffman coding huffman tree encoding decoding\" 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;\">When there is only one tree left, the algorithm is finished.<\/span><\/p><p><span style=\"font-weight: 400;\">Here is an example of building the Huffman tree to better understand the process. In this example we have placed the letters in ascending order unlike the previous example:<\/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=\"huffman coding huffman tree encoding decoding\" 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>Huffman&#039;s algorithm<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;\">More formally, Huffman&#039;s algorithm is as follows:<\/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=\"huffman coding huffman tree encoding decoding huffman algorithm\" 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>Coding and decoding<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;\">We can rewrite the tree in the form of an array. The coding of a letter is linked to the path traveled in the tree until the desired letter. Take the following table:<\/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;\">This type of code is said to be prefix, which means that no code is the prefix of another (the code of A is 10 and no other code starts with 10, the code of B is 001 and no other code does not start with 001). This property allows characters to be separated unambiguously.<\/span><\/p><p><span style=\"font-weight: 400;\">Attention, here everything leads to believe that the proposed table is not optimal. Indeed, there are 8 characters, so using binary, we could use 3 bits to encode all the characters (2^<\/span><span style=\"font-weight: 400;\">3<\/span><span style=\"font-weight: 400;\"> = 8 possibilities).\u00a0<\/span><\/p><p><span style=\"font-weight: 400;\">Here, the sum of the encoded letter bits is 2+3+3+4+2+4+4+4 = 26 bits, or an average of 26\/8 = 3.25 bits per character. But in fact what will count is not the average, but the frequency-weighted average as we will see in the example exercise.<\/span><\/p><p><span style=\"font-weight: 400;\">Using the array, it is possible to encode a message (here the + is a concatenation):<\/span><\/p><p><span style=\"font-weight: 400;\">CACHE=000+10+000+1111+01=00010000111101.<\/span><\/p><p><span style=\"font-weight: 400;\">We therefore have a 14-bit message instead of 5*3=15 bits, which corresponds to a memory reduction for text storage of (15-14)\/15 = 6.6%. Although on average the encoding is larger, in fact we have a reduction in the memory space used!<\/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>Example<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) We seek to encode each letter of this alphabet by a sequence of binary digits.<\/span><\/p><p><span style=\"font-weight: 400;\">a) How many bits are needed to encode each of the 8 letters of the alphabet.<\/span><\/p><p><span style=\"font-weight: 400;\">b) What is the length in bytes of a 1000-character message built on this alphabet?<\/span><\/p><p><span style=\"font-weight: 400;\">2) Provide a fixed size code for each character of the 8-letter alphabet.<\/span><\/p><p><span style=\"font-weight: 400;\">3) We now consider the following coding, the length of the code of each character being variable.<\/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) Using the previous table, give the message code: CACHE.<\/span><\/p><p><span style=\"font-weight: 400;\">b) What is the message corresponding to the code 001101100111001.<\/span><\/p><p><span style=\"font-weight: 400;\">4) In a text, each of the 8 characters has a different number of occurrences. This is summarized in the following table, constructed from 1,000 character text.<\/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=\"huffman coding huffman tree encoding decoding\" 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) Using the fixed size code proposed in question 2., what is the length in bits of the message containing the 1000 characters listed in the preceding table?<\/span><\/p><p><span style=\"font-weight: 400;\">b) Using the code from question 3., what is the length of the same message in bits.<\/span><\/p><p>5) <span style=\"font-weight: 400;\">Realize the Huffman tree optimizing the memory space. Redo questions 3 and 4 with the new tree.<\/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>Correction of the example<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 To encode the 8 letters, 3 bits are needed because 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 characters correspond to 1000*3 = 3000 bits. We divide by 8 to have the number of bytes = 375.<\/span><\/p><p><span style=\"font-weight: 400;\">2 \u2013 Since with 3 bits there are 8 possibilities, we will assign each possibility to a character such as:<\/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=\"huffman coding huffman tree encoding decoding\" 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 We saw it in the text CACHE is coded by 00010000111101.<\/span><\/p><p><span style=\"font-weight: 400;\">3b \u2013 We read the bits from left to right, as soon as the reading gives a letter we write it and we start looking again in the table for the corresponding character.<\/span><\/p><p><span style=\"font-weight: 400;\">0 gives nothing, 00 gives nothing, 001 gives a B. 1 gives nothing, 10 gives an A, and so on. The final word is BADGE.<\/span><\/p><p><span style=\"font-weight: 400;\">4a \u2013 The length would be 1000*3 = 3000 bits.\u00a0<\/span><\/p><p><span style=\"font-weight: 400;\">4b \u2013 To know the length with the coding table, we will multiply for each character its frequency by its encoding length: 240*2 + 140*3 + 160*3 + 51*4 + 280*2 + 49*4 + 45*4 + 35*4. That is 2660 bits with a reduction of (3000-2660)\/3000 = 11% (which is really not terrible\u2026).<\/span><\/p><p>5 \u2013\u00a0<span style=\"font-weight: 400;\">After performing the Huffman method, you get the following tree:<\/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=\"huffman coding huffman tree encoding decoding\" 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;\">In the end, it was the table that was already provided before, so it was already optimal!<\/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 Huffman coding Huffman coding is a process widely used in data compression. It is used to encode a... <\/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\/en\/wp-json\/wp\/v2\/pages\/16733","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/comments?post=16733"}],"version-history":[{"count":3,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/16733\/revisions"}],"predecessor-version":[{"id":17143,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/16733\/revisions\/17143"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/1062"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=16733"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}