{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Codage de Huffman\n",
    "\n",
    "Marc Lorenzi\n",
    "\n",
    "29 décembre 2018"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "import heapq"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voici trois chaînes de caractères que nous utiliserons dans tout le notebook. La chaîne `abra` est très courte et a des propriétés intéressantes. La chaîne `ovide` est un peu plus longue."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "abra = 'abracadabra'\n",
    "ovide = 'Ante mare et terras et quod tegit omnis caelum unus erat toto naturae uultus in orbe quem dixere Chaos'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1 Notion de code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1 Alphabets, lettres, mots"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Un __alphabet__ $A$ est un ensemble fini d'objets. Les éléments d'un alphabet sont appelés des __lettres__. Jusque là tout le monde me suit ? L'alphabet auquel nous pensons tous est évidemment $A=\\{a,b,\\dots,z\\}$, auquel nous pourrions rajouter les lettres majuscules, les chiffres, les symboles de ponctuation, etc. Mais n'importe quel ensemble fini fera l'affaire.\n",
    "\n",
    "Un __mot__ sur l'alphabet $A$ est une suite finie, éventuellement vide, de lettres.\n",
    "\n",
    "__Notation__ : On note $A^*$ l'ensemble des mots sur l'alphabet $A$. Un mot de __longueur__ (ou __taille__) $n\\ge 1$, $u=(a_0,\\ldots,a_{n-1})$ est noté plus simplement $u=a_0a_1\\ldots a_{n-1}$ par la juxtaposition de ses lettres. Le mot vide, l'unique mot de longueur 0, qui n'a pas de lettre, est noté $\\varepsilon$ si besoin. Nous noterons $|u|$ la longueur du mot $u$.\n",
    "\n",
    "Nous disposons donc de la fonction $|\\bullet|:A^*\\to\\mathbb N$ définie par $u\\mapsto |u|$.\n",
    "\n",
    "__Convention__ : Nous identifierons un mot de longueur 1 avec son unique lettre. Avec cette convention, $A\\subset A^*$.\n",
    "\n",
    "Dans toute la suite, $A$ désigne un alphabet. Lorsque nous écrivons $u=a_0\\ldots a_{n-1}$ et que $u$ est un mot, les $a_i$ sont les lettres de $u$ et $n$ est sa longueur. Le mot vide ne sera pas systématiquement traité comme il conviendrait à son rang, le lecteur est censé s'assurer que ce que nous raconterons s'applique aussi dans ce cas."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2 Produit de mots"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "L'ensemble $A^*$ est muni de l'opération de __concaténation__ (ou __produit__) des mots, que nous noterons multiplicativement :\n",
    "\n",
    "__Définition__ : \n",
    "\n",
    "- Soient $u=a_0a_1\\ldots a_{m-1}$ et $v=b_0b_1\\ldots b_{m-1}$ deux mots non vides. Le produit de $u$ et $v$ est le mot \n",
    "\n",
    "$$uv=a_0a_1\\ldots a_{m-1}b_0b_1\\ldots b_{n-1}$$\n",
    "\n",
    "- Si $u=\\epsilon$ est le mot vide, on pose $uv=v$.\n",
    "- Si $v=\\epsilon$ est le mot vide, on pose $uv=u$.\n",
    "\n",
    "\n",
    "__Propriété__ : $A^*$, muni du produit des mots, est un monoïde en général non commutatif. Précisément :\n",
    "\n",
    "- Pour tous $u,v,w\\in A^*$, $(uv)w=u(vw)$.\n",
    "- Pour tout $u\\in A^*$, $u\\varepsilon=\\varepsilon u=u$.\n",
    "- L'opération de concaténation est non commutative dès que $A$ possède au moins 2 lettres.\n",
    "\n",
    "__Démonstration__ : Sans difficulté particulière. Noter que si $a$ et $b$ sont deux lettres différentes de l'alphabet $A$, alors $a.b\\ne b.a$. Le produit n'est donc pas commutatif si $A$ possède au moins deux lettres.\n",
    "\n",
    "__Propriété__ : Tout mot est le produit de ses lettres.\n",
    "\n",
    "__Propriété__ : Pour tous mots $u, v\\in A^*$, $|uv|=|u| + |v|$. La fonction $|\\bullet|$ est donc un morphisme de monoïdes.\n",
    "\n",
    "__Démonstrations__ : faciles."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Remarque__ : Dans tout ce notebook, sauf tout à la fin dans la partie théorique, nous prendrons pour $A$ un ensemble contenant uniquement des lettres \"usuelles\" $a$, $b$, etc, des chiffres, des espaces, des caractères de ponctuation. Cela nous permet de représenter en Python un mot sur l'alphabet $A$ par une __chaîne de caractères__ (`string`). "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.3 Coder"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Une étape essentielle dans le stockage ou la transmission de l'information est le __codage__ des mots. Pour être stocké ou transmis, un mot doit être codé. Et ce que nous obtenons après codage doit pouvoir être décodé (c'est préférable). Pour ceux d'entre-vous qui se disent qu'ils ne stockent jamais de mots, dites vous qu'un fichier n'est qu'un long mot dont les lettres sont, par exemple, les octets du fichier. Nous allons travailler dans ce notebook sur des chaînes de caractères mais _tout ce que je vais raconter peut s'adapter assez facilement à des fichiers concrets_.\n",
    "\n",
    "__Définition incomplète__ : Un code est une fonction $c:A\\to \\mathbb B^*$ où $\\mathbb B=\\{0, 1\\}$.\n",
    "\n",
    "__Proposition__ : Soit $c$ un code. Il existe un unique morphisme de monoïdes $c^*:A^*\\to \\mathbb B^*$ tel que pour tout $u\\in A$, $c^*(u)=c(u)$.\n",
    "\n",
    "__Preuve__ : Soit $u=a_0\\ldots a_{n-1}\\in A^*$. Si un tel morphisme existe, on a $c^*(u)=c(a_0)\\ldots c(a_{n-1})$ puisque l'image d'un produit est le produit des images. Inversement, cette fonction convient.\n",
    "\n",
    "Bref, si on sait coder les lettres alors on sait coder les mots.\n",
    "\n",
    "__Exercice__ : Pensez-vous au mot vide ? Que vaut $c^*(\\varepsilon)$ ? Indication : Un morphisme conserve le neutre."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.4 Le code ASCII"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "ASCII signifie \"American Standard Code for Information Interchange\". Le code ASCII a été développé au paléolithique, plus précisément dans les années 1960. C'est une norme de codage des caractères. Le code ASCII \"pur\" code 128 caractères par des mots de 7 bits sur l'alphabet $\\mathbb B$. Par exemple, la lettre $a$ est codée `01100001`, la lettre $b$ est codée `01100010`, etc. En interprétant ces mots de $\\mathbb B^*$ comme des entiers en base 2, on retient plutôt que le code ASCII de $a$ est 97, celui de $b$ est 98, etc.\n",
    "\n",
    "Il existe de nombreuses extensions du code ASCII permettant de coder $2^8=256$ caractères. La plus utilisée par les français est le code ISO 8859-1, appelé aussi ISO Latin-1. Il permet de coder, en particulier, les lettres accentuées, par des codes supérieurs ou égaux à 128.\n",
    "\n",
    "__Remarque__ : Le code ASCII s'est avéré au fil du temps insuffisant pour coder les nombreux caractères des langues de la Galaxie. Son évolution est le code __Unicode__ qui peut coder $65536=2^{16}$ caractères, dont je ne parlerai pas plus avant. Les idées sous-tendant Unicode et ses implémentations concrètes sont intéressantes et je ne saurais trop vous conseiller de vous documenter sur le sujet."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction Python `ord` permet d'obtenir le code ASCII d'un caractère."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for c in 'Je vais à la pêche le dimanche.':\n",
    "    print(c, ord(c))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sa \"réciproque\" est la fonction `chr`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print([(k, chr(k)) for k in range(256)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Histoire de nous échauffer, écrivons une fonction Python qui code un mot au moyen du code ASCII.\n",
    "\n",
    "Voici tout d'abord une fonction qui prend en entier un entier $n$ et renvoie sa représentation binaire sous forme d'une chaîne de 8 caractères."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def entier_vers_binaire(n):\n",
    "    s = ''\n",
    "    for k in range(8):\n",
    "        s = str(n % 2) + s\n",
    "        n = n // 2\n",
    "    return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "entier_vers_binaire(97)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le codage d'un mot $u$ est alors immédiat. Il suffit de concaténer les codes de ses lettres."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def coder_ascii(u):\n",
    "    s = ''\n",
    "    for a in u:\n",
    "        s = s + entier_vers_binaire(ord(a))\n",
    "    return s"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le mot `ovide`, par exemple, est codé en ASCII sur 816 bits."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "v = coder_ascii(ovide)\n",
    "print(v)\n",
    "print(len(v))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.5 Représenter un code en Python. Coder"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Décidons de représenter un code par un dictionnaire. Si $c$ est un code, nous accédons donc à $c(a)$ par l'expression `c[a]`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "code = {'a': '00', 'b': '01', 'c': '10', 'd' : '11'}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def coder(s, code):\n",
    "    s1 = ''\n",
    "    for a in s:\n",
    "        s1 = s1 + code[a]\n",
    "    return s1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "coder('babaca', code)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voici un sous-code du code ASCII."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sous_ascii():\n",
    "    c = {}\n",
    "    s = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz 0123456789,;:.'\n",
    "    for a in s:\n",
    "        c[a] = entier_vers_binaire(ord(a))\n",
    "    return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mini_ascii = sous_ascii()\n",
    "print(mini_ascii)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def coder_ascii(u):\n",
    "    return coder(u, mini_ascii)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "coder_ascii(ovide)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.6 Décoder"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Comment décode-t-on ??? Nous pouvons commencer par fabriquer un dictionnaire \"inverse\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def inverser(code):\n",
    "    d = {}\n",
    "    for a in code:\n",
    "        d[code[a]] = a\n",
    "    return d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "inv_mini_ascii = inverser(mini_ascii)\n",
    "print(inv_mini_ascii)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Décoder le code ASCII, c'est facile. Il suffit de regrouper les 0 et les 1 par paquets de 8."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def decoder_ascii(s):\n",
    "    s1 = ''\n",
    "    for k in range(len(s) // 8):\n",
    "        a = s[8 * k: 8 * (k + 1)]\n",
    "        s1 = s1 + inv_mini_ascii[a]\n",
    "    return s1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "v = coder_ascii(ovide)\n",
    "print(v)\n",
    "print(decoder_ascii(v))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tentons un autre exemple, plus subtil."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "code = {'a':'1', 'b':'110', 'c' : '10', 'd':'111'}\n",
    "inv_code = inverser(code)\n",
    "print(inv_code)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Comment décoder un tel code ? Les codes des lettres n'ont pas tous la même longueur ! Tentons une approche par force brute. Pour décoder une chaîne de 0 et de 1 :\n",
    "\n",
    "- On cherche tous les codes qui sont des préfixes de cette chaîne.\n",
    "- Pour chacun de ces codes, on décode récursivement ce qui reste lorsqu'on a ôté le code du début de la chaîne.\n",
    "- On recolle le tout.\n",
    "\n",
    "La fonction `est_prefixe` prend en paramètres deux chaînes $s_1$ et $s_2$. Elle renvoie `True` lorsque $s_1$ est un __préfixe__ de $s_2$, c'est à dire lorsque les premières lettres de $s_2$ sont celles de $s_1$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def est_prefixe(s1, s2):\n",
    "    n = len(s1)\n",
    "    return n <= len(s2) and s2[:n] == s1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "est_prefixe('ab', 'abc')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Et voici la fonction `decoder`. Elle prend en paramètres une chaîne de 0 et de 1 et un \"code inverse\". Elle renvoie la liste des mots dont le code est la chaîne $s$. Euh, comment ça __les__ mots ? Eh, oui, regardez ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def decoder(s, inv_code):\n",
    "    if s == '': return ['']\n",
    "    else:\n",
    "        cs = [c for c in inv_code if est_prefixe(c, s)]\n",
    "        sols = []\n",
    "        for c in cs:\n",
    "            m = len(c)\n",
    "            sols1 = decoder(s[m:], inv_code, dbg, pad + 4)\n",
    "            sols = sols + [inv_code[c] + s1 for s1 in sols1]\n",
    "        return sols"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En voici une version qui affiche des informations au cours de son exécution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def decoder(s, inv_code, dbg=False, pad=0):\n",
    "    if dbg: print(pad * '.' + 'mot', s)\n",
    "    if s == '':\n",
    "        if dbg: print(pad * '.' + 'mot trouvé', s)\n",
    "        return ['']\n",
    "    else:\n",
    "        cs = [c for c in inv_code if est_prefixe(c, s)]\n",
    "        if dbg: print(pad * '.' + 'prefixes', *cs)\n",
    "        sols = []\n",
    "        for c in cs:\n",
    "            m = len(c)\n",
    "            sols1 = decoder(s[m:], inv_code, dbg, pad + 4)\n",
    "            sols = sols + [inv_code[c] + s1 for s1 in sols1]\n",
    "        return sols"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `decoder` a une complexité terrible. Mais pas d'inquiétude, nous ne l'utiliserons que dans ce paragraphe, juste pour illustrer un gros problème dans notre définition d'un code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "faux_code = {'a':'1', 'b':'110', 'c' : '10', 'd':'111'}\n",
    "inv_code = inverser(faux_code)\n",
    "print(faux_code)\n",
    "print(inv_code)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = 'baba'\n",
    "s1 = coder(s, faux_code)\n",
    "print(s1)\n",
    "s2 = decoder(s1, inv_code, dbg=True)\n",
    "print(s2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous avons clairement un souci. Quel est le mot d'origine ? C'est l'un des mots renvoyés par `decoder`, mais lequel ? Il est évident que nous devons changer notre définition.\n",
    "\n",
    "__Définition__ : Un code est une fonction $c:A\\to \\mathbb B^*$ tel que $c^*:A^*\\to \\mathbb B^*$ soit __injectif__.\n",
    "\n",
    "Ainsi, étant donnés deux mots $u,v\\in A^*$, si $c^*(u)=c^*(v)$ alors $u=v$. Maintenant, notre fonction `decoder` utilisée avec un \"vrai\" code renvoie une liste ayant un seul mot, le mot d'origine."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le \"code\" sur lequel nous venons de travailler n'en est pas un, puisque des mots différents de $A^*$ ont le même code. Un exemple de vrai code ? Le code ASCII, évidemment (?). Un exemple un peu moins évident ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "code = {'a':'0', 'b':'110', 'c':'10', 'd':'111'}\n",
    "inv_code = inverser(code)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s1 = coder('babacadaa', code)\n",
    "print(s1)\n",
    "s2 = decoder(s1, inv_code)\n",
    "print(s2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Exercice__ : Prouvez que le code ASCII est un code. Ou alors attendez un peu. Lorsque nous aurons parlé de codes préfixes ce sera évident."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2 Codes préfixes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.1 C'est quoi ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Soit $c:A\\to \\mathbb B^*$. Comment être certains que $c$ est bien un code ? C'est loin d'être un problème trivial puisqu'il s'agit de vérifier que son __prolongement__ $c^*:A^*\\to \\mathbb B^*$ est injectif. Mais $A^*$ est un ensemble infini. En fait, il est très difficile de donner une condition nécessaire et suffisante \"utilisable\" pour que $c$ soit un code. Il existe en revanche une condition __suffisante__ intéressante. Les codes qui la vérifient sont très utilisés en pratique.\n",
    "\n",
    "__Définition__ : Une fonction $c:A\\to \\mathbb B^*$ est dite __préfixe__ lorsque pour tous $a,a'\\in A$ distincts, le mot $c(a)$ n'est pas un préfixe du mot $c(a')$.\n",
    "\n",
    "__Proposition__ : Une fonction préfixe est un code.\n",
    "\n",
    "__Démonstration__ : Supposons $c^*(a_0\\ldots a_{m-1})=c^*(b_0\\ldots b_{n-1})$. Cela signifie que $c(a_0)\\ldots c(a_{m-1})=c(b_0)\\ldots c(b_{n-1})$. Que voit-on comme lettres au début de ce mot ? Il y a les lettres du mot $c(a_0)$, mais aussi celles du mot $c(b_0)$. On en déduit que $c(a_0)$ est un préfixe de $c(b_0)$, ou le contraire (le mot le plus court est préfixe du mot le plus long). Par la propriété __préfixe__, on en déduit que $a_0=b_0$. \n",
    "\n",
    "Le lecteur l'aura compris, le preuve se termine par une récurrence sur la longueur des mots que je ne ferai pas. Bref, $c$ est un code."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Exercice__ : Prouvez que le code ASCII est une fonction préfixe (facile, tous les codes ont la même longueur). Donc, le code ASCII est un code :-)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le code donné un tout petit peu plus haut était un code préfixe. Mais tous les codes ne sont-ils pas forcément préfixes ? Non. Voici un exemple de code non préfixe. $c(a)$ est un préfixe de $c(b)$, et pourtant il y a bien injectivité de la fonction de codage des mots.\n",
    "\n",
    "__Exercice__ : Prouvez-le. En exécutant les cellules ci-dessous vous comprendrez pourquoi on a bien un code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "code = {'a':'10','b':'100','c':'110'}\n",
    "inv_code = inverser(code)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = 'aba'\n",
    "s1 = coder(s, code)\n",
    "print(s1)\n",
    "s2 = decoder(s1, inv_code, True)\n",
    "print(s2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.2 Représenter un code préfixe par un arbre"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Soit $c:A\\to \\mathbb B^*$ un code préfixe. On peut coder $c$ (mais oui, codons les codes) par un arbre binaire. Les feuilles de cet arbre sont étiquetées par les lettres de l'alphabet $A$. Le code de chaque lettre est obtenu comme suit : il existe un unique chemin qui va de la racine à une feuille donnée. Chaque fois que l'on descend d'un niveau, on emprunte le fils gauche ou bien le fils droit du noeud où l'on se trouve. On peut ainsi coder le chemin suivi par une liste de 0 et de 1, où 0 signifie \"fils gauche\" et 1 signifie \"fils droit\". Le code de la feuille est la concaténation de ces 0 et 1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `faire_arbre` prend en paramètre un code préfixe. Elle renvoie l'arbre du code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def faire_arbre(code):\n",
    "    t = []\n",
    "    for a in code:\n",
    "        t = inserer_arbre(t, a, code[a])\n",
    "    return t"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Il est temps de nous demander comment nous allons représenter un arbre en Python.\n",
    "\n",
    "- L'arbre vide est codé par la liste vide `[]`.\n",
    "- Si l'arbre est réduit à une simple feuille contenant la lettre $a$, nous le représentons par la liste `['F', a]` ($F$ comme \"feuille\").\n",
    "\n",
    "- Sinon, il possède un fils gauche $t_1$ et un fils droit $t_2$. Soient $L$ et $R$ leurs représentations : nous représentons notre arbre par la liste `['N', L, R]` ($N$ comme \"noeud\")."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Les fonctions `gauche` et `droit` renvoient les fils de l'arbre $t$. Elles renvoient l'arbre vide si $t$ est vide : cela nous sera pratique plus tard."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gauche(t):\n",
    "    if t == []: return []\n",
    "    elif t[0] == 'F':\n",
    "        raise Exception('Feuille inattendue')\n",
    "    else:\n",
    "        return t[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def droit(t):\n",
    "    if t == []: return []\n",
    "    elif t[0] == 'F':\n",
    "        raise Exception('Feuille inattendue')\n",
    "    else:\n",
    "        return t[2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `inserer_arbre` insère un caractère $a$ de code $c$ dans l'arbre $t$. Elle renvoie un nouvel arbre, qui contient une nouvelle feuille d'étiquette $a$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def inserer_arbre(t, a, c):\n",
    "    if c == '':\n",
    "        return ['F', a]\n",
    "    elif c[0] == '0':\n",
    "        t1 = inserer_arbre(gauche(t), a, c[1:])\n",
    "        return ['N', t1, droit(t)]\n",
    "    else:\n",
    "        t1 = inserer_arbre(droit(t), a, c[1:])\n",
    "        return ['N', gauche(t), t1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "code = {'a':'0', 'b':'110', 'c':'10', 'd':'111'}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = faire_arbre(code)\n",
    "print(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Rappelez-vous le mini-code ASCII défini un peu plus_haut ... Voici son arbre."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = faire_arbre(mini_ascii)\n",
    "print(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.3 Décoder un code préfixe"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Si un code $c$ est un code préfixe et que l'on dispose de son arbre, il devient alors très facile de décoder ! Pour décoder une chaîne $s$ de 0 et de 1, on prend les caractères de $s$ l'un après l'autre. Si le caractère est un 0, on descend à gauche dans l'arbre. Si c'est un 1, on descend à droite. Lorsqu'on atteint une feuille on stocke la lettre qui est à cette feuille et on repart à la racine de l'arbre.\n",
    "\n",
    "La fonction `decoder_prefixe` a une complexité __linéaire__ en la longueur de la chaîne à décoder. On peut difficilement faire mieux."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def decoder_prefixe(s, t):\n",
    "    t1 = t\n",
    "    s1 = ''\n",
    "    k = 0\n",
    "    while k < len(s):\n",
    "        if t1[0] == 'F':\n",
    "            s1 = s1 + t1[1]\n",
    "            t1 = t\n",
    "        elif s[k] == '0':\n",
    "            t1 = gauche(t1)\n",
    "            k = k + 1\n",
    "        else:\n",
    "            t1 = droit(t1)\n",
    "            k = k + 1\n",
    "    return s1 + t1[1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Exercice__ : Pourquoi la fonction renvoie-t-elle `s1+t1[1]` et pas tout bêtement `s1` ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(code)\n",
    "t = faire_arbre(code)\n",
    "s = coder('ababaacabd', code)\n",
    "print(s)\n",
    "s1 = decoder_prefixe(s, t)\n",
    "print(s1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Maintenant que comprenons ce qu'est un code préfixe et que nous savons coder et décoder, nous pouvons entrer dans le vif du sujet."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3 Compression"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1 De quoi s'agit-il ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pourquoi se compliquer la vie avec des codes bizarres ? Le code ASCII n'est-il pas parfait ? Je vais expliquer où nous voulons en venir. \n",
    "\n",
    "Soit $c$ un code. Pour tout mot $u=a_0\\ldots a_{m-1}$, le __nombre de bits__ du codage de $u$ est $\\sum_{k=0}^{m-1}|c(a_k)|$ où la valeur absolue, rapppelons-le, désigne la longueur du mot. \n",
    "\n",
    "Reformulons différemment : soient $\\alpha_1,\\ldots,\\alpha_n$ les lettres __distinctes__ du mot $u$. L'ensemble $A=\\{\\alpha_1,\\ldots,\\alpha_n\\}$ est le plus petit alphabet tel que $u\\in A^*$. Pour tout $\\alpha\\in A$, notons $\\pi(\\alpha)$ le __poids__ de la lettre $\\alpha$ dans le mot $u$, c'est à dire son nombre d'occurences. Pour tout code $c$ sur l'alphabet $A$ nous disposons de la quantité :\n",
    "\n",
    "$$\\mathcal B(c)=\\sum_{k=1}^n \\pi(\\alpha_k)|c(\\alpha_k)|$$\n",
    "\n",
    "que nous exprimerons en __bits__.\n",
    "\n",
    "__Vocabulaire__ : La quantité $\\mathcal B(c)$ est appelée la longueur du code $c$.\n",
    "\n",
    "__Problème__ : Trouver un code _préfixe_ $c$ tel que $\\mathcal B(c)$ soit __minimal__.\n",
    "\n",
    "Un tel code existe forcément. En effet, si nous notons $\\mathcal C$ l'ensemble de tous les codes préfixes sur l'alphabet $A$, l'ensemble $\\{\\mathcal B(c), c\\in\\mathcal C\\}$ est une partie non vide de $\\mathbb N$, qui possède donc un plus petit élément.\n",
    "\n",
    "Nous allons passer le reste de ce notebook à étudier un tel code : il s'agit du __code de Huffman__. Mais avant tout, un peu de Python."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2 Un exemple"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voici tout d'abord une fonction qui calcule __l'histogramme__ d'un mot. Elle prend en paramètre un mot $u$ et renvoie un dictionnaire qui associe à chaque lettre de $u$ le nombre d'occurences de celle-ci dans $u$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def histogramme(u):\n",
    "    h = {}\n",
    "    for a in u:\n",
    "        if a in h: h[a] += 1\n",
    "        else: h[a] = 1\n",
    "    return h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "h = histogramme(ovide)\n",
    "print(h)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On y perd un peu son latin. Prenons un exemple plus simple. Abracadabra ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "h = histogramme(abra)\n",
    "print(h)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `longueur` prend en paramètres un histogramme $h$ et un code $c$. Elle renvoie l'entier $\\mathcal B(c)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def longueur(h, c):\n",
    "    s = 0\n",
    "    for a in h:\n",
    "        s += h[a] * len(c[a])\n",
    "    return s"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Testons sur un micro-code ASCII."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "c = {'a':'000', 'b':'001', 'c':'010', 'd':'011', 'r':'100'}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "longueur(h, c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Testons maintenant sur un code préfixe $c$ un peu plus subtil."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "c = {'a':'0', 'b':'10', 'c':'1101', 'd':'1100', 'r':'111'}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Exercice__ : Vérifiez que $c$ est un code préfixe."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "longueur(h, c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La longueur du second code est plus faible. Nous venons d'effectuer une __COMPRESSION__. Si nous codons le mot \"abracadabra\" avec le second code, 23 bits suffisent alors qu'avec le code ASCII nous avons besoin de 33 bits. Notre but est donc d'effectuer une compression __optimale__ : quel est le code préfixe associé à \"abracadabra\" dont la longueur est la plus petite possible ? Il s'avère que ce sera 23 ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4 Le codage de Huffman"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.1 L'arbre de Huffman"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous allons tout d'abord décrire l'algorithme de Huffman. Cet algorithme prend en paramètre un histogramme et crée l'arbre associé à un certain code préfixe. Comment ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pour fabriquer l'arbre associé à un histogramme on utilise une __file de priorité__ $Q$. Une file de priorité est une structure de données permettant les opérations suivantes :\n",
    "\n",
    "- Mettre dans la file un objet avec une priorité donnée (une priorité est, par exemple, un entier).\n",
    "- Retirer de la file un objet de priorité minimale.\n",
    "\n",
    "\n",
    "Voici notre algorithme :\n",
    "\n",
    "1. On met dans la file $Q$ les futures feuilles de notre arbre avec leurs poids comme priorités. Pour cela il suffit de lire l'histogramme dont les clés sont les lettres et les valeurs sont les poids.\n",
    "3. Pour $k$ allant de 0 au nombre de feuilles $-2$ :\n",
    "\n",
    "    1. On retire de la file les deux arbres $x$ et $y$ de priorités minimales.\n",
    "    2. On crée l'arbre $z$ dont les deux fils sont $x$ et $y$.\n",
    "    3. On met $z$ dans la file avec la priorité adéquate.\n",
    "    \n",
    "4. Maintenant, la file contient un unique arbre. On renvoie cet arbre."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def faire_arbre(h, dbg=False):\n",
    "    Q = []\n",
    "    for a in h:\n",
    "        heapq.heappush(Q, (h[a], ['F', a]))\n",
    "    if dbg: print('File initiale :', Q)\n",
    "    for k in range(len(h) - 1):\n",
    "        px, x = heapq.heappop(Q)\n",
    "        py, y = heapq.heappop(Q)\n",
    "        z = ['N', x, y]\n",
    "        heapq.heappush(Q, (px + py, z))\n",
    "        if dbg: print('Étape %d : %s' % (k, Q))\n",
    "    return heapq.heappop(Q)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = faire_arbre(histogramme(abra), dbg=True)\n",
    "print(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.2 Créer les codes de Huffman"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Une fois l'arbre construit, créer le code est une formalité. Il s'agit d'un parcours d'arbre. La fonction `faire_codes` prend en paramètre un arbre $t$ et renvoie le code associé."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def faire_codes_aux(t, s):\n",
    "    if t[0] == 'F':\n",
    "        return {t[1]: ''}\n",
    "    else:\n",
    "        c1 = faire_codes_aux(t[1], '0')\n",
    "        c2 = faire_codes_aux(t[2], '1')\n",
    "        for k in c1: c1[k] = '0' + c1[k]\n",
    "        for k in c2: c2[k] = '1' + c2[k]\n",
    "        c1.update(c2)\n",
    "        return c1\n",
    "    \n",
    "def faire_codes(t):\n",
    "    return faire_codes_aux(t, None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "c = faire_codes(t)\n",
    "print(c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Résumé__ : On part d'un mot $u$.\n",
    "\n",
    "1. On crée un histogramme $h$ à partir de $u$.\n",
    "2. On crée un arbre $t$ à partir de $h$.\n",
    "3. On crée un code $c$ à partir de $t$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.3 Coder un mot"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous avons déjà écrit la fonction `coder`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s1 = coder('abracadabra', c)\n",
    "print(s1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.4 Décoder"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous avons aussi déjà écrit la fonction `decoder_prefixe`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "decoder_prefixe(s1, t)    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tentons le tout avec `ovide`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print('Mot :', ovide)\n",
    "h = histogramme(ovide)\n",
    "t = faire_arbre(h)\n",
    "c = faire_codes(t)\n",
    "s1 = coder(ovide, c)\n",
    "print('Mot codé :', s1)\n",
    "s2 = decoder_prefixe(s1, t)\n",
    "print('Mot décodé :', s2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5 Optimalité du code de Huffman"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.1 Pensons arbres"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Soit $u\\in A^*$ où $A=\\{\\alpha_1,\\ldots,\\alpha_n\\}$ est l'ensemble des lettres distinctes de $u$, poids $\\pi(\\alpha_1),\\ldots,\\pi(\\alpha_n)$. À chaque code préfixe $c$ sur l'alphabet $A$ correspond, nous l'avons vu, un arbre $T$ dont les feuilles sont étiquetées par les lettres de $A$ et leurs poids. Remarquons que la longueur $|c(\\alpha)|$ du code d'une lettre $\\alpha$ est en fait la __profondeur__ $d(\\alpha)$ de la feuille correspondante, c'est à dire la distance de la feuille à la racine. Nous avons donc\n",
    "\n",
    "$$\\mathcal B(c)=\\sum_{\\alpha\\in A}\\pi(\\alpha)d(\\alpha)$$\n",
    "\n",
    "et nous voyons que nous pouvons oublier le code $c$ pour nous concentrer sur l'arbre $T$. Définissons donc\n",
    "\n",
    "$$\\mathcal B(T)=\\sum_{\\alpha\\in A}\\pi(\\alpha)d(\\alpha)$$\n",
    "\n",
    "Notre problème sur des codes se ramène donc à un problème sur des arbres. On peut oublier les codes et se concentrer sur des __alphabets pondérés__, c'est à dire des alphabets dont chaque lettre est associée à un entier, son poids. Dans toute la suite, nous considérerons que nos alphabets sont pondérés.\n",
    "\n",
    "__Définition__ : L'alphabet $A$ et les poids des lettres étant fixés, l'arbre $T$ est dit __optimal__ lorsque la quantité $\\mathcal B(T)$ est minimale."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.3 Un arbre optimal est complet"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Lemme__ : Soit $T$ un arbre optimal. L'arbre $T$ est __complet__ : aucun noeud de l'arbre n'a un fils vide.\n",
    "\n",
    "__Démonstration__ : Supposons qu'un noeud de l'arbre $T$ a un fils vide, son fils gauche par exemple. En supprimant ce noeud et en recollant à la place le fils droit du noeud, on obtient un arbre $T'$ dont la longueur est strictement inférieure. Impossible puisque $T$ est optimal."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.4 Lettres de plus petit poids"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Lemme__ : Soient $x$ et $y$ les deux lettres de $A$ de plus petit poids. Il y a un un arbre (de code) optimal pour lequel ces deux lettres sont dans des feuilles __soeurs__ (i.e. qui ont le même père) de profondeur maximale.\n",
    "\n",
    "__Démonstration__ : Soit $T$ un arbre optimal. Soient $b$ et $c$ deux feuilles soeurs de profondeur maximale (deux telles feuilles existent car notre arbre est complet). Supposons par exemple $\\pi(b)\\le \\pi(c)$ et $\\pi(x)\\le \\pi(y)$. Comme $x$ et $y$ ont les deux plus petits poids, on a $\\pi(x)\\le\\pi(b)$ et $\\pi(y)\\le\\pi(c)$. De plus, $b$ et $c$ sont à une profondeur maximale dans l'arbre $T$, donc $d(x)\\le d(b)$ et $d(y)\\le d(c)$. Échangeons $x$ et $b$. On obtient un nouvel arbre $T'$ tel que \n",
    "\n",
    "$$\\mathcal B(T')=\\mathcal B(T)-\\pi(x)d(x)-\\pi(b)d(b)+\\pi(x)d(b)+\\pi(b)d(x)=\\mathcal B(T)-(\\pi(b)-\\pi(x))(d(b)-d(x))\\le \\mathcal B(T)$$\n",
    "\n",
    "Mais l'arbre $T$ est optimal, donc $\\mathcal B(T')=\\mathcal B(T)$. Ainsi, $T'$ est aussi optimal. On fait de même en échangeant $c$ et $y$ et on obtient un nouvel arbre $T''$, toujours optimal, qui vérifie la condition voulue."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.5 Optimalité du code de Huffman"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Théorème__ : L'algorithme de Huffman produit un arbre optimal.\n",
    "\n",
    "__Démonstration__ : Faisons une récurrence sur le nombre $n$ de lettres de l'alphabet $A$. \n",
    "\n",
    "Si $n=2$, l'arbre renvoyé par l'algorithme de Huffman est clairement optimal. Il a deux feuilles à la profondeur 1 et on peut difficilement faire mieux :-).\n",
    "\n",
    "Soit maintenant $n\\ge 3$. Supposons la propriété d'optimalité vraie pour un alphabet $A$ ayant $n-1$ lettres. Regardez le code de la fonction `faire_arbre`. À l'itération $k=0$, la fonction prend les lettres $x$ et $y$ de plus petits poids et les accole pour former un arbre $z$. Puis elle met $z$ dans la file de priorité $Q$ qui contient maintenant 1 arbre de moins. Les $n-1$ dernières itérations ne sont autres que l'algorithme de Huffman appliqué à l'alphabet $A'=A\\cup\\{z\\}\\setminus\\{x,y\\}$, où $\\pi(z)=\\pi(x)+\\pi(y)$ et les poids des autres lettres sont les mêmes pour $A$ et $A'$. Par l'hypothèse de récurrence, l'algorithme renvoie donc un arbre $H$ optimal pour l'alphabet $A'$. Il nous reste à voir que cet arbre est optimal pour l'alphabet $A$.\n",
    "\n",
    "Alourdissons un peu les notations pour préciser à chaque fois sur quel alphabet on fait les calculs.\n",
    "\n",
    "On a $\\mathcal B_{A'}(H)=\\mathcal B_{A}(H) - \\pi(x)d(x)-\\pi(y)d(y)+\\pi(z)d(z)$. Mais $d(z)=d(x)-1=d(y)-1$. De là, $\\mathcal B_{A'}(H)=\\mathcal B_A(H)-(\\pi(x)+\\pi(y))$.\n",
    "\n",
    "Soit maintenant $T$ un arbre optimal pour l'alphabet $A$ avec les lettres $x$ et $y$ sur des feuilles soeurs de profondeurs maximales (ceci est possible par le lemme vu plus haut). $T$ peut également être vu comme un arbre sur l'alphabet $A'$. Or $H$ est optimal pour $A'$. Donc $\\mathcal B_{A'}(T)\\ge \\mathcal B_{A'}(H)$. Mais $\\mathcal B_{A'}(T)=\\mathcal B_A(T)-(\\pi(x)+\\pi(y))$ (mêmes calculs que ceux faits pour $H$), donc $\\mathcal B_A(T)-(\\pi(x)+\\pi(y))\\ge \\mathcal B_{A'}(H)=\\mathcal B_A(H)-(\\pi(x)+\\pi(y))$. On en déduit que $\\mathcal B_A(T)\\ge \\mathcal B_A(H)$. Comme $T$ est optimal pour $A$, on a en fait égalité : $\\mathcal B_A(H)=\\mathcal B_A(T)$ et $H$ est optimal pour l'alphabet $A$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Exercice__ : Qu'arrive-t-il si l'alphabet $A$ n'a qu'une lettre ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6 Un exemple grandeur nature"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Coder des mots de 10 lettres c'est rigolo, mais comment se comporte l'algorithme de Huffman dans la vie réelle ? J'ai choisi au hasard de coder l'Énéide de Virgile. Le texte intégral se trouve dans le fichier `eneide.txt`, qui fait environ 400 kilo-octets. Ce n'est pas gigantesque, mais bon, nous programmons en Python alors soyons raisonnables."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.1 Lire le texte de Virgile"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "f = open('eneide.txt')\n",
    "virgile = f.read()\n",
    "f.close()\n",
    "print(len(virgile))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La chaîne `virgile` contient maintenant tout le texte de Virgile. Affichons les 1000 premiers caractères. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(virgile[:1000])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.2 L'histogramme"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Calculons l'histogramme de `virgile`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "h = histogramme(virgile)\n",
    "print(h)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.3 L'arbre de Huffman"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Fabriquons l'arbre de Huffman."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = faire_arbre(h)\n",
    "print(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.4 Le code de Huffman"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Puis les codes de Huffman."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "c = faire_codes(t)\n",
    "print(c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.5 Codons"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s1 = coder(virgile, c)\n",
    "print(s1[:2000])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Évidemment, Virgile est beaucoup moins lisible comme ça."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.6 Taux de compression"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Définition__ : Soit $c$ un code. Soit $u$ un mot. Le taux de compression de $u$ par le code $c$ est\n",
    "\n",
    "$$\\tau(u, c) = 1 - \\frac{|c(u)|}{|u|}$$\n",
    "\n",
    "où toutes les longueurs sont exprimées en bits. Plus le taux de compression est élevé, plus le code est efficace. Certains auteurs appellent taux de compression la quantité $1-\\tau$ ...\n",
    "\n",
    "Quel est le taux de compression obtenu dans notre exemple ? Divisons la longueur de $s_1$ (qui contient des bits) par 8 fois la longueur de $s$. Pourquoi 8 fois ? Parce que chaque lettre de la chaîne $s$ serait codée avec le code ASCII sur 8 bits."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(1 - len(s1) / (8 * len(virgile)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "C'est d'après la théorie, le mieux que l'on peut faire avec un code préfixe. Et avec un code quelconque ? Ceci est une tout autre histoire ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.7 Décodons"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La chaîne codée par l'algorithme de Huffman a une longueur 43% plus courte qu'en codant par le code ASCII. Mais peut-être nous sommes nous trompés ? Essayons de décoder !"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s2 = decoder_prefixe(s1, t)\n",
    "print(s2[10000:11000])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Petit temps d'attente pour avoir le résultat. Pour tout dire, notre fonction de décodage n'est pas très efficace. Elle fait beaucoup de recopies de données (exemple : `t1 = gauche(t1)`) et ces données peuvent être de grande taille. Une implémentation propre utiliserait des pointeurs sur les données. J'imagine (un peu en l'air) qu'un code proprement écrit en C pourrait être mille fois plus rapide."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.8 Sommes-nous bien certains ???"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bon, histoire d'être bien certains :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(virgile == s2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "À moins que Huffman ne fonctionne que pour Virgile, nous pouvons être raisonnablement confiants dans nos fonctions Python :-)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Exercice__ :\n",
    "\n",
    "- Quel est le taux de compression obtenu pour Voyage au Centre de la Terre, de Jules Verne ? Je vous conseillle [ce site](http://www.gutenberg.org).\n",
    "- Quel est le taux de compression obtenu pour le notebook `Huffman.ipynb` ?\n",
    "- Quel est le taux de compression obtenu pour une image `JPG` de la Tour Eiffel (soyez raisonnables sur la taille de l'image, évitez une image de 6 Mo)?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 7 Compléments"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.1 Où est le piège ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Au lieu de coder lettre par lettre, regroupons les lettres $k$ par $k$, où $k\\ge 1$. Voici notre nouvelle fonction `histogramme2`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def histogramme2(s, k):\n",
    "    h = {}\n",
    "    n = len(s)\n",
    "    for i in range(n // k):\n",
    "        a = s[k * i : k * (i + 1)]\n",
    "        if a in h: h[a] += 1\n",
    "        else: h[a] = 1\n",
    "    if n % k != 0:\n",
    "        a = s[k * (n // k):]\n",
    "        h[a] = 1\n",
    "    return h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "h = histogramme2(abra, 2)\n",
    "print(h)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Il nous faut également réécrire la fonction `coder`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def coder2(s, code, k):\n",
    "    s1 = ''\n",
    "    n = len(s)\n",
    "    for i in range(n // k):\n",
    "        a = s[k * i: k * (i + 1)]\n",
    "        s1 = s1 + code[a]\n",
    "    if n % k != 0:\n",
    "        a = s[k * (n // k):]\n",
    "        s1 = s1 + code[a]\n",
    "    return s1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Reprenons notre épopée et lançons un compression avec $k=2$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "K = 2\n",
    "h = histogramme2(virgile, K)\n",
    "print(len(h))\n",
    "t = faire_arbre(h)\n",
    "#print(t)\n",
    "c = faire_codes(t)\n",
    "s1 = coder2(virgile, c, K)\n",
    "s2 = decoder_prefixe(s1, t)\n",
    "print(virgile == s2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Quel est le taux de compression ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(1 - len(s1) / (8 * len(virgile)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous avons donc amélioré le taux de compression. Euh, mais Huffman n'est-il pas optimal ? Oui, __pour un alphabet donné__. Mais en groupant les lettres deux par deux nous travaillons avec un mot sur un alphabet qui est l'ensemble des mots de deux lettres. Une idée nous vient alors à l'esprit : et si nous prenions $k=3$ ? $k=4$ ? $k=16$ ? Vous pouvez essayer en changeant ci-dessus la valeur de $K$. On constate que le taux de compression augmente, augmente ...\n",
    "\n",
    "Allez, soyons fous. Et si nous prenions $k=n-1$ où $n$ est la longueur du mot à coder ? Alors l'arbre de Huffman a deux feuilles, étiquetées par\n",
    "\n",
    "- Le mot $u$ privé de sa dernière lettre, de poids 1\n",
    "- La dernière lettre de $u$, de poids 1.\n",
    "\n",
    "Et le mot $u$ est codé par '01', c'est à dire avec 2 bits. QUEL QUE SOIT $u$.\n",
    "\n",
    "Alors où est le piège ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Si je veux stocker ou transmettre le mot $u$, je le code avec l'algorithme de Huffman ce qui aura pour effet de le compresser. Mais si je veux pouvoir le décoder un jour ... il va me falloir aussi stocker l'arbre de Huffman ! Ainsi, si $c$ est le code de Huffman associé à $u$, je stockerai (par exemple) le couple $(c^*(u), T)$ où $T$ est l'arbre associé au code $T$. Le taux de compression n'est donc pas $\\tau = 1-\\frac{|c^*(u)|}{|u|}$ mais $\\tau'=1-\\frac{|c^*(u)|+|T|}{|u|}=\\tau - \\frac{|T|}{|u|}$ où $|T|$ est la \"taille de $T$\" qui resterait à préciser. Le taux de compression est donc plus faible que prévu.\n",
    "\n",
    "Bon, et alors ? Nous avons menti tout au long du notebook ? Oui et non. Lorsque la taille de $u$ tend vers l'infini, $\\tau'$ tend vers $\\tau$ car pour un alphabet fixé la taille de $T$, elle, reste bornée. Je n'entre pas plus avant dans les détails mais il vaudrait mieux dire que l'algorithme de Huffman est asymptotiquement optimal. Et, toujours sans détailler, oui, il est vrai qu'en regroupant les lettres par paquets de $k$ on obtient des taux de compression asymptotiquement meilleurs en augmentant la valeur de $k$. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.2 Huffman et Shannon"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Soit $A$ un alphabet pondéré. Pour $\\alpha\\in A$, soit $P(\\alpha) = \\frac{\\pi(\\alpha)} N$ où $N$ est la somme de tous les poids des lettres. $P$ définit une probabilité sur $A$. Appelons __entropie__ de $A$ la quantité :\n",
    "\n",
    "$$\\mathcal H(A)=-\\sum_{\\alpha\\in A}P(\\alpha)\\lg P(\\alpha)$$\n",
    "\n",
    "où $\\lg$ désigne le logarithme en base 2. Pour tout mot $u$, l'entropie de $u$ est alors l'entropie de l'alphabet pondéré associé à $u$.\n",
    "\n",
    "Le nombre $\\mathcal H(u)$ est la __quantité d'information__ contenue dans $u$ (ou $A$). Il est mesuré en __bits__. La justification de cette appellation nécessiterait un exposé à part entière et nous admettrons qu'elle est cohérente."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def entropie(u):\n",
    "    n = len(u)\n",
    "    h = histogramme(u)\n",
    "    s = 0\n",
    "    for a in h:\n",
    "        P = h[a] / n\n",
    "        s = s - P * math.log(P, 2)\n",
    "    return s"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Prenons l'exemple de notre épopée :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "entropie(virgile)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "L'énéide a une entropie de 4.318. Virgile s'en doutait-il ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Théorème du codage sans bruit (Shannon)__ : Soit $u$ un mot. Soit $A$ l'alphabet pondéré associé à $u$. Soit enfin $c$ un code préfixe optimal pour $u$. Alors :\n",
    "\n",
    "$$\\mathcal H(u)\\le \\sum_{\\alpha\\in A}P(\\alpha)|c(\\alpha)|< \\mathcal H(u) + 1$$\n",
    "\n",
    "Ce notebook étant déjà d'une longueur terrible, je ne prouverai pas ce théorème. Mais c'est quoi $\\sum_{\\alpha\\in A}P(\\alpha)|c(\\alpha)|$ ? Ce n'est rien d'autre que $\\frac 1 {|u|}\\sum_{\\alpha\\in A}\\pi(\\alpha)|c(\\alpha)|=\\frac{|c^*(u)|}{|u|}=\\frac{\\mathcal B(c)}{|u|}$, quantité fortement liée à ce que nous avons appelé le taux de compression.. Que nous raconte le théorème du codage sans bruit ? Il nous dit que \n",
    "\n",
    "- $\\mathcal H(u)$ est une borne inférieure infranchissable pour tout codage préfixe de $u$.\n",
    "- Un codage préfixe optimal est égal à cette borne inférieure, à 1 près. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Exercice__ : Soit $A$ un alphabet ayant $n$ lettres de poids tous égaux. Montrer que $\\mathcal H(A)=\\lg n$. Que vaut $\\mathcal H(A)$ si $n=256$ ? Nous venons de montrer que la quantité d'information d'un octet aléatoire est égale à 8 bits :-). \n",
    "\n",
    "__Exercice__ : Que vaut $\\sum_{\\alpha\\in A}P(\\alpha)|c(\\alpha)|$ si $c$ est le code ASCII ? En déduire en utilisant le théorème de Shannon que pour tout alphabet $A$ ayant 256 lettres (de poids quelconques), $\\mathcal H(A) \\le 8$. Le code ASCII possède donc le pire taux imaginable. Mais ne lui jetons pas la pierre parce qu'il peut coder TOUS les mots !\n",
    "\n",
    "__Exercice__ : Seriez-vous capables de généraliser le résultat précédent, sans utiliser le théorème de Shannon, pour un alphabet à $n$ lettres avec $n\\ge 2$ quelconque ? Indication : la fonction $\\lg$ est une fonction concave. Elle vérifie donc des inégalités bien connues."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def taux(u, code):\n",
    "    n = len(u)\n",
    "    h = histogramme(u)\n",
    "    s = 0\n",
    "    for a in h:\n",
    "        P = h[a] / n\n",
    "        s = s + P * len(code[a])\n",
    "    return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "h = histogramme(virgile)\n",
    "t = faire_arbre(h)\n",
    "c = faire_codes(t)\n",
    "print(taux(virgile, c))\n",
    "#s1 = coder(s, c)\n",
    "#print(len(s1) / len(s))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Exercice__ :\n",
    "\n",
    "- Quelle est l'entropie de Voyage au Centre de la Terre ?\n",
    "- Quelle est l'entropie du notebook `Huffman.ipynb` ?\n",
    "- Quelle est l'entropie d'une image `JPG` de la Tour Eiffel ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.3 On n'est pas à 1 bit près ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le 1 dans le majorant du théorème de Shannon n'a pas l'air bien méchant. Pour l'Énéide l'entropie est d'environ 4.32 alors que le taux est 4.35. Maintenant, imaginons une entropie très faible, 0.01 par exemple. Et un taux égal à 1. Le taux serait alors égal à 100 fois l'entropie ! Quand cela arrive-t-il ? Prenons un alphabet $A=\\{a,b\\}$ de deux lettres, avec $\\pi(a)=N\\in\\mathbb N^*$ et $\\pi(b)=1$. On a\n",
    "\n",
    "$$\\mathcal H(A)=-\\frac{N}{N+1}\\lg(\\frac N {N+1})-\\frac{1}{N+1}\\lg(\\frac 1 {N+1})=\\frac{N}{N+1}\\lg(1+\\frac 1 {N})+\\frac{1}{N+1}\\lg(N+1)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le code de Huffman associé à cet alphabet code la lettre $a$ par '1' et la lettre $b$ par '0' (ou le contraire si $N=1$). Le taux associé est\n",
    "\n",
    "$$\\tau = 1$$\n",
    "\n",
    "On a $\\mathcal H(A)\\to 0$ lorsque $N$ tend vers l'infini, alors que $\\tau$ reste constant égal à 1. Ainsi, $\\frac{\\tau}{\\mathcal H(A)}\\to +\\infty$ lorsque $N$ tend vers l'infini, ce qui est très mauvais.\n",
    "\n",
    "Ainsi 1 bit fait __TOUTE__ la différence ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.4 Et après ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Si vous compressez le fichier `eneide.txt` au format `zip` vous obtiendrez un taux de compression d'environ 0.6. C'est en tout cas ce que j'obtiens sur ma machine. C'est mieux que Huffman. Alors, Huffman n'est pas optimal ?\n",
    "\n",
    "S'il faut retenir __UNE__ chose de ce notebook c'est que \"être optimal\" est une expression qui n'a aucun sens en soi. On est toujours optimal __dans un certain contexte__. Nous avons prouvé des résultats très précis sur le code de Huffman, en l'occurence que pour un alphabet __fixé__ avec des poids de lettres __fixés__ le code de Huffman est optimal parmi les codes __préfixes__. Cela fait beaucoup de conditions ... Je n'irai pas plus avnt, la théorie de la compression est vaste et riche, nous n'avons fait que lever un coin du voile."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Exercice__ : Lisez l'Énéide."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}