基于Zhang-Shasha算法的存储过程相似性匹配

Study on similarity matching of store procedure based on Zhang-Shasha algorithm

Zhang-Shasha算法在度量有序树的距离以及相似度应用中具有独特的优势。针对学习者存储过程作业自动评估的问题,提出了一种基于Zhang-Shasha算法的存储过程相似性匹配的解决方法,关键在于如何把存储过程块转换成算法要求的有序树形式。采用词法分析和语法分析把存储过程转换成语法树,再转换成有序二叉树。通过分析转换所得的二叉树属于RB型树,Zhang-Shasha-R算法在计算此类型树的距离和相似度时具有较高的效率。分析实验结果,该方法的准确率较高,且随着实验中题量的增加,评估的准确率逐步提高。

Zhang-Shasha algorithm has a unique advantage in editing distance between ordered trees and similarity measure- ment. Aiming at the problem of automatic assessment of the learners＇ stored procedure assignments, the paper put forward a solution for similarity matching of stored procedure block based on Zhang-Shasha algorithm. It was the key that how to convert the stored procedure block to the form of ordered tree required by the algorithm. Through lexical analysis and syntax analysis it transformed the stored procedure block into the abstract syntax tree, and then further convert to an ordered binary tree. Ac- cording to the analysis, the resulting binary tree belonged to right branch tree. Zhang-Shasha-R algorithm has higher efficiency in calculating the distance and similarity of this kind of tree. The experimental results show that this method has a high accura- cy rate, and with the increasing number of exercises in the experiment, the accuracy of the assessment increases gradually.