Detección de grupos de códigos fuente "similares"

10

Supongamos que tengo 400 estudiantes (que están en una gran universidad) que tienen que hacer un proyecto de informática y que tienen que trabajar solos (sin grupo de estudiantes). Un ejemplo de proyecto podría ser "implementar un algoritmo rápido de transformación de Fourier en fortran" (lo sé, eso no suena sexy pero eso hace que mi pregunta sea más simple). Soy el corrector y quiero enviar rutinas para verificar si hay grupos de estudiantes que han propuesto la implementación que son "demasiado similares para ser escritos de manera verdaderamente independiente".

Esta es una búsqueda no supervisada de clústeres. Creo que la pregunta es más sobre qué atributos usar en lugar de qué algoritmo de agrupamiento usar. Lo primero que haría es un histograma letra por letra. Idealmente, dado que los tramposos son más inteligentes que eso, eventualmente probaría permutaciones aleatorias de letras bien elegidas para ver si existe una buena coincidencia del histograma de la letra (con permutación). También que aquellos que no exploran la estructura del código, solo la distribución marginal de las letras ... ¿qué solución tienen? ¿Hay software o paquetes existentes dedicados a ese problema? (en realidad, en mis viejos tiempos, los profesores de informática decían que tenían ese tipo de herramienta, pero ahora sospecho que tenían algo muy simple)

Supongo que el abogado de los desarrollos de software también tiene ese tipo de problemas (no con 1000 estudiantes, sino con 2 códigos grandes ... lo que hace las cosas más difíciles).

hypothesis-testing clustering robin girard
fuente

Respuestas:

4

El paso obvio de preprocesamiento es fusionar archivos que son realmente idénticos.

Después de eso, la clave es la normalización . En algún momento, los estudiantes comenzarán a refactorizar el código, renombrar variables y demás. O reformular los comentarios. Un histograma de letras se ve demasiado afectado por esto (además capturará muchas de las propiedades del lenguaje).

Una técnica común es usar un analizador de lenguaje específico y transformar el código fuente en un árbol de sintaxis abstracta. Luego extraiga características de esto. Y quizás analice los comentarios por separado en paralelo.

Luego está el enfoque de "subsecuencia común más larga" basado en líneas. Si tiene una similitud razonablemente buena en líneas individuales, puede buscar la subsecuencia común más larga de cualquiera de los dos archivos. Esto también producirá una serie de coincidencias.

HA SALIDO - Anony-Mousse
fuente
Solo quería agregar que la subsecuencia común más larga se puede encontrar de manera eficiente utilizando árboles de sufijo o matrices de sufijo.
sebp
Gracias Anony, me gusta mucho el espíritu de tu respuesta (y la voté). Suena como verdaderas estadísticas de alta dimensión con "transformación de datos" y búsqueda de patrones extremos. ¿Qué tipo de distancia pondrías en esos árboles?
robin girard
No soy un experto en similitudes de representaciones de AST. Creo que hay una noción de "simulación" en el sentido de que un árbol es un tipo especial de subárbol del otro. Para comparar los AST, necesitaría alinearlos y contar las diferencias relativas, supongo. Tal vez no tenga en cuenta el orden de las ramas, por lo que los pedidos triviales de código no cambian los resultados. Ten en cuenta que es posible llegar al punto donde se obtiene falsos positivos, porque simplemente son n maneras de resolver el problema de manera eficiente, y se obtiene simplemente falsos positivos debido a que encontraron la solución correcta ...
Ha dejado de fumar - Anony-Mousse
0

Desde el mundo anti plagio, anteriormente me encontré con la noción de "isomorfismo gráfico". Quizás también puedas echarle un vistazo a eso.

LCS - La subsecuencia común más larga también es posible. Pero intente comparar todas estas soluciones y vea cuál es la mejor :)

Ismi Najmi
fuente
Bienvenido a este sitio! ¿Podría dar algunas referencias sobre el trabajo antes mencionado y tal vez más detalles para que los lectores puedan tener una mejor idea de cómo el isomorfismo gráfico o LCS podría resolver el problema en cuestión?
chl