Détection de clusters de codes sources «similaires»

10

Supposons que j'ai 400 étudiants (c'est dans une grande université) qui doivent faire un projet d'informatique et qu'ils doivent travailler seuls (pas de groupe d'étudiants). Un exemple de projet pourrait être laissé "implémenter un algorithme de transformée de Fourier rapide dans fortran" (je sais, cela ne semble pas sexy mais cela rend ma question plus simple). Je suis le correcteur et je veux envoyer des routines pour vérifier s'il y a des groupes d'étudiants qui ont proposé une implémentation qui est "trop ​​similaire pour être écrite de manière vraiment indépendante".

Il s'agit d'une recherche non supervisée de clusters. Je pense que la question porte davantage sur les attributs à utiliser que sur l'algorithme de clustering à utiliser. La première chose que je ferais est un histogramme lettre par lettre. Idéalement, puisque les tricheurs sont plus intelligents que cela, j'essaierais éventuellement des permutations aléatoires bien choisies de lettres pour voir s'il existe une bonne correspondance de l'histogramme des lettres (avec permutation). Aussi que ceux qui n'explorent pas la structure du code, seulement la distribution marginale des lettres ... quelle solution avez-vous? Existe-t-il des logiciels ou des packages dédiés à ce problème? (En fait, à l'époque, les professeurs d'informatique affirmaient qu'ils avaient ce type d'outil, mais je soupçonne maintenant qu'ils avaient quelque chose de très simple)

Je suppose que l'avocat des développements logiciels a également ce type de problèmes (pas avec 1000 étudiants, mais avec 2 gros codes ... ce qui rend les choses plus difficiles)?

hypothesis-testing clustering Robin Girard
la source

Réponses:

4

L'étape de prétraitement évidente consiste à fusionner des fichiers qui sont vraiment identiques.

Après cela, la clé est la normalisation . À un certain point, les élèves commenceront à refactoriser le code, à renommer les variables et autres. Ou reformulez les commentaires. Un histogramme de lettre est trop affecté par cela (en plus il capturera beaucoup de propriétés de langue).

Une technique courante consiste à utiliser un analyseur spécifique au langage et à transformer le code source en une arborescence de syntaxe abstraite. Ensuite, extrayez les fonctionnalités de cela. Et peut-être analyser les commentaires séparément en parallèle.

Ensuite, il y a l'approche basée sur la ligne "la plus longue sous-séquence commune". Si vous avez une assez bonne similitude sur des lignes simples, vous pouvez rechercher la sous-séquence commune la plus longue de deux fichiers. Cela donnera également un certain nombre de correspondances.

A QUIT - Anony-Mousse
la source
Je voulais juste ajouter que la sous-séquence commune la plus longue peut être trouvée efficacement en utilisant des arbres de suffixe ou des tableaux de suffixes.
2012
Merci Anony, j'aime vraiment l'esprit de votre réponse (et j'ai voté pour elle). Cela ressemble à de vraies statistiques de haute dimension avec une "transformation des données" et une recherche de motifs extrêmes. Quel type de distance mettriez-vous sur ces arbres?
robin girard
Je ne suis pas un expert pour la similitude des représentations AST. Je crois qu'il existe une notion de "simulation" dans le sens où un arbre est un type particulier de sous-arbre de l'autre. Pour comparer les AST, vous devez les aligner et compter les différences relatives, je suppose. Peut-être ne tenant pas compte de l'ordre des branches, les réorganisations de code triviales ne changent donc pas les résultats. Sachez que vous pourriez arriver au point où vous obtenez des faux positifs car il n'y a tout simplement pas moyen de résoudre le problème efficacement, et vous obtenez des faux positifs simplement parce qu'ils ont trouvé la bonne solution ...
A QUIT - Anony-Mousse
0

Du monde de l'anti plagiat, je suis déjà tombé sur la notion de "Graph Isomorphism". Vous pouvez peut-être y jeter un coup d'œil aussi.

LCS - La plus longue séquence commune est également possible. Mais essayez de comparer toutes ces solutions et voyez ce qui est le meilleur :)

Ismi Najmi
la source
Bienvenue sur ce site! Pourriez-vous donner quelques références sur le travail susmentionné, et peut-être plus de détails pour que les lecteurs puissent avoir une meilleure idée de la façon dont l'isomorphisme graphique ou LCS pourrait résoudre le problème actuel?
chl