Synthèse Recherche Textuelle

FondamentalAlgorithme naïf

L’algorithme naïf consiste simplement à comparer un à un, de gauche à droite, les caractères du texte apparaissant dans la fenêtre avec ceux du motif. En cas de non-correspondance, on avance simplement la fenêtre d’un indice vers la droite (si c'est possible).

Vidéo illustrant l'algorithme naïf
Informations[1]

Cet algorithme est à connaître par ❤️

1
def recherche_naive(texte, motif):
2
    '''
3
    renvoie la liste des indices (éventuellement vide) des occurrences de
4
    de la chaîne motif dans la chaîne texte.
5
    '''
6
    indices = []
7
    i = 0
8
    while i <= len(texte) - len(motif):
9
        j = 0
10
        while j < len(motif) and texte[i+j] == motif[j]:	#attention, j < len() doit être en premier, sinon risque d'erreur Index Out Of Range
11
            j += 1
12
        if j == len(motif):	#On a parcouru tout le motif
13
            indices.append(i)
14
        i += 1
15
16
    return indices
17
Cet algorithme n'est pas efficace ; concrètement, le temps de recherche est semblable quelque soit le motif recherché.
FondamentalAlgorithme de Boyer-Moore-Horspool
Voici les deux principes de l'algorithme proposé par Nigel Horspool pour optimiser l'algorithme naïf :
  1. Dans la fenêtre glissante, les caractères sont comparés de droite à gauche plutôt que de gauche à droite.
  2. En cas de non-correspondance, le décalage de la fenêtre va dépendre du caractère de texte. Ce principe s’appelle la règle du mauvais caractère.
La règle du mauvais caractère est la suivante :
On regarde le caractère X du texte sur lequel on s'est arrêté (car X n'était pas égal au caractère de rang équivalent dans le motif):
  • si X n'est pas dans le motif, il est inutile de se déplacer "de 1" : on retomberait tout de suite sur X, c'est du temps perdu. On se décale donc juste assez pour dépasser X, donc de la longueur du motif cherché.
  • si X est dans le motif (sauf à la dernière place du motif !), on va regarder la place de la dernière occurrence de X dans le motif et de déplacer de ce nombre, afin de faire coïncider le X du motif et le X du texte.
Vidéo illustrant l'algorithme Boyer-Moore-Horspool
Informations[2]
Cet algorithme est à comprendre !
1
def bad_carac_horspool(motif):
2
    """
3
    motif - str, chaîne de caractères
4
    Sortie: dict - dictionnaire tel que :
5
                 - les clefs sont les caractères de motif
6
                 - les valeurs associées sont leur indice "le plus à droite" dans motif
7
            Le dernier caractère de motif n'est pas parcouru
8
    """
9
    dico = {}
10
    for i in range(len(motif)-1):
11
        dico[motif[i]] = i
12
    return dico
13
14
def decalage_horspool(motif, texte, i, j, bad_carac):
15
    """
16
    motif - str, chaîne de caractères
17
    texte - str, chaîne de caractères
18
    i - int, position de la fenêtre telle que 0 <= i < len(texte)
19
    j - int, entier tel que 0 <= j < len(motif)
20
    bad_carac - dict, dictionnaire des mauvais caractères (Horspool)
21
    Sortie: int - décalage à appliquer à la fenêtre en cas de non correspondance
22
                    entre texte[i+j] et motif[j]
23
    """
24
    if texte[i+j] in bad_carac.keys():
25
        k = bad_carac[texte[i+j]]
26
        decalage = max(1, j-k)
27
    else:
28
        decalage = j+1
29
    return decalage
30
31
def positions_horspool(motif, texte):
32
    """
33
    motif - str, chaîne de caractères
34
    texte - str, chaîne de caractères
35
    Sortie: list - Tableau des positions où trouver motif dans texte
36
    """
37
    p = len(motif)
38
    n = len(texte)
39
    bad_carac = bad_carac_horspool(motif)
40
    i = 0
41
    indices = []
42
    while i <= n-p:
43
        j = p-1
44
        while j >= 0:
45
            if motif[j] != texte[i+j]:
46
                decalage = decalage_horspool(motif, texte, i, j, bad_carac)
47
                j = -2
48
            else:
49
                j = j-1
50
        
51
        if j == -1:     # On a parcouru tout le motif : il est présent dans texte
52
            indices.append(i)
53
            decalage = 1
54
        i += decalage
55
    return indices
Un autre code possible pour cet algorithme :
1
def bad_carac_horspool(motif):
2
    dico = {}
3
    for i in range(len(motif)-1):
4
        dico[motif[i]] = i
5
    return dico
6
7
def recherche_BMH(motif, texte):
8
    bad_carac = bad_carac_horspool(motif)
9
    indices = []
10
    i = len(motif) -1
11
    while i < len(texte):
12
        j = 0
13
        while j < len(motif) and motif[len(motif)-1-j] == texte[i-j]: #On remonte le motif à l'envers, tant qu'il y a correspondance et qu'on n'est pas arrivés au début du motif
14
            j += 1
15
        if j == len(motif): #Si on est arrivés au début du motif, c'est qu'on a trouvé le mot.
16
            indices.append(i-len(motif)+1)
17
            i += 1 #On a trouvé le motif, mais attention, il ne faut pas trop se décaler sinon on pourrait rater d'autres occurences du motif (pensez à la recherche du motif «mama» dans le mot «mamamamama»). On se décale donc de 1.
18
        else:
19
            if texte[i-j] in bad_carac:
20
                i = max(i - j  + len(motif) - bad_carac[texte[i-j]] - 1, i+1) #On décale juste de ce qu'il faut pour mettre en correspondance les lettres, en évitant le retour en arrière (d'où le max pour se décaler au moins de 1) 
21
            else:
22
                i = i - j + len(motif) #La lettre n'est pas dans le motif : on se positionne juste après elle. 
23
24
    return indices
25
En appliquant cet algorithme sur des textes et des motifs de longueurs différentes, on constate une chose remarquable : plus le motif recherché est long et plus la recherche est rapide.
ComplémentNombre de comparaisons
Pour calculer le nombre de comparaisons, on ajoute un simple compteur que l'on incrémente à juste avant de rentrer dans le test. Ainsi, pour l'algorithme naïf, on obtient ce code :
1
def nb_comparaisons_naif(motif, texte):
2
    """
3
    motif - str, chaîne de caractères
4
    texte - str, chaîne de caractères
5
    Sortie: int - Nombre de comparaisons nécessaires pour
6
            déterminer les positions où trouver motif dans texte
7
            selon l'algorithme naïf de recherche textuelle
8
    
9
    >>> motif = 'CAAGT'
10
    >>> texte = 'ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT'
11
    >>> nb_comparaisons_naif(motif, texte)
12
    52
13
    """
14
    p = len(motif)
15
    n = len(texte)
16
    i = 0
17
    nb_comparaisons = 0
18
    while i <= n-p:
19
        j = 0
20
        while j < p :
21
            nb_comparaisons += 1
22
            if motif[j] == texte[i+j]:
23
                j += 1
24
            else:
25
                j = p
26
        i += 1
27
    return nb_comparaisons
Alors que pour l'algorithme optimisé, on peut utiliser celui-ci :
1
def nb_comparaisons_horspool(motif, texte):
2
    """
3
    motif - str, chaîne de caractères
4
    texte - str, chaîne de caractères
5
    Sortie: int - Nombre de comparaisons nécessaires pour
6
            déterminer les positions où trouver motif dans texte
7
            selon l'algorithme de recherche textuelle simplifié de Horspool
8
    
9
    >>> motif = 'CAAGT'
10
    >>> texte = 'ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT'
11
    >>> nb_comparaisons_horspool(motif, texte)
12
    32
13
    """
14
    p = len(motif)
15
    n = len(texte)
16
    bad_carac = bad_carac_horspool(motif)
17
    i = 0
18
    nb_comparaisons = 0
19
    while i <= n-p:
20
        j = p-1
21
        while j >= 0:
22
            nb_comparaisons += 1
23
            if motif[j] != texte[i+j]:
24
                decalage = decalage_horspool(motif, texte, i, j, bad_carac)
25
                j = -2
26
            else:
27
                j = j-1
28
        if j == -1:
29
            decalage = 1
30
        i += decalage
31
    return nb_comparaisons