Tell me more ×
Cross Validated is a question and answer site for statisticians, data analysts, data miners and data visualization experts. It's 100% free, no registration required.
up vote 9 down vote favorite
2

Assume I have 400 students (that's in a big university) that have to do a computer science project, and that they have to work alone (no group of students). An example of project could be let "implementing a fast fourier transform algorithm in fortran" (I know, that doesn't sound sexy but that makes my question simpler). I am the correcter and I want to sent routines to check if there are groups of student that have proposed implementation that are "too similar to be truly independently written".

This is unsupervised search for clusters. I think the question is more about which attributes to use rather than the which clustering algorithm to use. The first thing I would do is a letter by letter histogram. Ideally, since cheaters are smarter than that, I would eventually try well chosen random permutations of letters to see if a good matching of letter's histogram (with permutation) exists. Also that those not explore the structure of the code, only the marginal distribution of letters... what solution do you have ? are there existing software or packages dedicated to that problem ? (actually in my old days computer science teachers claimed they had that type of tool, but I now suspect that they had something very simple)

I guess lawyer from software developments have that type of issues also (not with 1000 students, but with 2 large codes... which makes things harder) ?

share|improve this question

2 Answers

up vote 4 down vote

The obvious pre-processing step is to merge files that are truly identical.

After that the key is normalization. At some point, students will start refactoring the code, renaming variables and such. Or reword the comments. A letter histogram is too much affected by this (plus it will capture a lot of the language properties).

A common technique is to use a language-specific parser and transform the source code into an abstract syntax tree. Then extract features from this. And maybe analyze the comments separately in parallel.

Then there's the line-based "longest common subsequence" approach. If you have a reasonably good similarity on single lines, you can search for the longest common subsequence of any two files. This will also yield a number of matches.

share|improve this answer
Just wanted to add that the longest common subsequence can be found efficiently using Suffix trees or suffix arrays. – sebp Jul 8 '12 at 18:28
Thanks Anony, I really like the spirit of your answer (and upvoted it). It sounds like true high dimensional statistics with "data trasformation" and search for extreme patterns. What type of distance would you put on those trees ? – robin girard Jul 8 '12 at 19:38
I'm not an expert for similarity of AST representations. I believe there is a notion of "simulation" in the sense that one tree is a special kind of subtree of the other. To compare the ASTs, you'd need to align them and count the relative differences, I guess. Maybe not taking order of branches into account, so trivial code reorderings do not change results. Be aware that you might get to the point where you get false positives because there just are n ways of solving the problem efficiently, and you get false positives just because they found the correct solution... – Anony-Mousse Jul 9 '12 at 10:42
up vote 0 down vote

From the anti plagiarism world, I previously came across the notion of "Graph Isomorphism". Maybe you can take a look at that too.

LCS - Longest Common Subsequence is possible too. But try to compare all these solutions and see what's the best :)

share|improve this answer
Welcome to this site! Could you give some references on the aforementioned work, and maybe more details so that readers could get a better idea of how graph isomorphism or LCS might solve the problem at hand? – chl♦ Mar 27 at 10:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.