Le plagiat a existé de tout temps, mais ce problème ravive aujourd'hui
l'intérêt en raison de la disponibilité croissante des documents sous forme
électronique. Il y a donc une possibilité nouvelle de détecter les plagiats
par une méthode automatique. Inversement, les plagiats deviennent plus
faciles, d'où une nécessité accrue de les détecter...
Ce projet propose de mettre en oeuvre une technique simple, souple et
générale, déjà testée et utilisée à grande échelle sur le WEB.
Ici, le mot plagiat signifie seulement une ressemblance entre deux
documents. Il s'agit avant tout de comparer des paires de documents, plus
particulièrement de fournir deux opérations élémentaires à valeurs dans
l'intervalle [0,1] mesurant le taux de ressemblancer(A,B) et le
taux d'inclusioni(A,B) de deux documents A et B arbitraires.
Les notions de ressemblance et d'inclusion sont subjectives, mais elles
doivent clairement satisfaire certains critères objectifs. En effet, on
s'attend à ce que la ressemblance d'un document avec lui-même ou le taux
d'inclusion d'un document dans un autre qui le contient soient égaux à 1.
Inversement, les taux moyens de ressemblance et d'inclusion de documents
tirés au hasard doivent rester voisin de 0.
Comparer l'ensemble des mots apparaissant dans les documents A et B est
une méthode très vite éliminée: certains mots reviennent régulièrement dans
toute langue; en particulier, deux textes grammaticalement corrects tirés au
hasard auraient un fort taux de ressemblance. Pondérer les mots par la
fréquence de leur occurrence dans une langue ne résout pas le
problème. D'une part, il faudrait partir d'une donnée de ces pondérations
(ou d'un grand ensemble de documents permettant de les calculer). De plus,
la fréquence d'un mot n'est pas une notion absolue et dépend fortement du
contexte. Par exemple, les mots “preuve” et “théorème” apparaissent
fréquemment dans des textes scientifiques mais sont plutôt rares dans les
textes littéraires. D'autre part, cette mesure n'accorde aucune importance
à l'ordre d'apparition des mots.
Une méthode simple et robuste qui corrige simultanément les deux critiques,
s'appuie sur deux remarques convergentes:
Alors que certains mots sont fréquents, il est rare de les retrouver par
hasard dans des séquences identiques. La ressemblance doit mesurer
l'arrangement des mots plutôt que leur usage: les mots sont à tout le
monde, mais les phrases appartiennent à leur auteur.
Pour prendre en compte la position relative des mots, il suffit de
considérer des sous-séquences qui se recouvrent.
Une solution consiste à associer à un document A un ensemble de motifs
en deux étapes:
Extraire du document une suite d'atomes. En général, on prendra les mots
pour atomes (mais d'autres choix sont raisonnables, par exemple les
consonnes).
Cette phase élimine les caractères de ponctuation, les espaces,
et les caractères non imprimables, et transforme toutes les lettres en
minuscules, voire en lettres non accentuées, etc...
Extraire de la suite d'atomes, toutes les séquences (sous-suites contigües)
d'une longueur d'échantillonage k fixée globalement.
On note Sk(A) ou simplement S(A) l'ensemble des séquences obtenues,
appelé aussi la signature du document A. On définit
r(A,B) =
|S(A) ∩ S(B)|
|S(A) ∪ S(B)|
i(A,B) =
|S(A) ∩ S(B)|
|S(A)|
On pourrait aussi vérifier que la distance de deux documents d(A,B)
définie par 1 −r(A,B) est une métrique, en particulier elle
satisfait l'inégalité triangulaire.
Pour une longueur d'échantillonage fixée, le temps de calcul des
opérations r et i est linéaire en la taille des arguments. Les
opérations sont donc relativement efficace.
Toutefois, pour un usage à grande échelle, avec une base de données
comportant des millions de documents, telles que celles utilisées par les
moteurs de recherche sur le WEB, il est indispensable que la comparaison de
deux documents puisse se faire en coût constant et faible, après une étape
de compilation. Pour cela, il faut diminuer la taille de la signature des
documents et accepter de perdre en précision.
Le principe est de projeter de façon uniforme la signature d'un document
vers une représentation partielle.
Une première approximation consiste à conserver toutes les séquences mais à
les projeter vers une représentation plus compacte: les entiers. Une telle
opération de projection uniforme vers les entiers n'est autre qu'une
fonction de hachage. Son effet néfaste, d'identifier les séquences ayant la
même clé de hachage est en fait relativement négligeable.
Une deuxième approximation consiste à ne retenir que les séquences
appartenant à un sous-ensemble fixé, équi-réparti dans l'ensemble de toutes
les séquences possibles. En composant si besoin le hachage avec une
permutation aléatoire (dont le but est de rendre la fonction de hachage
aléatoire donc non prévisible1), un tel ensemble peut-être simplement défini
comme composé des séquences dont les clés de hachage sont nulles modulo un
entier m fixé (déterminant l'efficacité de la projection).
Si π est la composition des deux projections décrites ci-dessus,
remplacer S par π ∘ S dans le calcul de r et i conduit à
une approximation non biaisée de r et i.
La projection uniforme permet de diminuer la taille des documents dans un
rapport fixé mais ne permet pas de ramener les signatures des documents à
une taille constante. Pour aller plus loin, il existe deux méthodes.
La première utilise une projection non uniforme.
Par exemple, on ne retient que les p séquences ayant la plus petite clé de
hachage (en les prenant toutes s'il y en a un nombre inférieur à p).
Cette projection, notée minp (p étant fixé), fournit
encore une approximation non biaisée de r(A,B) par la formule ci-dessous,
mais elle ne permet plus le calcul de i(A,B).
|
min
p
(F(A) ∪ F(B)) ∩ F(A) ∩ F(B)|
|
min
p
(F(A) ∪ F(B))|
où
⎧
⎪
⎪
⎨
⎪
⎪
⎩
F(A) =
min
p
(S(A))
F(B) =
min
p
(S(B))
La seconde méthode consiste à utiliser une suite de projections uniformes de
plus en plus fortes (πq)q∈IN telle que πq+1 (S(A))
puisse se calculer à partir de πq(S(A)) seulement. Par exemple, πq
sera une projection uniforme modulo 2q. On attribue à un document A la
paire (q, πq (S(A))) où q est le plus petit entier tel que
|πq(S(A))| ne dépasse pas une borne fixée. Comme on sait calculer une
sous-signature (q',πq'(S(A))) pour tout entier q' > q, on peut
calculer une approximation de r(A,B) et i(A,B), à partir des
sous-signatures de A et B ramenées à un même rang.
Expliquer clairement le format de représentation des données et les
algorithmes retenus.
On prendra soin d'implanter les algorithmes de façon la plus modulaire
possible: par exemple, on devra pouvoir modifier facilement tous les
paramètres, modifier une projection ou insérer une projection
supplémentaire, ou encore changer la décomposition en atomes.
On effectuera d'abord les opérations de comparaisons exactes, puis
leur versions approchées, y compris celle qui associe des signatures de
taille fixe aux fichiers.
On effectuera plusieurs sortes de tests que l'on présentera de façon
lisible.
Les premiers serviront à régler les paramètres et vérifier la relativement
faible perte en précision due aux projections successives.
On considérera certains cas pathologiques: très petits fichiers, fichiers
identiques, fichiers inclus l'un dans l'autre, etc. On traitera aussi des
fichiers réels pour lesquels on s'attend à une assez forte ressemblance, par
exemple différentes versions dans le temps d'un même fichier (gardez des
traces de votre mémoire ou de vos programmes à différentes étapes de leur
rédaction). On devrait également pouvoir vérifier la citation que les
mots sont à tout le monde, mais les phrases appartiennent à leur auteur en
mesurant les taux de ressemblance de différents textes (ou programmes)
traitant d'un même sujet, qui devrait rester faible. Par exemple, l'ensembles
des rapports ou des programmes du projet plagiat.
Enfin, on essayera l'algorithme sur un ensemble de l'ordre du millier de
documents (ou plus) que l'on récupérera par exemple sur le WEB.
On pourra rechercher dans une base de fichiers, pour un fichier donné le ou
les fichiers qui lui sont les plus ressemblants.
La ressemblance n'est pas une relation transitive. On pourra toutefois
fermer la relation de ressemblance (en se fixant un seuil de ressemblance
suffisamment élevé). On pourra alors partitionner la base en de petits
groupes de fichiers très voisins (et par exemple retrouver ainsi les
différentes versions d'un même fichier parmi des milliers d'autres).
On pourra aussi utiliser le calcul exact des sous-séquences communes à deux
fichiers pour localiser rapidement (en temps linéaire) une occurrence de ces
sous-séquences dans chacun des fichiers, puis élargir par une recherche
classique cette sous-séquence commune autant que possible.
Nevin Heintze.
Scalable Document Fingerprinting, Prooceedings of the Second USENIX
Workshop on Electronic Commerce, Oakland, California, November 18-21, 1966,
Disponible depuis:
http://www.cs.cmu.edu/afs/cs/user/nch/www/koala/main.html.
N. Shivakumar and H. Garcia-Molina.
SCAM: A Copy Detection Mechanism for Digital Documents.
Prooceedings of the 2nd International Conference on Theory and Practice of
Digital Librairies, Austin, Texas, 1995.
Disponible depuis l'url http://www-db.stanford.edu/pub/papers/scam.ps.
Le calcul des clés de hachage assure une projection en générale uniforme
(équi-répartie) des clés qui n'est pas nécessairement aléatoire.
La composition d'une fonction de hachage avec une permutation aléatoire
produit une nouvelle fonction de hachage qui est plus aléatoire (pas
totalement, car la permutation est appliquée après la fonction de hachage).
En fait, de nombreuses fonctions de hachage ont un caractère suffisamment
aléatoire pour que cela ne soit pas nécessaire, a priori. Toutefois, pour la
détection de plagiats, il est important que le publique ne connaisse pas la
clé de la projection utilisée. Comme les fonctions de hachages sont souvent
connues, voire définies en librairie, il suffit de tirer une permutation
aléatoire pour créer une nouvelle fonction de hachage inconnue du publique.