Codage par paires d'octets.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.6"
    },
    "colab": {
      "name": "Codage par paires d'octets.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%20par%20paires%20d'octets.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "NoE6SSfSjQn8",
        "colab_type": "text"
      },
      "source": [
        "INF8770 Technologies multimédias\n",
        "\n",
        "Polytechnique Montréal\n",
        "\n",
        "Exemple de codage par paires d'octets"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "IEq4hotmjQn_",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "import numpy as np\n",
        "import regex as re"
      ],
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "bhdjKSN_jQoL",
        "colab_type": "text"
      },
      "source": [
        "Message à coder"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "C8eQ20PqjQoN",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "Message = \"ABAABAABACABBABCDAADACABABAAABAABBABABAABAAB\""
      ],
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "bDa6VP5CjQoX",
        "colab_type": "text"
      },
      "source": [
        "Vérification des octets utilisés. Utilisation d'une table pour faire le suivi."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "6_VpIdDNjQoY",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "LUToctetsdispo = [True] * 256\n",
        "dictsymb =[Message[0]]\n",
        "LUToctetsdispo[ord(Message[0])] = False\n",
        "nbsymboles = 1\n",
        "for i in range(1,len(Message)):\n",
        "    if Message[i] not in dictsymb:\n",
        "        dictsymb += [Message[i]]\n",
        "        LUToctetsdispo[ord(Message[i])] = False  #Octet utilisé\n",
        "        nbsymboles += 1\n",
        "        \n",
        "longueurOriginale = np.ceil(np.log2(nbsymboles))*len(Message)   \n",
        "nboctets = len(Message) "
      ],
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RbkXWUkxjQog",
        "colab_type": "text"
      },
      "source": [
        "Codage du message"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ZfgaJTsjjQoi",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 445
        },
        "outputId": "58ccc37c-6358-4dbb-b476-592a3e1162f2"
      },
      "source": [
        "dictsymb = []  #Dictionnaire des substitutions\n",
        "debut = ord(Message[0])  # Origine trouver un code de substitution. Et pour avoir des caractères imprimables...\n",
        "\n",
        "remplacementpossible = True\n",
        "while remplacementpossible == True:\n",
        "    #Recherche des paires\n",
        "    paires = []\n",
        "    for i in range(0,len(Message)-1):\n",
        "        temppaire = Message[i]+Message[i+1]\n",
        "        if not list(filter(lambda x: x[0] == temppaire, paires)): #Si la liste retournée par filter est vide.\n",
        "            paires += [[temppaire,len(re.findall(temppaire, Message, overlapped = True))]]\n",
        "\n",
        "    #Trouve la paire avec le plus de répétitions.\n",
        "    paires = sorted(paires, key=lambda x: x[1], reverse = True)\n",
        "\n",
        "    if paires[0][1] > 1:\n",
        "        #Remplace la paire\n",
        "        print(paires)\n",
        "        print(\"La paire \",paires[0][0], \" est la plus fréquente avec \",paires[0][1], \"répétitions\")\n",
        "        #Cherche un octet non utilisé\n",
        "        while debut <256 and LUToctetsdispo[debut] == False:\n",
        "            debut += 1\n",
        "        if debut < 256:     \n",
        "            #On substitut\n",
        "            Message = Message.replace(paires[0][0], chr(debut))\n",
        "            LUToctetsdispo[debut] = False\n",
        "            dictsymb += [[paires[0][0], chr(debut)]]\n",
        "            nbsymboles += 1\n",
        "        else:\n",
        "            print(\"Il n'y a plus d'octets disponible!\") #Bien sûr, ce n'est pas exact car la recherche commence à Message[0]\n",
        "        \n",
        "        print(Message)\n",
        "        print(dictsymb)\n",
        "    else:\n",
        "        remplacementpossible = False"
      ],
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[['AB', 13], ['BA', 11], ['AA', 8], ['AC', 2], ['CA', 2], ['BB', 2], ['DA', 2], ['BC', 1], ['CD', 1], ['AD', 1]]\n",
            "La paire  AB  est la plus fréquente avec  13 répétitions\n",
            "EAEAEACEBECDAADACEEAAEAEBEEAEAE\n",
            "[['AB', 'E']]\n",
            "[['EA', 7], ['AE', 6], ['AC', 2], ['CE', 2], ['EB', 2], ['BE', 2], ['DA', 2], ['AA', 2], ['EE', 2], ['EC', 1], ['CD', 1], ['AD', 1]]\n",
            "La paire  EA  est la plus fréquente avec  7 répétitions\n",
            "FFFCEBECDAADACEFAFEBEFFE\n",
            "[['AB', 'E'], ['EA', 'F']]\n",
            "[['FF', 3], ['CE', 2], ['EB', 2], ['BE', 2], ['DA', 2], ['EF', 2], ['FE', 2], ['FC', 1], ['EC', 1], ['CD', 1], ['AA', 1], ['AD', 1], ['AC', 1], ['FA', 1], ['AF', 1]]\n",
            "La paire  FF  est la plus fréquente avec  3 répétitions\n",
            "GFCEBECDAADACEFAFEBEGE\n",
            "[['AB', 'E'], ['EA', 'F'], ['FF', 'G']]\n",
            "[['CE', 2], ['EB', 2], ['BE', 2], ['DA', 2], ['GF', 1], ['FC', 1], ['EC', 1], ['CD', 1], ['AA', 1], ['AD', 1], ['AC', 1], ['EF', 1], ['FA', 1], ['AF', 1], ['FE', 1], ['EG', 1], ['GE', 1]]\n",
            "La paire  CE  est la plus fréquente avec  2 répétitions\n",
            "GFHBECDAADAHFAFEBEGE\n",
            "[['AB', 'E'], ['EA', 'F'], ['FF', 'G'], ['CE', 'H']]\n",
            "[['BE', 2], ['DA', 2], ['GF', 1], ['FH', 1], ['HB', 1], ['EC', 1], ['CD', 1], ['AA', 1], ['AD', 1], ['AH', 1], ['HF', 1], ['FA', 1], ['AF', 1], ['FE', 1], ['EB', 1], ['EG', 1], ['GE', 1]]\n",
            "La paire  BE  est la plus fréquente avec  2 répétitions\n",
            "GFHICDAADAHFAFEIGE\n",
            "[['AB', 'E'], ['EA', 'F'], ['FF', 'G'], ['CE', 'H'], ['BE', 'I']]\n",
            "[['DA', 2], ['GF', 1], ['FH', 1], ['HI', 1], ['IC', 1], ['CD', 1], ['AA', 1], ['AD', 1], ['AH', 1], ['HF', 1], ['FA', 1], ['AF', 1], ['FE', 1], ['EI', 1], ['IG', 1], ['GE', 1]]\n",
            "La paire  DA  est la plus fréquente avec  2 répétitions\n",
            "GFHICJAJHFAFEIGE\n",
            "[['AB', 'E'], ['EA', 'F'], ['FF', 'G'], ['CE', 'H'], ['BE', 'I'], ['DA', 'J']]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "EW_tJVjLjQoq",
        "colab_type": "text"
      },
      "source": [
        "Longueur en bits du message codé et celle de l'original"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "VijP_nZTjQor",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 51
        },
        "outputId": "d1429917-c6fd-418d-ab01-d9192daf2b1b"
      },
      "source": [
        "print(\"Longueur = {0}\".format(np.ceil(np.log2(nbsymboles))*len(Message)))\n",
        "print(\"Longueur originale = {0}\".format(longueurOriginale))"
      ],
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Longueur = 64.0\n",
            "Longueur originale = 88.0\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Chyj1UDWcmmk",
        "colab_type": "text"
      },
      "source": [
        "Mais si on suit strictement la définition du codage par paires d'octets, les longueurs en octets sont:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "I34qgloDczqj",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 51
        },
        "outputId": "6efddf24-4325-486e-d1a2-7bfb7b388145"
      },
      "source": [
        "print(\"Longueur = {0}\".format(len(Message)))\n",
        "print(\"Longueur originale = {0}\".format(nboctets))"
      ],
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Longueur = 16\n",
            "Longueur originale = 44\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}