A Method of Checking Duplication of Programming Language Codes Based on Tree and Sequence Similarity

Abstract

The invention discloses a method for checking plagiarism of programming language codes based on tree and sequence similarity. Firstly, the two sections of program codes to be compared are preprocessed, including removing text content such as comment information, console output sentences and operators, and determining the duplicate checking method. Then build a tree according to the control structure of the program, and record the position of the variables in each leaf node in the tree; secondly, establish a sequence of relative positions for the variables in each leaf node, and based on this, look for similar variables between functions, and then find out Similar leaf nodes finally determine the similarity between two pieces of code. The method of the present invention not only removes the influence of some irrelevant information on the duplicate checking results, but also has a better duplicate checking effect for variable renaming, modifying function positions and code redundancy. Through the method of the present invention, corresponding codes can be developed The plagiarism checking system can improve the efficiency of code duplication checking, and it has the best effect in the field of computer programming teaching in colleges and universities.

Description

technical field [0001] The invention relates to the field of data analysis and processing, in particular to a method for checking duplication of programming language codes based on tree and sequence similarity. Background technique [0002] Existing methods for program code duplication check include methods based on statistics, methods based on Token, methods based on trees and methods based on graphs. Specifically, the detection accuracy of the statistics-based method is low, the method is too abstract, the anti-aliasing ability is very low, the structural characteristics of the program are not considered, and the space complexity is low; the detection accuracy of the Token-based method is low, and its accuracy is mainly Relying on the selection and extraction of Token, its anti-obfuscation ability is low, it is difficult to deal with the implantation of redundant code, it can resist the confusion of replacing variable names, modifying function locations, etc., the time and...

AI Technical Summary

Problems solved by technology

Specifically, the detection accuracy of the statistics-based method is low, the method is too abstract, the anti-aliasing ability is very low, the structural characteristics of the program are not considered, and the space complexity is low; the detection accuracy of the Token-based method is low, and its accuracy is mainly Relying on the selection and extraction of Token, its anti-obfuscation ability is low, it is difficult to deal with the implantation of redundant code, it can resist the confusion of replacing variable names, modifying function locations, etc., the time and space complexity is low, mainly based on text structure and lexical analysis ; The detection accuracy of the tree-based method is generally high, and its detection accuracy mainly depends on the degree of refinement of the tree, and its ability to resist confusion is high. The method takes into account the grammatical features, but it is difficult to deal with modifying the location of functions, statement splitting, etc., and its time and space The complexity is high, mainly due to the high cost of building trees; the detection accuracy of the graph-based method is generally high, and its accuracy depends on the degree of refinement of the graph. This method has a high anti-aliasing ability and fully takes into account the syntax of the program Semantic features can resist layout confusion, but it is difficult to resist partial data and control confusion. It has high space-time complexity and high construction cost. Subgraph matching is an NP problem.

In general, statistics-based and Token-based methods have low detection accuracy, and graph-based methods have high accuracy, but their calculation time and space complexity is high. Tree-based code duplication check method has high accuracy and time-space complexity. Low characteristics, suitable for code duplication check in the case of few data samples

Images