(Durée : 2 heures)

L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.
Le langage de programmation choisi par le candidat doit être spécifié en tête de la copie.
On attachera une grande importance à la concision, à la clarté, et à la précision de la rédaction.

La quantité d'information disponible en ligne s'est considérablement accrue. Notons par exemple la numérisation électronique de nombreux ouvrages, le développement exponentiel du web ou la mise à disposition de données plus spécialisées comme le génome humain. Un problème clé lié à ce volume d'information est l'efficacité de la recherche d'informations.

Dans un moteur de recherche internet par exemple, un facteur d'importance d'une page pour une requête donnée est l'appartenance des mots recherchés à la page ainsi que leur nombre d'apparitions. Ces informations peuvent être obtenues simplement en parcourant le texte, comme nous le verrons dans une première partie. Toutefois, cette approche simple conduit à des algorithmes lents vu la taille des textes considérés. La suite du problème propose des réalisations plus efficaces.

Dans tout le problème, nous supposerons que le texte est donné dans un tableau d'entiers tab de taille et que les indices de ce tableau vont de 1 à . Chaque case du tableau contient un entier représentant une lettre. Nous supposerons donc que tous ces entiers ont des valeurs comprises entre 1 et 26 . De plus, dans l'énoncé, nous noterons tab , le texte extrait de tab composé des caractères d'indices allant de à et compris. On utilisera indifféremment le terme caractère ou entier pour désigner le caractère du texte ou de manière équivalente l'entier dans la case tab . Dans nos exemples, pour des raisons de lisibilité, le caractère espace est utilisé mais ce caractère n'est pas encodé, seules les lettre de 'a' à 'z' sont utilisées.

Quel que soit le langage dans lequel les candidats ont choisi de composer, ils emploieront des tableaux dynamiques. Plus précisément, on suppose données deux primitives : une primitive allouer qui renvoie un nouveau tableau de cases; et une primitive taille qui renvoie la taille du tableau . Par ailleurs, on suppose que les tableaux peuvent être passés en argument ou renvoyés comme résultat de fonction. Enfin, les booléens vrai et faux sont utilisés dans certaines questions de ce problème. Le candidat est libre d'utiliser les notations booléennes du langage dans lequel il compose.

Dans cette partie, nous allons mettre en œuvre des algorithmes simples permettant d'effectuer les opérations de recherche citées précédemment.

Introduisons d'abord quelques notions. Un mot est, dans notre contexte, tout simplement un texte. Un mot mot de taille apparaît dans le texte tab de taille , si et seulement si il existe un texte extrait de tab, noté , qui est égal à mot, caractère pour caractère. Le suffixe numéro du texte tab de taille est le texte extrait . On note que le mot mot apparaît dans le texte tab, si et seulement si il existe un suffixe tel que mot apparaît en tête de ce suffixe (mot et sont égaux, caractère pour caractère).
Question 1. Écrire une fonction enTeteDeSuffixe(mot, tab, ) qui renvoie vrai si le mot mot apparaît en tête du suffixe numéro du texte tab, et faux sinon. On pourra supposer que est un indice valide du tableau tab.

Question 2. Écrire une fonction rechercherMot(mot, tab) qui renvoie vrai si le mot mot apparaît dans le texte tab, et faux sinon.

Tester l'apparition d'un mot dans un texte ne suffit pas toujours, nombre de moteurs de recherche internet prennent en compte le nombre d'occurrences des mots recherchés dans une page donnée. 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.

Question 3. Écrire une fonction compterOccurrences(mot, tab) qui renvoie le nombre d'occurrences de mot dans le texte tab.

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 , , pour la taille 2 , on obtient bo(3), el(1), lb(1), nb(2), on(3), qu(1), ue(1).
Question 4. Écrire une fonction frequenceLettre(tab) qui calcule et renvoie un tableau de taille 26 dont la case contient la fréquence de la lettre dans le texte.
Question 5. Écrire une fonction afficherFrequenceBigramme(tab) qui affiche les mots de 2 lettres présents dans le texte ainsi que leur fréquence. On suppose écrite une fonction afficherMot (tab, ) qui affiche le mot présent dans tab, commençant à l'indice et de taille . Le candidat proposera une réalisation simple, qui parcourt le tableau tab de nombreuses fois ou crée un tableau de grande taille en mémoire.

Afin d'accélérer les fonctions précédentes, nous allons utiliser des algorithmes basés sur le tableau des suffixes, défini comme regroupant les suffixes du texte pris dans l'ordre du dictionnaire (dit ordre lexicographique).

Étant donné un texte tab de taille , un indice suffit à désigner un suffixe de tab comme le texte extrait . Le tableau des suffixes tabS sera donc représenté en machine comme
un tableau d'indices de tab. Par exemple, en prenant le texte « quelbonbonbon» on obtient les classements de la figure 1.

La seconde colonne du classement de droite donne le tableau tabS, c'est-à-dire : .

Il existe des méthodes très efficaces pour calculer le tableau des suffixes, nous nous contentons d'une méthode simple.
Question 6. Écrire une fonction comparerSuffixes(tab, ) qui prend en arguments deux suffixes du texte tab, représentés par leurs numéros, et renvoie un entier . L'entier traduit la comparaison lexicographique des suffixes et est strictement négatif quand précède strictement , nul quand et sont égaux, et strictement positif quand suit strictement .
Question 7. Écrire une fonction calculerSuffixes(tab) qui prend le texte tab en argument et renvoie le tableau des suffixes de ce texte (tableau noté tabS ci-dessus). On notera que calculerSuffixes effectue essentiellement un tri du tableau d'entiers selon l'ordre défini à la question précédente.

Nous avons déjà remarqué (Partie I) que le mot mot apparaît dans le texte tab, si et seulement si mot apparaît en en tête d'un suffixe de tab. Or le tableau tabS est le tableau trié des suffixes du texte, ce qui nous permet d'utiliser la technique de recherche dichotomique. Prenons l'exemple concret d'un tas trié de fiches nominatives, et supposons que nous recherchions une fiche portant un nom donné . On peut alors procéder ainsi :

2. S'il y a (encore) des fiches dans , alors on extrait une fiche située vers le milieu du tas, en prenant bien soin de distinguer le tas des fiches situées avant la fiche extraite (noté ) du tas des fiches situées après (noté ). Soit , le nom porté sur la fiche sélectionnée.
(a) Si est strictement plus petit que , alors recommencer en 1 en remplaçant par .
(b) Si est égal à , alors on a trouvé une fiche pour .
(c) Si est strictement plus grand que , alors recommencer en 1 en remplaçant par .

Pour appliquer la recherche dichotomique à la recherche d'un mot dans un texte à l'aide de son tableau des suffixes, on a besoin d'une fonction de comparaison entre mot et suffixe qui élargit le cas d'égalité par rapport à une pure comparaison.
Question 8. Écrire une fonction comparerMotSuffixe(mot, tab, ) qui prend en arguments un mot mot et un suffixe du texte tab, et qui renvoie un entier . L'entier traduit une légère adaptation de la comparaison lexicographique entre le mot mot et le suffixe . À savoir, est nul, si et seulement si le mot mot apparaît en tête du suffixe . Autrement, est strictement négatif (resp. positif) quand le mot précède (resp. suit) strictement le suffixe selon l'ordre lexicographique.
Question 9. Écrire une fonction rechercherMot2(mot, tab, tabS) qui renvoie vrai si le mot mot apparaît dans le texte tab, et faux sinon. On impose évidemment l'emploi de la technique de recherche dichotomique dans le tableau des suffixes tabS, que l'on suppose correct.
Question 10. Donner, sans justification, un ordre de grandeur du nombre de comparaisons de mots effectuées par rechercherMot (question 2) et par rechercherMot2 (question 9). Expliquer ensuite l'intérêt du tableau des suffixes, dans le cas d'un moteur de recherche internet.

Les deux questions suivantes montrent que la technique de cette partie s'applique aussi au cas du dénombrement des apparitions d'un mot dans un texte.
Question 11. Écrire une fonction rechercherPremierSuffixe(mot, tab, tabS) qui renvoie le plus petit indice 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, la fonction rechercherPremierSuffixe doit renvoyer zéro. À titre d'exemple, dans le cas où mot est « bonbon » et avec le tableau des suffixes de la figure 1, rechercherPremierSuffixe renvoie 2 . On impose évidemment une adaptation de la technique de recherche dichotomique dans le tableau des suffixes tabS.

On suppose écrite une fonction rechercherDernierSuffixe(mot, tab, tabS) analogue à la précédente, à ceci près que rechercherDernierSuffixe renvoie le plus grand indice tel que mot apparaît en tête du suffixe numéro tabS du texte tab.
Question 12. En déduire une fonction compterOccurrences2(mot, tab, tabS) qui renvoie le nombre d'occurrences de mot dans le texte tab.

Nous revenons sur le calcul des sous-mots possibles abordé à la fin de la première partie et traitons la question dans toute sa généralité.
Question 13. Écrire une fonction afficherFrequenceKgramme(tab, tabS, ) qui affiche les mots de lettres présents dans le texte ainsi que leur fréquence. On affichera les mots à l'aide de la fonction afficherMot de la question 5. Le candidat proposera une réalisation efficace qui exploite le tableau des suffixes.