#! /usr/bin/env python3
# -*- coding: utf-8; mode: python -*-
""" Correction du DS de vendredi 18 mars 2016.
Voici ci-dessous la documentation de la correction complète du sujet d'écrit d'informatique (Polytechnique, **2012**), pour PSI et PT.
Ce sujet d'écrit a été posé en devoir écrit surveillé (DS) pour le cours d'informatique pour tous en prépa MP au Lycée Lakanal.
Veuillez `consulter le code source pour tous les détails <_modules/DS3_info.html>`_ svp.
Ci dessous se trouve simplement la *documentation* de ce programme.
- *Date :* Jeudi 17 mars 2016,
- *Auteur :* Lilian Besson, pour le cours d'informatique pour tous en prépa MP (http://perso.crans.org/besson/infoMP/),
- *Licence :* MIT Licence (http://lbesson.mit-license.org).
.. note::
Cette correction contient beaucoup de documentation, des exemples et des détails.
TODO: Pour une correction beaucoup plus concise, voir `cette page <_modules/DS3_info__minimal_solution>`_.
-------
Dans tout le problème, nous supposerons que le texte est donné dans un tableau d'entiers ``tab`` de taille :math:`n`.
Chaque case du tableau contient un entier représentant une lettre.
Nous supposerons que tous ces entiers ont des valeurs comprises entre 0 et 25 (``'a' = 0``, ... , ``'z' = 25``).
Par exemple, le texte « quelbonbonbon » (quel bon bonbon) est représenté par le tableau suivant :
>>> texte = "quelbonbonbon"
>>> tab = [16, 20, 4, 11, 1, 14, 13, 1, 14, 13, 1, 14, 13]
Le sujet introduisait ensuite les notations classiques d'accès à un élément du tableau (``tab[i]``) et d'un sous-tableau (``tab[a..b] = tab[a:b+1]``, attention ``tab[a...b]`` n'est **PAS** une notation Python, mais ``tab[a:b+1]`` oui).
"""
from __future__ import print_function # Python 2 compatibility
# %% Partie 0 : Fonctions supposées données
print("\n\nPartie 0 : Fonctions supposees donnees.")
[docs]def texte_vers_tab(texte):
r""" Fonction convertissant une chaîne de caractère ``texte`` (une string) en un tableau d'entiers. On peut écrire une fonction transformant un texte en tableau d'entier, pour vérifier :
>>> texte = "quelbonbonbon"
>>> texte_vers_tab = lambda texte: [ord(lettre.lower()) - ord('a') for lettre in texte]
>>> print(texte)
quelbonbonbon
>>> print(texte_vers_tab(texte))
[16, 20, 4, 11, 1, 14, 13, 1, 14, 13, 1, 14, 13]
"""
return [ord(lettre.lower()) - ord('a') for lettre in texte]
[docs]def entier_vers_charactere(i):
""" Transforme un entier i entre 0 et 25 en la lettre entre 'a' et 'z' correspondate.
- Exemples :
>>> print(entier_vers_charactere(0))
a
>>> print(entier_vers_charactere(10))
k
"""
return chr(i + ord('a'))
[docs]def tab_vers_texte(tab):
r""" Fonction convertissant un tableau d'entiers ``tab`` en une chaîne de caractère ``texte`` (une string).
>>> tab = [16, 20, 4, 11, 1, 14, 13, 1, 14, 13, 1, 14, 13]
>>> texte = tab_vers_texte(tab)
>>> print(texte)
quelbonbonbon
"""
return "".join(entier_vers_charactere(i) for i in tab)
[docs]def egaliteTableaux(tab1, tab2):
r""" Teste l'égalité des deux tableaux ``tab1`` et ``tab2``, cases par cases.
- ``tab1 == tab2`` marche aussi, mais on préfèrait ré-implémenter ces fonctions d'égalité et d'ordre lexicographique.
- Complexité : en :math:`\mathcal{O}(n)` si ``n1 = n2``, ou :math:`\mathcal{O}(1)` sinon; où ``n1 = len(tab1)`` et ``n2 = len(tab2)``.
"""
n1, n2 = len(tab1), len(tab2)
if n1 != n2:
return False
else:
for i in range(n1):
if tab1[i] != tab2[i]:
return False
return True
# return tab1 == tab2
[docs]def ordreLexicographiqueTableaux(tab1, tab2):
r""" Ordre lexicographique des deux tableaux ``tab1`` et ``tab2`` :
- 0 si ``tab1`` = ``tab2`` sont égaux,
- +1 si ``tab1`` est plus petit que ``tab2``,
- -1 si ``tab1`` est plus grand que ``tab2``,
- On peut utiliser ``tab1 < tab2``, ``tab1 == tab2`` ou ``tab1 > tab2``, mais on préfèrait ré-implémenter ces fonctions d'égalité et d'ordre lexicographique.
- Complexité : en :math:`\mathcal{O}(n)` si ``n1 = n2``, ou :math:`\mathcal{O}(1)` sinon; où ``n1 = len(tab1)`` et ``n2 = len(tab2)``.
- Cette fonction n'utilise que des comparaisons termes à termes, ``tab1[i] < tab2[i]`` ou ``tab1[i] > tab2[i]``, donc elle marche pour des tableaux d'entiers comme pour des tableaux de n'importe quoi (et en fait, elle marche pour des str aussi).
- Exemples :
>>> tab1 = [1, 2, 3, 4, 5]
>>> print(ordreLexicographiqueTableaux(tab1, tab1)) # tab1 == tab1
0
>>> tab2 = [1, 2, 3, 5, 6]
>>> print(tab1 < tab2)
True
>>> print(ordreLexicographiqueTableaux(tab1, tab2)) # tab1 < tab2
-1
>>> print(tab2 < tab1)
False
>>> print(ordreLexicographiqueTableaux(tab2, tab1)) # tab2 > tab1
1
>>> tab3 = [-2, 3, 5, 6]
>>> print(tab1 < tab3)
False
>>> print(ordreLexicographiqueTableaux(tab1, tab3)) # tab1 > tab3
1
>>> print(tab2 < tab3)
False
>>> print(ordreLexicographiqueTableaux(tab2, tab3)) # tab2 > tab3
1
>>> tab4 = [1, 2, 3]
>>> print(tab4 < tab1)
True
>>> print(ordreLexicographiqueTableaux(tab1, tab4)) # tab1 > tab4
1
"""
if egaliteTableaux(tab1, tab2):
return 0
n1 = len(tab1)
n2 = len(tab2)
n = min(n1, n2)
r = 0
i = 0
# On continue tant que tab1[:i] == tab2[:i]
while (r == 0) and (i < n):
x1, x2 = tab1[i], tab2[i]
# Et à la première différence, soit < soit >, on a fini
if x1 < x2:
r = -1
elif x1 > x2:
r = +1
# Toujours pas de différence, on continue
i += 1
if r == 0: # Si les deux tableaux sont égaux sur les valeurs comparées
if n1 < n2: # Si tab1 est de taille < tab2, c'est un préfixe de tab2
r = -1
elif n1 > n2: # Inversement, si tab2 est un préfixe de tab1
r = +1
return r
# %% Partie 1 : Méthode directe
print("\n\nPartie 1 : Methode directe.")
[docs]def enTeteDeSuffixe(mot, tab, k):
r""" Renvoie True si le mot ``mot`` apparaît en tête du suffixe numéro ``k`` du texte ``tab``, et False sinon.
- On pourra supposer que ``k`` est un indice valide du tableau ``tab``.
- Complexité en temps : :math:`\mathcal{O}(m)` (``m = len(mot)``).
- Exemples :
>>> tab = texte_vers_tab("bonjaimelesbonbons")
>>> mot = texte_vers_tab("bon")
>>> print(enTeteDeSuffixe(mot, tab, 0))
True
>>> print(enTeteDeSuffixe(mot, tab, 1))
False
>>> print(enTeteDeSuffixe(mot, tab, 11))
True
"""
n = len(tab)
m = len(mot)
if m+k > n: # k + m <= n is required for tab[k:k+m] to work
return False
else:
# print("enTeteDeSuffixe(mot, tab, k) avec mot = {}, k = {}, tab[k:k+m] = {}".format(mot, k, tab[k:k+m]))
return egaliteTableaux(mot, tab[k:k+m])
# return mot == tab[k:k+m]
[docs]def rechercherMot(mot, tab):
r""" Renvoie True si le mot mot apparaît dans le texte tab, et False sinon.
- Implémentation très naîve, utilise :py:func:`enTeteDeSuffixe` pour chaque ``k = 0 .. n - m``.
- Complexité en temps : :math:`\mathcal{O}(n \times m)` (``m = len(mot)``, ``n = len(texte)``), dans le pire des cas, et :math:`\mathcal{O}(m)` dans le meilleur des cas (si le ``mot`` est en début du tableau ``tab``).
- Exemples :
>>> tab = texte_vers_tab("bonjaimelesbonbons")
>>> mot1 = texte_vers_tab("bon")
>>> print(rechercherMot(mot1, tab))
True
>>> mot2 = texte_vers_tab("jenaimepas")
>>> print(rechercherMot(mot2, tab))
False
>>> mot3 = texte_vers_tab("superman")
>>> print(rechercherMot(mot3, tab))
False
>>> mot4 = texte_vers_tab("bonbons")
>>> print(rechercherMot(mot4, tab))
True
"""
n = len(tab)
m = len(mot)
for k in range(n - m + 1): # k <= n - m ==> k + m <= n OK
if enTeteDeSuffixe(mot, tab, k):
return True
return False
[docs]def compterOccurrences(mot, tab):
r""" Renvoie le nombre d'occurrences de ``mot`` dans le texte ``tab``.
- La fonction est très simple à écrire, il suffit d'adapter le code de la fonction :py:func:`rechercherMot` précédente, et au lieu de quitter en renvoyant True dès qu'on trouve, on incrémente un compter ``nombre_occurrences``, qu'on renvoie à la fine.
- Complexité en temps : :math:`\mathcal{O}(n \times m)` (``m = len(mot)``, ``n = len(texte)``), dans tous les cas.
- Nous considérons le nombre d'occurrences avec recouvrement autorisé, qui est la notion la plus simple : on compte le nombre de répétitions du mot dans le texte, sans contrainte aucune.
- Par exemple, dans le texte « quelbonbonbon » (quel bon bonbon) le nombre d'occurrences de bonbon est 2, même si ces occurrences se recouvrent :
.. image:: DS3_info__figure_1.png
:width: 70%
- Exemples :
>>> tab = texte_vers_tab("quelbonbonbon")
>>> mot1 = texte_vers_tab("bonbon")
>>> print(compterOccurrences(mot1, tab))
2
>>> mot2 = texte_vers_tab("on")
>>> print(compterOccurrences(mot2, tab))
3
>>> mot3 = texte_vers_tab("quel")
>>> print(compterOccurrences(mot3, tab))
1
"""
nombre_occurrences = 0
n = len(tab)
m = len(mot)
for k in range(n - m + 1): # k <= n - m ==> k + m <= n OK
if enTeteDeSuffixe(mot, tab, k):
nombre_occurrences += 1
return nombre_occurrences
[docs]def frequenceLettre(tab):
r""" Calcule et renvoie un tableau de taille 26 dont la case ``i`` contient la fréquence de la lettre ``i`` dans le texte.
- C'est une *fonction qu'on a déjà vu*, deux fois : effectifs dans le TP2 et dans le TD/DS 4.
- Complexité en temps : :math:`\mathcal{O}(n)` (``n = len(texte)``), dans tous les cas (et la constante est petite).
- Exemples :
>>> tab1 = texte_vers_tab("quelbonbonbon")
>>> print(frequenceLettre(tab1))
[0, 3, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 3, 3, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0]
>>> tab2 = texte_vers_tab("superman")
>>> print(frequenceLettre(tab2))
[1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0]
>>> tab3 = texte_vers_tab("lilianbesson")
>>> print(frequenceLettre(tab3))
[1, 1, 0, 0, 1, 0, 0, 0, 2, 0, 0, 2, 0, 2, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0]
"""
histogramme_lettres = [0] * 26
for lettre in tab:
histogramme_lettres[lettre] += 1
return histogramme_lettres
[docs]def afficherFrequenceBigramme(tab):
r""" Affiche les mots de 2 lettres présents dans le texte ainsi que leur fréquence (un même mot ne devra être affiché qu'une seule fois).
- Complexité en temps : :math:`\mathcal{O}(n)` (``n = len(texte)``), dans tous les cas (et la constante est petite).
- Complexité en mémoire : :math:`\simeq 26^2`, dans tous les cas : on créé et utilise un tableau de tous les bigrammes (et il y en a :math:`26^2`).
- Nous allons maintenant calculer l'ensemble des mots d'une taille donnée qui apparaissent dans le texte ainsi que leur fréquence. Pour le moment, nous n'abordons que les tailles 1 et 2.
- Dans l'exemple précédent, pour la taille 1, on obtient les mots ``b(3)``, ``e(1)``, ``l(1)``, ``n(3)``, ``o(3)``, ``q(1)``, ``u(1)``, pour la taille 2, on obtient ``bo(3)``, ``el(1)``, ``lb(1)``, ``nb(2)``, ``on(3)``, ``qu(1)``, ``ue(1)``.
- Exemples :
>>> tab1 = texte_vers_tab("quelbonbonbon")
>>> afficherFrequenceBigramme(tab1)
lb(1), nb(2), ue(1), el(1), on(3), bo(3), qu(1)
>>> tab2 = texte_vers_tab("iamsuperman")
>>> afficherFrequenceBigramme(tab2)
ia(1), ma(1), pe(1), am(1), rm(1), an(1), up(1), er(1), ms(1), su(1)
>>> tab3 = texte_vers_tab("lilian")
>>> afficherFrequenceBigramme(tab3)
ia(1), li(2), il(1), an(1)
"""
K = 26
n = len(tab)
# 1. On créé un gros tableau plein de 0
# bigrammes = {(i, j): 0 for i in range(26) for j in range(26)} # FIXED inutile d'utiliser un dictionnaire
bigrammes = [0] * (K**2)
# 2. On parcourt le tableau tab une et une seule fois
for k in range(n-1):
# 2.a. On regarde le bigramme tab[k..k+1] = tab[k],tab[k+1] = (i,j)
i = tab[k]
j = tab[k+1]
# 2.b. On le compte en plus
# bigrammes[(i,j)] += 1 # FIXED inutile d'utiliser un dictionnaire
bigrammes[i + K*j] += 1
# 3. On affiche les bigrammes présents avec leur fréquence
chaine = ""
for gros_indice, freq in enumerate(bigrammes):
if freq > 0:
# 3.a. On extrait les indices i,j depuis le gros_indice
i = gros_indice % K
j = gros_indice // K
bigramme = "%s%s" % (entier_vers_charactere(i), entier_vers_charactere(j))
# chaine += "{}({}) ".format(bigramme, freq)
chaine += "%s(%i), " % (bigramme, freq)
print(chaine[:-2] if len(chaine) > 0 else "")
# %% Partie 2 : Tableau des suffixes
print("\n\nPartie 2 : Tableau des suffixes.")
[docs]def comparerSuffixes(tab, k1, k2):
r""" Compare les deux suffixents ``tab[k1:]`` et ``tab[k2:]`` par l'ordre lexicographique.
- Prend en arguments deux suffixes du texte tab, représentés par leurs numéros, et renvoie un entier ``r``.
- L'entier ``r`` traduit la comparaison lexicographique des suffixes 2 de numéros ``k1`` et ``k2`` : r est strictement négatif quand le suffixe ``k1`` précède strictement le suffixe ``k2`` , nul quand ils sont égaux, et strictement positif quand le suffixe ``k1`` suit strictement le suffixe ``k2`` .
.. note::
- C'est une convention usuelle, par exemple la fonction de tri :py:func:`sorted` accepte un argument optionnel ``cmp`` qui est exactement une fonction :math:`\mathrm{cmp}: x, y \mapsto 0` si :math:`x = y`, :math:`> 0` si :math:`x > y`, et :math:`< 0` si :math:`x < y`.
- Une telle fonction ``cmp`` est appelée **fonction de comparaison**, et avec les bonnes propriétés elle définit un ordre (total, partiel ou autre selon ses propriétés).
- Et cette convention est aussi employée dans d'autres langages, par exemple en OCaml : `Pervasives.compare <http://caml.inria.fr/pub/docs/manual-ocaml/libref/Pervasives.html#VALcompare>`_ est une telle fonction de comparaison (utilisable avec `List.sort <http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html#VALsort>`_).
- Exemples :
>>> tab = texte_vers_tab("quelbonbonbon")
>>> k1 = 10; k2 = 12
>>> print(comparerSuffixes(tab, k1, k2)) # tab[k1:] < tab[k2:]
-1
>>> print(comparerSuffixes(tab, k1, k1)) # tab[k1:] == tab[k1:]
0
>>> print(comparerSuffixes(tab, k2, k1)) # tab[k2:] < tab[k1:]
1
- Complexité en temps : :math:`\mathcal{O}(n)` dans le pire des cas, où ``n = len(tab)`` (si :math:`k_1 \simeq k_2` sont petits, et que le tableau est constant avec toute ses cases identiques, il faut comparer toutes les cases, soit au plus ``n - 1``).
"""
if k1 == k2: # Petite optimisation
return 0
s1, s2 = tab[k1:], tab[k2:]
# On utilise la fonction ré-implémentée
r = ordreLexicographiqueTableaux(s1, s2)
# Mais on aurait pu utiliser les < et > de Python à la place :
# if s1 == s2:
# r = 0
# elif s1 < s2:
# r = -1
# else:
# r = +1
return r
[docs]def suffixeMin(tab, suf):
r""" Prend en arguments le texte ``tab`` ainsi qu'un tableau ``suf`` *non vide* contenant des numéros de suffixes de ``tab``, et renvoie le numéro du suffixe contenu dans ``suf`` qui est minimal pour l'ordre lexicographique.
- Dans l'exemple de la figure 1, ``suffixeMin(tab, [1, 2, 4, 9, 8])`` doit renvoyer ``4``.
- Exemple :
>>> tab = texte_vers_tab("quelbonbonbon")
>>> suf = [1, 2, 4, 9, 8]
>>> print(suffixeMin(tab, suf)) # 4 : tab[4:] = "bonbonbon"
4
>>> suf2 = [1, 2, 9, 8]
>>> print(suffixeMin(tab, suf2)) # 2 : tab[2:] = "elbonbonbon"
2
>>> suf3 = [1, 9, 8]
>>> print(suffixeMin(tab, suf3)) # 9 : tab[9:] = "nbon"
9
- Complexité en temps : :math:`\mathcal{O}(s n)`, où ``s = len(suf)`` et ``n = len(tab)``.
"""
N = len(suf)
if N == 0:
return -1
kmin = suf[0]
for i in range(1, N):
k = suf[i]
r = comparerSuffixes(tab, kmin, k)
# print("i = {}, k = {}, r = {}, kmin = {}".format(i, k, r, kmin))
if r == 0:
print("suffixeMin(tab, suf): r = 0 should not happen !")
kmin = min(kmin, k) # Min des indices ?
elif r > 0: # suffixe tab[kmin:] > tab[k:]
kmin = k # kmin <- k
return kmin
[docs]def calculerSuffixes(tab):
r""" Calcule le table des suffixes ``tabS`` du texte ``tab``.
- Comme le disait l'énoncé, il s'agit essentiellement d'un tri du tableau d'entiers ``[0, 1, ..., n - 1]``, selon l'ordre défini à la question 6 :py:func:`comparerSuffixes`.
- Complexité en mémoire : :math:`\mathcal{O}(n)` (il faut créer et stocker la liste ``list(range(n))``).
- Complexité en temps : :math:`\mathcal{O}(n \log(n))` comparaisons pour trier, et chaque comparaisons est un appel à :py:func:`comparerSuffixes`, coûtant au plus :math:`\mathcal{O}(n)`, donc dans le pire des cas :py:func:`calculerSuffixes` sera en :math:`\mathcal{O}(n^2 \log(n))`.
.. image:: DS3_info__figure_2.png
:width: 80%
- Exemple (reproduisant la figure 1) :
>>> tab = texte_vers_tab("quelbonbonbon")
>>> n = len(tab)
>>> # Suffixes classés selon leur numéros :
>>> for i in range(n): print("{:>3} : {}".format(i, tab_vers_texte(tab[i:])))
0 : quelbonbonbon
1 : uelbonbonbon
2 : elbonbonbon
3 : lbonbonbon
4 : bonbonbon
5 : onbonbon
6 : nbonbon
7 : bonbon
8 : onbon
9 : nbon
10 : bon
11 : on
12 : n
- Et ensuite avec les suffixes triés :
>>> tabS = calculerSuffixes(tab)
>>> print(tabS)
[10, 7, 4, 2, 3, 12, 9, 6, 11, 8, 5, 0, 1]
>>> # Suffixes classés par ordre lexicographique :
>>> for i in range(n): print("{:>3} : {:>2} : {}".format(i, tabS[i], tab_vers_texte(tab[tabS[i]:])))
0 : 10 : bon
1 : 7 : bonbon
2 : 4 : bonbonbon
3 : 2 : elbonbonbon
4 : 3 : lbonbonbon
5 : 12 : n
6 : 9 : nbon
7 : 6 : nbonbon
8 : 11 : on
9 : 8 : onbon
10 : 5 : onbonbon
11 : 0 : quelbonbonbon
12 : 1 : uelbonbonbon
"""
n = len(tab)
liste = list(range(n))
def key(k):
""" Fonction ``key`` à appliquer aux éléments de la liste ``liste`` avant de les trier.
"""
return tab[k:]
# def cmp(k1, k2):
# """ Fonction de comparaison des entiers k1 et k2, utilisée avec :py:func:`sorted(liste, cmp=cmp)` pour trier. """
# return comparerSuffixes(tab, k1, k2)
return sorted(liste, key=key)
# return sorted(liste, cmp=cmp)
[docs]def q9():
r""" Réponse mathématique à la question 9. :
- J'ai un peu triché en utilisant la fonction de la librairie standard Python :py:func:`sorted`; mais si on code nous-même le tri (ce qui était demandé), on aura sûrement un tri naïf (soit `par insertion <https://fr.wikipedia.org/wiki/Tri_par_insertion>`_, soit `à bulle <https://fr.wikipedia.org/wiki/Tri_à_bulles>`_), et donc :math:`\mathcal{O}(n^2)` comparaisons de suffixes.
- Donc cette implémentation naïve serait en :math:`\mathcal{O}(n^3)`.
- En utilisant un algorithme de tri performant, comme le `tri fusion <https://fr.wikipedia.org/wiki/Tri_fusion>`_, le `tri rapide <https://fr.wikipedia.org/wiki/Tri_rapide>`_ (aux programme, ou le `tri par tas <https://fr.wikipedia.org/wiki/Tri_par_tas>`_, pas au programme), on aurait :math:`\mathcal{O}(n \log(n))` comparaisons, et donc une complexité finale en :math:`\mathcal{O}(n^2 \log(n))` dans le pire des cas.
.. seealso:: `Solution du TP8 <../../TPs/solutions/TP8.html>`_ sur les algorithmes de tris.
"""
pass
# %% Partie 3 : Exploitation du tableau des suffixes
print("\n\nPartie 3 : Exploitation du tableau des suffixes.")
[docs]def comparerMotSuffixe(mot, tab, k):
r""" Prend en arguments un mot ``mot`` et un suffixe ``k`` du texte ``tab``, et qui renvoie un entier ``r``.
- L'entier ``r`` traduit une légère adaptation de la comparaison lexicographique entre le mot ``mot`` et le suffixe ``k``. À savoir, ``r`` est nul si et seulement si le mot ``mot`` apparaît en tête du suffixe ``k``. Autrement, ``r`` est strictement négatif (resp. positif) quand le mot précède (resp. suit) strictement le suffixe selon l'ordre lexicographique.
- Complexité en temps : :math:`\mathcal{O}(\min(n, m))` dans le pire des cas, où ``n = len(tab)`` et ``m = len(mot)``.
>>> tab = texte_vers_tab("quelbonbonbon")
>>> mot = texte_vers_tab("lbo")
>>> print(comparerMotSuffixe(mot, tab, 0)) # "quelbonbonbon" > "lbo"
-1
>>> print(comparerMotSuffixe(mot, tab, 2)) # "elbonbonbon" < "lbo"
1
>>> # = 0 même si mot != tab[3:], mot n'est qu'un préfixe de tab[3:]
>>> print(comparerMotSuffixe(mot, tab, 3))
0
"""
if enTeteDeSuffixe(mot, tab, k):
r = 0
else:
r = ordreLexicographiqueTableaux(mot, tab[k:])
# elif mot < tab[k:]:
# r = -1
# else:
# r = 1
return r
[docs]def rechercherMot2Rec(mot, tab, tabS, i, j):
r""" Fonction récursive qui cherche le mot ``mot`` dans le sous-tableau des suffixes ``tabS[i...j] = tabS[i:j+1]``.
- Exactement la même astuce qu'une recherche dichotomique, l'utilisation de ces deux arguments ``i, j`` évite de devoir faire des recopies de sous-tableaux ``tab[i:j+1]`` tout le temps.
- Complexité en temps : :math:`\mathcal{O}(\log (j - i + 1))` dans le pire des cas (par récurrence).
"""
if i > j: # Tableau vide
return False
milieu = (i + j) // 2
pivot = tabS[milieu]
r = comparerMotSuffixe(mot, tab, pivot)
if r == 0: # On a trouvé le mot !
return True
elif r < 0:
return rechercherMot2Rec(mot, tab, tabS, i, milieu-1)
elif r > 0:
return rechercherMot2Rec(mot, tab, tabS, milieu+1, j)
else:
raise ValueError("rechercherMot2Rec(...): Erreur, ce cas ne devrait jamaisa arriver, r = 0, r < 0 ou r > 0 seulement.")
[docs]def rechercherMot2(mot, tab, tabS):
r""" Renvoie True si le mot ``mot`` apparaît dans le texte ``tab``, et False sinon.
- On impose évidemment l'emploi de la technique de recherche dichotomique dans le tableau des suffixes ``tabS``, que l'on suppose correct.
- Complexité en temps : :math:`\mathcal{O}(\log n)` dans le pire des cas, où ``n = len(tab)`` (par recherche dichotomique).
- En utilisant la fonction précédente, :py:func:`rechercherMot2Rec`, il suffit de l'appeler avec ``i = 0`` et ``j = n = len(tab)``.
- Exemples :
>>> tab = texte_vers_tab("quelbonbonbon")
>>> tabS = calculerSuffixes(tab)
>>> mot1 = texte_vers_tab("lbo")
>>> print(rechercherMot2(mot1, tab, tabS))
True
>>> mot2 = texte_vers_tab("lilian")
>>> print(rechercherMot2(mot2, tab, tabS))
False
>>> mot3 = texte_vers_tab("bonbonbon")
>>> print(rechercherMot2(mot3, tab, tabS))
True
"""
n = len(tab)
return rechercherMot2Rec(mot, tab, tabS, 0, n)
[docs]def q12():
r""" Réponse mathématique à la question 12.
- :py:func:`rechercherMot` (question 2) fait de l'ordre de :math:`\mathcal{O}(n)` comparaisons de mots;
- :py:func:`rechercherMot2` (question 11) par contre fait de l'ordre de :math:`\mathcal{O}(\log n)` comparaisons de mots.
"""
pass
[docs]def rechercherPremierSuffixeRec(mot, tab, tabS, i, j):
r""" Fonction récursive qui cherche le mot ``mot`` dans le sous-tableau des suffixes ``tabS[i...j] = tabS[i:j+1]``.
- Si ``mot`` est trouvé, cette fois on renvoie l'indice ``i`` tel que ``mot`` apparaisse en tête du suffixe ``tabS[i]``, et plus seulement True ou False.
- Exactement la même astuce qu'une recherche dichotomique, l'utilisation de ces deux arguments ``i, j`` évite de devoir faire des recopies de sous-tableaux ``tab[i:j+1]`` tout le temps.
- Complexité en temps : :math:`\mathcal{O}(\log (j - i + 1))` dans le pire des cas (par récurrence).
"""
if i > j:
return -1 # Ici on renvoie -1, et pas False
milieu = (i + j) // 2
pivot = tabS[milieu]
r = comparerMotSuffixe(mot, tab, pivot)
if r == 0: # On a trouvé le mot !
return milieu # Ici on renvoie la position du milieu, et pas True
elif r < 0: # On cherche à gauche
return rechercherPremierSuffixeRec(mot, tab, tabS, i, milieu-1)
elif r > 0: # On cherche à droite
return rechercherPremierSuffixeRec(mot, tab, tabS, milieu+1, j)
else:
raise ValueError("rechercherPremierSuffixeRec(...): Erreur, ce cas ne devrait jamaisa arriver, r = 0, r < 0 ou r > 0 seulement.")
# FIXME Devrait être dichotomique !
[docs]def rechercherPremierSuffixe(mot, tab, tabS):
r""" Renvoie le plus petit indice ``i`` de ``tabS`` tel que ``mot`` apparaît en tête du suffixe numéro ``tabS[i]`` du texte ``tab``.
- Si ``mot`` n'apparaît pas dans le texte ``tab``, on renvoie ``-1`` (convention).
- On impose évidemment une adaptation de la technique de recherche dichotomique dans le tableau des suffixes ``tabS`` : il faut une *implémentation efficace* !
- À titre d'exemple, dans le cas où mot est ``"bonbon"``, et avec le tableau des suffixes de la figure 1, :py:func:`rechercherPremierSuffixe` renvoie ``1``.
- Exemples :
>>> tab = texte_vers_tab("quelbonbonbon")
>>> tabS = calculerSuffixes(tab)
>>> mot1 = texte_vers_tab("bonbon")
>>> print(rechercherPremierSuffixe(mot1, tab, tabS))
1
>>> mot2 = texte_vers_tab("lilian")
>>> print(rechercherPremierSuffixe(mot2, tab, tabS))
-1
>>> mot3 = texte_vers_tab("bonbonbon")
>>> print(rechercherPremierSuffixe(mot3, tab, tabS))
2
"""
# print("rechercherPremierSuffixe(mot, tab, tabS) avec mot = {}, tab = {}, tabS = {}.".format(tab_vers_texte(mot), tab_vers_texte(tab), tabS))
suf = [i for i in range(len(tab)) if comparerMotSuffixe(mot, tab, tabS[i]) == 0]
# for j in suf:
# print("j = {}, tabS[j] = {}, suffixe = {}".format(j, tabS[j], tab_vers_texte(tab[tabS[j]:])))
# print("suf =", suf)
# return suffixeMin(tab, suf)
if len(suf) > 0:
return min(suf)
else:
return -1
# if not rechercherMot2(mot, tab, tabS):
# return -1
# else:
# return rechercherPremierSuffixeRec(mot, tab, tabS, 0, len(tab)-1)
# FIXME Devrait être dichotomique !
[docs]def rechercherDernierSuffixe(mot, tab, tabS):
r""" Fonction analogue à la précédente, à ceci près qu'ici on renvoie **le plus grand** indice ``i`` tel que ``mot`` apparaît en tête du suffixe numéro ``tabS[i]`` du texte ``tab``.
- Exemples :
>>> tab = texte_vers_tab("quelbonbonbon")
>>> tabS = calculerSuffixes(tab)
>>> mot1 = texte_vers_tab("bon")
>>> print(rechercherDernierSuffixe(mot1, tab, tabS))
2
>>> mot2 = texte_vers_tab("nb")
>>> print(rechercherDernierSuffixe(mot2, tab, tabS))
7
"""
suf = [i for i in range(len(tab)) if comparerMotSuffixe(mot, tab, tabS[i]) == 0]
if len(suf) > 0:
return max(suf)
else:
return -1
[docs]def compterOccurrences2(mot, tab):
r""" Renvoie le nombre d'occurrences du mot ``mot`` dans le texte ``tab``, implémentée de façon plus efficace que :py:func:`compterOccurrences`.
- L'algorithme qu'il fallait trouver est le suivant :
1. On calcule le tableau des suffixes de ``tab`` (via :py:func:`calculerSuffixes`),
2. On cherche le mot, s'il n'est pas là, on renvoie -1 directement,
3. Sinon, on calcule les deux indices ``kmin`` et ``kmax`` du premier et du dernier suffixes (via :py:func:`rechercherPremierSuffixe` et :py:func:`rechercherDernierSuffixe`),
4. Et on renvoie ``kmax - kmin + 1``.
- C'est très visuel, cf. la figure 1.
.. image:: DS3_info__figure_2.png
:width: 80%
- Renvoie -1 si le mot n'est pas présent.
- Complexité en temps : :math:`\mathcal{O}(n^2 \log(n))` pour calculer ``tabS``, et ensuite :math:`\mathcal{O}` pour rechercher les deux indices ``kmin`` et ``kmax``.
.. attention:: J'ai du mal à voir en quoi c'est plus efficace que l'implémentation naïve en :math:`\mathcal{O}(n \times m)`...
- Exemple :
>>> tab = texte_vers_tab("quelbonbonbon")
>>> mot1 = texte_vers_tab("bonbon")
>>> print(compterOccurrences2(mot1, tab))
2
>>> mot2 = texte_vers_tab("on")
>>> print(compterOccurrences2(mot2, tab))
3
>>> mot3 = texte_vers_tab("quel")
>>> print(compterOccurrences2(mot3, tab))
1
"""
tabS = calculerSuffixes(tab)
if not rechercherMot2(mot, tab, tabS):
return -1
else:
kmax = rechercherDernierSuffixe(mot, tab, tabS)
kmin = rechercherPremierSuffixe(mot, tab, tabS)
return kmax - kmin + 1
[docs]def afficherFrequenceKgramme(tab, tabS, k):
r""" Affiche les mots de ``k`` lettres présents dans le texte ainsi que leur fréquence.
- Le sujet demandait que "le candidat proposera une réalisation efficace qui exploite le tableau des suffixes". Cette question, la dernière du DS, était plus difficile que le reste, et demandait une certaine créativité.
- Dans l'exemple précédent, pour la taille 1, on obtient les mots ``b(3)``, ``e(1)``, ``l(1)``, ``n(3)``, ``o(3)``, ``q(1)``, ``u(1)``, pour la taille 2, on obtient ``bo(3)``, ``el(1)``, ``lb(1)``, ``nb(2)``, ``on(3)``, ``qu(1)``, ``ue(1)``.
- Exemple :
>>> tab = texte_vers_tab("quelbonbonbon")
>>> tabS = calculerSuffixes(tab)
>>> k = 1
>>> afficherFrequenceKgramme(tab, tabS, k)
b(3), e(1), l(1), n(3), o(3), q(1), u(1)
>>> k = 2
>>> afficherFrequenceKgramme(tab, tabS, k)
bo(3), el(1), lb(1), nb(2), on(3), qu(1), ue(1)
>>> k = 3
>>> afficherFrequenceKgramme(tab, tabS, k)
bon(3), elb(1), lbo(1), nbo(2), onb(2), que(1), uel(1)
>>> k = 4
>>> afficherFrequenceKgramme(tab, tabS, k)
bonb(2), elbo(1), lbon(1), nbon(2), onbo(2), quel(1), uelb(1)
>>> k = 5
>>> afficherFrequenceKgramme(tab, tabS, k)
bonbo(2), elbon(1), lbonb(1), nbonb(1), onbon(2), quelb(1), uelbo(1)
- L'algorithme fonctionne de la façon suivante : on lit le tableau des suffixes, en ne gardant que ceux de taille ``>= k``, et en sélectionnant seulement les ``k`` premières lettres :
>>> k = 3
>>> # k-suffixe de tous les suffixes (de taille >= k) classés par ordre lexicographique :
>>> for i in range(len(tab)):
... ksuffixe = tab[tabS[i]:]
... if len(ksuffixe) >= k:
... print("{}".format(tab_vers_texte(ksuffixe[:k])))
bon
bon
bon
elb
lbo
nbo
nbo
onb
onb
que
uel
- On voit alors que ces k-grammes arrivent triés dans l'ordre lexicographique, parce que ``tabS`` est construit ainsi, et que tronquer aux ``k`` premières lettres conserve l'ordre (par définition de l'ordre lexicographique).
- Donc il suffit d'avancer dans le tableau des suffixes (une et une seule fois), et de garder en mémoire le k-gramme actuellement lu (``sAAfficher`` dans mon code), de compter le nombre de fois qu'on le voit, et dès qu'on change de k-gramme, on affiche le k-gramme précédent (``sAAfficher``) et sa fréquence, puis on réinitialise ``sAAfficher`` comme le nouveau k-gramme détecté, et sa fréquence à 1.
- Il faut faire attention à aussi afficher le dernier k-gramme, en dehors de la boucle de parcours (``for j in tabS``).
- Complexité en temps : :math:`\mathcal{O}(n)` (si ``tabS`` déjà calculé), ce qui est indépendant de ``k``.
- Complexité en mémoire : :math:`\mathcal{O}(1)` (si ``tabS`` déjà calculé), ce qui est indépendant de ``k`` et ``n`` (ou bien :math:`\mathcal{O}(n)` si on créé la chaîne à afficher, et qu'on ne l'affiche qu'à la fin).
"""
n = len(tab)
chaine = ""
sAAfficher = None
freq = 0
# for j in tabS:
for i in range(n):
j = tabS[i]
if j > n - k:
# Morceau trop petit, on passe au i suivant
continue
s = tab[j:j+k]
if sAAfficher is None: # Premier cas, sAAfficher = None au début
sAAfficher = s
freq = 0 # 0 car +1 après (r = 0)
r = 0 # Pas besoin de les comparer, ils sont égaux ici
else:
# On compare s et sAAfficher
r = ordreLexicographiqueTableaux(s, sAAfficher)
if r > 0:
# On est passé à un autre morceau, on doit afficher le sAAfficher précédent
kgramme = tab_vers_texte(sAAfficher)
chaine += "%s(%i), " % (kgramme, freq)
# Puis réinitialiser les deux
sAAfficher = s
freq = 1 # Vu une fois !
elif r == 0: # On a vu une fois de plus ce motif s
freq += 1
# Le dernier n'a pas été affiché vu notre boucle au dessus
if sAAfficher is not None:
kgramme = tab_vers_texte(sAAfficher)
chaine += "%s(%i), " % (kgramme, freq)
print(chaine[:-2] if len(chaine) > 0 else "")
# %% Fin de la correction.
if __name__ == '__main__':
from doctest import testmod
print("\nTest automatique de toutes les doctests ecrites dans la documentation (docstring) de chaque fonction :")
testmod(verbose=True)
# testmod()
print("\nPlus de details sur ces doctests sont dans la documentation de Python:\nhttps://docs.python.org/3/library/doctest.html (en anglais)")
# Fin de X_PSI-PT_2010.py