Automatic Detection of Similarity of Programs in Karel Programming Language based on Natural Language Processing Techniques

Authors

  • Grigori Sidorov Instituto Politecnico Nacional - CIC
  • Martín Ibarra Romero Instituto Politecnico Nacional -CIC
  • Ilia Markov Instituto Politecnico Nacional -CIC
  • Rafael Guzman Cabrera Universidad de Guanajuato
  • Liliana Chanona-Hernández Instituto Politecnico Nacional - ESIME
  • Francisco Velásquez Universidad Politecnica de Querétaro

DOI:

https://doi.org/10.13053/cys-20-2-2369

Keywords:

Similarity, n-grams, program, source code, latent semantic analysis, information retrieval, natural language processing.

Abstract

In this paper, we present a method for calculating similarity between programs (source codes). One of the applications of the task is detection of code reuse, for example, in the case of plagiarism. The Karel programming language is used for experiments. In order to determine similarity between Karel programs and/or similar software solutions, we make use of techniques from the fields of natural language processing and information retrieval. These techniques use representations of documents as vectors of features and their values. Usually, the features are n-grams of words or n-grams of characters. In addition, we consider application of the latent semantic analysis for reduction  of the number of dimensions of the vector space. Finally, we use a supervised machine learning approach for classification of texts (or programs, which are texts as well) based on their similarity. For evaluation of the proposed method, two corpora were developed: the first corpus is composed of 100 different programs with a total of 9,341 source codes. The second corpus consists of 34 tasks with a total of 374 codes, which are grouped by the proposed solution. Our experiments showed that for the first corpus, the best results were obtained using trigrams of terms (words) accompanied with application of latent semantic analysis, while for the second corpus, the best representation was achieved using character trigrams.

Author Biographies

Grigori Sidorov, Instituto Politecnico Nacional - CIC

Grigori Sidorov es Doctor en Ciencias (PhD) por la Universidad Estatal Lomonosov de Moscú, Rusia, 1996. Actualmente es profesor-investigador del Laboratorio de Lenguaje Natural y Procesamiento de Texto del Centro de Investigación en Computación del Instituto Politécnico Nacional (CIC-IPN), México. Es Investigador Nacional de México (miembro del SNI) nivel 3 y miembro de la Academia Mexicana de Ciencias. Sus áreas de interés científico son lingüística computacional, procesamiento automático de textos, aplicación de métodos de aprendizaje automático a las tareas de procesamiento de lenguaje natural.

Martín Ibarra Romero, Instituto Politecnico Nacional -CIC

Martin Ibarra Romero es Licenciado en Ciencias de la Informática, por Unidad Profesional Interdisciplinaria de UPIICSA–IPN en 1986, Maestría en ciencias de la computación en el CIC-IPN en el 2013. Ha trabajado como consultor de informática por 30 años. Ha sido coordinador del diplomado .net en la dirección de cómputo académico de la UNAM por 5 años. Ha sido delegado de la olimpiada de informática del D.F. y Estado de México desde el 2003. Sus principales áreas de investigación incluyen procesamiento del lenguaje natural, lingüística computacional y recuperación de información.

Ilia Markov, Instituto Politecnico Nacional -CIC

Ilia Markov recibió su grado de Licenciado en Ingeniería Informática en 2001 de la Universidad Técnica Estatal de Kaliningrado, Rusia. Obtuvo el grado de Maestro en Ciencias de Lenguaje en 2012 de la Universidad de Algarve, Portugal. Actualmente es estudiante de doctorado en el Instituto Politécnico Nacional, Centro de Investigación en Computación, México. Sus principales áreas de investigación incluyen procesamiento del lenguaje natural, lingüística computacional y recuperación de información.

Rafael Guzman Cabrera, Universidad de Guanajuato

Rafael Guzmán-Cabrera es Profesor Titular del departamento de Ingeniería Eléctrica de la División de Ingenierías del campus Irapuato-Salamanca de la Universidad de Guanajuato desde hace 18 años, Dr. en Reconocimiento de Formas e Inteligencia Artificial por la Universidad Politécnica de Valencia, España. Miembro del grupo de NanoBioFotónica. Miembro de la Academia Mexicana de Ciencias, SNI-1.

Liliana Chanona-Hernández, Instituto Politecnico Nacional - ESIME

Liliana Chanona-Hernández es inginiera en sistemas computacionales por el Instituto Tecnológico de Tuxtla Gutierrez, Chiapas, México; recibió su grado de Maestra en Ciencias en el Centro de Investigación en Computación del Insituto Politécnico Nacional, México. Actualmente es profesora de ESIMEZ-IPN. Sus áreas de interés son procesamiento automático de lenguaje natural, lingüística computacional, minería de datos.

Francisco Velásquez, Universidad Politecnica de Querétaro

Francisco Antonio Castillo Velásquez es Licenciado en Informática por la Universidad Veracruzana y Maestro y Doctor en Ciencias de la Computación por el Instituto Politécnico Nacional. Su área de investigación es el aprendizaje automático (machine-learning) aplicado en el área del Procesamiento del Lenguaje Natural. Su tesis doctoral propuso un método innovador para la detección automática de autoría de textos para el español, y actualmente está trabajando sobre la identificación del género (sexo) de los autores en textos cortos. Estos trabajos contribuyen especialmente a tareas dentro del cómputo forense, como la detección de plagio, suplantación de identidad, etc. Ha publicado diversos artículos en revistas nacionales e internacionales, coautor de un libro y tiene una patente registrada. Obtuvo una beca para intercambio de experiencias en la Northwest University, Seattle, WA, EEUU, conociendo empresas como Microsoft (Redmond) y Google (Kirkland). A la par de su experiencia empresarial, ha sido docente en diversas universidades privadas y actualmente es Profesor Investigador de Tiempo Completo en la Universidad Politécnica de Querétaro.

Downloads

Published

2016-06-25

Issue

Vol. 20 No. 2 (2016): 20-2 (2016)

Section

Articles

License 

Hereby I transfer exclusively to the Journal "Computación y 
Sistemas", published by the Computing Research Center (CIC-IPN),
the Copyright of the aforementioned paper. I also accept that these 
rights will not be transferred to any other publication, in any other 
format, language or other existing means of developing.
I certify that the paper has not been previously disclosed or simultaneo
usly submitted to any other publication, and that it does not contain 
material whose publication would violate the Copyright or other 
proprietary rights of any person, company or institution. I certify that 
I have the permission from the institution or company where I work or 
study to publish this work.
The representative author accepts the responsibility for the publication
of this paper on behalf of each and every one of the authors. 
This transfer is subject to the following conditions:
  • The authors retain all ownership rights (such as patent rights) of this work, except for the publishing rights transferred to the CIC, through this document.
  • Authors retain the right to publish the work in whole or in part in any book they are the authors or publishers. They can also make use of this work in conferences, courses, personal web pages, and so on.
  • Authors may include working as part of his thesis, for non-profit distribution only.