Codage Huffman.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.6.3"
    },
    "colab": {
      "name": "Codage Huffman.ipynb",
      "provenance": [],
      "include_colab_link": true
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/gabilodeau/INF8770/blob/master/Codage%20Huffman.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Otl17dQ2gDNX"
      },
      "source": [
        "INF8770 Technologies multimédias\n",
        "\n",
        "Polytechnique Montréal\n",
        "\n",
        "Exemple de codage Huffman"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tlHk-7kigfRz"
      },
      "source": [
        "Exécuter la ligne suivante pour colab"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "_8J4A7mPgcNE",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "5355648c-b1ea-4ec9-88cb-41006f009f2c"
      },
      "source": [
        "!pip install anytree"
      ],
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Requirement already satisfied: anytree in /usr/local/lib/python3.10/dist-packages (2.12.1)\n",
            "Requirement already satisfied: six in /usr/local/lib/python3.10/dist-packages (from anytree) (1.16.0)\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vEL_HFc2gDNb"
      },
      "source": [
        "import numpy as np\n",
        "import math\n",
        "from anytree import Node, RenderTree, PreOrderIter, AsciiStyle"
      ],
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "sa8dGc6cgDNk"
      },
      "source": [
        "Message à coder"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "TdUX0hIFgDNl"
      },
      "source": [
        "Message = \"EBFFBEABEFCFDEBBFFFEFEFCCBFACBBABCDACDCABABBBCDDCDCAAABBBABABAABAAB\""
      ],
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ICArX3GjgDNr"
      },
      "source": [
        "Préparation pour la création de l'arbre. On trouve les feuilles (symboles) et leurs poids (nb occurences)."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "eAE_QCKigDNs"
      },
      "source": [
        "#Liste qui sera modifié jusqu'à ce qu'elle contienne seulement la racine de l'arbre\n",
        "ArbreSymb =[[Message[0], Message.count(Message[0]), Node(Message[0])]]\n",
        "#dictionnaire obtenu à partir de l'arbre.\n",
        "dictionnaire = [[Message[0], '']]\n",
        "nbsymboles = 1\n",
        "\n",
        "#Recherche des feuilles de l'arbre\n",
        "for i in range(1,len(Message)):\n",
        "    if not list(filter(lambda x: x[0] == Message[i], ArbreSymb)):\n",
        "        ArbreSymb += [[Message[i], Message.count(Message[i]),Node(Message[i])]]\n",
        "        dictionnaire += [[Message[i], '']]\n",
        "        nbsymboles += 1\n",
        "\n",
        "longueurOriginale = np.ceil(np.log2(nbsymboles))*len(Message)\n",
        "\n",
        "OccSymb = ArbreSymb.copy()"
      ],
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "nCjmn5cQgDNx"
      },
      "source": [
        "Affichage des feuilles trouvées. Les feuilles sont triées pour la construction de l'arbre selon l'algorithme Huffman"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "fqeUeqEXgDNy",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "203f8c82-97fd-461a-f1b7-c489b973be5b"
      },
      "source": [
        "ArbreSymb = sorted(ArbreSymb, key=lambda x: x[1])\n",
        "print(ArbreSymb)"
      ],
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[['E', 6, Node('/E')], ['D', 6, Node('/D')], ['F', 10, Node('/F')], ['C', 10, Node('/C')], ['A', 15, Node('/A')], ['B', 20, Node('/B')]]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "mkCDPzgMgDN4"
      },
      "source": [
        "Création de l'arbre"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "hh9PnKYKgDN5",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "9ededd8e-b2fe-45de-e34a-1f0671a3f2b9"
      },
      "source": [
        "while len(ArbreSymb) > 1:\n",
        "    #Fusion des noeuds de poids plus faibles\n",
        "    symbfusionnes = ArbreSymb[0][0] + ArbreSymb[1][0]\n",
        "    #Création d'un nouveau noeud\n",
        "    noeud = Node(symbfusionnes)\n",
        "    temp = [symbfusionnes, ArbreSymb[0][1] + ArbreSymb[1][1], noeud]\n",
        "    #Ajustement de l'arbre pour connecter le nouveau avec ses parents\n",
        "    ArbreSymb[0][2].parent = noeud\n",
        "    ArbreSymb[1][2].parent = noeud\n",
        "    #Enlève les noeuds fusionnés de la liste de noeud à fusionner.\n",
        "    del ArbreSymb[0:2]\n",
        "    #Ajout du nouveau noeud à la liste et tri.\n",
        "    ArbreSymb += [temp]\n",
        "    #Pour affichage de l'arbre ou des sous-branches\n",
        "    print('\\nArbre actuel:\\n\\n')\n",
        "    for i in range(len(ArbreSymb)):\n",
        "        if len(ArbreSymb[i][0]) > 1:\n",
        "            print(RenderTree(ArbreSymb[i][2], style=AsciiStyle()).by_attr())\n",
        "    ArbreSymb = sorted(ArbreSymb, key=lambda x: x[1])\n",
        "    print(ArbreSymb)"
      ],
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "\n",
            "Arbre actuel:\n",
            "\n",
            "\n",
            "ED\n",
            "|-- E\n",
            "+-- D\n",
            "[['F', 10, Node('/F')], ['C', 10, Node('/C')], ['ED', 12, Node('/ED')], ['A', 15, Node('/A')], ['B', 20, Node('/B')]]\n",
            "\n",
            "Arbre actuel:\n",
            "\n",
            "\n",
            "ED\n",
            "|-- E\n",
            "+-- D\n",
            "FC\n",
            "|-- F\n",
            "+-- C\n",
            "[['ED', 12, Node('/ED')], ['A', 15, Node('/A')], ['B', 20, Node('/B')], ['FC', 20, Node('/FC')]]\n",
            "\n",
            "Arbre actuel:\n",
            "\n",
            "\n",
            "FC\n",
            "|-- F\n",
            "+-- C\n",
            "EDA\n",
            "|-- ED\n",
            "|   |-- E\n",
            "|   +-- D\n",
            "+-- A\n",
            "[['B', 20, Node('/B')], ['FC', 20, Node('/FC')], ['EDA', 27, Node('/EDA')]]\n",
            "\n",
            "Arbre actuel:\n",
            "\n",
            "\n",
            "EDA\n",
            "|-- ED\n",
            "|   |-- E\n",
            "|   +-- D\n",
            "+-- A\n",
            "BFC\n",
            "|-- B\n",
            "+-- FC\n",
            "    |-- F\n",
            "    +-- C\n",
            "[['EDA', 27, Node('/EDA')], ['BFC', 40, Node('/BFC')]]\n",
            "\n",
            "Arbre actuel:\n",
            "\n",
            "\n",
            "EDABFC\n",
            "|-- EDA\n",
            "|   |-- ED\n",
            "|   |   |-- E\n",
            "|   |   +-- D\n",
            "|   +-- A\n",
            "+-- BFC\n",
            "    |-- B\n",
            "    +-- FC\n",
            "        |-- F\n",
            "        +-- C\n",
            "[['EDABFC', 67, Node('/EDABFC')]]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "kbOnLW7UgDN-"
      },
      "source": [
        "On traverse l'arbre des symboles par parcours préfix, et on construit un arbre semblable de codes binaires. Le premier enfant avec 0, le deuxième avec 1.  Ensuite, on utilisera les 2 arbres pour construire le dictionnaire."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "YVHGEgJOgDOA",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "f35d04b6-673c-4dde-fd0d-16103697e74e"
      },
      "source": [
        "ArbreCodes = Node('')\n",
        "noeud = ArbreCodes\n",
        "#print([node.name for node in PreOrderIter(ArbreSymb[0][2])])\n",
        "parcoursprefix = [node for node in PreOrderIter(ArbreSymb[0][2])]\n",
        "parcoursprefix = parcoursprefix[1:len(parcoursprefix)] #ignore la racine\n",
        "\n",
        "Prevdepth = 0 #pour suivre les mouvements en profondeur dans l'arbre\n",
        "for node in parcoursprefix:  #Liste des noeuds\n",
        "    if Prevdepth < node.depth: #On va plus profond dans l'arbre, on met un 0\n",
        "        temp = Node(noeud.name + '0')\n",
        "        noeud.children = [temp]\n",
        "        if node.children: #On avance le \"pointeur\" noeud si le noeud ajouté a des enfants.\n",
        "            noeud = temp\n",
        "    elif Prevdepth == node.depth: #Même profondeur, autre feuille, on met un 1\n",
        "        temp = Node(noeud.name + '1')\n",
        "        noeud.children = [noeud.children[0], temp]  #Ajoute le deuxième enfant\n",
        "        if node.children: #On avance le \"pointeur\" noeud si le noeud ajouté a des enfants.\n",
        "            noeud = temp\n",
        "    else:\n",
        "        for i in range(Prevdepth-node.depth): #On prend une autre branche, donc on met un 1\n",
        "            noeud = noeud.parent #On remontre dans l'arbre pour prendre la prochaine branche non explorée.\n",
        "        temp = Node(noeud.name + '1')\n",
        "        noeud.children = [noeud.children[0], temp]\n",
        "        if node.children:\n",
        "            noeud = temp\n",
        "\n",
        "    Prevdepth = node.depth\n",
        "\n",
        "print('\\nArbre des codes:\\n\\n',RenderTree(ArbreCodes, style=AsciiStyle()).by_attr())\n",
        "print('\\nArbre des symboles:\\n\\n', RenderTree(ArbreSymb[0][2], style=AsciiStyle()).by_attr())"
      ],
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "\n",
            "Arbre des codes:\n",
            "\n",
            " \n",
            "|-- 0\n",
            "|   |-- 00\n",
            "|   |   |-- 000\n",
            "|   |   +-- 001\n",
            "|   +-- 01\n",
            "+-- 1\n",
            "    |-- 10\n",
            "    +-- 11\n",
            "        |-- 110\n",
            "        +-- 111\n",
            "\n",
            "Arbre des symboles:\n",
            "\n",
            " EDABFC\n",
            "|-- EDA\n",
            "|   |-- ED\n",
            "|   |   |-- E\n",
            "|   |   +-- D\n",
            "|   +-- A\n",
            "+-- BFC\n",
            "    |-- B\n",
            "    +-- FC\n",
            "        |-- F\n",
            "        +-- C\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y0ZNqTu2gDOH",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "4300c050-e891-4b70-9c9c-76e48a72a23b"
      },
      "source": [
        "ArbreSymbList = [node for node in PreOrderIter(ArbreSymb[0][2])]\n",
        "ArbreCodeList = [node for node in PreOrderIter(ArbreCodes)]\n",
        "\n",
        "for i in range(len(ArbreSymbList)):\n",
        "    if ArbreSymbList[i].is_leaf: #Génère des codes pour les feuilles seulement\n",
        "        temp = list(filter(lambda x: x[0] == ArbreSymbList[i].name, dictionnaire))\n",
        "        if temp:\n",
        "            indice = dictionnaire.index(temp[0])\n",
        "            dictionnaire[indice][1] = ArbreCodeList[i].name\n",
        "\n",
        "print(dictionnaire)"
      ],
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[['E', '000'], ['B', '10'], ['F', '110'], ['A', '01'], ['C', '111'], ['D', '001']]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "oIf0-eVMgDOK"
      },
      "source": [
        "Codage du message avec le dictionnaire"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "mNp58IZ1gDOK"
      },
      "source": [
        "MessageCode = []\n",
        "longueur = 0\n",
        "for i in range(len(Message)):\n",
        "    substitution = list(filter(lambda x: x[0] == Message[i], dictionnaire))\n",
        "    MessageCode += [substitution[0][1]]\n",
        "    longueur += len(substitution[0][1])"
      ],
      "execution_count": 9,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "piDeqhNhgDOQ",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "d8fdeced-5d7a-4423-c558-b5fa1774a66a"
      },
      "source": [
        "print(MessageCode)"
      ],
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "['000', '10', '110', '110', '10', '000', '01', '10', '000', '110', '111', '110', '001', '000', '10', '10', '110', '110', '110', '000', '110', '000', '110', '111', '111', '10', '110', '01', '111', '10', '10', '01', '10', '111', '001', '01', '111', '001', '111', '01', '10', '01', '10', '10', '10', '111', '001', '001', '111', '001', '111', '01', '01', '01', '10', '10', '10', '01', '10', '01', '10', '01', '01', '10', '01', '01', '10']\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ngVWAm6qgDOT"
      },
      "source": [
        "Longueur en bits du message codé et celle de l'original"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "c2ZNI3O4gDOT",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "61f55991-416a-4e64-9db2-06e35e8ed9ff"
      },
      "source": [
        "print(\"Longueur = {0}\".format(longueur))\n",
        "print(\"Longueur originale = {0}\".format(longueurOriginale))"
      ],
      "execution_count": 11,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Longueur = 166\n",
            "Longueur originale = 201.0\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Espérance de la longueur d'un code avec Huffman vs Entropie"
      ],
      "metadata": {
        "id": "17oA6mOojzPI"
      }
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2OvSltPngDOW",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "412901a3-8430-4867-84a4-ae7cede1bbfa"
      },
      "source": [
        "print('Espérance: ' + str(longueur/len(Message)))\n",
        "entropie =0\n",
        "for i in range(nbsymboles):\n",
        "  entropie = entropie-(OccSymb[i][1]/len(Message))*math.log(OccSymb[i][1]/len(Message),2)\n",
        "\n",
        "print('Entropie: ' + str(entropie))"
      ],
      "execution_count": 12,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Espérance: 2.4776119402985075\n",
            "Entropie: 2.446685716752158\n"
          ]
        }
      ]
    }
  ]
}