DS 5 : X PSI-PT 2010 ¶

5ème DS, rechercher un mot dans un texte et compter ses occurrences.

Le sujet est une ré-écriture du sujet X PSI-PT de 2010. L’accent a été mis sur la partie II pour la rendre plus intéressante.

Le sujet commençait par une petite introduction, motivant le problème algorithmique de recherche d’un mot dans un texte (recherche d’une sous-chaîne) par la quantité toujours croissante d’informatique disponible en ligne.

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 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.

Dans tout le problème, nous supposerons que le texte est donné dans un tableau d’entiers tab de taille \(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).

DS3_info.texte_vers_tab(texte)[source]¶

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]

DS3_info.entier_vers_charactere(i)[source]¶

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

DS3_info.tab_vers_texte(tab)[source]¶

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

DS3_info.egaliteTableaux(tab1, tab2)[source]¶

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 \(\mathcal{O}(n)\) si n1 = n2, ou \(\mathcal{O}(1)\) sinon; où n1 = len(tab1) et n2 = len(tab2).

DS3_info.ordreLexicographiqueTableaux(tab1, tab2)[source]¶

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 \(\mathcal{O}(n)\) si n1 = n2, ou \(\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

DS3_info.enTeteDeSuffixe(mot, tab, k)[source]¶

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 : \(\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

DS3_info.rechercherMot(mot, tab)[source]¶

Renvoie True si le mot mot apparaît dans le texte tab, et False sinon.

Implémentation très naîve, utilise enTeteDeSuffixe() pour chaque k = 0 .. n - m.
Complexité en temps : \(\mathcal{O}(n \times m)\) (m = len(mot), n = len(texte)), dans le pire des cas, et \(\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

DS3_info.compterOccurrences(mot, tab)[source]¶

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 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 : \(\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 :

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

DS3_info.frequenceLettre(tab)[source]¶

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 : \(\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]

DS3_info.afficherFrequenceBigramme(tab)[source]¶

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 : \(\mathcal{O}(n)\) (n = len(texte)), dans tous les cas (et la constante est petite).
Complexité en mémoire : \(\simeq 26^2\), dans tous les cas : on créé et utilise un tableau de tous les bigrammes (et il y en a \(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)

DS3_info.comparerSuffixes(tab, k1, k2)[source]¶

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 sorted() accepte un argument optionnel cmp qui est exactement une fonction \(\mathrm{cmp}: x, y \mapsto 0\) si \(x = y\), \(> 0\) si \(x > y\), et \(< 0\) si \(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 est une telle fonction de comparaison (utilisable avec List.sort).

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 : \(\mathcal{O}(n)\) dans le pire des cas, où n = len(tab) (si \(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).

DS3_info.suffixeMin(tab, suf)[source]¶

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 : \(\mathcal{O}(s n)\), où s = len(suf) et n = len(tab).

DS3_info.calculerSuffixes(tab)[source]¶

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 comparerSuffixes().
Complexité en mémoire : \(\mathcal{O}(n)\) (il faut créer et stocker la liste list(range(n))).
Complexité en temps : \(\mathcal{O}(n \log(n))\) comparaisons pour trier, et chaque comparaisons est un appel à comparerSuffixes(), coûtant au plus \(\mathcal{O}(n)\), donc dans le pire des cas calculerSuffixes() sera en \(\mathcal{O}(n^2 \log(n))\).

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:])))
: quelbonbonbon
: uelbonbonbon
: elbonbonbon
: lbonbonbon
: bonbonbon
: onbonbon
: nbonbon
: bonbon
: onbon
: nbon
: bon
: on
: 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]:])))
: 10 : bon
:  7 : bonbon
:  4 : bonbonbon
:  2 : elbonbonbon
:  3 : lbonbonbon
: 12 : n
:  9 : nbon
:  6 : nbonbon
: 11 : on
:  8 : onbon
:  5 : onbonbon
:  0 : quelbonbonbon
:  1 : uelbonbonbon

DS3_info.q9()[source]¶

Réponse mathématique à la question 9. :

J’ai un peu triché en utilisant la fonction de la librairie standard Python 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, soit à bulle), et donc \(\mathcal{O}(n^2)\) comparaisons de suffixes.
Donc cette implémentation naïve serait en \(\mathcal{O}(n^3)\).
En utilisant un algorithme de tri performant, comme le tri fusion, le tri rapide (aux programme, ou le tri par tas, pas au programme), on aurait \(\mathcal{O}(n \log(n))\) comparaisons, et donc une complexité finale en \(\mathcal{O}(n^2 \log(n))\) dans le pire des cas.

Voir aussi

Solution du TP8 sur les algorithmes de tris.

DS3_info.comparerMotSuffixe(mot, tab, k)[source]¶

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 : \(\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

DS3_info.rechercherMot2Rec(mot, tab, tabS, i, j)[source]¶

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 : \(\mathcal{O}(\log (j - i + 1))\) dans le pire des cas (par récurrence).

DS3_info.rechercherMot2(mot, tab, tabS)[source]¶

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 : \(\mathcal{O}(\log n)\) dans le pire des cas, où n = len(tab) (par recherche dichotomique).
En utilisant la fonction précédente, 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

DS3_info.q12()[source]¶

Réponse mathématique à la question 12.

rechercherMot() (question 2) fait de l’ordre de \(\mathcal{O}(n)\) comparaisons de mots;
rechercherMot2() (question 11) par contre fait de l’ordre de \(\mathcal{O}(\log n)\) comparaisons de mots.

DS3_info.rechercherPremierSuffixeRec(mot, tab, tabS, i, j)[source]¶

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 : \(\mathcal{O}(\log (j - i + 1))\) dans le pire des cas (par récurrence).

DS3_info.rechercherPremierSuffixe(mot, tab, tabS)[source]¶

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, 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

DS3_info.rechercherDernierSuffixe(mot, tab, tabS)[source]¶

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

DS3_info.compterOccurrences2(mot, tab)[source]¶

Renvoie le nombre d’occurrences du mot mot dans le texte tab, implémentée de façon plus efficace que compterOccurrences().

L’algorithme qu’il fallait trouver est le suivant :
1. On calcule le tableau des suffixes de tab (via 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 rechercherPremierSuffixe() et rechercherDernierSuffixe()),
4. Et on renvoie kmax - kmin + 1.
C’est très visuel, cf. la figure 1.

Renvoie -1 si le mot n’est pas présent.
Complexité en temps : \(\mathcal{O}(n^2 \log(n))\) pour calculer tabS, et ensuite \(\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 \(\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

DS3_info.afficherFrequenceKgramme(tab, tabS, k)[source]¶

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 : \(\mathcal{O}(n)\) (si tabS déjà calculé), ce qui est indépendant de k.
Complexité en mémoire : \(\mathcal{O}(1)\) (si tabS déjà calculé), ce qui est indépendant de k et n (ou bien \(\mathcal{O}(n)\) si on créé la chaîne à afficher, et qu’on ne l’affiche qu’à la fin).

Conseils¶

Améliorez la présentation de vos copies,
Essayez d’être encore plus attentif à la syntaxe de Python (il y a eu trop d’erreurs d’indentation et de : manquants),
Vous devez être plus attentif aux consignes de l’énoncé (certains élèves oublient de donner la complexité dans les dernières questions),
Comme dans chaque concours/DS, vous devez essayer de “grapiller” des points là où vous peuvez.

Sortie du script¶

$ python3 DS3_info.py


Partie 0 : Fonctions supposees donnees.


Partie 1 : Methode directe.


Partie 2 : Tableau des suffixes.


Partie 3 : Exploitation du tableau des suffixes.

Test automatique de toutes les doctests ecrites dans la documentation (docstring) de chaque fonction :
Trying:
    texte = "quelbonbonbon"
Expecting nothing
ok
Trying:
    tab = [16, 20, 4, 11, 1, 14, 13, 1, 14, 13, 1, 14, 13]
Expecting nothing
ok
Trying:
    tab1 = texte_vers_tab("quelbonbonbon")
Expecting nothing
ok
Trying:
    afficherFrequenceBigramme(tab1)
Expecting:
    lb(1), nb(2), ue(1), el(1), on(3), bo(3), qu(1)
ok
Trying:
    tab2 = texte_vers_tab("iamsuperman")
Expecting nothing
ok
Trying:
    afficherFrequenceBigramme(tab2)
Expecting:
    ia(1), ma(1), pe(1), am(1), rm(1), an(1), up(1), er(1), ms(1), su(1)
ok
Trying:
    tab3 = texte_vers_tab("lilian")
Expecting nothing
ok
Trying:
    afficherFrequenceBigramme(tab3)
Expecting:
    ia(1), li(2), il(1), an(1)
ok
Trying:
    tab = texte_vers_tab("quelbonbonbon")
Expecting nothing
ok
Trying:
    tabS = calculerSuffixes(tab)
Expecting nothing
ok
Trying:
    k = 1
Expecting nothing
ok
Trying:
    afficherFrequenceKgramme(tab, tabS, k)
Expecting:
    b(3), e(1), l(1), n(3), o(3), q(1), u(1)
ok
Trying:
    k = 2
Expecting nothing
ok
Trying:
    afficherFrequenceKgramme(tab, tabS, k)
Expecting:
    bo(3), el(1), lb(1), nb(2), on(3), qu(1), ue(1)
ok
Trying:
    k = 3
Expecting nothing
ok
Trying:
    afficherFrequenceKgramme(tab, tabS, k)
Expecting:
    bon(3), elb(1), lbo(1), nbo(2), onb(2), que(1), uel(1)
ok
Trying:
    k = 4
Expecting nothing
ok
Trying:
    afficherFrequenceKgramme(tab, tabS, k)
Expecting:
    bonb(2), elbo(1), lbon(1), nbon(2), onbo(2), quel(1), uelb(1)
ok
Trying:
    k = 5
Expecting nothing
ok
Trying:
    afficherFrequenceKgramme(tab, tabS, k)
Expecting:
    bonbo(2), elbon(1), lbonb(1), nbonb(1), onbon(2), quelb(1), uelbo(1)
ok
Trying:
    k = 3
Expecting nothing
ok
Trying:
    for i in range(len(tab)):
        ksuffixe = tab[tabS[i]:]
        if len(ksuffixe) >= k:
            print("{}".format(tab_vers_texte(ksuffixe[:k])))
Expecting:
    bon
    bon
    bon
    elb
    lbo
    nbo
    nbo
    onb
    onb
    que
    uel
ok
Trying:
    tab = texte_vers_tab("quelbonbonbon")
Expecting nothing
ok
Trying:
    n = len(tab)
Expecting nothing
ok
Trying:
    for i in range(n): print("{:>3} : {}".format(i, tab_vers_texte(tab[i:])))
Expecting:
      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
ok
Trying:
    tabS = calculerSuffixes(tab)
Expecting nothing
ok
Trying:
    print(tabS)
Expecting:
    [10, 7, 4, 2, 3, 12, 9, 6, 11, 8, 5, 0, 1]
ok
Trying:
    for i in range(n): print("{:>3} : {:>2} : {}".format(i, tabS[i], tab_vers_texte(tab[tabS[i]:])))
Expecting:
      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
ok
Trying:
    tab = texte_vers_tab("quelbonbonbon")
Expecting nothing
ok
Trying:
    mot = texte_vers_tab("lbo")
Expecting nothing
ok
Trying:
    print(comparerMotSuffixe(mot, tab, 0))  # "quelbonbonbon" > "lbo"
Expecting:
    -1
ok
Trying:
    print(comparerMotSuffixe(mot, tab, 2))  # "elbonbonbon" < "lbo"
Expecting:
    1
ok
Trying:
    print(comparerMotSuffixe(mot, tab, 3))
Expecting:
    0
ok
Trying:
    tab = texte_vers_tab("quelbonbonbon")
Expecting nothing
ok
Trying:
    k1 = 10; k2 = 12
Expecting nothing
ok
Trying:
    print(comparerSuffixes(tab, k1, k2))  # tab[k1:] < tab[k2:]
Expecting:
    -1
ok
Trying:
    print(comparerSuffixes(tab, k1, k1))  # tab[k1:] == tab[k1:]
Expecting:
    0
ok
Trying:
    print(comparerSuffixes(tab, k2, k1))  # tab[k2:] < tab[k1:]
Expecting:
    1
ok
Trying:
    tab = texte_vers_tab("quelbonbonbon")
Expecting nothing
ok
Trying:
    mot1 = texte_vers_tab("bonbon")
Expecting nothing
ok
Trying:
    print(compterOccurrences(mot1, tab))
Expecting:
    2
ok
Trying:
    mot2 = texte_vers_tab("on")
Expecting nothing
ok
Trying:
    print(compterOccurrences(mot2, tab))
Expecting:
    3
ok
Trying:
    mot3 = texte_vers_tab("quel")
Expecting nothing
ok
Trying:
    print(compterOccurrences(mot3, tab))
Expecting:
    1
ok
Trying:
    tab = texte_vers_tab("quelbonbonbon")
Expecting nothing
ok
Trying:
    mot1 = texte_vers_tab("bonbon")
Expecting nothing
ok
Trying:
    print(compterOccurrences2(mot1, tab))
Expecting:
    2
ok
Trying:
    mot2 = texte_vers_tab("on")
Expecting nothing
ok
Trying:
    print(compterOccurrences2(mot2, tab))
Expecting:
    3
ok
Trying:
    mot3 = texte_vers_tab("quel")
Expecting nothing
ok
Trying:
    print(compterOccurrences2(mot3, tab))
Expecting:
    1
ok
Trying:
    tab = texte_vers_tab("bonjaimelesbonbons")
Expecting nothing
ok
Trying:
    mot = texte_vers_tab("bon")
Expecting nothing
ok
Trying:
    print(enTeteDeSuffixe(mot, tab, 0))
Expecting:
    True
ok
Trying:
    print(enTeteDeSuffixe(mot, tab, 1))
Expecting:
    False
ok
Trying:
    print(enTeteDeSuffixe(mot, tab, 11))
Expecting:
    True
ok
Trying:
    print(entier_vers_charactere(0))
Expecting:
    a
ok
Trying:
    print(entier_vers_charactere(10))
Expecting:
    k
ok
Trying:
    tab1 = texte_vers_tab("quelbonbonbon")
Expecting nothing
ok
Trying:
    print(frequenceLettre(tab1))
Expecting:
    [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]
ok
Trying:
    tab2 = texte_vers_tab("superman")
Expecting nothing
ok
Trying:
    print(frequenceLettre(tab2))
Expecting:
    [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]
ok
Trying:
    tab3 = texte_vers_tab("lilianbesson")
Expecting nothing
ok
Trying:
    print(frequenceLettre(tab3))
Expecting:
    [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]
ok
Trying:
    tab1 = [1, 2, 3, 4, 5]
Expecting nothing
ok
Trying:
    print(ordreLexicographiqueTableaux(tab1, tab1))  # tab1 == tab1
Expecting:
    0
ok
Trying:
    tab2 = [1, 2, 3, 5, 6]
Expecting nothing
ok
Trying:
    print(tab1 < tab2)
Expecting:
    True
ok
Trying:
    print(ordreLexicographiqueTableaux(tab1, tab2))  # tab1 < tab2
Expecting:
    -1
ok
Trying:
    print(tab2 < tab1)
Expecting:
    False
ok
Trying:
    print(ordreLexicographiqueTableaux(tab2, tab1))  # tab2 > tab1
Expecting:
    1
ok
Trying:
    tab3 = [-2, 3, 5, 6]
Expecting nothing
ok
Trying:
    print(tab1 < tab3)
Expecting:
    False
ok
Trying:
    print(ordreLexicographiqueTableaux(tab1, tab3))  # tab1 > tab3
Expecting:
    1
ok
Trying:
    print(tab2 < tab3)
Expecting:
    False
ok
Trying:
    print(ordreLexicographiqueTableaux(tab2, tab3))  # tab2 > tab3
Expecting:
    1
ok
Trying:
    tab4 = [1, 2, 3]
Expecting nothing
ok
Trying:
    print(tab4 < tab1)
Expecting:
    True
ok
Trying:
    print(ordreLexicographiqueTableaux(tab1, tab4))  # tab1 > tab4
Expecting:
    1
ok
Trying:
    tab = texte_vers_tab("quelbonbonbon")
Expecting nothing
ok
Trying:
    tabS = calculerSuffixes(tab)
Expecting nothing
ok
Trying:
    mot1 = texte_vers_tab("bon")
Expecting nothing
ok
Trying:
    print(rechercherDernierSuffixe(mot1, tab, tabS))
Expecting:
    2
ok
Trying:
    mot2 = texte_vers_tab("nb")
Expecting nothing
ok
Trying:
    print(rechercherDernierSuffixe(mot2, tab, tabS))
Expecting:
    7
ok
Trying:
    tab = texte_vers_tab("bonjaimelesbonbons")
Expecting nothing
ok
Trying:
    mot1 = texte_vers_tab("bon")
Expecting nothing
ok
Trying:
    print(rechercherMot(mot1, tab))
Expecting:
    True
ok
Trying:
    mot2 = texte_vers_tab("jenaimepas")
Expecting nothing
ok
Trying:
    print(rechercherMot(mot2, tab))
Expecting:
    False
ok
Trying:
    mot3 = texte_vers_tab("superman")
Expecting nothing
ok
Trying:
    print(rechercherMot(mot3, tab))
Expecting:
    False
ok
Trying:
    mot4 = texte_vers_tab("bonbons")
Expecting nothing
ok
Trying:
    print(rechercherMot(mot4, tab))
Expecting:
    True
ok
Trying:
    tab = texte_vers_tab("quelbonbonbon")
Expecting nothing
ok
Trying:
    tabS = calculerSuffixes(tab)
Expecting nothing
ok
Trying:
    mot1 = texte_vers_tab("lbo")
Expecting nothing
ok
Trying:
    print(rechercherMot2(mot1, tab, tabS))
Expecting:
    True
ok
Trying:
    mot2 = texte_vers_tab("lilian")
Expecting nothing
ok
Trying:
    print(rechercherMot2(mot2, tab, tabS))
Expecting:
    False
ok
Trying:
    mot3 = texte_vers_tab("bonbonbon")
Expecting nothing
ok
Trying:
    print(rechercherMot2(mot3, tab, tabS))
Expecting:
    True
ok
Trying:
    tab = texte_vers_tab("quelbonbonbon")
Expecting nothing
ok
Trying:
    tabS = calculerSuffixes(tab)
Expecting nothing
ok
Trying:
    mot1 = texte_vers_tab("bonbon")
Expecting nothing
ok
Trying:
    print(rechercherPremierSuffixe(mot1, tab, tabS))
Expecting:
    1
ok
Trying:
    mot2 = texte_vers_tab("lilian")
Expecting nothing
ok
Trying:
    print(rechercherPremierSuffixe(mot2, tab, tabS))
Expecting:
    -1
ok
Trying:
    mot3 = texte_vers_tab("bonbonbon")
Expecting nothing
ok
Trying:
    print(rechercherPremierSuffixe(mot3, tab, tabS))
Expecting:
    2
ok
Trying:
    tab = texte_vers_tab("quelbonbonbon")
Expecting nothing
ok
Trying:
    suf = [1, 2, 4, 9, 8]
Expecting nothing
ok
Trying:
    print(suffixeMin(tab, suf))  # 4 : tab[4:] = "bonbonbon"
Expecting:
    4
ok
Trying:
    suf2 = [1, 2, 9, 8]
Expecting nothing
ok
Trying:
    print(suffixeMin(tab, suf2))  # 2 : tab[2:] = "elbonbonbon"
Expecting:
    2
ok
Trying:
    suf3 = [1, 9, 8]
Expecting nothing
ok
Trying:
    print(suffixeMin(tab, suf3))  # 9 : tab[9:] = "nbon"
Expecting:
    9
ok
Trying:
    tab = [16, 20, 4, 11, 1, 14, 13, 1, 14, 13, 1, 14, 13]
Expecting nothing
ok
Trying:
    texte = tab_vers_texte(tab)
Expecting nothing
ok
Trying:
    print(texte)
Expecting:
    quelbonbonbon
ok
Trying:
    texte = "quelbonbonbon"
Expecting nothing
ok
Trying:
    texte_vers_tab = lambda texte: [ord(lettre.lower()) - ord('a') for lettre in texte]
Expecting nothing
ok
Trying:
    print(texte)
Expecting:
    quelbonbonbon
ok
Trying:
    print(texte_vers_tab(texte))
Expecting:
    [16, 20, 4, 11, 1, 14, 13, 1, 14, 13, 1, 14, 13]
ok
5 items had no tests:
    __main__.egaliteTableaux
    __main__.q12
    __main__.q9
    __main__.rechercherMot2Rec
    __main__.rechercherPremierSuffixeRec
19 items passed all tests:
   2 tests in __main__
   6 tests in __main__.afficherFrequenceBigramme
  14 tests in __main__.afficherFrequenceKgramme
   6 tests in __main__.calculerSuffixes
   5 tests in __main__.comparerMotSuffixe
   5 tests in __main__.comparerSuffixes
   7 tests in __main__.compterOccurrences
   7 tests in __main__.compterOccurrences2
   5 tests in __main__.enTeteDeSuffixe
   2 tests in __main__.entier_vers_charactere
   6 tests in __main__.frequenceLettre
  15 tests in __main__.ordreLexicographiqueTableaux
   6 tests in __main__.rechercherDernierSuffixe
   9 tests in __main__.rechercherMot
   8 tests in __main__.rechercherMot2
   8 tests in __main__.rechercherPremierSuffixe
   7 tests in __main__.suffixeMin
   3 tests in __main__.tab_vers_texte
   4 tests in __main__.texte_vers_tab
125 tests in 24 items.
125 passed and 0 failed.
Test passed.

Plus de details sur ces doctests sont dans la documentation de Python:
https://docs.python.org/3/library/doctest.html (en anglais)

Le fichier Python se trouve ici : DS3_info.py.

DS 5 : X PSI-PT 2010¶

Conseils¶

Sortie du script¶

DS 5 : X PSI-PT 2010 ¶