基于改进编辑距离和LCS的同源性检测技术

传统基于Token的同源性检测算法存在代码变体结构化信息定位困难、模块提取、识别能力差、同源性度量精度低的问题.为此，提出了一种基于改进编辑距离和LCS（longest common sequence）的结构化识别同源性检测技术.在编辑距离（edit distance）计算中，引入交换算子，提高模块内部同源性度量精度.在LCS算法中，引入相似模块度量的最小尺寸监测机制和代码行间最大动态相关性度量，提供代码结构边界划分、模块行关联、代码有效结构化信息抽取的能力.实验证明，该方法是一种有效的基于结构化信息的同源性检测技术，其随机抽样检测结果的准确率、召回率及F值均有较优表现，且稳定性较好. 

A Homology Detection Technology Based on Improved Edit Distance and LCS

Because some problems existed in traditional token-based algorithm for homology detection in structured information location, module identification, module extraction and high precision homology measure for code variants, a structured recognition homology detection technology was proposed based on an improved edit distance algorithm and improved longest common sequence (LCS) algorithm. In the edit distance calculation, the exchange operator was introduced to improve the measurement accuracy of internal homology modules. In the LCS algorithm, a minimum size monitoring mechanism and line maximum dynamic correlation measure were introduced for similar modules, which offered the ability of code structure boundary division, module line association and structured information extraction. Experiments show that the structure information based algorithm is effective and stable for code homology detection, and the results of random sampling detection show its better performances in precision, recall rate and F values. Experiments show that the algorithm utilizing structure information for code homology detection is effective and stable, and the results of random sampling detection have better performances in precision, recall rate and F values.