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

摘要

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