Affiliation of Author(s):Yamaguchi Univ.
Journal:ICTCSCC
Place of Publication:Korea
Key Words:syntax tree, similarity degree, program similarity, bipartite matching
Abstract:In this paper, we deal with evaluation method of similarity of two given ordered trees. A similarity computation technique of ordered trees has been proposed, which first transforms two ordered trees respectively to two character strings and then computes the similarity of the two strings by using edit distance of the strings. With respect to this, we propose a method of similarity evaluation by finding maximum matching of the nodes with same depth without doing the transformation of ordered trees. Firstly, we compute node distance from the root for each node and construct individually a bipartite graph for the nodes with same distance. Then we find maximum matching for each bipartite graph and evaluate the similarity of ordered trees based on the number of matched nodes. Finally, we show an example by applying our method to the judgement of similarity for C language programs to show the validity of our method.
Indexed by:Research Atricle
Discipline:Engineering
First-Level Discipline:Computer Science and Technology
Document Type:JST
Volume:3
Issue:2
Page Number:78-82
ISSN No.:1745-1361
Translation or Not:no
Date of Publication:2013-07-02