1. Agrégation externe de mathématiques¶
1.1 Leçon orale, option informatique¶
- Ce notebook Jupyter est une implémentation d'un algorithme constituant un développement pour l'option informatique de l'agrégation externe de mathématiques.
- Il s'agit du calcul du plus long sous mot commun.
- Cette implémentation (partielle) a été rédigée par Lilian Besson (sur GitHub ?, sur Bitbucket ?), et est open-source.
Feedbacks?¶
- Vous avez trouvé un bug ? → Signalez-le moi svp !, merci d'avance.
- Vous avez une question ? → Posez la svp !
2. Calcul du plus long sous mot commun¶
2.0.1 Implémentation d'un développement pour les leçons 906, 907.¶
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 !).
É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$. 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$ !
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 $Y$, mais cette solution est inefficace : il y a $\mathcal{O}(2^m)$ sous-mots de X...
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)$).
2.0.2 Références :¶
- Bien traité dans "Cormen", Ch15.4 p341,
- Esquissé dans "Aho, Hopcroft, Ullman", Ch5.6 p192,
- Dévéloppement tapé en PDF ici.
2.0.3 Applications, généralisations :¶
- 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).
- On peut citer en application la comparaison de chaînes d'ADN, mais aussi la commande
diffdes systèmes GNU/Linux. - 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)).
3. Algorithme naïf (exponentiel)¶
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.
3.1 Détecter si $u$ est sous mot de $y$¶
L'objectif de toutes les fonctions suivantes est de proscrire toute recopie de chaines (slicing, x[i:j]), qui sont très couteuse.
In [1]:
def indiceSousMotAux(u, n, k, y, m, i, delta=0):
""" 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."""
# print("{}indiceSousMotAux(u = {}, n = {}, k = {}, y = {}, m = {}, i = {}, delta = {})".format(' '*delta, u, n, k, y, m, i, delta)) # DEBUG
if n == 0: # Mot vide, commun partout, par defaut on donne 0
return 0
else: # Mot pas vide
if k >= len(u) or i >= m: # On a cherché trop loin, échec
return -1 # -1 signifie échec
elif u[k] == y[i]: # Lettre en commun
if delta == n - 1: # On a fini, on a trouvé !
return i - n + 1 # i est l'indice de la derniere lettre ici
else: # On continue de chercher, une lettre de moins
return indiceSousMotAux(u, n, k + 1, y, m, i + 1, delta=delta+1)
else: # On recommence a chercher en i+1
return indiceSousMotAux(u, n, k - delta, y, m, i + 1)
def indiceSousMot(u, y):
""" En O(|u|), trouve l'indice j tel que u = y[j:j+|u|], ou -1 en cas d'échec."""
return indiceSousMotAux(u, len(u), 0, y, len(y), 0)
def estSousMot(u, y):
""" Vérifie en O(|u|) si u est sous-mot de y."""
return indiceSousMotAux(u, len(u), 0, y, len(y), 0) >= 0
Quelques tests :
In [2]:
def test_estSousMot(u, y):
""" Teste et affiche. """
i = indiceSousMot(u, y)
if i >= 0:
print("Le mot u = '{}' est sous-mot de y = '{}', a partir de l'indice i = {}.".format(u, y, i))
else:
print("Le mot u = '{}' n'est pas sous-mot de y = '{}'.".format(u, y))
u = "cde"
y1 = "abcdefghijklmnopqrstuvwxyz"
test_estSousMot(u, y1) # True
y2 = "abcDefghijklmnopqrstuvwxyz"
test_estSousMot(u, y2) # False
Le mot u = 'cde' est sous-mot de y = 'abcdefghijklmnopqrstuvwxyz', a partir de l'indice i = 2. Le mot u = 'cde' n'est pas sous-mot de y = 'abcDefghijklmnopqrstuvwxyz'.
3.2 Trouver un sous-mot de longueur k¶
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) :
In [3]:
def aSousMotDeLongueur(x, y, k):
""" Trouve le premier sous-mot de x de longueur k et renvoit i, j, u, ou échoue avec une ValueError. """
imax = len(x) - k + 1
# Les sous mots seront x0..xk-1, .., ximax-1,..,xn-1
for debut in range(imax):
j = indiceSousMotAux(x, k, debut, y, len(y), 0)
if j >= 0:
return debut, debut + j, x[debut:debut+k]
# Pas trouvé !
raise ValueError("Aucun sous-mot de longueur k = {} de x = '{}' n'est dans y = '{}'.".format(k, x, y))
Un test :
In [4]:
def test_aSousMotDeLongueur(x, y, k):
""" Teste et affiche. """
try:
i, j, u = aSousMotDeLongueur(x, y, k)
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))
except ValueError:
print("==> Aucun sous-mot de longueur k = {} de x = '{}' n'est dans y = '{}'.".format(k, x, y))
x = "aabcde"
y = "aABcdE"
for k in range(0, min(len(x), len(y)) + 1):
test_aSousMotDeLongueur(x, y, k)
x = "aabffcde"
y = "aABGGGGGcdE"
for k in range(0, min(len(x), len(y)) + 1):
test_aSousMotDeLongueur(x, y, k)
==> Sous-mot de longueur k = 0 de x = 'aabcde' dans y = 'aABcdE' : u = '' en indice i = 0 pour x et j = 0 pour y. ==> 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. ==> 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. ==> Aucun sous-mot de longueur k = 3 de x = 'aabcde' n'est dans y = 'aABcdE'. ==> Aucun sous-mot de longueur k = 4 de x = 'aabcde' n'est dans y = 'aABcdE'. ==> Aucun sous-mot de longueur k = 5 de x = 'aabcde' n'est dans y = 'aABcdE'. ==> Aucun sous-mot de longueur k = 6 de x = 'aabcde' n'est dans y = 'aABcdE'. ==> Sous-mot de longueur k = 0 de x = 'aabffcde' dans y = 'aABGGGGGcdE' : u = '' en indice i = 0 pour x et j = 0 pour y. ==> 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. ==> 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. ==> Aucun sous-mot de longueur k = 3 de x = 'aabffcde' n'est dans y = 'aABGGGGGcdE'. ==> Aucun sous-mot de longueur k = 4 de x = 'aabffcde' n'est dans y = 'aABGGGGGcdE'. ==> Aucun sous-mot de longueur k = 5 de x = 'aabffcde' n'est dans y = 'aABGGGGGcdE'. ==> Aucun sous-mot de longueur k = 6 de x = 'aabffcde' n'est dans y = 'aABGGGGGcdE'. ==> Aucun sous-mot de longueur k = 7 de x = 'aabffcde' n'est dans y = 'aABGGGGGcdE'. ==> Aucun sous-mot de longueur k = 8 de x = 'aabffcde' n'est dans y = 'aABGGGGGcdE'.
3.3 Sous-mot de longueur maximale (version naïve)¶
In [5]:
def _sousMotMax(x, y, verb=True):
""" |x| doit etre plus petit que |y|."""
k = len(x)
while k >= 0:
if verb:
print(" On essaie de trouver un sous-mot commun à x = '{}' et y = '{}' de taille k = {} ...".format(x, y, k))
try:
i, j, u = aSousMotDeLongueur(x, y, k)
if verb:
print(" ==> On a un sous-mot commun à x = '{}' et y = '{}' de taille k = {} : u = '{}' (i = {}, j = {}) !".format(x, y, k, u, i, j))
return i, j, u
except ValueError:
if verb:
print(" ==> Aucun sous-mot commun à x = '{}' et y = '{}' de taille k = {} ...".format(x, y, k))
k -= 1
def sousMotMax(x, y, verb=True):
""" Trouve un sous-mot de longueur maximale (le plus à gauche possible de x et y), en temps exponentiel en n = |x|."""
if len(x) <= len(y):
return _sousMotMax(x, y, verb=verb)
else:
return _sousMotMax(y, x, verb=verb)
Quelques tests :
In [6]:
x = "abcABCabc123456abcABCabc99"
y = "abcDEFdef123456abcDEFdef9999"
sousMotMax(x, y, verb=False)
Out[6]:
(9, 18, '123456abc')
In [7]:
x = "abcABCabc"
y = "abcDEFdef"
sousMotMax(x, y)
On essaie de trouver un sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 9 ... ==> Aucun sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 9 ... On essaie de trouver un sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 8 ... ==> Aucun sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 8 ... On essaie de trouver un sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 7 ... ==> Aucun sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 7 ... On essaie de trouver un sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 6 ... ==> Aucun sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 6 ... On essaie de trouver un sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 5 ... ==> Aucun sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 5 ... On essaie de trouver un sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 4 ... ==> Aucun sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 4 ... On essaie de trouver un sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 3 ... ==> On a un sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 3 : u = 'abc' (i = 0, j = 0) !
Out[7]:
(0, 0, 'abc')
4. Méthode gloutonne (programmation dynamique)¶
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}$).
Cette approche a l'avantage d'être bien plus efficace, mais aussi plus simple à coder.
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.
In [8]:
# On a besoin du module numpy. Cf. http://numpy.org/ pour l'installer si besoin
import numpy as np
4.1 Programmation dynamique, sans optimisation mémoire¶
La fonction ci-dessous procède en 4 étapes :
- Initialisation de la matrice
longueurs, pleine de $0$ et de taille $(n+1) \times (m+1)$ où $y := |x|$ et $m := |y|$, - Calcul "bottom-up" de la matrice
longueurs, par l'équation suivante : $$ \mathrm{longueurs}[i, j] = 1 + \mathrm{longueurs}[i-1, j-1] \; \text{si} \; x[i-1] = y[i-1]. $$ - Calcul de la longueur maximale d'une correspondance entre
xety, par un simple parcours (longueur_max), et calcul des indices de début de cette coresspondance maximale (= plus long sous-mot !),idebutetjdebut. - (optionnel) On vérifie que
x[idebut : idebut + longueur_max]=y[jdebut : jdebut + longueur_max].
On commence en utilisant une matrice, pleine de $0$ (ie. une matrice nulle). 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. La version suivante sera optimisée (en utilisant une matrice sparse, ie. creuse).
Cet algorithme sera en :
- $\mathcal{O}(n m)$ en mémoire, dans tous les cas (mais on peut faire mieux),
- $\mathcal{O}(n m)$ en temps, dans tous les cas (et on ne peut pas faire mieux).
In [9]:
def sousMotMaxGlouton(x, y, verb=False, verifie=True):
""" Calcule le plus long sous-mot commun a x et y, par programmation dynamique.
- affiche un peu ce qu'il se passe si verb=True,
- vérifie que le sous-mot commun est bien un bon sous-mot commun si verifie=True.
"""
def message(*args):
if verb:
print(*args)
# 1. et 2. Initialisation et construction Matrice longueurs
n = len(x)
m = len(y)
message("\n1. Initialisation de la look-up matrice longueurs de taille (n+1, m+1) : n = {} m = {} ...".format(n, m))
longueurs = np.zeros((n+1, m+1), dtype=int)
message("2. Construction bottom-up de la loop-up matrice longueurs ...")
for i in range(1, n+1):
for j in range(1, m+1):
if x[i-1] == y[j-1]:
longueurs[i, j] = 1 + longueurs[i-1, j-1]
message(" Correspondance en cours, u[{}] = {} et v[{}] = {}, de longueur courante {} ...".format(i-1, x[i-1], j-1, y[j-1], longueurs[i, j]))
# 3. Utilisation de la matrice longueurs
iFin, jFin = 0, 0
longueur_max = -1 # Pas encore
message("3. Calcul de la position du plus long sous mot via la matrice longueurs ...")
for i in range(0, n+1):
for j in range(0, m+1):
if longueur_max < longueurs[i, j]:
longueur_max = longueurs[i, j]
iFin, jFin = i, j
# Note : avec les fonctions numpy np.max et np.argmax on pourrait faire ça plus vite (pour des matrices) :
# longueur_max = np.max(longueurs)
# iFin, jFin = np.unravel_index(np.argmax(longueurs), np.shape(longueurs))
# Calcul des indices de debut
iDebut, jDebut = iFin - longueur_max, jFin - longueur_max
message("4. On a obtenu iDebut = {} et jDebut = {} et longueur_max = {} ...".format(iDebut, jDebut, longueur_max))
# 4. Vérification
if verifie:
xSous = x[iDebut: iDebut + longueur_max]
ySous = y[jDebut: jDebut + longueur_max]
message(" Sous-mot dans x = {}, et sous-mot dans y = {} ...".format(xSous, ySous))
assert xSous == ySous, "Erreur, xSous et ySous sont différents !"
leSousMot = x[iDebut: iDebut + longueur_max]
return iDebut, jDebut, leSousMot, longueurs
On peut faire quelques tests, comme pour l'approche initiale.
In [10]:
x = "BDCABA"
y = "ABCBDAB"
sousMotMaxGlouton(x, y, verb=True)
1. Initialisation de la look-up matrice longueurs de taille (n+1, m+1) : n = 6 m = 7 ...
2. Construction bottom-up de la loop-up matrice longueurs ...
Correspondance en cours, u[0] = B et v[1] = B, de longueur courante 1 ...
Correspondance en cours, u[0] = B et v[3] = B, de longueur courante 1 ...
Correspondance en cours, u[0] = B et v[6] = B, de longueur courante 1 ...
Correspondance en cours, u[1] = D et v[4] = D, de longueur courante 2 ...
Correspondance en cours, u[2] = C et v[2] = C, de longueur courante 1 ...
Correspondance en cours, u[3] = A et v[0] = A, de longueur courante 1 ...
Correspondance en cours, u[3] = A et v[5] = A, de longueur courante 1 ...
Correspondance en cours, u[4] = B et v[1] = B, de longueur courante 2 ...
Correspondance en cours, u[4] = B et v[3] = B, de longueur courante 1 ...
Correspondance en cours, u[4] = B et v[6] = B, de longueur courante 2 ...
Correspondance en cours, u[5] = A et v[0] = A, de longueur courante 1 ...
Correspondance en cours, u[5] = A et v[5] = A, de longueur courante 1 ...
3. Calcul de la position du plus long sous mot via la matrice longueurs ...
4. On a obtenu iDebut = 0 et jDebut = 3 et longueur_max = 2 ...
Sous-mot dans x = BD, et sous-mot dans y = BD ...
Out[10]:
(0, 3, 'BD', array([[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 1, 0, 0, 1],
[0, 0, 0, 0, 0, 2, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 1, 0],
[0, 0, 2, 0, 1, 0, 0, 2],
[0, 1, 0, 0, 0, 0, 1, 0]]))
In [11]:
x = "abcABCabc123456abcABCabc99"
y = "abcDEFdef123456abcDEFdef9999"
sousMotMaxGlouton(x, y, verb=True)
1. Initialisation de la look-up matrice longueurs de taille (n+1, m+1) : n = 26 m = 28 ...
2. Construction bottom-up de la loop-up matrice longueurs ...
Correspondance en cours, u[0] = a et v[0] = a, de longueur courante 1 ...
Correspondance en cours, u[0] = a et v[15] = a, de longueur courante 1 ...
Correspondance en cours, u[1] = b et v[1] = b, de longueur courante 2 ...
Correspondance en cours, u[1] = b et v[16] = b, de longueur courante 2 ...
Correspondance en cours, u[2] = c et v[2] = c, de longueur courante 3 ...
Correspondance en cours, u[2] = c et v[17] = c, de longueur courante 3 ...
Correspondance en cours, u[6] = a et v[0] = a, de longueur courante 1 ...
Correspondance en cours, u[6] = a et v[15] = a, de longueur courante 1 ...
Correspondance en cours, u[7] = b et v[1] = b, de longueur courante 2 ...
Correspondance en cours, u[7] = b et v[16] = b, de longueur courante 2 ...
Correspondance en cours, u[8] = c et v[2] = c, de longueur courante 3 ...
Correspondance en cours, u[8] = c et v[17] = c, de longueur courante 3 ...
Correspondance en cours, u[9] = 1 et v[9] = 1, de longueur courante 1 ...
Correspondance en cours, u[10] = 2 et v[10] = 2, de longueur courante 2 ...
Correspondance en cours, u[11] = 3 et v[11] = 3, de longueur courante 3 ...
Correspondance en cours, u[12] = 4 et v[12] = 4, de longueur courante 4 ...
Correspondance en cours, u[13] = 5 et v[13] = 5, de longueur courante 5 ...
Correspondance en cours, u[14] = 6 et v[14] = 6, de longueur courante 6 ...
Correspondance en cours, u[15] = a et v[0] = a, de longueur courante 1 ...
Correspondance en cours, u[15] = a et v[15] = a, de longueur courante 7 ...
Correspondance en cours, u[16] = b et v[1] = b, de longueur courante 2 ...
Correspondance en cours, u[16] = b et v[16] = b, de longueur courante 8 ...
Correspondance en cours, u[17] = c et v[2] = c, de longueur courante 3 ...
Correspondance en cours, u[17] = c et v[17] = c, de longueur courante 9 ...
Correspondance en cours, u[21] = a et v[0] = a, de longueur courante 1 ...
Correspondance en cours, u[21] = a et v[15] = a, de longueur courante 1 ...
Correspondance en cours, u[22] = b et v[1] = b, de longueur courante 2 ...
Correspondance en cours, u[22] = b et v[16] = b, de longueur courante 2 ...
Correspondance en cours, u[23] = c et v[2] = c, de longueur courante 3 ...
Correspondance en cours, u[23] = c et v[17] = c, de longueur courante 3 ...
Correspondance en cours, u[24] = 9 et v[24] = 9, de longueur courante 1 ...
Correspondance en cours, u[24] = 9 et v[25] = 9, de longueur courante 1 ...
Correspondance en cours, u[24] = 9 et v[26] = 9, de longueur courante 1 ...
Correspondance en cours, u[24] = 9 et v[27] = 9, de longueur courante 1 ...
Correspondance en cours, u[25] = 9 et v[24] = 9, de longueur courante 1 ...
Correspondance en cours, u[25] = 9 et v[25] = 9, de longueur courante 2 ...
Correspondance en cours, u[25] = 9 et v[26] = 9, de longueur courante 2 ...
Correspondance en cours, u[25] = 9 et v[27] = 9, de longueur courante 2 ...
3. Calcul de la position du plus long sous mot via la matrice longueurs ...
4. On a obtenu iDebut = 9 et jDebut = 9 et longueur_max = 9 ...
Sous-mot dans x = 123456abc, et sous-mot dans y = 123456abc ...
Out[11]:
(9,
9,
'123456abc',
array([[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0],
[0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0],
[0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0],
[0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0],
[0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 1, 2, 2, 2]]))
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".
In [12]:
x = "abcZZdeFG597"
y = "AbCdEFG413ZAQCWQ"
sousMotMaxGlouton(x, y, verb=True)
1. Initialisation de la look-up matrice longueurs de taille (n+1, m+1) : n = 12 m = 16 ...
2. Construction bottom-up de la loop-up matrice longueurs ...
Correspondance en cours, u[1] = b et v[1] = b, de longueur courante 1 ...
Correspondance en cours, u[3] = Z et v[10] = Z, de longueur courante 1 ...
Correspondance en cours, u[4] = Z et v[10] = Z, de longueur courante 1 ...
Correspondance en cours, u[5] = d et v[3] = d, de longueur courante 1 ...
Correspondance en cours, u[7] = F et v[5] = F, de longueur courante 1 ...
Correspondance en cours, u[8] = G et v[6] = G, de longueur courante 2 ...
3. Calcul de la position du plus long sous mot via la matrice longueurs ...
4. On a obtenu iDebut = 7 et jDebut = 5 et longueur_max = 2 ...
Sous-mot dans x = FG, et sous-mot dans y = FG ...
Out[12]:
(7, 5, 'FG', array([[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]))
4.2 Utilisation d'une matrice creuse¶
On va utiliser le module scipy.sparse pour utiliser un codage efficace pour cette matrice longueurs : un codage dit creux qui permettra de ne pas stocker tous ces zéros inutiles.
In [13]:
from scipy.sparse import lil_matrix
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).
Exemple :
In [14]:
print("I_12 pleine :\n", np.eye(12))
I12 = lil_matrix(np.eye(12))
print("I_12 creuse :\n", I12)
I12
I_12 pleine : [[ 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.] [ 0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.] [ 0. 0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0.] [ 0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 0. 0.] [ 0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 0.] [ 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 0.] [ 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0.] [ 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0.] [ 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0.] [ 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0.] [ 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 0.] [ 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1.]] I_12 creuse : (0, 0) 1.0 (1, 1) 1.0 (2, 2) 1.0 (3, 3) 1.0 (4, 4) 1.0 (5, 5) 1.0 (6, 6) 1.0 (7, 7) 1.0 (8, 8) 1.0 (9, 9) 1.0 (10, 10) 1.0 (11, 11) 1.0
Out[14]:
<12x12 sparse matrix of type '<class 'numpy.float64'>' with 12 stored elements in LInked List format>
In [15]:
print("Taille de I_12 creuse =", I12.size)
Taille de I_12 creuse = 12
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.
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). Notez que ce sera un poil moins efficace, mais on garde la complexité en temps en $\mathcal{O}(n m)$ de toute façon.
In [16]:
def sousMotMaxGloutonCreux(x, y, verb=False, verifie=True):
""" Calcule le plus long sous-mot commun a x et y, par programmation dynamique.
- affiche un peu ce qu'il se passe si verb=True,
- vérifie que le sous-mot commun est bien un bon sous-mot commun si verifie=True.
"""
def message(*args):
if verb:
print(*args)
# 1. et 2. Initialisation et construction Matrice longueurs
n = len(x)
m = len(y)
message("\n1. Initialisation de la look-up matrice longueurs, creuse de taille (n+1, m+1) : n = {} m = {} ...".format(n, m))
longueurs = lil_matrix(np.zeros((n+1, m+1), dtype=int))
message("2. Construction bottom-up de la loop-up matrice longueurs ...")
for i in range(1, n+1):
for j in range(1, m+1):
if x[i-1] == y[j-1]:
longueurs[i, j] = 1 + longueurs[i-1, j-1]
message(" Correspondance en cours, u[{}] = {} et v[{}] = {}, de longueur courante {} ...".format(i-1, x[i-1], j-1, y[j-1], longueurs[i, j]))
# 3. Utilisation de la matrice longueurs
iFin, jFin = 0, 0
longueur_max = -1 # Pas encore
message("3. Calcul de la position du plus long sous mot via la matrice longueurs ...")
for i in range(0, n+1):
for j in range(0, m+1):
if longueur_max < longueurs[i, j]:
longueur_max = longueurs[i, j]
iFin, jFin = i, j
# Calcul des indices de debut
iDebut, jDebut = iFin - longueur_max, jFin - longueur_max
message("4. On a obtenu iDebut = {} et jDebut = {} et longueur_max = {} ...".format(iDebut, jDebut, longueur_max))
# 4. Vérification
if verifie:
xSous = x[iDebut: iDebut + longueur_max]
ySous = y[jDebut: jDebut + longueur_max]
message(" Sous-mot dans x = {}, et sous-mot dans y = {} ...".format(xSous, ySous))
assert xSous == ySous, "Erreur, xSous et ySous sont différents !"
leSousMot = x[iDebut: iDebut + longueur_max]
return iDebut, jDebut, leSousMot, longueurs
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) :
In [17]:
x = "ab0cABC0abc123456abcABCabc99"
y = "abZQXCVQDScD0EFd0ef123456abcDEFdef9999"
iDebut, jDebut, sousxy, longueurs = sousMotMaxGloutonCreux(x, y, verb=True)
print("Taille de la matrice pleine = (n+1)(m+1) =", (len(x) + 1) * (len(y) + 1))
print("Taille de la matrice creuse longueurs =", longueurs.size)
1. Initialisation de la look-up matrice longueurs, creuse de taille (n+1, m+1) : n = 28 m = 38 ...
2. Construction bottom-up de la loop-up matrice longueurs ...
Correspondance en cours, u[0] = a et v[0] = a, de longueur courante 1 ...
Correspondance en cours, u[0] = a et v[25] = a, de longueur courante 1 ...
Correspondance en cours, u[1] = b et v[1] = b, de longueur courante 2 ...
Correspondance en cours, u[1] = b et v[26] = b, de longueur courante 2 ...
Correspondance en cours, u[2] = 0 et v[12] = 0, de longueur courante 1 ...
Correspondance en cours, u[2] = 0 et v[16] = 0, de longueur courante 1 ...
Correspondance en cours, u[3] = c et v[10] = c, de longueur courante 1 ...
Correspondance en cours, u[3] = c et v[27] = c, de longueur courante 1 ...
Correspondance en cours, u[6] = C et v[5] = C, de longueur courante 1 ...
Correspondance en cours, u[7] = 0 et v[12] = 0, de longueur courante 1 ...
Correspondance en cours, u[7] = 0 et v[16] = 0, de longueur courante 1 ...
Correspondance en cours, u[8] = a et v[0] = a, de longueur courante 1 ...
Correspondance en cours, u[8] = a et v[25] = a, de longueur courante 1 ...
Correspondance en cours, u[9] = b et v[1] = b, de longueur courante 2 ...
Correspondance en cours, u[9] = b et v[26] = b, de longueur courante 2 ...
Correspondance en cours, u[10] = c et v[10] = c, de longueur courante 1 ...
Correspondance en cours, u[10] = c et v[27] = c, de longueur courante 3 ...
Correspondance en cours, u[11] = 1 et v[19] = 1, de longueur courante 1 ...
Correspondance en cours, u[12] = 2 et v[20] = 2, de longueur courante 2 ...
Correspondance en cours, u[13] = 3 et v[21] = 3, de longueur courante 3 ...
Correspondance en cours, u[14] = 4 et v[22] = 4, de longueur courante 4 ...
Correspondance en cours, u[15] = 5 et v[23] = 5, de longueur courante 5 ...
Correspondance en cours, u[16] = 6 et v[24] = 6, de longueur courante 6 ...
Correspondance en cours, u[17] = a et v[0] = a, de longueur courante 1 ...
Correspondance en cours, u[17] = a et v[25] = a, de longueur courante 7 ...
Correspondance en cours, u[18] = b et v[1] = b, de longueur courante 2 ...
Correspondance en cours, u[18] = b et v[26] = b, de longueur courante 8 ...
Correspondance en cours, u[19] = c et v[10] = c, de longueur courante 1 ...
Correspondance en cours, u[19] = c et v[27] = c, de longueur courante 9 ...
Correspondance en cours, u[22] = C et v[5] = C, de longueur courante 1 ...
Correspondance en cours, u[23] = a et v[0] = a, de longueur courante 1 ...
Correspondance en cours, u[23] = a et v[25] = a, de longueur courante 1 ...
Correspondance en cours, u[24] = b et v[1] = b, de longueur courante 2 ...
Correspondance en cours, u[24] = b et v[26] = b, de longueur courante 2 ...
Correspondance en cours, u[25] = c et v[10] = c, de longueur courante 1 ...
Correspondance en cours, u[25] = c et v[27] = c, de longueur courante 3 ...
Correspondance en cours, u[26] = 9 et v[34] = 9, de longueur courante 1 ...
Correspondance en cours, u[26] = 9 et v[35] = 9, de longueur courante 1 ...
Correspondance en cours, u[26] = 9 et v[36] = 9, de longueur courante 1 ...
Correspondance en cours, u[26] = 9 et v[37] = 9, de longueur courante 1 ...
Correspondance en cours, u[27] = 9 et v[34] = 9, de longueur courante 1 ...
Correspondance en cours, u[27] = 9 et v[35] = 9, de longueur courante 2 ...
Correspondance en cours, u[27] = 9 et v[36] = 9, de longueur courante 2 ...
Correspondance en cours, u[27] = 9 et v[37] = 9, de longueur courante 2 ...
3. Calcul de la position du plus long sous mot via la matrice longueurs ...
4. On a obtenu iDebut = 11 et jDebut = 19 et longueur_max = 9 ...
Sous-mot dans x = 123456abc, et sous-mot dans y = 123456abc ...
Taille de la matrice pleine = (n+1)(m+1) = 1131
Taille de la matrice creuse longueurs = 44
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 !
In [18]:
x = "abcZZdeFG597"
y = "AbCdEFG413ZAQCWQ"
iDebut, jDebut, sousxy, longueurs = sousMotMaxGloutonCreux(x, y, verb=True)
print("Taille de la matrice pleine = (n+1)(m+1) =", (len(x) + 1) * (len(y) + 1))
print("Taille de la matrice creuse longueurs =", longueurs.size)
1. Initialisation de la look-up matrice longueurs, creuse de taille (n+1, m+1) : n = 12 m = 16 ...
2. Construction bottom-up de la loop-up matrice longueurs ...
Correspondance en cours, u[1] = b et v[1] = b, de longueur courante 1 ...
Correspondance en cours, u[3] = Z et v[10] = Z, de longueur courante 1 ...
Correspondance en cours, u[4] = Z et v[10] = Z, de longueur courante 1 ...
Correspondance en cours, u[5] = d et v[3] = d, de longueur courante 1 ...
Correspondance en cours, u[7] = F et v[5] = F, de longueur courante 1 ...
Correspondance en cours, u[8] = G et v[6] = G, de longueur courante 2 ...
3. Calcul de la position du plus long sous mot via la matrice longueurs ...
4. On a obtenu iDebut = 7 et jDebut = 5 et longueur_max = 2 ...
Sous-mot dans x = FG, et sous-mot dans y = FG ...
Taille de la matrice pleine = (n+1)(m+1) = 221
Taille de la matrice creuse longueurs = 6
Avec des mots x et y plus longs, le gain en mémoire induit par le codage creux est encore plus impressionnant :
In [19]:
x = "ab0cABC0abc123456abcABCabc99abcZZdeFG597abcZZdeFG597abcZZdeFG597abcZZdeFG597aethjrynghù*ejgodknùebjtzinhmodgkùjihrznhumbajzdgihbjmnaekrzùdbnvkzriùnodgkl ojzirnùodk bùgbznùod1249721325414765132486513486565465klfrzinhbùodfskl p*bjùdkl nbdnù"
y = "abZQXCVQDScD0EFd0ef123456abcDEFdef9999AbCdEFG413ZAQCWQAbCdEFG413ZAQCWQAbCdEFG413ZAQCWQAbCdEFG413ZAQCWQAbCdEFG413ZAQCWQzrthekĝbùpbgmhbgdmv hubznemr1249721325414765132486513486565465ebgd"
iDebut, jDebut, sousxy, longueurs = sousMotMaxGloutonCreux(x, y, verb=False)
print("Taille de la matrice pleine = (n+1)(m+1) =", (len(x) + 1) * (len(y) + 1))
print("Taille de la matrice creuse longueurs =", longueurs.size)
Taille de la matrice pleine = (n+1)(m+1) = 44215 Taille de la matrice creuse longueurs = 1046
4.2.1 Version condensée¶
Le code de cette fonction sousMotMaxGloutonCreux peut sembler un peu long, mais sans messages ni commentaires il est vraiment court et simple :
In [20]:
def sousMotMaxGloutonCreux2(x, y):
n = len(x)
m = len(y)
longueurs = lil_matrix(np.zeros((n+1, m+1), dtype=int))
for i in range(1, n+1):
for j in range(1, m+1):
if x[i-1] == y[j-1]:
longueurs[i, j] = 1 + longueurs[i-1, j-1]
iFin, jFin = 0, 0
longueur_max = -1 # Pas encore
for i in range(0, n+1):
for j in range(0, m+1):
if longueur_max < longueurs[i, j]:
longueur_max = longueurs[i, j]
iFin, jFin = i, j
iDebut, jDebut = iFin - longueur_max, jFin - longueur_max
leSousMot = x[iDebut: iDebut + longueur_max]
return iDebut, jDebut, leSousMot, longueurs
Et le même exemple donne pareil :
In [21]:
x = "ab0cABC0abc123456abcABCabc99abcZZdeFG597abcZZdeFG597abcZZdeFG597abcZZdeFG597aethjrynghù*ejgodknùebjtzinhmodgkùjihrznhumbajzdgihbjmnaekrzùdbnvkzriùnodgkl ojzirnùodk bùgbznùod1249721325414765132486513486565465klfrzinhbùodfskl p*bjùdkl nbdnù"
y = "abZQXCVQDScD0EFd0ef123456abcDEFdef9999AbCdEFG413ZAQCWQAbCdEFG413ZAQCWQAbCdEFG413ZAQCWQAbCdEFG413ZAQCWQAbCdEFG413ZAQCWQzrthekĝbùpbgmhbgdmv hubznemr1249721325414765132486513486565465ebgd"
iDebut, jDebut, sousxy, longueurs = sousMotMaxGloutonCreux2(x, y)
print("Taille de la matrice pleine = (n+1)(m+1) =", (len(x) + 1) * (len(y) + 1))
print("Taille de la matrice creuse longueurs =", longueurs.size)
print("Sous-mot :", sousxy)
Taille de la matrice pleine = (n+1)(m+1) = 44215 Taille de la matrice creuse longueurs = 1046 Sous-mot : 1249721325414765132486513486565465
5. Calcule de la plus longue sous-séquence commune¶
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.
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. Le développement d'agrégation devrait concerner le second problème, qui est plus intéressant: Par exemple, voici une version tapée en PDF : http://minerve.bretagne.ens-cachan.fr/images/Dvt_plsc.pdf.
5.1 Vérifier qu'une sous-séquence est une bonne sous-séquence¶
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.
In [22]:
def estSousSeq(seq, x, verb=True, indices=True):
""" Verifie en temps O(|seq| |x|) que seq est une bonne sous-sequence de x.
"""
result = False
indices_x = []
try:
i = -1
for l in seq:
j = i+1 + x[i+1:].index(l)
indices_x.append(j)
i = j
result = True
except Exception as e:
if verb:
print("Erreur dans estSousSeq(seq = {}, x = {}):\n{}".format(seq, x, e))
if indices:
return result, indices_x
else:
return result
5.2 Algorithme pour la plus longue sous-séquence¶
On adapte l'algorithme du plus long sous-mot pour détecter les séquences aussi. Cf. le PDF page 2/3.
TODO meilleures explications
In [23]:
def utiliseTableOrigines_x(x, origines, i, j, accu=''):
""" Renvoie la sous-séquence de x codée dans la table origines. Cf. PDF (Algorithme 2).
- Calcul tail récursif (stocké dans la variable accu).
"""
# print(" utiliseTableOrigines(x = {}, origines, i = {}, j = {}, accu = {}) : origines[i, j] = {} ...".format(x, i, j, accu, origines[i, j])) # DEBUG
if i == 0 or j == 0:
return accu
if origines[i, j] == '↖': # Vraie correspondance, on ajoute une lettre !
return utiliseTableOrigines_x(x, origines, i-1, j-1, x[i-1] + accu)
elif origines[i, j] == '↑': # Fausse correspondance, on continue a gauche...
return utiliseTableOrigines_x(x, origines, i-1, j, accu)
elif origines[i, j] == '←': # Fausse correspondance, on continue en haut...
return utiliseTableOrigines_x(x, origines, i, j-1, accu)
else:
raise ValueError("Erreur dans la table 'origines', invalide pour le mot x = {} ...".format(x))
def utiliseTableOrigines_y(x, origines, i, j, accu=''):
""" Renvoie la sous-séquence de y codée dans la table origines. Cf. PDF (Algorithme 2).
- Calcul tail récursif (stocké dans la variable accu).
"""
# print(" utiliseTableOrigines(y = {}, origines, i = {}, j = {}, accu = {}) : origines[i, j] = {} ...".format(y, i, j, accu, origines[i, j])) # DEBUG
if i == 0 or j == 0:
return accu
if origines[i, j] == '↖': # Vraie correspondance, on ajoute une lettre !
return utiliseTableOrigines_y(x, origines, i-1, j-1, y[j-1] + accu)
elif origines[i, j] == '↑': # Fausse correspondance, on continue a gauche...
return utiliseTableOrigines_y(x, origines, i-1, j, accu)
elif origines[i, j] == '←': # Fausse correspondance, on continue en haut...
return utiliseTableOrigines_y(x, origines, i, j-1, accu)
else:
raise ValueError("Erreur dans la table 'origines', invalide pour le mot y = {} ...".format(y))
TODO meilleures explications
In [24]:
def sousMotSeqGlouton(x, y, verb=False, verifie=True):
""" Calcule la plus longue sous-mot séquence a x et y, par programmation dynamique.
- affiche un peu ce qu'il se passe si verb=True,
- vérifie que la sous-séquence commun est bien une bonne sous-séquence commune si verifie=True,
- renvoie laSousSeq, longueurs, origines, indices_x, indices_y si verifie=False,
- renvoie laSousSeq, longueurs, origines, indices_x, indices_y si verifie=True.
"""
def message(*args):
if verb:
print(*args)
# 1. et 2. Initialisation et construction Matrice longueurs
n = len(x)
m = len(y)
message("\n1. Initialisation des look-up matrices longueurs et origines de taille (n+1, m+1) : n = {} m = {} ...".format(n, m))
longueurs = np.zeros((n+1, m+1), dtype=int) # Matrice c du dev en PDF
origines = np.array([[' '] * (m+1)] * (n+1), dtype=str) # Matrice b du dev en PDF
# Note : on pourrait utiliser un codage a base d'entier, 0 1 2 3 pour ' ' '←' '↑' '↖' mais c'est moins joli...
message("2. Construction bottom-up des loop-up matrices longueurs et origines ...")
for i in range(1, n+1):
for j in range(1, m+1):
if x[i-1] == y[j-1]:
longueurs[i, j] = 1 + longueurs[i-1, j-1]
origines[i, j] = '↖'
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]))
elif longueurs[i-1, j] >= longueurs[i, j-1]:
longueurs[i, j] = longueurs[i-1, j]
origines[i, j] = '↑'
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]))
else:
longueurs[i, j] = longueurs[i, j-1]
origines[i, j] = '←'
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]))
# 3. Utilisation de la matrice longueurs
laSousSeq = utiliseTableOrigines_x(x, origines, n, m, accu='')
# 4. Vérification
if verifie:
res_x, indices_x = estSousSeq(laSousSeq, x, indices=True)
if not res_x:
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))
laSousSeq_y = utiliseTableOrigines_y(y, origines, n, m, accu='')
if laSousSeq != laSousSeq_y:
raise ValueError("Erreur: La sous-séquence {} de x est différente de celle de y : {} ...".format(laSousSeq, laSousSeq_y))
res_y, indices_y = estSousSeq(laSousSeq, y, indices=True)
if not res_y:
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))
# Fini !
return laSousSeq, longueurs, origines, indices_x, indices_y
else:
return laSousSeq, longueurs, origines
5.2.1 Exemple, venant du développement¶
Blabla
In [25]:
x = "ABCBDAB"
y = "BDCABA"
laSousSeq, longueurs, origines, indices_x, indices_y = sousMotSeqGlouton(x, y, verifie=True)
print("Sous-seq de taille", len(laSousSeq), "valant", laSousSeq, "...")
print(" - aux indices", indices_x, "pour x =", x, "...")
print(" - aux indices", indices_y, "pour y =", y, "...")
print("Et la table longueurs vaut :\n", longueurs, "...")
print("Et la table origines vaut :\n", origines, "...")
Sous-seq de taille 4 valant BCBA ... - aux indices [1, 2, 3, 5] pour x = ABCBDAB ... - aux indices [0, 2, 4, 5] pour y = BDCABA ... Et la table longueurs vaut : [[0 0 0 0 0 0 0] [0 0 0 0 1 1 1] [0 1 1 1 1 2 2] [0 1 1 2 2 2 2] [0 1 1 2 2 3 3] [0 1 2 2 2 3 3] [0 1 2 2 3 3 4] [0 1 2 2 3 4 4]] ... Et la table origines vaut : [[' ' ' ' ' ' ' ' ' ' ' ' ' '] [' ' '↑' '↑' '↑' '↖' '←' '↖'] [' ' '↖' '←' '←' '↑' '↖' '←'] [' ' '↑' '↑' '↖' '←' '↑' '↑'] [' ' '↖' '↑' '↑' '↑' '↖' '←'] [' ' '↑' '↖' '↑' '↑' '↑' '↑'] [' ' '↑' '↑' '↑' '↖' '↑' '↖'] [' ' '↖' '↑' '↑' '↑' '↖' '↑']] ...
5.2.2 Autres exemples¶
TODO
C'est tout pour aujourd'hui les amis ! Allez voir d'autres notebooks si vous voulez.