{ "cells": [ { "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": { "collapsed": true, "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": { "collapsed": false, "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": { "collapsed": false, "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": { "collapsed": false, "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": { "collapsed": true, "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": { "collapsed": false, "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": { "collapsed": false, "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": { "collapsed": true, "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": { "collapsed": true, "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": { "collapsed": false, "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": { "collapsed": false, "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": { "collapsed": false, "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": { "collapsed": true, "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": { "collapsed": false, "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 ''\n", "\twith 12 stored elements in LInked List format>" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "print(\"I_12 pleine :\\n\", np.eye(12))\n", "I12 = lil_matrix(np.eye(12))\n", "print(\"I_12 creuse :\\n\", I12)\n", "I12" ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "collapsed": false, "nbpresent": { "id": "aeae66fa-b1bc-4c62-83a3-f1e5d1cdf67a" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Taille de I_12 creuse = 12\n" ] } ], "source": [ "print(\"Taille de I_12 creuse =\", I12.size)" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "e9c0d0ef-7fb9-4d13-b0ab-12f7ef0095b9" } }, "source": [ "On peut prendre exactement la même fonction, et changer la ligne qui crée la matrice ``longueurs`` : on ajoute un appel à ``lil_matrix`` pour en faire une matrice creuse.\n", "\n", "Et voilà comment on passe, en une ligne, de $\\mathcal{O}(n m)$ en mémoire dans tous les cas à un $\\mathcal{O}(n m)$ dans le pire des cas et $\\mathcal{O}(\\sum \\text{longueur des sous-mots de x et y})$ dans tous les cas (en moyenne, ce sera $\\mathcal{O}(\\min(n, m))$ au pire).\n", "Notez que ce sera un poil moins efficace, mais on garde la complexité en temps en $\\mathcal{O}(n m)$ de toute façon." ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "collapsed": true, "nbpresent": { "id": "0ba86758-f1f8-4303-8546-6e7438d7b569" } }, "outputs": [], "source": [ "def sousMotMaxGloutonCreux(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, creuse de taille (n+1, m+1) : n = {} m = {} ...\".format(n, m))\n", " longueurs = lil_matrix(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", " # 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": "4773db1d-567a-42b6-9c33-79b6fa0b96a6" } }, "source": [ "On peut faire quelques exemples en plus, et on calcule aussi la taille de la matrice creuse ``longueurs`` (pour comparer a la taille de la matrice pleine de la fonction d'avant) :" ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "collapsed": false, "nbpresent": { "id": "5feab5e3-f15a-490c-8722-935bf5dd84c6" }, "scrolled": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "1. Initialisation de la look-up matrice longueurs, creuse de taille (n+1, m+1) : n = 28 m = 38 ...\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[25] = 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[26] = b, de longueur courante 2 ...\n", " Correspondance en cours, u[2] = 0 et v[12] = 0, de longueur courante 1 ...\n", " Correspondance en cours, u[2] = 0 et v[16] = 0, de longueur courante 1 ...\n", " Correspondance en cours, u[3] = c et v[10] = c, de longueur courante 1 ...\n", " Correspondance en cours, u[3] = c et v[27] = c, de longueur courante 1 ...\n", " Correspondance en cours, u[6] = C et v[5] = C, de longueur courante 1 ...\n", " Correspondance en cours, u[7] = 0 et v[12] = 0, de longueur courante 1 ...\n", " Correspondance en cours, u[7] = 0 et v[16] = 0, de longueur courante 1 ...\n", " Correspondance en cours, u[8] = a et v[0] = a, de longueur courante 1 ...\n", " Correspondance en cours, u[8] = a et v[25] = a, de longueur courante 1 ...\n", " Correspondance en cours, u[9] = b et v[1] = b, de longueur courante 2 ...\n", " Correspondance en cours, u[9] = b et v[26] = b, de longueur courante 2 ...\n", " Correspondance en cours, u[10] = c et v[10] = c, de longueur courante 1 ...\n", " Correspondance en cours, u[10] = c et v[27] = c, de longueur courante 3 ...\n", " Correspondance en cours, u[11] = 1 et v[19] = 1, de longueur courante 1 ...\n", " Correspondance en cours, u[12] = 2 et v[20] = 2, de longueur courante 2 ...\n", " Correspondance en cours, u[13] = 3 et v[21] = 3, de longueur courante 3 ...\n", " Correspondance en cours, u[14] = 4 et v[22] = 4, de longueur courante 4 ...\n", " Correspondance en cours, u[15] = 5 et v[23] = 5, de longueur courante 5 ...\n", " Correspondance en cours, u[16] = 6 et v[24] = 6, de longueur courante 6 ...\n", " Correspondance en cours, u[17] = a et v[0] = a, de longueur courante 1 ...\n", " Correspondance en cours, u[17] = a et v[25] = a, de longueur courante 7 ...\n", " Correspondance en cours, u[18] = b et v[1] = b, de longueur courante 2 ...\n", " Correspondance en cours, u[18] = b et v[26] = b, de longueur courante 8 ...\n", " Correspondance en cours, u[19] = c et v[10] = c, de longueur courante 1 ...\n", " Correspondance en cours, u[19] = c et v[27] = c, de longueur courante 9 ...\n", " Correspondance en cours, u[22] = C et v[5] = C, de longueur courante 1 ...\n", " Correspondance en cours, u[23] = a et v[0] = a, de longueur courante 1 ...\n", " Correspondance en cours, u[23] = a et v[25] = a, de longueur courante 1 ...\n", " Correspondance en cours, u[24] = b et v[1] = b, de longueur courante 2 ...\n", " Correspondance en cours, u[24] = b et v[26] = b, de longueur courante 2 ...\n", " Correspondance en cours, u[25] = c et v[10] = c, de longueur courante 1 ...\n", " Correspondance en cours, u[25] = c et v[27] = c, de longueur courante 3 ...\n", " Correspondance en cours, u[26] = 9 et v[34] = 9, de longueur courante 1 ...\n", " Correspondance en cours, u[26] = 9 et v[35] = 9, de longueur courante 1 ...\n", " Correspondance en cours, u[26] = 9 et v[36] = 9, de longueur courante 1 ...\n", " Correspondance en cours, u[26] = 9 et v[37] = 9, de longueur courante 1 ...\n", " Correspondance en cours, u[27] = 9 et v[34] = 9, de longueur courante 1 ...\n", " Correspondance en cours, u[27] = 9 et v[35] = 9, de longueur courante 2 ...\n", " Correspondance en cours, u[27] = 9 et v[36] = 9, de longueur courante 2 ...\n", " Correspondance en cours, u[27] = 9 et v[37] = 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 = 11 et jDebut = 19 et longueur_max = 9 ...\n", " Sous-mot dans x = 123456abc, et sous-mot dans y = 123456abc ...\n", "Taille de la matrice pleine = (n+1)(m+1) = 1131\n", "Taille de la matrice creuse longueurs = 44\n" ] } ], "source": [ "x = \"ab0cABC0abc123456abcABCabc99\"\n", "y = \"abZQXCVQDScD0EFd0ef123456abcDEFdef9999\"\n", "iDebut, jDebut, sousxy, longueurs = sousMotMaxGloutonCreux(x, y, verb=True)\n", "print(\"Taille de la matrice pleine = (n+1)(m+1) =\", (len(x) + 1) * (len(y) + 1))\n", "print(\"Taille de la matrice creuse longueurs =\", longueurs.size)" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "c026476c-371c-4f75-8754-21fe897e324c" } }, "source": [ "Ici, sur deux mots de tailles raisonnables (``x = \"ab0cABC0abc123456abcABCabc99\"`` et ``y = \"abZQXCVQDScD0EFd0ef123456abcDEFdef9999\"``), on passe d'une matrice pleine de taille ``1131`` entiers à une matrice creuse de taille ``44`` entiers : le gain est considérable ! " ] }, { "cell_type": "code", "execution_count": 18, "metadata": { "collapsed": false, "nbpresent": { "id": "42faa621-3766-4ef9-adc8-f8a1f1e7cc5f" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "1. Initialisation de la look-up matrice longueurs, creuse 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", "Taille de la matrice pleine = (n+1)(m+1) = 221\n", "Taille de la matrice creuse longueurs = 6\n" ] } ], "source": [ "x = \"abcZZdeFG597\"\n", "y = \"AbCdEFG413ZAQCWQ\"\n", "iDebut, jDebut, sousxy, longueurs = sousMotMaxGloutonCreux(x, y, verb=True)\n", "print(\"Taille de la matrice pleine = (n+1)(m+1) =\", (len(x) + 1) * (len(y) + 1))\n", "print(\"Taille de la matrice creuse longueurs =\", longueurs.size)" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "39788369-262a-49c6-a335-a90b04bc57b0" } }, "source": [ "Avec des mots ``x`` et ``y`` plus longs, le gain en mémoire induit par le codage creux est encore plus impressionnant :" ] }, { "cell_type": "code", "execution_count": 19, "metadata": { "collapsed": false, "nbpresent": { "id": "adce5d12-902d-4b0a-9e33-7f6ff2a1685d" }, "scrolled": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Taille de la matrice pleine = (n+1)(m+1) = 44215\n", "Taille de la matrice creuse longueurs = 1046\n" ] } ], "source": [ "x = \"ab0cABC0abc123456abcABCabc99abcZZdeFG597abcZZdeFG597abcZZdeFG597abcZZdeFG597aethjrynghù*ejgodknùebjtzinhmodgkùjihrznhumbajzdgihbjmnaekrzùdbnvkzriùnodgkl ojzirnùodk bùgbznùod1249721325414765132486513486565465klfrzinhbùodfskl p*bjùdkl nbdnù\"\n", "y = \"abZQXCVQDScD0EFd0ef123456abcDEFdef9999AbCdEFG413ZAQCWQAbCdEFG413ZAQCWQAbCdEFG413ZAQCWQAbCdEFG413ZAQCWQAbCdEFG413ZAQCWQzrthekĝbùpbgmhbgdmv hubznemr1249721325414765132486513486565465ebgd\"\n", "iDebut, jDebut, sousxy, longueurs = sousMotMaxGloutonCreux(x, y, verb=False)\n", "print(\"Taille de la matrice pleine = (n+1)(m+1) =\", (len(x) + 1) * (len(y) + 1))\n", "print(\"Taille de la matrice creuse longueurs =\", longueurs.size)" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "32b2eb7b-1f5b-45dc-bb9b-0913756c1358" } }, "source": [ "### 4.2.1 Version condensée" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "0b453f22-b605-4285-a1f6-24d4f54865fa" } }, "source": [ "Le code de cette fonction `sousMotMaxGloutonCreux` peut sembler un peu long, mais sans messages ni commentaires il est vraiment court et simple :" ] }, { "cell_type": "code", "execution_count": 20, "metadata": { "collapsed": true, "nbpresent": { "id": "02caf31c-8652-445c-a8a3-f257bb2e1bb4" } }, "outputs": [], "source": [ "def sousMotMaxGloutonCreux2(x, y):\n", " n = len(x)\n", " m = len(y)\n", " \n", " longueurs = lil_matrix(np.zeros((n+1, m+1), dtype=int))\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", " \n", " iFin, jFin = 0, 0\n", " longueur_max = -1 # Pas encore\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", " iDebut, jDebut = iFin - longueur_max, jFin - longueur_max\n", "\n", " leSousMot = x[iDebut: iDebut + longueur_max]\n", " return iDebut, jDebut, leSousMot, longueurs" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "f21c577a-a8ba-4a28-95d2-f038c705804c" } }, "source": [ "Et le même exemple donne pareil :" ] }, { "cell_type": "code", "execution_count": 21, "metadata": { "collapsed": false, "nbpresent": { "id": "37e58043-93b4-427b-ba89-ac5175983835" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Taille de la matrice pleine = (n+1)(m+1) = 44215\n", "Taille de la matrice creuse longueurs = 1046\n", "Sous-mot : 1249721325414765132486513486565465\n" ] } ], "source": [ "x = \"ab0cABC0abc123456abcABCabc99abcZZdeFG597abcZZdeFG597abcZZdeFG597abcZZdeFG597aethjrynghù*ejgodknùebjtzinhmodgkùjihrznhumbajzdgihbjmnaekrzùdbnvkzriùnodgkl ojzirnùodk bùgbznùod1249721325414765132486513486565465klfrzinhbùodfskl p*bjùdkl nbdnù\"\n", "y = \"abZQXCVQDScD0EFd0ef123456abcDEFdef9999AbCdEFG413ZAQCWQAbCdEFG413ZAQCWQAbCdEFG413ZAQCWQAbCdEFG413ZAQCWQAbCdEFG413ZAQCWQzrthekĝbùpbgmhbgdmv hubznemr1249721325414765132486513486565465ebgd\"\n", "iDebut, jDebut, sousxy, longueurs = sousMotMaxGloutonCreux2(x, y)\n", "print(\"Taille de la matrice pleine = (n+1)(m+1) =\", (len(x) + 1) * (len(y) + 1))\n", "print(\"Taille de la matrice creuse longueurs =\", longueurs.size)\n", "print(\"Sous-mot :\", sousxy)" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "71aad76b-3065-4bc6-b778-547ed96aaea6" } }, "source": [ "----" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "071fe529-377f-46d0-986a-aaf7da101fef" } }, "source": [ "# 5. Calcule de la plus longue sous-séquence commune" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "e172a934-fc99-4cd9-81ab-1afcc9875423" } }, "source": [ "Maintenant qu'on a fait tout ca, on peut implementer, de facon tres semblable, l'algorithme glouton pour le calcul de la plus longue sous-séquence commune.\n", "\n", "Dans cet autre problème, on cherche des sous-séquences et plus des sous-mots, donc on peut extraire de facon non consécutives.\n", "Le développement d'agrégation devrait concerner le second problème, qui est plus intéressant:\n", "Par exemple, voici une version tapée en PDF : http://minerve.bretagne.ens-cachan.fr/images/Dvt_plsc.pdf." ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "43bf9fa4-82e6-44a7-938d-de9304b7835b" } }, "source": [ "## 5.1 Vérifier qu'une sous-séquence est une bonne sous-séquence" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "e8f68e52-0412-4e94-8392-1cf1ae090978" } }, "source": [ "On commencer par écrire une petite fonction qui permet de vérifier rapidement qu'une chaine est une sous-séquence d'une autre, juste en regardant la définition." ] }, { "cell_type": "code", "execution_count": 22, "metadata": { "collapsed": true, "nbpresent": { "id": "d5241d34-488d-4175-b8a8-a241226b7a3c" } }, "outputs": [], "source": [ "def estSousSeq(seq, x, verb=True, indices=True):\n", " \"\"\" Verifie en temps O(|seq| |x|) que seq est une bonne sous-sequence de x.\n", " \"\"\"\n", " result = False\n", " indices_x = []\n", " try:\n", " i = -1\n", " for l in seq:\n", " j = i+1 + x[i+1:].index(l)\n", " indices_x.append(j)\n", " i = j\n", " result = True\n", " except Exception as e:\n", " if verb:\n", " print(\"Erreur dans estSousSeq(seq = {}, x = {}):\\n{}\".format(seq, x, e))\n", " if indices:\n", " return result, indices_x\n", " else:\n", " return result" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "7ff35116-bcd8-4402-880d-f6d3c8071a67" } }, "source": [ "## 5.2 Algorithme pour la plus longue sous-séquence" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "3af0c210-e6b4-4eed-9e59-f6a6b4ecf677" } }, "source": [ "On adapte l'algorithme du plus long sous-mot pour détecter les séquences aussi.\n", "Cf. le PDF page 2/3.\n", "\n", "TODO meilleures explications" ] }, { "cell_type": "code", "execution_count": 23, "metadata": { "collapsed": true, "nbpresent": { "id": "85bd73dd-62e7-48c3-865f-27e20b2ffc16" } }, "outputs": [], "source": [ "def utiliseTableOrigines_x(x, origines, i, j, accu=''):\n", " \"\"\" Renvoie la sous-séquence de x codée dans la table origines. Cf. PDF (Algorithme 2).\n", " \n", " - Calcul tail récursif (stocké dans la variable accu).\n", " \"\"\"\n", " # print(\" utiliseTableOrigines(x = {}, origines, i = {}, j = {}, accu = {}) : origines[i, j] = {} ...\".format(x, i, j, accu, origines[i, j])) # DEBUG\n", " if i == 0 or j == 0:\n", " return accu\n", " if origines[i, j] == '↖': # Vraie correspondance, on ajoute une lettre !\n", " return utiliseTableOrigines_x(x, origines, i-1, j-1, x[i-1] + accu)\n", " elif origines[i, j] == '↑': # Fausse correspondance, on continue a gauche...\n", " return utiliseTableOrigines_x(x, origines, i-1, j, accu)\n", " elif origines[i, j] == '←': # Fausse correspondance, on continue en haut...\n", " return utiliseTableOrigines_x(x, origines, i, j-1, accu)\n", " else:\n", " raise ValueError(\"Erreur dans la table 'origines', invalide pour le mot x = {} ...\".format(x))\n", "\n", "\n", "def utiliseTableOrigines_y(x, origines, i, j, accu=''):\n", " \"\"\" Renvoie la sous-séquence de y codée dans la table origines. Cf. PDF (Algorithme 2).\n", " \n", " - Calcul tail récursif (stocké dans la variable accu).\n", " \"\"\"\n", " # print(\" utiliseTableOrigines(y = {}, origines, i = {}, j = {}, accu = {}) : origines[i, j] = {} ...\".format(y, i, j, accu, origines[i, j])) # DEBUG\n", " if i == 0 or j == 0:\n", " return accu\n", " if origines[i, j] == '↖': # Vraie correspondance, on ajoute une lettre !\n", " return utiliseTableOrigines_y(x, origines, i-1, j-1, y[j-1] + accu)\n", " elif origines[i, j] == '↑': # Fausse correspondance, on continue a gauche...\n", " return utiliseTableOrigines_y(x, origines, i-1, j, accu)\n", " elif origines[i, j] == '←': # Fausse correspondance, on continue en haut...\n", " return utiliseTableOrigines_y(x, origines, i, j-1, accu)\n", " else:\n", " raise ValueError(\"Erreur dans la table 'origines', invalide pour le mot y = {} ...\".format(y))" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "cb50812e-6786-4637-8875-4192cc230fcf" } }, "source": [ "TODO meilleures explications" ] }, { "cell_type": "code", "execution_count": 24, "metadata": { "collapsed": false, "nbpresent": { "id": "48e14a23-1f2a-4b8e-a439-950dd9975515" } }, "outputs": [], "source": [ "def sousMotSeqGlouton(x, y, verb=False, verifie=True):\n", " \"\"\" Calcule la plus longue sous-mot séquence a x et y, par programmation dynamique.\n", " \n", " - affiche un peu ce qu'il se passe si verb=True,\n", " - vérifie que la sous-séquence commun est bien une bonne sous-séquence commune si verifie=True,\n", " - renvoie laSousSeq, longueurs, origines, indices_x, indices_y si verifie=False,\n", " - renvoie laSousSeq, longueurs, origines, indices_x, indices_y 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 des look-up matrices longueurs et origines de taille (n+1, m+1) : n = {} m = {} ...\".format(n, m))\n", " longueurs = np.zeros((n+1, m+1), dtype=int) # Matrice c du dev en PDF\n", " origines = np.array([[' '] * (m+1)] * (n+1), dtype=str) # Matrice b du dev en PDF\n", " # Note : on pourrait utiliser un codage a base d'entier, 0 1 2 3 pour ' ' '←' '↑' '↖' mais c'est moins joli...\n", " message(\"2. Construction bottom-up des loop-up matrices longueurs et origines ...\")\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", " origines[i, j] = '↖'\n", " message(\" Vraie correspondance en cours, u[{}] = {} et v[{}] = {}, de longueur courante {} ...\".format(i-1, x[i-1], j-1, y[j-1], longueurs[i, j]))\n", " elif longueurs[i-1, j] >= longueurs[i, j-1]:\n", " longueurs[i, j] = longueurs[i-1, j]\n", " origines[i, j] = '↑'\n", " message(\" Correspondance gauche (u) en cours, u[{}] = {} et v[{}] = {}, de pseudo-longueur courante {} ...\".format(i-1, x[i-1], j-1, y[j-1], longueurs[i, j]))\n", " else:\n", " longueurs[i, j] = longueurs[i, j-1]\n", " origines[i, j] = '←'\n", " message(\" Correspondance haute (v) en cours, u[{}] = {} et v[{}] = {}, de pseudo-longueur courante {} ...\".format(i-1, x[i-1], j-1, y[j-1], longueurs[i, j]))\n", "\n", " # 3. Utilisation de la matrice longueurs\n", " laSousSeq = utiliseTableOrigines_x(x, origines, n, m, accu='')\n", "\n", " # 4. Vérification\n", " if verifie:\n", " res_x, indices_x = estSousSeq(laSousSeq, x, indices=True)\n", " if not res_x:\n", " raise ValueError(\"Erreur: La séquence {} de x (aux indices {}) n'est pas une bonne sous-séquence de x = {}.\".format(laSousSeq, indices_x, x))\n", " \n", " laSousSeq_y = utiliseTableOrigines_y(y, origines, n, m, accu='')\n", " if laSousSeq != laSousSeq_y:\n", " raise ValueError(\"Erreur: La sous-séquence {} de x est différente de celle de y : {} ...\".format(laSousSeq, laSousSeq_y))\n", "\n", " res_y, indices_y = estSousSeq(laSousSeq, y, indices=True)\n", " if not res_y:\n", " raise ValueError(\"Erreur: La séquence {} de y (aux indices {}) n'est pas une bonne sous-séquence de y = {}.\".format(laSousSeq, indices_y, y))\n", " \n", " # Fini !\n", " return laSousSeq, longueurs, origines, indices_x, indices_y\n", " else:\n", " return laSousSeq, longueurs, origines" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "ff3fd202-2ddb-4a3a-b28a-e68b99afe8b1" } }, "source": [ "---" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "0c0c8cad-eaee-44e5-9a17-5186cf661c91" } }, "source": [ "### 5.2.1 Exemple, venant du développement" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "15d06766-c839-4390-a7c0-2ced861ea9c5" } }, "source": [ "Blabla" ] }, { "cell_type": "code", "execution_count": 25, "metadata": { "collapsed": false, "nbpresent": { "id": "cf445208-e3a7-4baf-8c23-cc3a460bc34a" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Sous-seq de taille 4 valant BCBA ...\n", " - aux indices [1, 2, 3, 5] pour x = ABCBDAB ...\n", " - aux indices [0, 2, 4, 5] pour y = BDCABA ...\n", "Et la table longueurs vaut :\n", " [[0 0 0 0 0 0 0]\n", " [0 0 0 0 1 1 1]\n", " [0 1 1 1 1 2 2]\n", " [0 1 1 2 2 2 2]\n", " [0 1 1 2 2 3 3]\n", " [0 1 2 2 2 3 3]\n", " [0 1 2 2 3 3 4]\n", " [0 1 2 2 3 4 4]] ...\n", "Et la table origines vaut :\n", " [[' ' ' ' ' ' ' ' ' ' ' ' ' ']\n", " [' ' '↑' '↑' '↑' '↖' '←' '↖']\n", " [' ' '↖' '←' '←' '↑' '↖' '←']\n", " [' ' '↑' '↑' '↖' '←' '↑' '↑']\n", " [' ' '↖' '↑' '↑' '↑' '↖' '←']\n", " [' ' '↑' '↖' '↑' '↑' '↑' '↑']\n", " [' ' '↑' '↑' '↑' '↖' '↑' '↖']\n", " [' ' '↖' '↑' '↑' '↑' '↖' '↑']] ...\n" ] } ], "source": [ "x = \"ABCBDAB\"\n", "y = \"BDCABA\"\n", "laSousSeq, longueurs, origines, indices_x, indices_y = sousMotSeqGlouton(x, y, verifie=True)\n", "print(\"Sous-seq de taille\", len(laSousSeq), \"valant\", laSousSeq, \"...\")\n", "print(\" - aux indices\", indices_x, \"pour x =\", x, \"...\")\n", "print(\" - aux indices\", indices_y, \"pour y =\", y, \"...\")\n", "print(\"Et la table longueurs vaut :\\n\", longueurs, \"...\")\n", "print(\"Et la table origines vaut :\\n\", origines, \"...\")" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "9689610e-f181-4377-a878-aeaf261e8567" } }, "source": [ "### 5.2.2 Autres exemples" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "96dc1ad2-d5db-4ed7-931d-cdd3107f3fd5" } }, "source": [ "TODO" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "636d18ab-b153-4566-81d5-3b608284d2e4" } }, "source": [ "----\n", "\n", "> *C'est tout pour aujourd'hui les amis !*\n", "> [Allez voir d'autres notebooks](https://github.com/Naereen/notebooks/tree/master/agreg) si vous voulez." ] } ], "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.4.3+" }, "nbpresent": { "slides": { "054f873f-fc0c-43f8-9ffb-5b4b70e36525": { "id": "054f873f-fc0c-43f8-9ffb-5b4b70e36525", "prev": "66942006-40b7-4b08-94c1-ab4b27693b7c", "regions": { "a1c27410-7876-4b2d-be97-94ca3169eb5b": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "09532d01-e5b2-4105-a9cd-bfa84c1a2dd3", "part": "whole" }, "id": "a1c27410-7876-4b2d-be97-94ca3169eb5b" } } }, "067d3558-5fe3-4116-aafd-0d1ac44c460a": { "id": "067d3558-5fe3-4116-aafd-0d1ac44c460a", "prev": "3cd85433-8ab0-4087-8f4b-b642a04bc77d", "regions": { "74f4f12b-f06d-4318-8072-6dcc75704f47": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "21cc9ac6-1dd1-4456-a880-56876759502b", "part": "whole" }, "id": "74f4f12b-f06d-4318-8072-6dcc75704f47" } } }, "06fdad76-73ed-4bb9-9008-d3c9117eb783": { "id": "06fdad76-73ed-4bb9-9008-d3c9117eb783", "prev": "8c8a0fc3-6191-447e-a2e8-ad5c66d7bb55", "regions": { "be8f30f7-843d-40dd-b0ec-2ad49a8bde0e": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "e8ba8fa2-6f98-4431-8222-c897d1145a15", "part": "whole" }, "id": "be8f30f7-843d-40dd-b0ec-2ad49a8bde0e" } } }, "13af60a5-502c-409f-b1db-306d3546673e": { "id": "13af60a5-502c-409f-b1db-306d3546673e", "prev": "2b1e9a92-db79-49ba-a823-a3310a4d8b82", "regions": { "a565c42d-fbfa-4df2-83a0-00249b64379c": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "e8f68e52-0412-4e94-8392-1cf1ae090978", "part": "whole" }, "id": "a565c42d-fbfa-4df2-83a0-00249b64379c" } } }, "1537ce27-bbb3-482a-b930-61128dfaa5fc": { "id": "1537ce27-bbb3-482a-b930-61128dfaa5fc", "prev": "a90c03e9-50ce-4af3-ac3e-ad0a6517f2b2", "regions": { "26365346-f58c-41cf-ae5d-8921e5dc9ce6": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "6c587b6e-3c08-48f2-877d-11454634634d", "part": "whole" }, "id": "26365346-f58c-41cf-ae5d-8921e5dc9ce6" } } }, "1bdba887-217a-43fe-9f80-bd6830d26787": { "id": "1bdba887-217a-43fe-9f80-bd6830d26787", "prev": "054f873f-fc0c-43f8-9ffb-5b4b70e36525", "regions": { "cbffc2f5-895d-43ab-b3f3-d292cd0e549d": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "aeae66fa-b1bc-4c62-83a3-f1e5d1cdf67a", "part": "whole" }, "id": "cbffc2f5-895d-43ab-b3f3-d292cd0e549d" } } }, "1d7bd639-1931-42bc-ab90-9fe0f2f4feae": { "id": "1d7bd639-1931-42bc-ab90-9fe0f2f4feae", "prev": "80edbb16-b6a1-4233-8833-0d4f6addea00", "regions": { "2bfd3f5f-27be-46cc-8b51-b2bcc005da0f": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "35222aea-86e6-4146-9019-9528e53a7570", "part": "whole" }, "id": "2bfd3f5f-27be-46cc-8b51-b2bcc005da0f" } } }, "1e187c07-2118-486e-abbc-0fbb90d33727": { "id": "1e187c07-2118-486e-abbc-0fbb90d33727", "prev": "a71c3f64-e3c1-4810-b2f1-dc1d3f19582e", "regions": { "0444cd52-edb4-4c99-88bd-b929b56fcd69": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "be75ea87-42f6-4c1c-a38c-a2a1a147830a", "part": "whole" }, "id": "0444cd52-edb4-4c99-88bd-b929b56fcd69" } } }, "1eb71078-a076-49a3-b399-7b00d19bf154": { "id": "1eb71078-a076-49a3-b399-7b00d19bf154", "prev": "e688f732-8379-4090-baee-d74e938ba845", "regions": { "eeea3537-7d0c-480d-b516-45d7b93e21b4": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "5feab5e3-f15a-490c-8722-935bf5dd84c6", "part": "whole" }, "id": "eeea3537-7d0c-480d-b516-45d7b93e21b4" } } }, "223ff166-4f0b-4bb8-9790-e6dd8baaa596": { "id": "223ff166-4f0b-4bb8-9790-e6dd8baaa596", "prev": "1eb71078-a076-49a3-b399-7b00d19bf154", "regions": { "03c25d93-3281-49da-be77-7e281ef6f8b5": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "c026476c-371c-4f75-8754-21fe897e324c", "part": "whole" }, "id": "03c25d93-3281-49da-be77-7e281ef6f8b5" } } }, "22a5b54c-6bab-4a6a-9e2a-284251395517": { "id": "22a5b54c-6bab-4a6a-9e2a-284251395517", "prev": "5a15637b-9b0d-4d3f-a5ea-7ad444b66e0f", "regions": { "d6ba9f77-cf66-4d48-b250-aeb275df6249": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "cb50812e-6786-4637-8875-4192cc230fcf", "part": "whole" }, "id": "d6ba9f77-cf66-4d48-b250-aeb275df6249" } } }, "236a6645-3284-442b-8949-2d8c3862d978": { "id": "236a6645-3284-442b-8949-2d8c3862d978", "prev": "ba50a6b2-dc8e-4d6c-aad2-73e8ad79009d", "regions": { "d92c8c26-6cd8-465f-afd0-62367f0b167f": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "05ce1f79-4f0b-445b-95a7-fba4ddf88b56", "part": "whole" }, "id": "d92c8c26-6cd8-465f-afd0-62367f0b167f" } } }, "23e8d199-7954-4110-aa00-268a4780d229": { "id": "23e8d199-7954-4110-aa00-268a4780d229", "prev": "1d7bd639-1931-42bc-ab90-9fe0f2f4feae", "regions": { "318a5ace-e981-4c5f-91a3-eaba49b0f4f0": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "3c02fca1-76e3-45f8-8a66-71708b4ddc6b", "part": "whole" }, "id": "318a5ace-e981-4c5f-91a3-eaba49b0f4f0" } } }, "23ea59ee-f9eb-4bbd-9abf-fe2faf91940c": { "id": "23ea59ee-f9eb-4bbd-9abf-fe2faf91940c", "prev": "c8c721ae-658b-4ab2-9d84-b90908992724", "regions": { "859f277d-69eb-4bb6-b250-09f2f3b0c7d4": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "534391af-839f-4ee6-b6d3-cccc89272bad", "part": "whole" }, "id": "859f277d-69eb-4bb6-b250-09f2f3b0c7d4" } } }, "27b11791-c0ea-4bea-9fbf-63fa48817d50": { "id": "27b11791-c0ea-4bea-9fbf-63fa48817d50", "prev": "3c6725f6-bc47-40a9-94e2-014861c0aaa9", "regions": { "fcc64b20-b382-4958-90c1-1af02266472b": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "fe95c114-6e8b-498d-9c9a-41cb8d9208ce", "part": "whole" }, "id": "fcc64b20-b382-4958-90c1-1af02266472b" } } }, "286a64ba-5991-4131-bae4-9bc5f703c587": { "id": "286a64ba-5991-4131-bae4-9bc5f703c587", "prev": "2efc19be-5e2b-49e6-b09c-ad31f997b49e", "regions": { "a76f7335-0e9b-4ab6-9cef-8a42f0e6a815": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "189c0d2e-0093-447a-866b-671dc5216b01", "part": "whole" }, "id": "a76f7335-0e9b-4ab6-9cef-8a42f0e6a815" } } }, "2b1e9a92-db79-49ba-a823-a3310a4d8b82": { "id": "2b1e9a92-db79-49ba-a823-a3310a4d8b82", "prev": "aceeab4b-ab16-432d-9f6c-5447735b45aa", "regions": { "6d8cfe60-941c-4421-bd22-baa74594e5b8": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "43bf9fa4-82e6-44a7-938d-de9304b7835b", "part": "whole" }, "id": "6d8cfe60-941c-4421-bd22-baa74594e5b8" } } }, "2efc19be-5e2b-49e6-b09c-ad31f997b49e": { "id": "2efc19be-5e2b-49e6-b09c-ad31f997b49e", "prev": "236a6645-3284-442b-8949-2d8c3862d978", "regions": { "8149b52a-52d7-41ba-8e2b-89299e7a5b12": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "e9e66dc0-c61a-46a7-87b6-ac376fc2d781", "part": "whole" }, "id": "8149b52a-52d7-41ba-8e2b-89299e7a5b12" } } }, "31ea5d42-cbb0-4f5c-ba85-30991589589e": { "id": "31ea5d42-cbb0-4f5c-ba85-30991589589e", "prev": "27b11791-c0ea-4bea-9fbf-63fa48817d50", "regions": { "393db737-c5d6-47e5-92be-7cbff464bbf9": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "78e99f8a-7548-4572-b1b2-f8bec7116db0", "part": "whole" }, "id": "393db737-c5d6-47e5-92be-7cbff464bbf9" } } }, "3c6725f6-bc47-40a9-94e2-014861c0aaa9": { "id": "3c6725f6-bc47-40a9-94e2-014861c0aaa9", "prev": "ade912c4-b81e-467c-ab6f-deb527b0403e", "regions": { "026d3ebd-0e73-4da1-a754-fb7863569017": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "2e792d1e-c43e-486e-8edc-6ad23f73fa03", "part": "whole" }, "id": "026d3ebd-0e73-4da1-a754-fb7863569017" } } }, "3cd85433-8ab0-4087-8f4b-b642a04bc77d": { "id": "3cd85433-8ab0-4087-8f4b-b642a04bc77d", "prev": "69e8c329-6de9-4d81-bc36-30b914a3b1a0", "regions": { "02b1ec57-7a4a-4b12-97c8-e8322cdd61a0": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "5cc3b653-680e-4d7f-b888-f84b5af084dd", "part": "whole" }, "id": "02b1ec57-7a4a-4b12-97c8-e8322cdd61a0" } } }, "3cdb3114-6e24-4903-96e2-f40297203d1a": { "id": "3cdb3114-6e24-4903-96e2-f40297203d1a", "prev": "ce5b519b-be27-475a-b316-163d53ae89b9", "regions": { "07fd106c-8632-400a-849a-21f14f01c976": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "071fe529-377f-46d0-986a-aaf7da101fef", "part": "whole" }, "id": "07fd106c-8632-400a-849a-21f14f01c976" } } }, "40d9250c-0bf8-4eb1-99cd-2e27b04bc3e8": { "id": "40d9250c-0bf8-4eb1-99cd-2e27b04bc3e8", "prev": "1bdba887-217a-43fe-9f80-bd6830d26787", "regions": { "20c3e1bf-d22d-4e64-b4e9-f2f413f846ee": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "e9c0d0ef-7fb9-4d13-b0ab-12f7ef0095b9", "part": "whole" }, "id": "20c3e1bf-d22d-4e64-b4e9-f2f413f846ee" } } }, "49200624-0a03-4694-8554-e9d9e24ab75f": { "id": "49200624-0a03-4694-8554-e9d9e24ab75f", "prev": "40d9250c-0bf8-4eb1-99cd-2e27b04bc3e8", "regions": { "a1894abd-9c6f-4df2-bbae-513e0c7016b0": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "0ba86758-f1f8-4303-8546-6e7438d7b569", "part": "whole" }, "id": "a1894abd-9c6f-4df2-bbae-513e0c7016b0" } } }, "4a531b84-65c7-4b54-ba9a-329ea45c3270": { "id": "4a531b84-65c7-4b54-ba9a-329ea45c3270", "prev": "97bdcf66-ffea-49f3-b367-eb46ae8584b6", "regions": { "6e0d949c-6014-409d-b75f-6abf8df43af6": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "15d06766-c839-4390-a7c0-2ced861ea9c5", "part": "whole" }, "id": "6e0d949c-6014-409d-b75f-6abf8df43af6" } } }, "4ce88900-a885-49e9-9229-431d70ad25df": { "id": "4ce88900-a885-49e9-9229-431d70ad25df", "prev": "c790ea0b-37f6-4f69-937f-5d651da48601", "regions": { "5aff0d19-262e-4fed-bae7-286c9beb59d1": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "0b453f22-b605-4285-a1f6-24d4f54865fa", "part": "whole" }, "id": "5aff0d19-262e-4fed-bae7-286c9beb59d1" } } }, "5032b6ad-f2dc-4a4a-8232-51307d785be5": { "id": "5032b6ad-f2dc-4a4a-8232-51307d785be5", "prev": "d7bb974a-4cee-417e-8ae2-37897bbda801", "regions": { "543b1253-3137-4d63-aaf4-db711a577fed": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "77640a71-1cc5-47c9-ae52-940ec6c95024", "part": "whole" }, "id": "543b1253-3137-4d63-aaf4-db711a577fed" } } }, "58f94107-080a-4c92-92d5-77572c38595a": { "id": "58f94107-080a-4c92-92d5-77572c38595a", "prev": "1537ce27-bbb3-482a-b930-61128dfaa5fc", "regions": { "aae44782-7b3b-4de1-a2cc-ff47ce8e451a": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "4e2a85b7-6833-442a-bfae-cfd3fb98ca45", "part": "whole" }, "id": "aae44782-7b3b-4de1-a2cc-ff47ce8e451a" } } }, "5a15637b-9b0d-4d3f-a5ea-7ad444b66e0f": { "id": "5a15637b-9b0d-4d3f-a5ea-7ad444b66e0f", "prev": "d797644c-769d-4dca-ace3-b5b80cd83bca", "regions": { "0bb5cae3-7ee7-405a-8ec8-cdbfb326e9eb": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "85bd73dd-62e7-48c3-865f-27e20b2ffc16", "part": "whole" }, "id": "0bb5cae3-7ee7-405a-8ec8-cdbfb326e9eb" } } }, "5bd7b2f8-7942-4b57-97e3-1523fc403278": { "id": "5bd7b2f8-7942-4b57-97e3-1523fc403278", "prev": "79848694-9e95-4bfa-9589-acc949f2dc0f", "regions": { "bc5c04b7-d3f8-4fc6-958f-c29eefdedc24": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "f21c577a-a8ba-4a28-95d2-f038c705804c", "part": "whole" }, "id": "bc5c04b7-d3f8-4fc6-958f-c29eefdedc24" } } }, "5e3c3e16-eff0-48cb-9523-a6711e3c73e1": { "id": "5e3c3e16-eff0-48cb-9523-a6711e3c73e1", "prev": "abc8aabe-20bf-4af1-9ffe-145f0ff4db01", "regions": { "67177a4e-b9e7-4bca-9849-6e48cda581de": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "861c638f-ec78-4001-b39c-875cce76dfdc", "part": "whole" }, "id": "67177a4e-b9e7-4bca-9849-6e48cda581de" } } }, "5e6bfa51-005a-4ac3-a6bb-4c7f0de82fde": { "id": "5e6bfa51-005a-4ac3-a6bb-4c7f0de82fde", "prev": "a64a9a11-1ada-4951-bb3e-7b545e7ae93e", "regions": { "4a412fda-3924-463f-8925-e98ee61eeb22": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "39788369-262a-49c6-a335-a90b04bc57b0", "part": "whole" }, "id": "4a412fda-3924-463f-8925-e98ee61eeb22" } } }, "60066575-1881-4528-93eb-300c304a4342": { "id": "60066575-1881-4528-93eb-300c304a4342", "prev": "6ebd9705-73b1-40a7-81ba-52661f96afe2", "regions": { "07702d81-3992-4081-ad46-48df67b3409b": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "bd505a24-4f2d-4f14-9a90-126ad2c5c2ea", "part": "whole" }, "id": "07702d81-3992-4081-ad46-48df67b3409b" } } }, "6522066d-1956-47bc-ae36-5912628d835f": { "id": "6522066d-1956-47bc-ae36-5912628d835f", "prev": "a8ae03d3-7805-40c7-be3d-9c52caaf52fd", "regions": { "545af007-b9ee-4da3-b3b3-600cd315a182": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "bfb9ef9f-8bcf-4100-8c99-57bf8959c57b", "part": "whole" }, "id": "545af007-b9ee-4da3-b3b3-600cd315a182" } } }, "66942006-40b7-4b08-94c1-ab4b27693b7c": { "id": "66942006-40b7-4b08-94c1-ab4b27693b7c", "prev": "e446495f-108d-45f6-ba1a-a969b912750b", "regions": { "9e983782-98b1-4956-9e92-a3b1dc7ffbd7": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "96bc8eb2-feff-46e5-b296-729b4de0039a", "part": "whole" }, "id": "9e983782-98b1-4956-9e92-a3b1dc7ffbd7" } } }, "69e8c329-6de9-4d81-bc36-30b914a3b1a0": { "id": "69e8c329-6de9-4d81-bc36-30b914a3b1a0", "prev": "ea8db5d2-d9d8-4c6a-abe9-72f81aea2952", "regions": { "79df5a58-e178-4551-b8f1-033c41cde61a": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "80e8a873-9828-444d-9c44-e5d980c7c0eb", "part": "whole" }, "id": "79df5a58-e178-4551-b8f1-033c41cde61a" } } }, "6ebd9705-73b1-40a7-81ba-52661f96afe2": { "id": "6ebd9705-73b1-40a7-81ba-52661f96afe2", "prev": "31ea5d42-cbb0-4f5c-ba85-30991589589e", "regions": { "e384199c-40a6-40f6-8c82-b13b14aa13a1": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "fdd83dc1-2853-4125-8090-947f35da5a5c", "part": "whole" }, "id": "e384199c-40a6-40f6-8c82-b13b14aa13a1" } } }, "74760939-8196-4861-a640-82556ac326e0": { "id": "74760939-8196-4861-a640-82556ac326e0", "prev": "7714a1fd-114e-4a07-b7df-09dac566ef2c", "regions": { "27056150-d637-4a50-b7e3-e93cc1841a31": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "636d18ab-b153-4566-81d5-3b608284d2e4", "part": "whole" }, "id": "27056150-d637-4a50-b7e3-e93cc1841a31" } } }, "75639f5b-0444-4adf-bc17-6fa09cd11e4f": { "id": "75639f5b-0444-4adf-bc17-6fa09cd11e4f", "prev": "23e8d199-7954-4110-aa00-268a4780d229", "regions": { "91414a49-bc36-4d94-841d-cf621cbd1d2b": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "97260746-1fd8-4fa0-8c0f-1a71a4a54c11", "part": "whole" }, "id": "91414a49-bc36-4d94-841d-cf621cbd1d2b" } } }, "7714a1fd-114e-4a07-b7df-09dac566ef2c": { "id": "7714a1fd-114e-4a07-b7df-09dac566ef2c", "prev": "ad309bb4-6c88-4e11-8449-6ae247c95ab8", "regions": { "b81b7f31-0342-46c9-9d8d-c0e3727c84c9": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "96dc1ad2-d5db-4ed7-931d-cdd3107f3fd5", "part": "whole" }, "id": "b81b7f31-0342-46c9-9d8d-c0e3727c84c9" } } }, "79848694-9e95-4bfa-9589-acc949f2dc0f": { "id": "79848694-9e95-4bfa-9589-acc949f2dc0f", "prev": "4ce88900-a885-49e9-9229-431d70ad25df", "regions": { "aad0690b-c3a1-4ed8-8572-0a96aa217605": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "02caf31c-8652-445c-a8a3-f257bb2e1bb4", "part": "whole" }, "id": "aad0690b-c3a1-4ed8-8572-0a96aa217605" } } }, "80edbb16-b6a1-4233-8833-0d4f6addea00": { "id": "80edbb16-b6a1-4233-8833-0d4f6addea00", "prev": "5e3c3e16-eff0-48cb-9523-a6711e3c73e1", "regions": { "c202597f-d64f-42b6-aa97-b71b020ac093": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "d7fdbdf8-251b-4756-9e47-ac3110b5c849", "part": "whole" }, "id": "c202597f-d64f-42b6-aa97-b71b020ac093" } } }, "828f54ef-bb4f-4628-8fdd-f9dcb6afccc3": { "id": "828f54ef-bb4f-4628-8fdd-f9dcb6afccc3", "prev": null, "regions": { "1bfa9a1a-2f0a-48de-a2d3-b66b1df07933": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "b4d399ae-27e7-426f-a2ac-c79b5a6cb02f", "part": "whole" }, "id": "1bfa9a1a-2f0a-48de-a2d3-b66b1df07933" } } }, "8c8a0fc3-6191-447e-a2e8-ad5c66d7bb55": { "id": "8c8a0fc3-6191-447e-a2e8-ad5c66d7bb55", "prev": "aa9424f6-6619-449d-83af-4719ad42e3ae", "regions": { "30fe711c-8907-45d6-ac55-ac30de2b2a98": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "5ec8bf14-57ad-4e1b-8b13-d7da42924760", "part": "whole" }, "id": "30fe711c-8907-45d6-ac55-ac30de2b2a98" } } }, "8e9740f7-a327-4809-a72a-65cad5c3720c": { "id": "8e9740f7-a327-4809-a72a-65cad5c3720c", "prev": "23ea59ee-f9eb-4bbd-9abf-fe2faf91940c", "regions": { "f980d771-df3b-45ae-afac-fea9d27c7ab4": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "99eac7dc-c7d5-419c-afd4-1e7a8a6ef96e", "part": "whole" }, "id": "f980d771-df3b-45ae-afac-fea9d27c7ab4" } } }, "9063a41d-0c8f-46e6-b1b2-af0f273651f9": { "id": "9063a41d-0c8f-46e6-b1b2-af0f273651f9", "prev": "5e6bfa51-005a-4ac3-a6bb-4c7f0de82fde", "regions": { "32d58d61-c9a4-4551-9832-32720bffd761": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "adce5d12-902d-4b0a-9e33-7f6ff2a1685d", "part": "whole" }, "id": "32d58d61-c9a4-4551-9832-32720bffd761" } } }, "93d373b9-1605-42b8-b613-65a22a86457a": { "id": "93d373b9-1605-42b8-b613-65a22a86457a", "prev": "b7f6b015-7ae2-4473-abfe-2350ff7b7a74", "regions": { "b311a3ed-17e1-4f3d-88cc-65dc7adb7576": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "7ff35116-bcd8-4402-880d-f6d3c8071a67", "part": "whole" }, "id": "b311a3ed-17e1-4f3d-88cc-65dc7adb7576" } } }, "94c99125-eda5-43c9-8a6e-4e25b65c3ad7": { "id": "94c99125-eda5-43c9-8a6e-4e25b65c3ad7", "prev": "a1b0d131-cc76-4359-8b13-57092129f3ee", "regions": { "c8616b9f-4328-4545-bb21-e73a43e25082": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "ff3fd202-2ddb-4a3a-b28a-e68b99afe8b1", "part": "whole" }, "id": "c8616b9f-4328-4545-bb21-e73a43e25082" } } }, "97bdcf66-ffea-49f3-b367-eb46ae8584b6": { "id": "97bdcf66-ffea-49f3-b367-eb46ae8584b6", "prev": "94c99125-eda5-43c9-8a6e-4e25b65c3ad7", "regions": { "2dd96cf8-aba6-4e94-be3b-5a434e544cbc": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "0c0c8cad-eaee-44e5-9a17-5186cf661c91", "part": "whole" }, "id": "2dd96cf8-aba6-4e94-be3b-5a434e544cbc" } } }, "9ee094cd-3ad0-401d-8544-abc9b7f8910f": { "id": "9ee094cd-3ad0-401d-8544-abc9b7f8910f", "prev": "06fdad76-73ed-4bb9-9008-d3c9117eb783", "regions": { "bfc2695a-953a-44d2-a952-4e26f8c555ef": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "30fc4b21-e1d3-4823-b437-4e300f2f07b9", "part": "whole" }, "id": "bfc2695a-953a-44d2-a952-4e26f8c555ef" } } }, "a06df86d-1723-47b7-a3c5-3b42a1867829": { "id": "a06df86d-1723-47b7-a3c5-3b42a1867829", "prev": "4a531b84-65c7-4b54-ba9a-329ea45c3270", "regions": { "fac15ceb-c752-4113-9952-2b56d8266204": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "cf445208-e3a7-4baf-8c23-cc3a460bc34a", "part": "whole" }, "id": "fac15ceb-c752-4113-9952-2b56d8266204" } } }, "a1b0d131-cc76-4359-8b13-57092129f3ee": { "id": "a1b0d131-cc76-4359-8b13-57092129f3ee", "prev": "22a5b54c-6bab-4a6a-9e2a-284251395517", "regions": { "74c6031a-0a08-4221-99e1-434276672e84": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "48e14a23-1f2a-4b8e-a439-950dd9975515", "part": "whole" }, "id": "74c6031a-0a08-4221-99e1-434276672e84" } } }, "a64a9a11-1ada-4951-bb3e-7b545e7ae93e": { "id": "a64a9a11-1ada-4951-bb3e-7b545e7ae93e", "prev": "223ff166-4f0b-4bb8-9790-e6dd8baaa596", "regions": { "8733407c-3582-4cb8-bd3e-d92e851f5c61": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "42faa621-3766-4ef9-adc8-f8a1f1e7cc5f", "part": "whole" }, "id": "8733407c-3582-4cb8-bd3e-d92e851f5c61" } } }, "a71c3f64-e3c1-4810-b2f1-dc1d3f19582e": { "id": "a71c3f64-e3c1-4810-b2f1-dc1d3f19582e", "prev": "286a64ba-5991-4131-bae4-9bc5f703c587", "regions": { "1fcc4a10-48c2-47fa-8a46-e99cf060e1b1": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "7bb9f155-8411-4e5c-af83-da460ef3d52d", "part": "whole" }, "id": "1fcc4a10-48c2-47fa-8a46-e99cf060e1b1" } } }, "a8ae03d3-7805-40c7-be3d-9c52caaf52fd": { "id": "a8ae03d3-7805-40c7-be3d-9c52caaf52fd", "prev": "9ee094cd-3ad0-401d-8544-abc9b7f8910f", "regions": { "ff7e8867-e66c-43bc-9c27-493cc2099901": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "7ccc0315-1973-4d63-849a-246a327f7e98", "part": "whole" }, "id": "ff7e8867-e66c-43bc-9c27-493cc2099901" } } }, "a90c03e9-50ce-4af3-ac3e-ad0a6517f2b2": { "id": "a90c03e9-50ce-4af3-ac3e-ad0a6517f2b2", "prev": "e778dcb9-b482-4919-81af-f22fde87e026", "regions": { "cf9adabf-24a2-4502-95a2-37b7be2873b7": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "7fa5fa37-e894-4caa-8052-55d6ce2677d4", "part": "whole" }, "id": "cf9adabf-24a2-4502-95a2-37b7be2873b7" } } }, "aa9424f6-6619-449d-83af-4719ad42e3ae": { "id": "aa9424f6-6619-449d-83af-4719ad42e3ae", "prev": "828f54ef-bb4f-4628-8fdd-f9dcb6afccc3", "regions": { "c0187196-5d1f-4e9a-8ce2-67253da07c3e": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "8dbcdbe6-b5e4-4803-b5bf-d591a1c0c4c4", "part": "whole" }, "id": "c0187196-5d1f-4e9a-8ce2-67253da07c3e" } } }, "abc8aabe-20bf-4af1-9ffe-145f0ff4db01": { "id": "abc8aabe-20bf-4af1-9ffe-145f0ff4db01", "prev": "5032b6ad-f2dc-4a4a-8232-51307d785be5", "regions": { "24ea2c92-f65c-4976-b7d6-a8d5c2cc1c02": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "69a559a9-9d4f-43d5-bc83-12c2b0abc776", "part": "whole" }, "id": "24ea2c92-f65c-4976-b7d6-a8d5c2cc1c02" } } }, "aceeab4b-ab16-432d-9f6c-5447735b45aa": { "id": "aceeab4b-ab16-432d-9f6c-5447735b45aa", "prev": "3cdb3114-6e24-4903-96e2-f40297203d1a", "regions": { "270384cc-6c46-496e-be93-9308489cb2d6": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "e172a934-fc99-4cd9-81ab-1afcc9875423", "part": "whole" }, "id": "270384cc-6c46-496e-be93-9308489cb2d6" } } }, "ad309bb4-6c88-4e11-8449-6ae247c95ab8": { "id": "ad309bb4-6c88-4e11-8449-6ae247c95ab8", "prev": "a06df86d-1723-47b7-a3c5-3b42a1867829", "regions": { "e717a043-952a-4207-af94-f7b1063c007e": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "9689610e-f181-4377-a878-aeaf261e8567", "part": "whole" }, "id": "e717a043-952a-4207-af94-f7b1063c007e" } } }, "ade912c4-b81e-467c-ab6f-deb527b0403e": { "id": "ade912c4-b81e-467c-ab6f-deb527b0403e", "prev": "6522066d-1956-47bc-ae36-5912628d835f", "regions": { "dc9001c6-926e-4b85-b76f-3daebf26aca0": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "1d33ae35-b5e7-4ccc-8c63-39831848cbed", "part": "whole" }, "id": "dc9001c6-926e-4b85-b76f-3daebf26aca0" } } }, "b7f6b015-7ae2-4473-abfe-2350ff7b7a74": { "id": "b7f6b015-7ae2-4473-abfe-2350ff7b7a74", "prev": "13af60a5-502c-409f-b1db-306d3546673e", "regions": { "6f9ffdd1-72d7-45ea-80a5-27017764d19b": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "d5241d34-488d-4175-b8a8-a241226b7a3c", "part": "whole" }, "id": "6f9ffdd1-72d7-45ea-80a5-27017764d19b" } } }, "ba50a6b2-dc8e-4d6c-aad2-73e8ad79009d": { "id": "ba50a6b2-dc8e-4d6c-aad2-73e8ad79009d", "prev": "e2c44a3e-8997-499b-b2f5-c033ce4782cb", "regions": { "ef670ea7-c5aa-477e-8b12-873019747b45": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "38788d23-75be-41f6-9145-ce2c398f2822", "part": "whole" }, "id": "ef670ea7-c5aa-477e-8b12-873019747b45" } } }, "bf9a2ce6-4a53-4f90-97aa-64c615b42af4": { "id": "bf9a2ce6-4a53-4f90-97aa-64c615b42af4", "prev": "75639f5b-0444-4adf-bc17-6fa09cd11e4f", "regions": { "177e3268-4533-434e-98c4-431fa298f314": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "c4aafc17-eed8-4830-8333-02a98f4ccb8b", "part": "whole" }, "id": "177e3268-4533-434e-98c4-431fa298f314" } } }, "c790ea0b-37f6-4f69-937f-5d651da48601": { "id": "c790ea0b-37f6-4f69-937f-5d651da48601", "prev": "9063a41d-0c8f-46e6-b1b2-af0f273651f9", "regions": { "14718b54-effc-4274-b93a-3f004c2de83a": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "32b2eb7b-1f5b-45dc-bb9b-0913756c1358", "part": "whole" }, "id": "14718b54-effc-4274-b93a-3f004c2de83a" } } }, "c81bbceb-6c06-4989-ab5d-4e0002ed988e": { "id": "c81bbceb-6c06-4989-ab5d-4e0002ed988e", "prev": "f4456832-176a-43f1-b5c7-42607ca0a1ba", "regions": { "612f5fd0-05ce-40c6-94bf-01c174e2f6d4": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "42af5ecb-6024-4366-94ef-a3e32a6db894", "part": "whole" }, "id": "612f5fd0-05ce-40c6-94bf-01c174e2f6d4" } } }, "c8c721ae-658b-4ab2-9d84-b90908992724": { "id": "c8c721ae-658b-4ab2-9d84-b90908992724", "prev": "1e187c07-2118-486e-abbc-0fbb90d33727", "regions": { "798f0056-6bf6-4ad5-8e2d-e4be0ecd3282": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "8ee08570-75e7-4d93-8c2a-a46fd707c7ed", "part": "whole" }, "id": "798f0056-6bf6-4ad5-8e2d-e4be0ecd3282" } } }, "ce5b519b-be27-475a-b316-163d53ae89b9": { "id": "ce5b519b-be27-475a-b316-163d53ae89b9", "prev": "d1d19576-767a-4986-9673-60710110c7cf", "regions": { "9d4fce6c-372a-4cdc-911f-f3e250c5fb1b": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "71aad76b-3065-4bc6-b778-547ed96aaea6", "part": "whole" }, "id": "9d4fce6c-372a-4cdc-911f-f3e250c5fb1b" } } }, "d1d19576-767a-4986-9673-60710110c7cf": { "id": "d1d19576-767a-4986-9673-60710110c7cf", "prev": "5bd7b2f8-7942-4b57-97e3-1523fc403278", "regions": { "5e9a49bd-3397-466d-a7a1-a98d3f67d2d2": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "37e58043-93b4-427b-ba89-ac5175983835", "part": "whole" }, "id": "5e9a49bd-3397-466d-a7a1-a98d3f67d2d2" } } }, "d797644c-769d-4dca-ace3-b5b80cd83bca": { "id": "d797644c-769d-4dca-ace3-b5b80cd83bca", "prev": "93d373b9-1605-42b8-b613-65a22a86457a", "regions": { "ade6c14b-8434-44c3-acdc-3bd0627963af": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "3af0c210-e6b4-4eed-9e59-f6a6b4ecf677", "part": "whole" }, "id": "ade6c14b-8434-44c3-acdc-3bd0627963af" } } }, "d7bb974a-4cee-417e-8ae2-37897bbda801": { "id": "d7bb974a-4cee-417e-8ae2-37897bbda801", "prev": "c81bbceb-6c06-4989-ab5d-4e0002ed988e", "regions": { "a08eea5d-f846-447a-9b1a-4e92d5af1c14": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "874d2766-f8ac-47c6-8315-fb5ff2c1016b", "part": "whole" }, "id": "a08eea5d-f846-447a-9b1a-4e92d5af1c14" } } }, "e2c44a3e-8997-499b-b2f5-c033ce4782cb": { "id": "e2c44a3e-8997-499b-b2f5-c033ce4782cb", "prev": "067d3558-5fe3-4116-aafd-0d1ac44c460a", "regions": { "57ccbf20-430c-4a3e-9cd1-4132802cd5b5": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "d4e520ac-1237-43a3-9364-64aad7136867", "part": "whole" }, "id": "57ccbf20-430c-4a3e-9cd1-4132802cd5b5" } } }, "e2e22cc1-0ad6-4045-845e-0ef700d2e83e": { "id": "e2e22cc1-0ad6-4045-845e-0ef700d2e83e", "prev": "bf9a2ce6-4a53-4f90-97aa-64c615b42af4", "regions": { "ba8e9e1b-44ff-4dbb-a8ce-27b7fbb4a22d": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "b8b90419-d1ec-4439-890e-9717780094b3", "part": "whole" }, "id": "ba8e9e1b-44ff-4dbb-a8ce-27b7fbb4a22d" } } }, "e446495f-108d-45f6-ba1a-a969b912750b": { "id": "e446495f-108d-45f6-ba1a-a969b912750b", "prev": "8e9740f7-a327-4809-a72a-65cad5c3720c", "regions": { "64cc2992-3254-4026-925e-3c5948953d3d": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "f47df73d-5867-4efe-b999-d4ce1b83c7dd", "part": "whole" }, "id": "64cc2992-3254-4026-925e-3c5948953d3d" } } }, "e688f732-8379-4090-baee-d74e938ba845": { "id": "e688f732-8379-4090-baee-d74e938ba845", "prev": "49200624-0a03-4694-8554-e9d9e24ab75f", "regions": { "888a7e34-06b6-4a42-88d5-899aa7e2bfd4": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "4773db1d-567a-42b6-9c33-79b6fa0b96a6", "part": "whole" }, "id": "888a7e34-06b6-4a42-88d5-899aa7e2bfd4" } } }, "e778dcb9-b482-4919-81af-f22fde87e026": { "id": "e778dcb9-b482-4919-81af-f22fde87e026", "prev": "e2e22cc1-0ad6-4045-845e-0ef700d2e83e", "regions": { "aa89fea5-9aa9-4ac5-9d99-610c673fd606": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "4519e7df-5d72-44be-ab36-44c1e2d04268", "part": "whole" }, "id": "aa89fea5-9aa9-4ac5-9d99-610c673fd606" } } }, "ea8db5d2-d9d8-4c6a-abe9-72f81aea2952": { "id": "ea8db5d2-d9d8-4c6a-abe9-72f81aea2952", "prev": "58f94107-080a-4c92-92d5-77572c38595a", "regions": { "d7661bbb-ffb2-449c-b7db-0c4a3de5b092": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "bd1de069-0df7-48bc-83f7-f5e061a7d06e", "part": "whole" }, "id": "d7661bbb-ffb2-449c-b7db-0c4a3de5b092" } } }, "f4456832-176a-43f1-b5c7-42607ca0a1ba": { "id": "f4456832-176a-43f1-b5c7-42607ca0a1ba", "prev": "60066575-1881-4528-93eb-300c304a4342", "regions": { "ffef117a-cb35-43dc-8590-a61b23f082db": { "attrs": { "height": 0.8, "width": 0.8, "x": 0.1, "y": 0.1 }, "content": { "cell": "d9f646a4-f5b9-482b-aaf2-eaa055292db0", "part": "whole" }, "id": "ffef117a-cb35-43dc-8590-a61b23f082db" } } } }, "themes": {} } }, "nbformat": 4, "nbformat_minor": 0 }