论文研究基于ZhangShasha算法的存储过程相似性匹配.pdf

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