Aller au contenu

L'algorithme de Rabin-Karp☘

La fonction ord☘

Le langage Python dispose d'une fonction ord. Rechercher sur la toile à quoi correspond cette fonction.

Réponse

Commencer par lire la documentation de la fonction. Puis faîtes quelques tests.

Remarque: pour les caractères usuels, le code unicode correpond au code ASCII. Nous reparlerons du problème de représentation des caractères et d'encodage du texte dans un autre cours.
L'important pour la suite de cette page est de retenir que la fonction ord associe chaque caractère à un entier (deux caractères distincts sont associés à des entiers distincts).

Associer un entier à une chaîne☘

La fonction ord associe à chaque caractère un entier. Nous aimerions ici associer à une chaîne de caractères un entier. Pour cela, nous choisissons tout simplement d'associer à la chaîne la somme des valeurs ord(x) pour x parcourant la chaîne.

  • Écrire une telle fonction en langage Python.
def empreinte(chaine):
    """
    chaine -- de type str

    renvoie la somme des ord(x) pour x caractère de chaîne
    """
Un code possible
def empreinte(chaine):
    """
    chaine -- de type str

    renvoie la somme des ord(x) pour x caractère de chaîne
    """
    somme = 0
    for caractere in chaine: somme += ord(caractere)
    return somme

Exemple d'utilisation:

>>> empreinte("cou")
327

Note

Pour comprendre d'où vient le choix du terme "empreinte" utilisé pour nommer notre fonction, vous pouvez lire cette page wikipedia concernant les fonctions de hachage ou encore cette page concernant les sommes de contrôle.

  • Deux chaînes de caractères distinctes auront-elles des empreintes distinctes?
Solution

Non.

>>> empreinte("bb")
196
>>> empreinte("ac")
196

Une lecture de fichier texte☘

Dans cet exercice, nous allons utiliser un fichier texte contenant le texte de "Vingt mille Lieues Sous Les Mers" de Jules Verne.

Source

Ce fichier a été téléchargé sur les pages du projet Gutenberg.

Avec le code Python suivant (à exécuter depuis un fichier .py se trouvant dans le même répertoire que le fichier vingtmille.txt):

with open("vingtmille.txt", 'r') as f:
    texte = f.read()

print(texte[:100])

on récupère dans une variable de type str (nommée ici texte) l'ensemble du texte du fichier, puis on affiche dans le terminal les 100 premiers caractères de cette chaîne.

Note

La lettre 'r' utilisée en second argument de open("vingtmille.txt", 'r') signifie 'read': on ouvre le fichier en lecture seulement (on ne peut donc pas écrire dans le fichier).

  • Tester le code précédent.

Une liste de "mots"☘

Avec la fonction split de Python, nous créons une liste correspondant à peu près à la liste des mots.

Note

La fonction split crée une liste des sous-chaînes de texte séparées par des espaces.

Par exemple:

>>> "coucou les loulous.".split()
['coucou', 'les', 'loulous.'] 
>>> "Suis-je un mot (ou non ---)?".split()
['Suis-je', 'un', 'mot', '(ou', 'non', '---)?']

On voit avec ces exemples qu'il nous faudrait un traitement plus fin pour détecter réellement les mots de la langue française. Mais ce traitement (séparation des sous-chaînes en repérant les espaces) nous suffira ici.

with open("vingtmille.txt", 'r') as f:
    texte = f.read()


liste = texte.split()

print(liste[:20])

Le code précédent affiche les 20 premiers "mots" du fichier.

  • Tester le code précédent.

  • Écrire maintenant un script python
    qui crée une liste de tous les mots du fichier vingtmille.txt qui commencent par la lettre 'a'.

Un code possible
def liste_lettre(texte, lettre):
    """
    texte -- type str
    lettre -- caractère

    renvoie la liste des mots de texte commençant par lettre.
    """
    texte = texte.split()
    return [mot for mot in texte if mot[0] == lettre]


with open("vingtmille.txt", 'r') as f:
    texte = f.read()


print(liste_lettre(texte, 'a'))

split perso☘

  • Écrire une fonction lister_les_mots prenant un texte en paramètre et renvoyant la liste des "mots" comme nous l'avons vu dans l'exercice précédent avec la fonction python split (mais cette fois, vous n'avez pas droit à cette fonction split: l'objectif est d'écrire votre propre fonction split).

  • Mettre en oeuvre votre fonction lister_les_mots avec le texte du fichier vingtmille.txt.

Pseudo code

Après quelques essais avec python, vous constaterez qu'il faut tenir compte des caractères blancs mais aussi des caractères \n qui sont des caractères marquant les fins de lignes.

L ← liste vide
chaine ← chaîne vide

Pour chaque caractère x du texte:
    si le caractère x est un blanc (ou équivalent comme \n):
        soit le blanc est le blanc marquant la fin d'un mot:
            dans ce cas, chaine est un mot, on l'ajoute à L et on vide chaine (chaine ← chaîne vide)
        soit le blanc suit d'autres blancs ou fins de ligne (cas où chaine a déjà été vidée):
            dans ce cas, on poursuit son chemin sans rien faire
    sinon (le caractère x n'est pas un blanc):
        dans ce cas, on cumule x avec ce qu'il y a déjà dans chaine, c'est à dire avec 
        les caractères cumulés depuis le dernier blanc rencontré (chaine ← concaténation de chaine et x)

L est maintenant la liste des "mots".
Un code possible

Un code possible:

def lister_les_mots(texte):
    L = []
    ch = ''
    for x in texte:
        if x == ' ' or x == '\n':
            if ch == '':
                pass
            else:
                L.append(ch)
                ch = ''
        else:
            ch = ch + x
    return L


# ouverture du fichier en lecture:
with open("vingtmille.txt", 'r') as f:
    texte = f.read()


liste = lister_les_mots(texte)

# affichage des 20 premiers éléments de la liste:
print(liste[:20])

On obtient:

['JULES', 'VERNE', 'VINGT', 'MILLE', 'LIEUES', 'SOUS', 'LES', 'MERS', 
'------------------------------------------------------------------------', 
'TABLE', 'DES', 'MATIÈRES', 'PREMIÈRE', 'PARTIE', 'I', 'Un', 
'écueil', 'fuyant', 'II', 'Le']

Une liste d'empreintes☘

Écrire une fonction python créant une liste de toutes les sous-chaînes du texte du fichier vingtmille.txt de même longueur et même empreinte que le mot "compagnons".

Un code possible
def meme_empreinte(motif, texte):
    """
    texte -- type str
    motif -- type str

    renvoie la liste des sous-chaînes de texte ayant même empreinte 
    et même longueur que motif.
    """
    # on transforme le texte en liste de "mots":
    liste_mots = texte.split()
    # on sélectionne les mots du texte de même longueur que motif:
    mots_longueur_motif =  [mot for mot in liste_mots if  len(mot) == len(motif)]
    # on sélectionne les mots du texte ayant même longueur et même empreinte que motif:
    return [mot for mot in mots_longueur_motif if empreinte(mot) == empreinte(motif)]


with open("vingtmille.txt", 'r') as f:
    texte = f.read()



print(meme_empreinte('compagnons', texte))

On obtient:

['compagnons', 'cramponner', 'rencontrai', 'compagnons', 'compagnons', 'compagnons', 
'vivifiante', 'compagnons', 'compagnons', 'compagnons', 'compagnons', 'compagnons', 
'compagnons', 'compagnons', 'compagnons', 'aucunement', 'compagnons', 'aucunement', 
'aucunement', 'compagnons', 'compagnons', 'aucunement', 'attiraient', 'bondissant', 
'compagnons', 'compagnons', 'compagnons', 'compagnons', 'compagnons', 'compagnons', 
'compagnons', 'compagnons', 'compagnons', 'compagnons', 'compagnons', 'compagnons', 
'rencontrai', 'compagnons', 'compagnons', 'moment-là,', 'compagnons', 'aucunement', 
'compagnons', 'attiraient', 'compagnons', 'compagnons', 'compagnons', 'compagnons', 
'rencontrai', 'compagnons', 'compagnons', 'compagnons', 'compagnons', 'compagnons', 
'compagnons', 'compagnons', 'compagnons', 'pêche-t-on', 'compagnons', 'compagnons', 
'compagnons', 'compagnons', 'compagnons', 'craquement']

On voit ainsi que d'autres chaînes que "compagnons" ont la même empreinte.

Une autre empreinte☘

On décide maintenant que l'empreinte d'une chaîne de caractères n'est plus la somme des ord(x) pour x parcourant les caractères de la chaîne, mais la somme des carrés des ord(x).

Avec cette nouvelle empreinte, déterminer comme dans l'exercice précédent la liste des mots du fichier du texte de Jules Verne ayant même longueur et même empreinte que "compagnons".

Un code

Il nous suffit de modifier la fonction de calcul des empreintes.

def empreinte(chaine):
    """
    chaine -- de type str

    renvoie la somme des ord(x) pour x caractère de chaîne
    """
    somme = 0
    for caractere in chaine: somme += ord(caractere)*ord(caractere)
    return somme


def meme_empreinte(motif, texte):
    """
    texte -- type str
    motif -- type str

    renvoie la liste des sous-chaînes de texte ayant même empreinte 
    et même longueur que motif.
    """
    # on transforme le texte en liste de "mots":
    liste_mots = texte.split()
    # on sélectionne les mots du texte de même longueur que motif:
    mots_longueur_motif =  [mot for mot in liste_mots if  len(mot) == len(motif)]
    # on sélectionne les mots du texte ayant même longueur et même empreinte que motif:
    return [mot for mot in mots_longueur_motif if empreinte(mot) == empreinte(motif)]


with open("vingtmille.txt", 'r') as f:
    texte = f.read()



print(meme_empreinte('compagnons', texte))

On obtient:

['compagnons', 'compagnons', 'compagnons', 'compagnons', 
'compagnons', 'compagnons', 'compagnons', 'compagnons', 
'compagnons', 'compagnons', 'compagnons', 'compagnons', 
'compagnons', 'compagnons', 'compagnons', 'compagnons', 
'compagnons', 'compagnons', 'compagnons', 'compagnons', 
'compagnons', 'compagnons', 'compagnons', 'compagnons', 
'compagnons', 'compagnons', 'compagnons', 'compagnons', 
'compagnons', 'compagnons', 'compagnons', 'compagnons', 
'compagnons', 'compagnons', 'compagnons', 'compagnons', 
'compagnons', 'compagnons', 'compagnons', 'compagnons', 
'compagnons', 'compagnons', 'compagnons', 'compagnons', 
'compagnons', 'compagnons', 'compagnons', 'compagnons']

Nous voyons avec cette nouvelle fonction d'empreinte que seul le mot "compagnons" a cette fois été trouvé.

Rabin Karp☘

On a vu ci-dessus qu'une fonction d'empreinte bien choisie permettait (au moins dans certains cas) de limiter le nombre de chaînes distinctes ayant même empreinte.

Cela suggère que les notions mises en jeu précédemment pourraient être à la base d'une recherche de motif dans un texte.

C'est effectivement le cas avec l'algorithme de Rabin Karp. Nous ne rentrerons pas plus dans les détails de cet algorithme, mais vous pouvez, par exemple, lire cette page wikipedia pour en savoir plus.