Aller au contenu

TP : Détecteur de Plagiat

Contexte

Vous travaillez pour une startup EdTech qui développe un outil anti-plagiat pour les établissements scolaires. Votre mission : implémenter le moteur de recherche textuelle qui permettra de détecter les passages copiés entre différents documents.

Les outils comme Turnitin, Compilatio ou Plag.fr utilisent des algorithmes similaires à ceux que vous allez implémenter.

Objectifs

  • Implémenter l'algorithme de recherche naïve
  • Implémenter l'algorithme de Boyer-Moore simplifié
  • Comparer les performances des algorithmes
  • Construire un détecteur de plagiat fonctionnel

Partie 1 : Recherche naïve

1.1. Implémentation de base

Implémenter la fonction recherche_naive(texte, motif) qui renvoie la première position du motif dans le texte, ou -1 si le motif n'est pas trouvé.

def recherche_naive(texte, motif):
    """
    Recherche un motif dans un texte avec l'algorithme naïf.

    :param texte: (str) Le texte dans lequel chercher
    :param motif: (str) Le motif à rechercher
    :return: (int) Position de la première occurrence, ou -1 si non trouvé
    """
    # À compléter
    pass

Tests : 

>>> recherche_naive("bonjour tout le monde", "tout")
8
>>> recherche_naive("abracadabra", "abra")
0
>>> recherche_naive("python", "java")
-1

1.2. Toutes les occurrences

Modifier votre fonction pour créer recherche_naive_toutes(texte, motif) qui renvoie la liste de toutes les positions où le motif apparaît.

def recherche_naive_toutes(texte, motif):
    """
    Trouve toutes les occurrences d'un motif dans un texte.

    :param texte: (str) Le texte dans lequel chercher
    :param motif: (str) Le motif à rechercher
    :return: (list) Liste des positions de toutes les occurrences
    """
    # À compléter
    pass

Tests : 

>>> recherche_naive_toutes("abracadabra", "abra")
[0, 7]
>>> recherche_naive_toutes("aaaa", "aa")
[0, 1, 2]
>>> recherche_naive_toutes("hello", "xyz")
[]

1.3. Compteur de comparaisons

Créer une version recherche_naive_compteur(texte, motif) qui renvoie un tuple (position, nb_comparaisons) pour analyser les performances.

def recherche_naive_compteur(texte, motif):
    """
    Recherche naïve avec compteur de comparaisons.

    :return: (tuple) (position, nombre_de_comparaisons)
    """
    # À compléter
    pass

Test : 

>>> recherche_naive_compteur("abcdefghij", "hij")
(7, 10)  # Trouvé en position 7 après 10 comparaisons

Partie 2 : Algorithme de Boyer-Moore

2.1. Table des dernières occurrences

L'algorithme de Boyer-Moore utilise une table indiquant la dernière position de chaque caractère dans le motif.

Implémenter construire_table(motif) :

def construire_table(motif):
    """
    Construit la table des dernières occurrences pour Boyer-Moore.

    :param motif: (str) Le motif à analyser
    :return: (dict) Dictionnaire {caractère: dernière_position}
    """
    # À compléter
    pass

Tests : 

>>> construire_table("EXEMPLE")
{'E': 6, 'X': 1, 'M': 3, 'P': 4, 'L': 5}
>>> construire_table("abracadabra")
{'a': 10, 'b': 8, 'r': 9, 'c': 4, 'd': 6}

2.2. Implémentation de Boyer-Moore

Implémenter boyer_moore(texte, motif) en utilisant la règle du "mauvais caractère" :

def boyer_moore(texte, motif):
    """
    Recherche un motif avec l'algorithme de Boyer-Moore (règle du mauvais caractère).

    :param texte: (str) Le texte dans lequel chercher
    :param motif: (str) Le motif à rechercher
    :return: (int) Position de la première occurrence, ou -1 si non trouvé
    """
    # À compléter
    pass

Rappel de l'algorithme : 1. Comparer le motif de droite à gauche 2. En cas d'échec sur un caractère c du texte : - Si c est dans le motif, décaler pour aligner c avec sa dernière occurrence - Sinon, décaler le motif entièrement après c

Tests : 

>>> boyer_moore("voici un exemple de texte", "exemple")
9
>>> boyer_moore("abracadabra", "abra")
0
>>> boyer_moore("hello world", "xyz")
-1

2.3. Version avec compteur

Créer boyer_moore_compteur(texte, motif) pour comparer avec la recherche naïve.

Partie 3 : Comparaison des performances

3.1. Générateur de texte

Créer une fonction qui génère un texte aléatoire pour les tests :

import random

def generer_texte(longueur, alphabet="abcdefghijklmnopqrstuvwxyz"):
    """Génère un texte aléatoire de la longueur spécifiée."""
    # À compléter
    pass

3.2. Benchmark

Comparer les deux algorithmes sur différents cas :

def benchmark(texte, motif):
    """Compare les performances des deux algorithmes."""
    _, comparaisons_naive = recherche_naive_compteur(texte, motif)
    _, comparaisons_bm = boyer_moore_compteur(texte, motif)

    print(f"Texte: {len(texte)} caractères, Motif: '{motif}' ({len(motif)} car.)")
    print(f"  Naïf:        {comparaisons_naive} comparaisons")
    print(f"  Boyer-Moore: {comparaisons_bm} comparaisons")
    print(f"  Gain: {comparaisons_naive - comparaisons_bm} comparaisons économisées")

Tests à réaliser :

  1. Texte de 1000 caractères, motif de 5 caractères présent
  2. Texte de 1000 caractères, motif de 5 caractères absent
  3. Cas défavorable : texte "aaa...a" et motif "aaab"
  4. Cas favorable pour Boyer-Moore : alphabet riche et long motif

Partie 4 : Détecteur de plagiat

4.1. Classe Document

Créer une classe représentant un document texte :

class Document:
    """Représente un document textuel."""

    def __init__(self, titre, contenu):
        """
        Initialise un document.

        :param titre: (str) Titre du document
        :param contenu: (str) Contenu textuel
        """
        # À compléter
        pass

    def normaliser(self):
        """
        Normalise le contenu : minuscules, suppression de la ponctuation.

        :return: (str) Contenu normalisé
        """
        # À compléter
        pass

    def __repr__(self):
        return f"Document('{self.titre}', {len(self.contenu)} caractères)"

4.2. Détecteur de plagiat

Créer la classe principale :

class DetecteurPlagiat:
    """Détecte les passages plagiés entre documents."""

    def __init__(self, taille_minimum=20):
        """
        Initialise le détecteur.

        :param taille_minimum: (int) Taille minimale d'un passage plagié
        """
        self.documents = []
        self.taille_minimum = taille_minimum

    def ajouter_document(self, document):
        """Ajoute un document à la base."""
        # À compléter
        pass

    def rechercher_plagiat(self, document_suspect):
        """
        Recherche des passages plagiés dans un document.

        :param document_suspect: (Document) Document à analyser
        :return: (list) Liste des plagiats détectés
        """
        # À compléter
        pass

    def extraire_passages(self, texte, taille):
        """
        Extrait tous les passages de taille donnée d'un texte.

        :param texte: (str) Le texte source
        :param taille: (int) Taille des passages
        :return: (list) Liste des passages
        """
        # À compléter
        pass

4.3. Test du détecteur

# Documents originaux (base de référence)
doc1 = Document("Cours Python", """
Python est un langage de programmation interprété, multi-paradigme et
multiplateformes. Il favorise la programmation impérative structurée,
fonctionnelle et orientée objet.
""")

doc2 = Document("Cours Java", """
Java est un langage de programmation orienté objet créé par Sun Microsystems.
Il est conçu pour être portable et sécurisé.
""")

# Document suspect
suspect = Document("Devoir élève", """
Python est un langage de programmation interprété, multi-paradigme et
multiplateformes. C'est mon langage préféré car il est simple à apprendre.
""")

# Détection
detecteur = DetecteurPlagiat(taille_minimum=30)
detecteur.ajouter_document(doc1)
detecteur.ajouter_document(doc2)

resultats = detecteur.rechercher_plagiat(suspect)
for r in resultats:
    print(r)

Sortie attendue : 

Plagiat détecté !
  Source: 'Cours Python'
  Passage: 'python est un langage de programmation interprété, multi-paradigme et multiplateformes'
  Position dans le suspect: 0

Partie 5 : Améliorations (Bonus)

5.1. Score de similarité

Ajouter une méthode calculer_similarite(doc1, doc2) qui renvoie un pourcentage de similarité entre deux documents.

5.2. Interface utilisateur

Créer une interface en ligne de commande permettant : - D'ajouter des documents depuis des fichiers - De vérifier un nouveau document - D'afficher un rapport détaillé

5.3. Optimisation

Implémenter une version utilisant des n-grammes (séquences de n mots) pour une détection plus robuste au reformulation.

Barème indicatif

Partie Points
Partie 1 : Recherche naïve 4
Partie 2 : Boyer-Moore 5
Partie 3 : Comparaison 3
Partie 4 : Détecteur 6
Partie 5 : Bonus 2
Total 20

Auteur : Florian Mathieu

Licence CC BY NC

Licence Creative Commons
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.