Algorithme de Boyer-Moore : module avec fonction principale et programme principal

Module

def table_decal(motif : str) -> list:
    """ Fonction qui construit une table de décalage 
    (algorithme de Boyer-Moore) pour un 'motif' donné.
    
    Pré-conditions :
    - motif est un argument de type string, non vide
    
    Post-conditions :
    - renvoie une liste de dictionnaires, un élément d'un dictionnaire est 
    constitué d'une clé (key) qui est une lettre du motif 
    et d'une valeur qui est son index le plus proche dans le motif.
    """

    # initialisation de la table : on le remplit avec des dictionnaires vides
    tab = []
    for i in range (len(motif)):
        tab.append({})

    # construction par compréhension :
    # tab=[{} for i in range (0, len(motif))]

    # remplissage des dictionnaires
    for i in range (len(motif)):
        for j in range (0,i):
            tab[i][motif[j]] = j

    return tab

def val_decal(tdd : list, idc : int ,car : str) -> int :
    """ Détermine la valeur du décalage du motif dans l'algorithme
    de Boyer-Moore, lorsque le caractère du texte 'car' est différent
    de celui du motif d'index 'idc'.
    
    Pré-conditions
    >>> 'tdd' : table de décalage, liste de dictionnaires
    >>> 'idc ' : index du caractère dans le motif, entier positif,
        supérieur ou égal à zéro, strictement inférieur au nombre de 
        caractères du motif
    >>> 'car' : caractère du texte en face du caractère du motif, str : une
        seule lettre

    Post-conditions
    >>> renvoie un entier positif compris entre 1 et la longueur du motif,
        inclus.
    """

    # On consulte le dictionnaire situé à l'index 'idc' dans la table 
    # de décalage
    
    # Cas 1 - le caractère du texte est une des clés du dictionnaire
    if car in tdd[idc]:

        # on renvoie une valeur de décalage calculée à partir
        # de la valeur de index et de la valeur associée à la clé 'car'
        return idc - tdd[idc][car]
    
    # Cas 2 - le caractère du texte n'est pas une des clés du dictionnair
    return idc + 1

def affiche_RTBM(t, m):
    
    occurrences = recherche_bm(m,t)
    
    if occurrences == []:
        texte = "Aucune occurrence de '" + m + "' dans le texte "
        if len(t) >= 5:
            texte += "'"+t[:5] + " ... "
            texte += t[len(t)-5:len(t)]+"'"
        texte += "\n"
        print(texte)
        
    else:
        for index in occurrences:
            
            print(">>> occurence du motif '" + m + "' à la position : " + str(index))
            
            texte = "... "
            
            debut = 0
            if index - 20 > 0:
                debut = index - 20
            
            fin = len(t)
            if index + len(m) + 20 < len(t):
                fin = index + len(m) + 20
                
            texte += t[debut : index]
            texte += " - " + m + " - "
            texte += t[index + len(m) : fin] + "...\n"
       
            print(texte)
        

def recherche_bm(m : str, t : str) -> list:
    """
    Cherche le motif 'm' dans le texte 't'.
    Affiche les index des occurrences de 'm' dans 't'.
    
    Arguments
    ----------
    m : str
        motif : chaine de caractères recherchée, non vide
    t : str
        texte : chaîne de caractères non vide
        
    Le nombre de caractères de 'm' est inférieur à celui de 't'.

    Returns
    -------
    Une liste des occurrences, liste d'entiers, chacun étant un index d'une 
    position de m dans t. 
    Liste vide si aucune occurrence

    """
    # 'occurrences' : liste des occurrences de 'm' dans 't'
    occurrences = []
    
    # 'lt' : nombre de caractères du texte
    lt = len(t)
    # 'lm' : nombre de caractères du motif
    lm = len(m)
    
    # Vérifications des préconditions
    if type(m) != str or type(t) != str or lm > lt:
        return occurrences
    
    # affectation à la variable 'dc' d'une table de décalage
    # obtenu avec la fonction table_decal(motif)
    dc = table_decal(m)

    # affectation à la variable 'idc' de la valeur 0
    # 'idc'' indique l'index du caractère dans le texte
    # où on en est rendu dans la recherche
    idc = 0

    # on parcourt le texte 't' du début (idc = 0) jusqu'à la fin
    # la fin correspond au caractère situé à l'index len(t)-len(m)
    lt = lt - lm
    
    # après chaque décalage, on parcourt le motif 'm' du dernier caractère 
    # d'index lm - 1 jusqu'au premier d'index 0
    lm = lm -1
    
    while idc <= lt :

        # on initialise une variable décalage
        # La valeur du décalage est comprise entre 1 (valeur minimale)
        # et len(m) (valeur maximale.
        decalage = 0

        # index : index du caractère dans m
        for index in range(lm,-1,-1):

            # Comparaison des caractères du texte et du motif
            if t[idc + index] != m[index]:
                # si les caractères sont différents
                # appel de la fonction 'val_decal()'
                decalage = val_decal(dc,index,t[idc + index])

                # interruption de la boucle "for"
                break

        # si la valeur de 'decalage' est toujours égale à zéro
        # cela signifie que la fonction décalage n'a pas été appelée
        # et donc qu'il y a correspondance entre toutes les lettres du
        # motif et celles du texte, donc que l'on a trouvé une occurrence.
        if decalage == 0:
            occurrences.append(idc)
            decalage = 1

        # on décale le motif
        idc += decalage
    
    # renvoie du résultat
    return occurrences

# JEU DE TESTS
if __name__ == '__main__':
    
    assert recherche_bm("che", "Recherche textuelle") == [2, 6]
    assert recherche_bm("tex", "Recherche textuelle") == [10]
    assert recherche_bm("ame", "Recherche textuelle") == []
    print(recherche_bm("elle", "Recherche textuelle"))

Programme principal

from module_boyer_moore import *

t = """Chante, déesse, du Pèlèiade Akhilleus la colère désastreuse, qui de maux infinis accabla les Akhaiens, et précipita chez Aidès tant de fortes âmes de héros, livrés eux-mêmes en pâture aux chiens et à tous les oiseaux carnassiers. Et le dessein de Zeus s’accomplissait ainsi, depuis qu’une querelle avait divisé l’Atréide, roi des hommes, et le divin Akhilleus.
Qui d’entre les dieux les jeta dans cette dissension ? Le fils de Zeus et de Lètô. Irrité contre le roi, il suscita dans l’armée un mal mortel, et les peuples périssaient, parce que l’Atréide avait couvert d’opprobre Khrysès le sacrificateur.
Et celui-ci était venu vers les nefs rapides des Akhaiens pour racheter sa fille ; et, portant le prix infini de l’affranchissement, et, dans ses mains, les bandelettes de l’Archer Apollôn, suspendues au sceptre d’or, il conjura tous les Akhaiens, et surtout les deux Atréides, princes des peuples :
– Atréides, et vous, anciens aux belles knèmides, que les dieux qui habitent les demeures olympiennes vous donnent de détruire la ville de Priamos et de vous retourner heureusement ; mais rendez-moi ma fille bien-aimée et recevez le prix de l’affranchissement, si vous révérez le fils de Zeus, l’archer Apollôn.
Et tous les Akhaiens, par des rumeurs favorables, voulaient qu’on respectât le sacrificateur et qu’on reçût le prix splendide ; mais cela ne plut point à l’âme de l’Atréide Agamemnôn, et il le chassa outrageusement, et il lui dit cette parole violente :
– Prends garde, vieillard, que je te rencontre auprès des nefs creuses, soit que tu t’y attardes, soit que tu reviennes, de peur que le sceptre et les bandelettes du dieu ne te protègent plus. Je n’affranchirai point ta fille. La vieillesse l’atteindra, en ma demeure, dans Argos, loin de sa patrie, tissant la toile et partageant mon lit. Mais, va ! ne m’irrite point, afin de t’en retourner sauf.
Il parla ainsi, et le vieillard trembla et obéit. Et il allait, silencieux, le long du rivage de la mer aux bruits sans nombre. Et, se voyant éloigné, il conjura le roi Apollôn que Lètô à la belle chevelure enfanta :
– Entends-moi, porteur de l’arc d’argent, qui protèges Khrysè et Killa la sainte, et commandes fortement sur Ténédos, Smintheus ! Si jamais j’ai orné ton beau temple, si jamais j’ai brûlé pour toi les cuisses grasses des taureaux et des chèvres, exauce mon vœu : que les Danaens expient mes larmes sous tes flèches !
Il parla ainsi en priant, et Phoibos Apollôn l’entendit ; et, du sommet Olympien, il se précipita, irrité dans son cœur, portant l’arc sur ses épaules, avec le plein carquois. Et les flèches sonnaient sur le dos du dieu irrité, à chacun de ses mouvements. Et il allait, semblable à la nuit.
Assis à l’écart, loin des nefs, il lança une flèche, et un bruit terrible sortit de l’arc d’argent. Il frappa les mulets d’abord et les chiens rapides ; mais, ensuite, il perça les hommes eux-mêmes du trait qui tue. Et sans cesse les bûchers brûlaient, lourds de cadavres.
Depuis neuf jours les flèches divines sifflaient à travers l’armée ; et, le dixième, Akhilleus convoqua les peuples dans l’agora. Hèrè aux bras blancs le lui avait inspiré, anxieuse des Danaens et les voyant périr. Et quand ils furent tous réunis, se levant au milieu d’eux, Akhilleus aux pieds rapides parla ainsi :
– Atréide, je pense qu’il nous faut reculer et reprendre nos courses errantes sur la mer, si toutefois nous évitons la mort, car, toutes deux, la guerre et la contagion domptent les Akhaiens. Hâtons-nous d’interroger un divinateur ou un sacrificateur, ou un interprète des songes, car le songe vient de Zeus. Qu’il dise pourquoi Phoibos Apollôn est irrité, soit qu’il nous reproche des vœux négligés ou qu’il demande des hécatombes promises. Sachons si, content de la graisse fumante des agneaux et des belles chèvres, il écartera de nous cette contagion.
Ayant ainsi parlé, il s’assit. Et le Thestoride Kalkhas, l’excellent divinateur, se leva. Il savait les choses présentes, futures et passées, et il avait conduit à Ilion les nefs Akhaiennes, à l’aide de la science sacrée dont l’avait doué Phoibos Apollôn. Très sage, il dit dans l’agora :
– Ô Akhilleus, cher à Zeus, tu m’ordonnes d’expliquer la colère du roi Apollôn l’archer. Je le ferai, mais promets d’abord et jure que tu me défendras de ta parole et de tes mains ; car, sans doute, je vais irriter l’homme qui commande à tous les Argiens et à qui tous les Akhaiens obéissent.
Un roi est trop puissant contre un inférieur qui l’irrite. Bien que, dans l’instant, il refrène sa colère, il l’assouvit un jour, après l’avoir couvée dans son cœur. Dis-moi donc que tu me protégeras.
Et Akhilleus aux pieds rapides, lui répondant, parla ainsi :
– Dis sans peur ce que tu sais. Non ! par Apollôn, cher à Zeus, et dont tu découvres aux Danaens les volontés sacrées, non ! nul d’entre eux, Kalkhas, moi vivant et les yeux ouverts, ne portera sur toi des mains violentes auprès des nefs creuses, quand même tu nommerais Agamemnôn, qui se glorifie d’être le plus puissant des Akhaiens.
Et le divinateur irréprochable prit courage et dit :
– Apollôn ne vous reproche ni vœux ni hécatombes ; mais il venge son sacrificateur, qu’Agamemnôn a couvert d’opprobre, car il n’a point délivré sa fille, dont il a refusé le prix d’affranchissement. Et c’est pour cela que l’archer Apollôn vous accable de maux ; et il vous en accablera, et il n’écartera point les lourdes kères de la contagion, que vous n’ayez rendu à son père bien-aimé la jeune fille aux sourcils arqués, et qu’une hécatombe sacrée n’ait été conduite à Khrysè. Alors nous apaiserons le dieu."""

m = "ion"

affiche_RTBM(t, m)
affiche_RTBM(t, "alors")

affiche_RTBM("Numérique et Sciences Informatiques", "format")
affiche_RTBM("Numérique et Sciences Informatiques", "que")
affiche_RTBM("Numérique et Sciences Informatiques", "alpha")