Erkennen von Clustern „ähnlicher“ Quellcodes

Angenommen, ich habe 400 Studenten (das ist an einer großen Universität), die ein Informatikprojekt durchführen müssen und die alleine arbeiten müssen (keine Gruppe von Studenten). Ein Beispiel für ein Projekt könnte sein, "einen schnellen Fourier-Transformations-Algorithmus in fortran zu implementieren" (ich weiß, das klingt nicht sexy, aber das macht meine Frage einfacher). Ich bin der Korrektor und möchte Routinen senden, um zu überprüfen, ob es Gruppen von Studenten gibt, die eine Implementierung vorgeschlagen haben, die "zu ähnlich sind, um wirklich unabhängig geschrieben zu werden".

Dies ist eine unbeaufsichtigte Suche nach Clustern. Ich denke, die Frage ist eher, welche Attribute verwendet werden sollen, als welcher Clustering-Algorithmus verwendet werden soll. Das erste, was ich tun würde, ist ein Buchstaben-für-Buchstaben-Histogramm. Da Betrüger klüger sind, würde ich im Idealfall gut ausgewählte zufällige Permutationen von Buchstaben ausprobieren, um festzustellen, ob eine gute Übereinstimmung des Histogramms des Buchstabens (mit Permutation) vorliegt. Auch, dass diejenigen nicht die Struktur des Codes untersuchen, sondern nur die marginale Verteilung der Buchstaben ... welche Lösung haben Sie? Gibt es vorhandene Software oder Pakete für dieses Problem? (Eigentlich behaupteten Informatiklehrer in meinen alten Tagen, sie hätten diese Art von Werkzeug, aber ich vermute jetzt, dass sie etwas sehr Einfaches hatten)

Ich denke, Anwälte aus Softwareentwicklungen haben auch solche Probleme (nicht mit 1000 Studenten, sondern mit 2 großen Codes ... was die Sache schwieriger macht)?

Der offensichtliche Vorverarbeitungsschritt besteht darin, Dateien zusammenzuführen, die wirklich identisch sind.

Danach ist der Schlüssel die Normalisierung . Irgendwann werden die Schüler anfangen, den Code umzugestalten, Variablen umzubenennen und so weiter. Oder formulieren Sie die Kommentare neu. Ein Buchstabenhistogramm ist davon zu stark betroffen (außerdem werden viele Spracheigenschaften erfasst).

Eine übliche Technik besteht darin, einen sprachspezifischen Parser zu verwenden und den Quellcode in einen abstrakten Syntaxbaum umzuwandeln. Extrahieren Sie dann Features daraus. Und vielleicht die Kommentare separat parallel analysieren.

Dann gibt es den zeilenbasierten Ansatz "längste gemeinsame Teilsequenz". Wenn Sie eine einigermaßen gute Ähnlichkeit in einzelnen Zeilen haben, können Sie nach der längsten gemeinsamen Teilfolge von zwei beliebigen Dateien suchen. Dies führt auch zu einer Reihe von Übereinstimmungen.

In der Welt der Anti-Plagiate bin ich zuvor auf den Begriff "Graph Isomorphism" gestoßen. Vielleicht können Sie sich das auch ansehen.

LCS - Longest Common Subsequence ist ebenfalls möglich. Aber versuchen Sie, all diese Lösungen zu vergleichen und herauszufinden, was das Beste ist :)