TP : Benchmark pour la recherche de sous-mot 
L'objectif de ce TP est de comparer la vitesse de plusieurs algorithmes de recherche de mot dans un texte. L'idéal est de recoder par vous-même les algorithmes. Si vous n'y arrivez pas, regardez le cours ou demandez-moi.
Algorithme naïf¶
Dans ce premier algorithme, pour chercher un mot $w$ de taille $k$ on regarde chaque fenêtre de taille $k$ que l'on compare avec $w$ (remarque : on peut directement comparer 2 chaînes de caractères avec =).
Exercice
Écrire une fonction naive permettant de savoir si un mot apparaît dans un texte. Par exemple, naive "hello world" "world" renvoie true.
On pourra utiliser String.sub pour extraire un sous-mot, où String.sub s i k extrait le sous-mot de s à partir de l'indice i et de taille k.
Pour faire des benchmarks, on pourra utiliser la fonction suivante, qui teste la fonction f sur le fichier file en y cherchant le mot w. v est un booléen indiquant si le mot est effectivement présente (pour vérifier que la fonction a bien renvoyé la bonne valeur) :
let benchmark f file w v =
let file = open_in file in
let rec read () =
try let l = input_line file in l^(read ())
with End_of_file -> "" in
let file = read () in
let t = Sys.time () in
(* Format.printf "%s@." (read ()): *)
assert (f file w = v);
Sys.time() -. t
val benchmark : (string -> 'a -> 'b) -> string -> 'a -> 'b -> float = <fun>
benchmark f file w v déclenche une exception si f ne renvoie pas la valeur v, et sinon renvoie le temps d'exécution de la fonction (en secondes). Par exemple, en utilisant un fichier du code source de GCC :
benchmark naive "gcc.cc" "int" true
- : float = 4.9999999999883471e-05
Algorithme de Rabin-Karp¶
Rabin-Karp calcule un hash (un entier donné par une fonction de hachage) de chaque sous-chaîne du texte, qui est comparé avec le hash du mot cherché.
Étant donné un mot $w = w_0...w_{k - 1}$, un entier $b$ (le nombre de caractères possibles) et un entier $q$, on définit $h(w) \in \{0, ..., q - 1\}$ par :
$$h(w) = \sum_{i = 0}^{n - 1} \text{code}(w_i) b^{n - 1 - i} \mod q$$
où $\text{code}(w_i)$ est le code de la lettre $w_i$ (par exemple, le code ASCII, donné par Char.code).
Exercice
Écrire une fonction hash b q s calculant le hash de la chaîne s avec $b$ caractères et $q$ comme modulo.
Exercice
Écrire une fonction pow a n q renvoyant $a^n \mod q$. Cette fonction sera utile pour mettre à jour le hash d'une fenêtre.
Exercice
Écrire une fonction rabin_karp text w appliquant l'algorithme de Rabin-Karp. Plutôt que de recalculer le hash de chaque fenêtre, on mettra à jour le hash de la fenêtre précédente plutôt qu'utiliser la fonction précédente à chaque fois.
Exercice
Tester rabin_karp et comparer le temps d'exécution avec naive. On pourra tester avec des longs mots.
Algorithme de Boyer-Moore¶
Boyer-Moore commence par calculer un dictionnaire d qui à chaque caractère d'un mot associe l'indice de sa première apparition par rapport à la fin.
Exemple : si w = "CGGCAG" alors d associe 1 à A, 2 à C, 3 à G.
Voici un exemple de création de dictionnaire avec Map :
let module M = Map.Make(String) in
let d = M.empty in (* dictionnaire vide *)
let d1 = M.add "a" 1 d in (* renvoie un dictionnaire avec l'association "a" -> 1 *)
M.find_opt "a" d1 (* renvoie None ou Some(v) où v est la valeur associée à la clé "a" *)
- : int option = Some 1
Exercice
Écrire une fonction ayant un mot en argument et renvoyant le dictionnaire d.
On regarde ensuite, pour chaque indice $i$ du texte, si la fenêtre terminant en $i$ correspond au mot $w$ qu'on cherche. Pour cela, on regarde les lettres de $w$ de droite à gauche. Si une lettre de $w$ est différente de la lettre $a$ correspondante dans le texte, on décale d'un nombre de caractères égal au décalage de $a$ dans le dictionnaire (si $a$ n'est pas dans le dictionnaire ou si le décalage donne un prochain indice inférieur à $i$, on décale $i$ de 1 seulement). À chaque fois que l'on passe à une nouvelle fenêtre, il faut refaire la comparaison avec le mot en entier (et toujours de droite à gauche).
Exercice
Écrire une fonction boyer_moore text w déterminant si w apparaît dans text.
Exercice
Faire des comparaisons de vitesse avec la fonction benchmark.