Detectando clusters de códigos-fonte "semelhantes"

Suponha que eu tenho 400 estudantes (que estão em uma grande universidade) que precisam fazer um projeto de ciência da computação e que precisam trabalhar sozinhos (sem grupo de estudantes). Um exemplo de projeto poderia ser "implementando um algoritmo de transformação rápida de fourier no fortran" (eu sei, isso não soa sexy, mas simplifica minha pergunta). Sou o corretor e desejo enviar rotinas para verificar se há grupos de estudantes que propuseram a implementação "muito semelhantes para serem realmente escritos de forma independente".

Esta é uma pesquisa não supervisionada de clusters. Eu acho que a pergunta é mais sobre quais atributos usar, em vez do algoritmo de clustering a ser usado. A primeira coisa que eu faria é um histograma de letra por letra. Idealmente, como os trapaceiros são mais espertos do que isso, acabaria por tentar permutações aleatórias bem escolhidas de letras para ver se existe uma boa correspondência do histograma da letra (com permutação). Além disso, aqueles que não exploram a estrutura do código, apenas a distribuição marginal de letras ... que solução você tem? existem softwares ou pacotes existentes dedicados a esse problema? (na verdade, nos meus velhos tempos, os professores de ciência da computação alegavam ter esse tipo de ferramenta, mas agora suspeito que eles tinham algo muito simples)

Eu acho que o advogado do desenvolvimento de software também tem esse tipo de problema (não com 1000 alunos, mas com 2 códigos grandes ... o que dificulta as coisas)?

A etapa óbvia de pré-processamento é mesclar arquivos que são verdadeiramente idênticos.

Depois disso, a chave é normalização . Em algum momento, os alunos começarão a refatorar o código, renomeando variáveis ​​e assim por diante. Ou reformule os comentários. Um histograma de letra é muito afetado por isso (além disso, ele captura muitas propriedades do idioma).

Uma técnica comum é usar um analisador específico de idioma e transformar o código-fonte em uma árvore de sintaxe abstrata. Em seguida, extraia recursos disso. E talvez analise os comentários separadamente em paralelo.

Depois, há a abordagem de "subsequência comum mais longa" baseada em linhas. Se você tiver uma similaridade razoavelmente boa em linhas únicas, poderá procurar a subsequência comum mais longa de dois arquivos. Isso também produzirá um número de correspondências.

Do mundo anti-plágio, eu já me deparei com a noção de "Graph Isomorphism". Talvez você possa dar uma olhada nisso também.

LCS - Subseqüência Comum Mais Longa também é possível. Mas tente comparar todas essas soluções e veja qual é a melhor :)