{ "cells": [ { "cell_type": "markdown", "metadata": { "toc": "true" }, "source": [ "# Table of Contents\n", "
" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "b4d399ae-27e7-426f-a2ac-c79b5a6cb02f" } }, "source": [ "# Table des matières\n", "* [1. Agrégation externe de mathématiques](#1.-Agrégation-externe-de-mathématiques)\n", "\t* [1.1 Leçon orale, option informatique](#1.1-Leçon-orale,-option-informatique)\n", "* [2. Calcul du plus long sous mot commun](#2.-Calcul-du-plus-long-sous-mot-commun)\n", "\t* \n", "\t\t* [2.0.1 Implémentation d'un développement pour les leçons 906, 907.](#2.0.1-Implémentation-d'un-développement-pour-les-leçons-906,-907.)\n", "\t\t* [2.0.2 Références :](#2.0.2-Références-:)\n", "\t\t* [2.0.3 Applications, généralisations :](#2.0.3-Applications,-généralisations-:)\n", "* [3. Algorithme naïf (exponentiel)](#3.-Algorithme-naïf-%28exponentiel%29)\n", "\t* [3.1 Détecter si $u$ est sous mot de $y$](#3.1-Détecter-si-$u$-est-sous-mot-de-$y$)\n", "\t* [3.2 Trouver *un* sous-mot de longueur ``k``](#3.2-Trouver-*un*-sous-mot-de-longueur-k)\n", "\t* [3.3 Sous-mot de longueur maximale (version naïve)](#3.3-Sous-mot-de-longueur-maximale-%28version-naïve%29)\n", "* [4. Méthode gloutonne (programmation dynamique)](#4.-Méthode-gloutonne-%28programmation-dynamique%29)\n", "\t* [4.1 Programmation dynamique, sans optimisation mémoire](#4.1-Programmation-dynamique,-sans-optimisation-mémoire)\n", "\t* [4.2 Utilisation d'une matrice *creuse*](#4.2-Utilisation-d'une-matrice-*creuse*)\n", "\t\t* [4.2.1 Version condensée](#4.2.1-Version-condensée)\n", "* [5. Calcule de la plus longue sous-séquence commune](#5.-Calcule-de-la-plus-longue-sous-séquence-commune)\n", "\t* [5.1 Vérifier qu'une sous-séquence est une bonne sous-séquence](#5.1-Vérifier-qu'une-sous-séquence-est-une-bonne-sous-séquence)\n", "\t* [5.2 Algorithme pour la plus longue sous-séquence](#5.2-Algorithme-pour-la-plus-longue-sous-séquence)\n", "\t\t* [5.2.1 Exemple, venant du développement](#5.2.1-Exemple,-venant-du-développement)\n", "\t\t* [5.2.2 Autres exemples](#5.2.2-Autres-exemples)\n" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "8dbcdbe6-b5e4-4803-b5bf-d591a1c0c4c4" } }, "source": [ "# 1. Agrégation externe de mathématiques" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "5ec8bf14-57ad-4e1b-8b13-d7da42924760" } }, "source": [ "## 1.1 Leçon orale, option informatique" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "e8ba8fa2-6f98-4431-8222-c897d1145a15" } }, "source": [ "> - Ce [notebook Jupyter](http://jupyter.org/) est une implémentation d'un algorithme constituant un développement pour l'option informatique de l'agrégation externe de mathématiques.\n", "> - Il s'agit du calcul du [plus long sous mot commun](https://fr.wikipedia.org/wiki/Plus_longue_sous-séquence_commune).\n", "> - Cette implémentation (partielle) a été rédigée par [Lilian Besson](http://perso.crans.org/besson/) ([sur GitHub ?](https://github.com/Naereen/), [sur Bitbucket ?](https://bitbucket.org/lbesson)), et [est open-source](https://github.com/Naereen/notebooks/blob/master/agreg/Plus%20long%20sous%20mot%20commun%20%28python3%29.ipynb).\n", "\n", "> #### Feedbacks?\n", "> - Vous avez trouvé un bug ? → [Signalez-le moi svp !](https://github.com/Naereen/notebooks/issues/new), merci d'avance.\n", "> - Vous avez une question ? → [Posez la svp !](https://github.com/Naereen/ama.fr) [![Demandez moi n'importe quoi !](https://img.shields.io/badge/Demandez%20moi-n'%20importe%20quoi-1abc9c.svg)](https://GitHub.com/Naereen/ama.fr)\n", "\n", "----" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "30fc4b21-e1d3-4823-b437-4e300f2f07b9" } }, "source": [ "# 2. Calcul du plus long sous mot commun" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "7ccc0315-1973-4d63-849a-246a327f7e98" } }, "source": [ "### 2.0.1 Implémentation d'un développement pour les leçons 906, 907." ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "bfb9ef9f-8bcf-4100-8c99-57bf8959c57b" } }, "source": [ "On présente ici un algorithme de programmation dynamique pour **le calcul du plus long sous mot commun** (attention, c'est différent de la plus longue sous séquence commune !).\n", "\n", "Étant donnés deux mots $X = x_1 \\dots x_m$ et $Y = y_1 \\dots y_n$ sur un alphabet $\\Sigma$, on cherche à savoir quel est le plus long sous-mot commun à $X$ et $Y$.\n", "Un sous-mot correspond à un morceau commun aux deux mots : on extraie de **façon consécutive** une sous-séquence de $x$ et $y$ et elles doivent être égales : $u = x_{i_0} \\dots x_{i_0 + k} = y_{j_0} \\dots y_{j_0 + k} = v$ !\n", "\n", "La solution naïve est d’énumérer tous les sous-mots de $X$, et de regarder ensuite s'ils sont aussi sous-mots de\n", "$Y$, mais cette solution est inefficace : il y a $\\mathcal{O}(2^m)$ sous-mots de X...\n", "\n", "L'objectif est donc d'obtenir un algorithme plus efficace, si possible polynomial en $m = |X|$ et $n = |Y|$ (il sera en $\\mathcal{O}(m n)$)." ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "1d33ae35-b5e7-4ccc-8c63-39831848cbed" } }, "source": [ "### 2.0.2 Références :" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "2e792d1e-c43e-486e-8edc-6ad23f73fa03" } }, "source": [ "- Bien traité dans [\"Cormen\", Ch15.4 p341](https://catalogue.ens-cachan.fr/cgi-bin/koha/opac-detail.pl?biblionumber=15671),\n", "- Esquissé dans [\"Aho, Hopcroft, Ullman\", Ch5.6 p192](https://catalogue.ens-cachan.fr/cgi-bin/koha/opac-detail.pl?biblionumber=35831),\n", "- [Dévéloppement tapé en PDF ici](http://minerve.bretagne.ens-cachan.fr/images/Dvt_plsc.pdf)." ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "fe95c114-6e8b-498d-9c9a-41cb8d9208ce" } }, "source": [ "### 2.0.3 Applications, généralisations :" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "78e99f8a-7548-4572-b1b2-f8bec7116db0" } }, "source": [ "- Un généralisation est le calcul de la plus longue sous-sequence commune, pour lequel on ne se restreint plus à extraire de façon consécutive (ca semble plus compliqué, mais le même algorithme permet de régler le problème avec la même complexité, en fait).\n", "- On peut citer en application la comparaison de chaînes d'ADN, mais aussi la commande ``diff`` des systèmes GNU/Linux.\n", "- Généralisation : aucune chance d'avoir un algorithme aussi efficace s'il s'agit de trouver le plus long sous mot commun à $K$ chaînes de caractères (et en fait, le probleme général est $\\mathcal{NP}$, en le nombre de chaînes, [comme expliqué ici (en anglais)](https://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Complexity)).\n", "\n", "----" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "fdd83dc1-2853-4125-8090-947f35da5a5c" } }, "source": [ "# 3. Algorithme naïf (exponentiel)" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "bd505a24-4f2d-4f14-9a90-126ad2c5c2ea" } }, "source": [ "On va d'abord montrer rapidement une implémentation simple de l'algorithme naïf, pour ensuite vérifier que l'algorithme plus complexe fonctionne aussi bien." ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "d9f646a4-f5b9-482b-aaf2-eaa055292db0" } }, "source": [ "## 3.1 Détecter si $u$ est sous mot de $y$" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "42af5ecb-6024-4366-94ef-a3e32a6db894" } }, "source": [ "L'objectif de toutes les fonctions suivantes est de proscrire toute recopie de chaines (*slicing*, ``x[i:j]``), qui sont très couteuse." ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "nbpresent": { "id": "874d2766-f8ac-47c6-8315-fb5ff2c1016b" } }, "outputs": [], "source": [ "def indiceSousMotAux(u, n, k, y, m, i, delta=0):\n", " \"\"\" Fonction tail-récursive qui trouve l'indice j tel que u[k:k+n] = y[i+j:i+j+n], ou -1 en cas d'échec.\"\"\"\n", " # print(\"{}indiceSousMotAux(u = {}, n = {}, k = {}, y = {}, m = {}, i = {}, delta = {})\".format(' '*delta, u, n, k, y, m, i, delta)) # DEBUG\n", " if n == 0: # Mot vide, commun partout, par defaut on donne 0\n", " return 0\n", " else: # Mot pas vide\n", " if k >= len(u) or i >= m: # On a cherché trop loin, échec\n", " return -1 # -1 signifie échec\n", " elif u[k] == y[i]: # Lettre en commun\n", " if delta == n - 1: # On a fini, on a trouvé !\n", " return i - n + 1 # i est l'indice de la derniere lettre ici\n", " else: # On continue de chercher, une lettre de moins\n", " return indiceSousMotAux(u, n, k + 1, y, m, i + 1, delta=delta+1)\n", " else: # On recommence a chercher en i+1\n", " return indiceSousMotAux(u, n, k - delta, y, m, i + 1)\n", "\n", "\n", "def indiceSousMot(u, y):\n", " \"\"\" En O(|u|), trouve l'indice j tel que u = y[j:j+|u|], ou -1 en cas d'échec.\"\"\"\n", " return indiceSousMotAux(u, len(u), 0, y, len(y), 0)\n", "\n", "\n", "def estSousMot(u, y):\n", " \"\"\" Vérifie en O(|u|) si u est sous-mot de y.\"\"\"\n", " return indiceSousMotAux(u, len(u), 0, y, len(y), 0) >= 0" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "77640a71-1cc5-47c9-ae52-940ec6c95024" } }, "source": [ "Quelques tests :" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "nbpresent": { "id": "69a559a9-9d4f-43d5-bc83-12c2b0abc776" }, "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Le mot u = 'cde' est sous-mot de y = 'abcdefghijklmnopqrstuvwxyz', a partir de l'indice i = 2.\n", "Le mot u = 'cde' n'est pas sous-mot de y = 'abcDefghijklmnopqrstuvwxyz'.\n" ] } ], "source": [ "def test_estSousMot(u, y):\n", " \"\"\" Teste et affiche. \"\"\"\n", " i = indiceSousMot(u, y)\n", " if i >= 0:\n", " print(\"Le mot u = '{}' est sous-mot de y = '{}', a partir de l'indice i = {}.\".format(u, y, i))\n", " else:\n", " print(\"Le mot u = '{}' n'est pas sous-mot de y = '{}'.\".format(u, y)) \n", "\n", "\n", "u = \"cde\"\n", "y1 = \"abcdefghijklmnopqrstuvwxyz\"\n", "test_estSousMot(u, y1) # True\n", "\n", "y2 = \"abcDefghijklmnopqrstuvwxyz\"\n", "test_estSousMot(u, y2) # False" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "861c638f-ec78-4001-b39c-875cce76dfdc" } }, "source": [ "## 3.2 Trouver *un* sous-mot de longueur ``k``" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "d7fdbdf8-251b-4756-9e47-ac3110b5c849" } }, "source": [ "On peut chercher **tous** les sous-mots de longueur ``k`` dans ``x`` et regarder si l'**un d'entre eux** est inclus dans y (on s'arrête dès qu'on en a trouvé un) :" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "nbpresent": { "id": "35222aea-86e6-4146-9019-9528e53a7570" } }, "outputs": [], "source": [ "def aSousMotDeLongueur(x, y, k):\n", " \"\"\" Trouve le premier sous-mot de x de longueur k et renvoit i, j, u, ou échoue avec une ValueError. \"\"\"\n", " imax = len(x) - k + 1\n", " # Les sous mots seront x0..xk-1, .., ximax-1,..,xn-1\n", " for debut in range(imax):\n", " j = indiceSousMotAux(x, k, debut, y, len(y), 0)\n", " if j >= 0:\n", " return debut, debut + j, x[debut:debut+k]\n", " # Pas trouvé !\n", " raise ValueError(\"Aucun sous-mot de longueur k = {} de x = '{}' n'est dans y = '{}'.\".format(k, x, y))" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "3c02fca1-76e3-45f8-8a66-71708b4ddc6b" } }, "source": [ "Un test :" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "nbpresent": { "id": "97260746-1fd8-4fa0-8c0f-1a71a4a54c11" }, "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "==> Sous-mot de longueur k = 0 de x = 'aabcde' dans y = 'aABcdE' : u = '' en indice i = 0 pour x et j = 0 pour y.\n", "==> Sous-mot de longueur k = 1 de x = 'aabcde' dans y = 'aABcdE' : u = 'a' en indice i = 0 pour x et j = 0 pour y.\n", "==> Sous-mot de longueur k = 2 de x = 'aabcde' dans y = 'aABcdE' : u = 'cd' en indice i = 3 pour x et j = 6 pour y.\n", "==> Aucun sous-mot de longueur k = 3 de x = 'aabcde' n'est dans y = 'aABcdE'.\n", "==> Aucun sous-mot de longueur k = 4 de x = 'aabcde' n'est dans y = 'aABcdE'.\n", "==> Aucun sous-mot de longueur k = 5 de x = 'aabcde' n'est dans y = 'aABcdE'.\n", "==> Aucun sous-mot de longueur k = 6 de x = 'aabcde' n'est dans y = 'aABcdE'.\n", "==> Sous-mot de longueur k = 0 de x = 'aabffcde' dans y = 'aABGGGGGcdE' : u = '' en indice i = 0 pour x et j = 0 pour y.\n", "==> Sous-mot de longueur k = 1 de x = 'aabffcde' dans y = 'aABGGGGGcdE' : u = 'a' en indice i = 0 pour x et j = 0 pour y.\n", "==> Sous-mot de longueur k = 2 de x = 'aabffcde' dans y = 'aABGGGGGcdE' : u = 'cd' en indice i = 5 pour x et j = 13 pour y.\n", "==> Aucun sous-mot de longueur k = 3 de x = 'aabffcde' n'est dans y = 'aABGGGGGcdE'.\n", "==> Aucun sous-mot de longueur k = 4 de x = 'aabffcde' n'est dans y = 'aABGGGGGcdE'.\n", "==> Aucun sous-mot de longueur k = 5 de x = 'aabffcde' n'est dans y = 'aABGGGGGcdE'.\n", "==> Aucun sous-mot de longueur k = 6 de x = 'aabffcde' n'est dans y = 'aABGGGGGcdE'.\n", "==> Aucun sous-mot de longueur k = 7 de x = 'aabffcde' n'est dans y = 'aABGGGGGcdE'.\n", "==> Aucun sous-mot de longueur k = 8 de x = 'aabffcde' n'est dans y = 'aABGGGGGcdE'.\n" ] } ], "source": [ "def test_aSousMotDeLongueur(x, y, k):\n", " \"\"\" Teste et affiche. \"\"\"\n", " try:\n", " i, j, u = aSousMotDeLongueur(x, y, k)\n", " print(\"==> Sous-mot de longueur k = {} de x = '{}' dans y = '{}' : u = '{}' en indice i = {} pour x et j = {} pour y.\".format(k, x, y, u, i, j))\n", " except ValueError:\n", " print(\"==> Aucun sous-mot de longueur k = {} de x = '{}' n'est dans y = '{}'.\".format(k, x, y))\n", "\n", "x = \"aabcde\"\n", "y = \"aABcdE\"\n", "for k in range(0, min(len(x), len(y)) + 1):\n", " test_aSousMotDeLongueur(x, y, k)\n", "\n", "x = \"aabffcde\"\n", "y = \"aABGGGGGcdE\"\n", "for k in range(0, min(len(x), len(y)) + 1):\n", " test_aSousMotDeLongueur(x, y, k)" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "c4aafc17-eed8-4830-8333-02a98f4ccb8b" } }, "source": [ "## 3.3 Sous-mot de longueur maximale (version naïve)" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "nbpresent": { "id": "b8b90419-d1ec-4439-890e-9717780094b3" } }, "outputs": [], "source": [ "def _sousMotMax(x, y, verb=True):\n", " \"\"\" |x| doit etre plus petit que |y|.\"\"\"\n", " k = len(x)\n", " while k >= 0:\n", " if verb:\n", " print(\" On essaie de trouver un sous-mot commun à x = '{}' et y = '{}' de taille k = {} ...\".format(x, y, k))\n", " try:\n", " i, j, u = aSousMotDeLongueur(x, y, k)\n", " if verb:\n", " print(\" ==> On a un sous-mot commun à x = '{}' et y = '{}' de taille k = {} : u = '{}' (i = {}, j = {}) !\".format(x, y, k, u, i, j))\n", " return i, j, u\n", " except ValueError:\n", " if verb:\n", " print(\" ==> Aucun sous-mot commun à x = '{}' et y = '{}' de taille k = {} ...\".format(x, y, k))\n", " k -= 1\n", "\n", " \n", "def sousMotMax(x, y, verb=True):\n", " \"\"\" Trouve un sous-mot de longueur maximale (le plus à gauche possible de x et y), en temps exponentiel en n = |x|.\"\"\"\n", " if len(x) <= len(y):\n", " return _sousMotMax(x, y, verb=verb)\n", " else:\n", " return _sousMotMax(y, x, verb=verb)" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "4519e7df-5d72-44be-ab36-44c1e2d04268" } }, "source": [ "Quelques tests :" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "nbpresent": { "id": "7fa5fa37-e894-4caa-8052-55d6ce2677d4" } }, "outputs": [ { "data": { "text/plain": [ "(9, 18, '123456abc')" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x = \"abcABCabc123456abcABCabc99\"\n", "y = \"abcDEFdef123456abcDEFdef9999\"\n", "sousMotMax(x, y, verb=False)" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "nbpresent": { "id": "6c587b6e-3c08-48f2-877d-11454634634d" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " On essaie de trouver un sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 9 ...\n", " ==> Aucun sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 9 ...\n", " On essaie de trouver un sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 8 ...\n", " ==> Aucun sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 8 ...\n", " On essaie de trouver un sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 7 ...\n", " ==> Aucun sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 7 ...\n", " On essaie de trouver un sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 6 ...\n", " ==> Aucun sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 6 ...\n", " On essaie de trouver un sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 5 ...\n", " ==> Aucun sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 5 ...\n", " On essaie de trouver un sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 4 ...\n", " ==> Aucun sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 4 ...\n", " On essaie de trouver un sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 3 ...\n", " ==> On a un sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 3 : u = 'abc' (i = 0, j = 0) !\n" ] }, { "data": { "text/plain": [ "(0, 0, 'abc')" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x = \"abcABCabc\"\n", "y = \"abcDEFdef\"\n", "sousMotMax(x, y)" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "4e2a85b7-6833-442a-bfae-cfd3fb98ca45" } }, "source": [ "# 4. Méthode gloutonne (programmation dynamique)" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "bd1de069-0df7-48bc-83f7-f5e061a7d06e" } }, "source": [ "On passe désormais à la seconde approche, qui sera bien plus efficace (et qui montrera que le probleme du plus long sous-mot commun de deux mots est dans $\\mathcal{P}$)." ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "80e8a873-9828-444d-9c44-e5d980c7c0eb" } }, "source": [ "Cette approche a l'avantage d'être bien plus efficace, mais aussi plus simple à coder.\n", "On a juste besoin d'une matrice de taille $(|x|+1)(|y|+1)$ (un ``numpy.array``, pour être plus efficace qu'une liste de liste), et quelques boucles ``for``." ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "nbpresent": { "id": "5cc3b653-680e-4d7f-b888-f84b5af084dd" } }, "outputs": [], "source": [ "# On a besoin du module numpy. Cf. http://numpy.org/ pour l'installer si besoin\n", "import numpy as np" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "21cc9ac6-1dd1-4456-a880-56876759502b" } }, "source": [ "## 4.1 Programmation dynamique, sans optimisation mémoire" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "d4e520ac-1237-43a3-9364-64aad7136867" } }, "source": [ "La fonction ci-dessous procède en 4 étapes :\n", "\n", "1. Initialisation de la matrice ``longueurs``, pleine de $0$ et de taille $(n+1) \\times (m+1)$ où $y := |x|$ et $m := |y|$,\n", "2. Calcul \"bottom-up\" de la matrice ``longueurs``, par l'équation suivante :\n", " $$ \\mathrm{longueurs}[i, j] = 1 + \\mathrm{longueurs}[i-1, j-1] \\; \\text{si} \\; x[i-1] = y[i-1]. $$\n", "3. Calcul de la longueur maximale d'une correspondance entre ``x`` et ``y``, par un simple parcours (``longueur_max``), et calcul des indices de début de cette coresspondance maximale (= plus long sous-mot !), ``idebut`` et ``jdebut``.\n", "4. (optionnel) On vérifie que ``x[idebut : idebut + longueur_max]`` = ``y[jdebut : jdebut + longueur_max]``.\n", "\n", "\n", "On commence en utilisant une matrice, pleine de $0$ (ie. une matrice nulle).\n", "Comme on va le voir dans les exemples ci-dessous, en pratique cette matrice restera presque \"vide\", consommant beaucoup de memoire ($\\mathcal{O}(n m)$) inutilement.\n", "La version suivante sera optimisée (en utilisant une matrice *sparse*, ie. creuse)." ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "38788d23-75be-41f6-9145-ce2c398f2822" } }, "source": [ "Cet algorithme sera en :\n", "\n", "- $\\mathcal{O}(n m)$ en mémoire, dans tous les cas (mais on peut faire mieux),\n", "- $\\mathcal{O}(n m)$ en temps, dans tous les cas (et on ne peut pas faire mieux).\n", "\n", "----" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "nbpresent": { "id": "05ce1f79-4f0b-445b-95a7-fba4ddf88b56" } }, "outputs": [], "source": [ "def sousMotMaxGlouton(x, y, verb=False, verifie=True):\n", " \"\"\" Calcule le plus long sous-mot commun a x et y, par programmation dynamique.\n", " \n", " - affiche un peu ce qu'il se passe si verb=True,\n", " - vérifie que le sous-mot commun est bien un bon sous-mot commun si verifie=True.\n", " \"\"\"\n", " def message(*args):\n", " if verb:\n", " print(*args) \n", " # 1. et 2. Initialisation et construction Matrice longueurs\n", " n = len(x)\n", " m = len(y)\n", " message(\"\\n1. Initialisation de la look-up matrice longueurs de taille (n+1, m+1) : n = {} m = {} ...\".format(n, m))\n", " longueurs = np.zeros((n+1, m+1), dtype=int)\n", " message(\"2. Construction bottom-up de la loop-up matrice longueurs ...\")\n", " for i in range(1, n+1):\n", " for j in range(1, m+1):\n", " if x[i-1] == y[j-1]:\n", " longueurs[i, j] = 1 + longueurs[i-1, j-1]\n", " message(\" Correspondance en cours, u[{}] = {} et v[{}] = {}, de longueur courante {} ...\".format(i-1, x[i-1], j-1, y[j-1], longueurs[i, j]))\n", " # 3. Utilisation de la matrice longueurs\n", " iFin, jFin = 0, 0\n", " longueur_max = -1 # Pas encore\n", " message(\"3. Calcul de la position du plus long sous mot via la matrice longueurs ...\")\n", " for i in range(0, n+1):\n", " for j in range(0, m+1):\n", " if longueur_max < longueurs[i, j]:\n", " longueur_max = longueurs[i, j]\n", " iFin, jFin = i, j\n", " # Note : avec les fonctions numpy np.max et np.argmax on pourrait faire ça plus vite (pour des matrices) :\n", " # longueur_max = np.max(longueurs)\n", " # iFin, jFin = np.unravel_index(np.argmax(longueurs), np.shape(longueurs))\n", " # Calcul des indices de debut\n", " iDebut, jDebut = iFin - longueur_max, jFin - longueur_max\n", " message(\"4. On a obtenu iDebut = {} et jDebut = {} et longueur_max = {} ...\".format(iDebut, jDebut, longueur_max))\n", "\n", " # 4. Vérification\n", " if verifie:\n", " xSous = x[iDebut: iDebut + longueur_max]\n", " ySous = y[jDebut: jDebut + longueur_max]\n", " message(\" Sous-mot dans x = {}, et sous-mot dans y = {} ...\".format(xSous, ySous))\n", " assert xSous == ySous, \"Erreur, xSous et ySous sont différents !\"\n", " \n", " leSousMot = x[iDebut: iDebut + longueur_max]\n", " return iDebut, jDebut, leSousMot, longueurs" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "e9e66dc0-c61a-46a7-87b6-ac376fc2d781" } }, "source": [ "On peut faire quelques tests, comme pour l'approche initiale." ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "nbpresent": { "id": "189c0d2e-0093-447a-866b-671dc5216b01" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "1. Initialisation de la look-up matrice longueurs de taille (n+1, m+1) : n = 6 m = 7 ...\n", "2. Construction bottom-up de la loop-up matrice longueurs ...\n", " Correspondance en cours, u[0] = B et v[1] = B, de longueur courante 1 ...\n", " Correspondance en cours, u[0] = B et v[3] = B, de longueur courante 1 ...\n", " Correspondance en cours, u[0] = B et v[6] = B, de longueur courante 1 ...\n", " Correspondance en cours, u[1] = D et v[4] = D, de longueur courante 2 ...\n", " Correspondance en cours, u[2] = C et v[2] = C, de longueur courante 1 ...\n", " Correspondance en cours, u[3] = A et v[0] = A, de longueur courante 1 ...\n", " Correspondance en cours, u[3] = A et v[5] = A, de longueur courante 1 ...\n", " Correspondance en cours, u[4] = B et v[1] = B, de longueur courante 2 ...\n", " Correspondance en cours, u[4] = B et v[3] = B, de longueur courante 1 ...\n", " Correspondance en cours, u[4] = B et v[6] = B, de longueur courante 2 ...\n", " Correspondance en cours, u[5] = A et v[0] = A, de longueur courante 1 ...\n", " Correspondance en cours, u[5] = A et v[5] = A, de longueur courante 1 ...\n", "3. Calcul de la position du plus long sous mot via la matrice longueurs ...\n", "4. On a obtenu iDebut = 0 et jDebut = 3 et longueur_max = 2 ...\n", " Sous-mot dans x = BD, et sous-mot dans y = BD ...\n" ] }, { "data": { "text/plain": [ "(0, 3, 'BD', array([[0, 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 1, 0, 1, 0, 0, 1],\n", " [0, 0, 0, 0, 0, 2, 0, 0],\n", " [0, 0, 0, 1, 0, 0, 0, 0],\n", " [0, 1, 0, 0, 0, 0, 1, 0],\n", " [0, 0, 2, 0, 1, 0, 0, 2],\n", " [0, 1, 0, 0, 0, 0, 1, 0]]))" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x = \"BDCABA\"\n", "y = \"ABCBDAB\"\n", "sousMotMaxGlouton(x, y, verb=True)" ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "nbpresent": { "id": "7bb9f155-8411-4e5c-af83-da460ef3d52d" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "1. Initialisation de la look-up matrice longueurs de taille (n+1, m+1) : n = 26 m = 28 ...\n", "2. Construction bottom-up de la loop-up matrice longueurs ...\n", " Correspondance en cours, u[0] = a et v[0] = a, de longueur courante 1 ...\n", " Correspondance en cours, u[0] = a et v[15] = a, de longueur courante 1 ...\n", " Correspondance en cours, u[1] = b et v[1] = b, de longueur courante 2 ...\n", " Correspondance en cours, u[1] = b et v[16] = b, de longueur courante 2 ...\n", " Correspondance en cours, u[2] = c et v[2] = c, de longueur courante 3 ...\n", " Correspondance en cours, u[2] = c et v[17] = c, de longueur courante 3 ...\n", " Correspondance en cours, u[6] = a et v[0] = a, de longueur courante 1 ...\n", " Correspondance en cours, u[6] = a et v[15] = a, de longueur courante 1 ...\n", " Correspondance en cours, u[7] = b et v[1] = b, de longueur courante 2 ...\n", " Correspondance en cours, u[7] = b et v[16] = b, de longueur courante 2 ...\n", " Correspondance en cours, u[8] = c et v[2] = c, de longueur courante 3 ...\n", " Correspondance en cours, u[8] = c et v[17] = c, de longueur courante 3 ...\n", " Correspondance en cours, u[9] = 1 et v[9] = 1, de longueur courante 1 ...\n", " Correspondance en cours, u[10] = 2 et v[10] = 2, de longueur courante 2 ...\n", " Correspondance en cours, u[11] = 3 et v[11] = 3, de longueur courante 3 ...\n", " Correspondance en cours, u[12] = 4 et v[12] = 4, de longueur courante 4 ...\n", " Correspondance en cours, u[13] = 5 et v[13] = 5, de longueur courante 5 ...\n", " Correspondance en cours, u[14] = 6 et v[14] = 6, de longueur courante 6 ...\n", " Correspondance en cours, u[15] = a et v[0] = a, de longueur courante 1 ...\n", " Correspondance en cours, u[15] = a et v[15] = a, de longueur courante 7 ...\n", " Correspondance en cours, u[16] = b et v[1] = b, de longueur courante 2 ...\n", " Correspondance en cours, u[16] = b et v[16] = b, de longueur courante 8 ...\n", " Correspondance en cours, u[17] = c et v[2] = c, de longueur courante 3 ...\n", " Correspondance en cours, u[17] = c et v[17] = c, de longueur courante 9 ...\n", " Correspondance en cours, u[21] = a et v[0] = a, de longueur courante 1 ...\n", " Correspondance en cours, u[21] = a et v[15] = a, de longueur courante 1 ...\n", " Correspondance en cours, u[22] = b et v[1] = b, de longueur courante 2 ...\n", " Correspondance en cours, u[22] = b et v[16] = b, de longueur courante 2 ...\n", " Correspondance en cours, u[23] = c et v[2] = c, de longueur courante 3 ...\n", " Correspondance en cours, u[23] = c et v[17] = c, de longueur courante 3 ...\n", " Correspondance en cours, u[24] = 9 et v[24] = 9, de longueur courante 1 ...\n", " Correspondance en cours, u[24] = 9 et v[25] = 9, de longueur courante 1 ...\n", " Correspondance en cours, u[24] = 9 et v[26] = 9, de longueur courante 1 ...\n", " Correspondance en cours, u[24] = 9 et v[27] = 9, de longueur courante 1 ...\n", " Correspondance en cours, u[25] = 9 et v[24] = 9, de longueur courante 1 ...\n", " Correspondance en cours, u[25] = 9 et v[25] = 9, de longueur courante 2 ...\n", " Correspondance en cours, u[25] = 9 et v[26] = 9, de longueur courante 2 ...\n", " Correspondance en cours, u[25] = 9 et v[27] = 9, de longueur courante 2 ...\n", "3. Calcul de la position du plus long sous mot via la matrice longueurs ...\n", "4. On a obtenu iDebut = 9 et jDebut = 9 et longueur_max = 9 ...\n", " Sous-mot dans x = 123456abc, et sous-mot dans y = 123456abc ...\n" ] }, { "data": { "text/plain": [ "(9,\n", " 9,\n", " '123456abc',\n", " array([[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n", " 0, 0, 0, 0, 0, 0, 0],\n", " [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,\n", " 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0,\n", " 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0,\n", " 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n", " 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n", " 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n", " 0, 0, 0, 0, 0, 0, 0],\n", " [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,\n", " 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0,\n", " 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0,\n", " 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n", " 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n", " 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n", " 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0,\n", " 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0,\n", " 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0,\n", " 0, 0, 0, 0, 0, 0, 0],\n", " [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0,\n", " 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0,\n", " 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 0, 0, 0,\n", " 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n", " 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n", " 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n", " 0, 0, 0, 0, 0, 0, 0],\n", " [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,\n", " 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0,\n", " 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0,\n", " 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n", " 0, 0, 0, 1, 1, 1, 1],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n", " 0, 0, 0, 1, 2, 2, 2]]))" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x = \"abcABCabc123456abcABCabc99\"\n", "y = \"abcDEFdef123456abcDEFdef9999\"\n", "sousMotMaxGlouton(x, y, verb=True)" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "be75ea87-42f6-4c1c-a38c-a2a1a147830a" } }, "source": [ "On commence à constater que la matrice `longueurs` est toujours presque remplie de zéros, même après tous les calculs ! Peut-être qu'on peut faire mieux, niveau espace de stockage (complexité en mémoire), pour éviter de stocker un nombre trop grand de zéros inutiles. Une version améliorée est présentée ci-dessous, on parvient à diminuer grandement la complexité (moyenne) en mémoire en utilisant une structure intelligente de matrice *\"creuse\"*." ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "nbpresent": { "id": "8ee08570-75e7-4d93-8c2a-a46fd707c7ed" }, "scrolled": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "1. Initialisation de la look-up matrice longueurs de taille (n+1, m+1) : n = 12 m = 16 ...\n", "2. Construction bottom-up de la loop-up matrice longueurs ...\n", " Correspondance en cours, u[1] = b et v[1] = b, de longueur courante 1 ...\n", " Correspondance en cours, u[3] = Z et v[10] = Z, de longueur courante 1 ...\n", " Correspondance en cours, u[4] = Z et v[10] = Z, de longueur courante 1 ...\n", " Correspondance en cours, u[5] = d et v[3] = d, de longueur courante 1 ...\n", " Correspondance en cours, u[7] = F et v[5] = F, de longueur courante 1 ...\n", " Correspondance en cours, u[8] = G et v[6] = G, de longueur courante 2 ...\n", "3. Calcul de la position du plus long sous mot via la matrice longueurs ...\n", "4. On a obtenu iDebut = 7 et jDebut = 5 et longueur_max = 2 ...\n", " Sous-mot dans x = FG, et sous-mot dans y = FG ...\n" ] }, { "data": { "text/plain": [ "(7, 5, 'FG', array([[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],\n", " [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]))" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x = \"abcZZdeFG597\"\n", "y = \"AbCdEFG413ZAQCWQ\"\n", "sousMotMaxGlouton(x, y, verb=True)" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "534391af-839f-4ee6-b6d3-cccc89272bad" } }, "source": [ "## 4.2 Utilisation d'une matrice *creuse*" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "99eac7dc-c7d5-419c-afd4-1e7a8a6ef96e" } }, "source": [ "On va utiliser le module [``scipy.sparse``](https://docs.scipy.org/doc/scipy/reference/sparse.html) pour utiliser un codage efficace pour cette matrice ``longueurs`` : un codage dit creux qui permettra de ne pas stocker tous ces zéros inutiles." ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "nbpresent": { "id": "f47df73d-5867-4efe-b999-d4ce1b83c7dd" } }, "outputs": [], "source": [ "from scipy.sparse import lil_matrix" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "96bc8eb2-feff-46e5-b296-729b4de0039a" } }, "source": [ "On utilise la structure ``lil_matrix`` (``lil`` pour *\"LInked List\"*), car c'est la plus efficace quant la matrice change de structure *sparse* (on rajoute des valeurs non-nulles au fur et à mesure de sa construction).\n", "\n", "Exemple :" ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "nbpresent": { "id": "09532d01-e5b2-4105-a9cd-bfa84c1a2dd3" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "I_12 pleine :\n", " [[1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]\n", " [0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]\n", " [0. 0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0.]\n", " [0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 0. 0.]\n", " [0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 0.]\n", " [0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 0.]\n", " [0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0.]\n", " [0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0.]\n", " [0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0.]\n", " [0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0.]\n", " [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 0.]\n", " [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1.]]\n", "I_12 creuse :\n", " (0, 0)\t1.0\n", " (1, 1)\t1.0\n", " (2, 2)\t1.0\n", " (3, 3)\t1.0\n", " (4, 4)\t1.0\n", " (5, 5)\t1.0\n", " (6, 6)\t1.0\n", " (7, 7)\t1.0\n", " (8, 8)\t1.0\n", " (9, 9)\t1.0\n", " (10, 10)\t1.0\n", " (11, 11)\t1.0\n" ] }, { "data": { "text/plain": [ "<12x12 sparse matrix of type '