\( \def\N{{\mathbb{N}}} \def\R{{\mathbb{R}}} \def\D{{\mathbb{D}}} \def\C{{\mathbb{C}}} \def\Z{{\mathbb{Z}}} \def\Q{{\mathbb{Q}}} \def\K{{\mathbb{K}}} \def\KX{{\mathbb{K}}[X]} \def\U{{\mathbb{U}}} \def\B{{\mathcal{B}}} \newcommand\ensfonctions[2]{\mathcal{F}(#1,#2)} \newcommand\ensfonctionszero[3]{\mathcal{F}_{#3,0}(#1,#2)} \newcommand\continues[2]{\mathcal{C}(#1,#2)} \newcommand\lineaires[2]{\mathcal{L}(#1,#2)} \newcommand\nlineaires[3]{\mathcal{L}_{#1}(#2,#3)} \newcommand\ensendo[1]{\mathcal{L}(#1)} \newcommand\derivables[2]{\mathcal{D}(#1,#2)} \newcommand\segment[2]{[#1,#2]} \newcommand\intouvert[2]{]#1,#2[} \newcommand\intouvertgauche[2]{]#1,#2]} \newcommand\intouvertdroite[2]{[#1,#2[} \newcommand\classeck[3]{\mathcal{C}^{#1}(#2,#3)} \newcommand\range[2]{[| #1,#2 |]} \newcommand\mod[0]{\mathop{mod}} \newcommand\land[0]{\mathop{land}} \newcommand\voisinages[2]{\mathcal{V}_{#1}(#2)} \newcommand\matrices[3]{\mathcal{M}_{#1,#2}(#3)} \newcommand\matricescarres[2]{\mathcal{M}_{#1}(#2)} \newcommand\gln[2]{\mbox{GL}_{#1}(#2)} \newcommand\Vect[1]{\mbox{Vect}(#1)} \newcommand\Support[1]{\mbox{Supp}(#1)} \newcommand\rang[1]{\mbox{rg}(#1)} \newcommand\trace[1]{\mbox{tr}(#1)} \newcommand\gl[1]{\mbox{GL}(#1)} \newcommand\dom[0]{\mbox{dom}} \newcommand\codim[0]{\mbox{codim}} \newcommand\tr{\mbox{tr}} \newcommand\uniondisjointe{\sqcup} \def\Rbar{\overline\R} \def\lt{<} \def\rR{\mathcal{R}} \newcommand\parties[1]{\mathcal{P}(#1)} \newcommand\entiere[1]{\left\lfloor #1 \right\rfloor} \newcommand\congru[3]{#1 = #2\ [#3]} \newcommand\enscomp[2]{\left\{\left.\ #1\ \right|\ #2\ \right\}} \newcommand\classe[1]{\overline{#1}} \newcommand\classemod[2]{\overline{#1}^{[#2]}} \newcommand\quotient[2]{#1 / #2} \newcommand\ZnZ[1]{\quotient{\Z}{#1 \Z}} \newcommand\card[1]{\text{Card}\ #1} \newcommand\Det{\mbox{Det}} \newcommand\indic{\mathbbm{1}} \newcommand\groupeengendre[1]{\langle #1 \rangle} \renewcommand\Im{\mathfrak{I}} \newcommand\id{\mbox{id}} \newcommand\Bary[1]{\mbox{Bary}\{#1\}} \newcommand\Ker{\mbox{Ker}~} \newcommand\Ima{\mbox{Im}~} \newcommand\Perm[1]{\mathfrak{S}_#1} \newcommand\comb[2]{\binom{#1}{#2}} \newcommand\tend[2]{\xrightarrow[#1 \rightarrow #2]{}} \newcommand\limite[2]{\lim_{#1 \rightarrow #2}} \newcommand\sh{\mbox{sh}} \newcommand\ch{\mbox{ch}} \renewcommand\tanh{\mbox{th}} \newcommand\Arcsin{\mbox{Arcsin}~} \newcommand\Arccos{\mbox{Arccos}~} \newcommand\Arctan{\mbox{Arctan}~} \newcommand\Argsh{\mbox{Argsh}} \newcommand\Argch{\mbox{Argch}} \newcommand\Argth{\mbox{Argth}} \newcommand\argu{\mbox{arg}} \newcommand\dron[2]{\frac{\partial #1}{\partial #2}} \newcommand\conj[1]{\overline{#1}} \newcommand\ei[1]{e^{i #1}} \newcommand\eii[2]{e^{#1 i #2}} \newcommand\crochet[1]{\left[ #1 \right]} \newcommand\application[5]{\begin{array}{rcccc} #1 & : & #2 & \mapsto & #3 \\ & & #4 & \mapsto & #5 \end{array}} \newcommand{\diff}{\mathop{}\mathopen{}\mathrm{d}} \newcommand{\cc}{{\cal C}} \)

Algorithmique du texte

Source image : https://xkcd.com/1288/

Note
version très partielle uniquement pour présenter Rabin-Karp

1 Algorithme de Rabin-Karp

1.1 Principe

L’algorithme de Rabin-Karp est un algorithme de recherche d’un motif dans un texte qui utilise une notion d’empreinte pour déterminer, en temps constant, si il est probable que la position actuelle corresponde à une occurrence du motif.

Pour cela, si on cherche un motif de longueur \(p\) sur l’alphabet \(\Sigma\), on considère une fonction de hachage \(h : \Sigma^p \rightarrow X\). Les éléments de l’ensemble \(X\) sont appelés des empreintes et on suppose que l’égalité entre deux empreintes se vérifie en temps constant contrairement à l’égalité dans \(\Sigma^p\) qui se vérifie en \(O(p)\) dans le pire des cas. Le plus souvent, on choisit pour \(X\) un type entier machine.

Note
Sûrement mettre ici des renvois vers la partie portant le plus sur la notion de fonction de hachage pour la définition la plus complète.

Bien qu’il soit normalement aussi coûteux de calculer l’image par \(h\) d’une sous-chaîne de longueur \(p\) que de tester l’égalité entre cette sous-chaîne et le motif, le point essentiel de l’algorithme de Rabin-Karp est d’utiliser une fonction de hachage permettant un calcul incrémental en temps constant :

Ici, on considère donc, pour \(a, b \in \Sigma\), une fonction de mise à jour \(\delta_{a,b} : X \rightarrow X\) telle que pour tout \(c_2,\dots,c_p \in \Sigma\) on ait \(\delta_{a,b}(h(ac_2 \dots c_p)) = h(c_2\dots c_p b)\).

L’algorithme de Rabin-Karp procède alors ainsi pour chercher \(m\) de longueur \(p\) dans la chaîne \(s = c_0 \dots c_{n-1}\)\(n \ge p\) :

  • calcul de \(e_m = h(m)\) et \(e = h(c_0..c_{p-1})\).

  • Pour \(i\) allant de \(0\) à \(n-p\) :

    • Si \(e_m = e\), on renvoie un succès pour la recherche à la position \(i\) si \(m = c_i \dots c_{i+p-1}\)
    • si \(i<n-p\) on met à jour l’empreinte \(e \leftarrow \delta_{c_i,c_{i+p}}(e)\).

La complexité temporelle liée à la gestion des empreintes est donc en \(O(n+p) = O(n)\) car \(n \ge p\). Par contre, pour calculer la complexité liée à la recherche \(m = c_i \dots c_{i+p-1}\), il est nécessaire d’estimer la proportion de faux positifs, c’est-à-dire de positions \(i\) telles que \(e_m = e\) mais \(m \neq c_i \dots c_{i+p-1}\). On va voir dans la partie suivante qu’on peut supposer qu’elle est négligeable, ce qui permet de considérer que l’algorithme de Rabin-Karp est linéaire.

1.2 Choix d’une fonction de hachage

Réaliser une bonne fonction de hachage est une question très complexe qui dépasse le cadre du cours d’informatique de MPI. Cependant, il est possible de réaliser ici une fonction de hachage répondant aux contraintes de Rabin-Karp assez facilement.

Pour cela, on considère que les caractères sont des entiers compris entre 0 et 255, ce qui correspond au type des caractères non signés sur un octet. On peut alors identifier une chaîne de longueur \(p\) avec un nombre entre \(0\) et \(r^{p} - 1\)\(r =2^8\), on note ainsi \[ P(c_0\dots c_{p-1}) = \sum_{i=0}^{p-1} c_i r^{p-1-i} = c_0 r^{p-1} + c_1 r^{p-2} + \dots + c_{p-1} \]

On considère de plus un entier premier \(q\) et on pose \(h(s) = P(s) \mod q\) c’est-à-dire le reste de \(P(s)\) dans la division euclidienne par \(q\). On peut ainsi définir \(\delta_{a,b}(e) = (r (e - a r^{p-1}) + b) \mod q\).

Si on précalcule \(r^{p-1} \mod q\) il suffit d’un nombre d’opération constant, et indépendant de \(p\), pour calculer la nouvelle empreinte à l’aide de \(\delta_{a,b}\).

Le point essentiel est alors de déterminer un nombre premier \(q\) tel qu’il soit peu probable d’obtenir des faux positifs. Une analyse mathématique permet d’affirmer que chaque élément de \([|0;q-1|]\) a de l’ordre de \(\frac{r^p}{q}\) antécédents par \(h\). Ainsi, si on choisit deux chaînes aléatoirement dans \(\Sigma^p\), il y aura collision avec probabilité proche de \(\frac{1}{q}\). En considérant \(q\) proche de la taille maximale pour le type entier considéré, on minimise donc cette probabilité.

Remarque
On peut également s’intéresser à des nombres \(q\) pour lesquels le modulo soit rapide à calculer. Un exemple classique est \(q = 2^{31} - 1\) car on peut déduire la division euclidienne de \(a\) par \(q\) de l’écriture de \(a\) en base \(2^{31}\). En effet, si \(a = \sum_{k=0}^n a_k 2^{31k}\) comme \(2^{31}-1 | 2^{31k} - 1\) pour \(k \ge 1\), on a \(2^{31k} \equiv 1 ~[q]\) et ainsi \(a \equiv \sum_{k=0}^n a_k [q]\). On remarque que \(a_k = (a >> 31k) \& 2^{31}\), on a alors soit \(a_k < q\) et alors \(a_k \mod q = a_k\), soit \(a_k = q\) et \(a_k \mod q = 0\). Il suffit donc de faire un masquage pour obtenir directement \(a_k \mod q = (a >> 31k) \& q\).

On obtient alors le programme suivant :

let rec fastmod a =
    let s = ref 0 in
    let x = ref a in
    let q = 0x7fffffff in
    while !x > 0 do
        s := !s + (!x land q);
        x := !x lsr 31
    done;
    if !s > q
    then fastmod !s
    else if !s = q
    then 0
    else !s

int64_t fastmod(int64_t a)
{
    int64_t s = 0;
    const int64_t q = 0x7fffffff;
    
    while (a > 0)
    {
        s = s + a & q;
        a = a >> 31;
    }

    if (s > q)
        return fastmod(s);
    if (s == q)
        return 0;
    return s;
}

def fastmod(a):
    s = 0
    q = 0x7fffffff
    while a > 0:
        s = s + a & q
        a = a >> 31
    if s > q:
        return fastmod(s)
    elif s == q:
        return 0

    return s

Le programme suivant implémente naïvement les calculs de \(h\) et de \(\delta_{a,b}\) :

let hash r q s =
    let p = ref 1 in
    let e = ref 0 in
    for i = String.length s - 1 downto 0 do
        e := (!p * (Char.code s.[i]) + !e) mod q;
        p := (r * !p) mod q
    done;
    !e

let delta r q rp a b e = (* rp est r^(p-1) mod q *)
    (r * (e - rp * (Char.code a)) + Char.code b) mod q

int64_t hash(int64_t r, int64_t q, char *s, int n)
{
    int64_t p = 1;
    int64_t e = 0;

    for (int i = n-1; i >= 0; i--)
    {
        e = (p * s[i] + e) % q;
        p = (r * p) % q;
    }

    return e;
}


int64_t delta(int64_t r, int64_t q, int64_t rp,
        char a, char b, int64_t e)
{
    return (r * (e - rp * a) + b) % q;
}

def hash(r,q,s):
    e = 0
    p = 1
    for c in reversed(s):
        e = (ord(c) * p + e) % q
        p = (r * p) % q
    return e

def delta(r,q,rp,a,b,e):
    return (r * (e - rp * ord(a)) + ord(b)) % q

1.3 Implémentation

Une implémentation directe de l’algorithme de Rabin-Karp est donnée dans le programme qui suit. On se sert ici du caractère paresseux du && pour n’effecuter le test coûteux d’égalité des chaînes qu’en cas d’égalité des empreintes.

exception Trouve of int

let rabin_karp m s =
    let n = String.length s in
    let p = String.length m in
    let r = 256 in
    let q = 0x7fffffff in (* 2^(31)-1 *)
    let rp = pow r (p-1) q in
    let me = hash r q m in
    let e = ref (hash r q (String.sub s 0 p)) in
    try
        for i = 0 to n-p+1 do
            if me = !e && m = String.sub s i p
            then raise (Trouve i);
            if i+p < n then e := delta r q rp s.[i] s.[i+p] !e
        done; None
    with Trouve k -> Some k

int rabin_karp(char *m, char *s)
{
    const int64_t r = 256;
    const int64_t q = 0x7fffffff;
    const int p = strlen(m);
    const int n = strlen(s);
    const int64_t rp = powmod(r,p-1,q);
    const int64_t me = hash(r,q,m,p);
    int64_t e = hash(r,q,s,p);
    for (int i=0; i <n-p+1; i++)
    {
        if (me == e && strncmp(m,(s+i),p) == 0)
            return i;
        if (i+p < n)
            e = delta(r,q,rp,s[i],s[i+p],e);
    }
    return -1;
}

def rabin_karp(m, s):
    p, n = len(m), len(s)
    r, q = 256, 0x7fffffff
    rp = (r ** (p-1)) % q
    me, e = hash(r,q,m), hash(r,q,s[:p])
    for i in range(0,n-p+2):
        if me == e and m == s[i:i+p]:
            return i
        if i+p < n:
            e = delta(r,q,rp,s[i],s[i+p],e)
    return None

Si on suppose qu’il est improbable d’obtenir un faux positif, il est possible de renvoyer un succès dès que les empreintes sont égales. L’avantage d’une telle version est alors d’être un algorithme sans retour sur les données. C’est-à-dire qu’il n’est pas nécessaire de garder en mémoire ou de réaccéder à un caractère.

1.4 L’algorithme originel de Rabin et Karp

Si on regarde l’article originel de Rabin et Karp décrivant cette méthode, on peut être étonné du fait que la méthode précédemment décrite était considérée comme déjà connue dans la littérature par les auteurs. En fait, ce qu’ils décrivent et annoncent comme étant novateur est l’utilisation d’un algorithme probabiliste en choisissant aléatoirement une fonction de hachage à chaque lancement de l’algorithme. En pratique, il s’agit de choisir aléatoirement un nombre premier \(q\) parmi un ensemble précalculé de nombres premiers.

L’algorithme que l’on vient de décrire a un pire cas qui est très improbable car on considère que la probabilité d’un faux positif est à peu près de \(1/q\), donc moins de \(5.10^{-10}\) pour \(q = 2^{31}-1\). Le problème ici est la notion de probabilité sur les entrées : est-on certain que l’algorithme recevra une entrée choisie uniformément ? Rabin et Karp parlent d’un adversaire intelligent qui aurait connaissance de la fonction de hachage choisie pour produire des entrées en pire cas. On pourrait ainsi imaginer une attaque sur serveur effectuant une recherche avec Rabin-Karp suite à l’entrée d’un utilisateur. Un adversaire pourrait construire une entrée en pire cas et tenter de surcharger le serveur en l’effectuant de manière répétée.

Pour bien mettre en lumière ce phénomène, nous allons ici construire, dans un cas très simple de fonction de hachage, une telle chaîne problématique. Pour cela, considérons la fonction de hachage précédemment décrite dans le cas de motif de taille 2, avec \(\Sigma\) contenant les lettres de a à z, \(r = 26\) et \(q = 17\). On considère une recherche du motif aa dont l’empreinte est 0, la même que celle des chaînes ar et ra. On peut donc considérer la chaîne arar...ar qui produira un faux positif à chaque étape.

Remarque
Détail des calculs. Ici on associe à a la valeur \(0\), …, à z la valeur \(25\). On a donc \[h(aa) = (0 \times 26 + 0) \mod 17 = 0\] \[h(ar) = (0 \times 26 + 17) \mod 17 = 0\] \[h(ra) = (17 \times 26 + 0) \mod 17 = 0\] L’empreinte reste ainsi nulle tout au long de l’algorithme de Rabin-Karp et on a un faux positif à chaque itération.