| Presentation | 2013-01-23 A Proposal of Similarity Evaluation for Ordered Trees : Application to Similarity Verification of C Language Programs Huricha BAO, Mitsuru NAKATA, Qi-Wei GE, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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 propse 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | syntax tree / similarity degree / program similarity / bipartite matching |
| Paper # | MSS2012-56 |
| Date of Issue |
| Conference Information | |
| Committee | MSS |
|---|---|
| Conference Date | 2013/1/15(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Mathematical Systems Science and its applications(MSS) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A Proposal of Similarity Evaluation for Ordered Trees : Application to Similarity Verification of C Language Programs |
| Sub Title (in English) | |
| Keyword(1) | syntax tree |
| Keyword(2) | similarity degree |
| Keyword(3) | program similarity |
| Keyword(4) | bipartite matching |
| 1st Author's Name | Huricha BAO |
| 1st Author's Affiliation | Graduate School of East Asian Studies, Yamaguchi Univ.() |
| 2nd Author's Name | Mitsuru NAKATA |
| 2nd Author's Affiliation | Faculty of Education, Yamaguchi Univ. |
| 3rd Author's Name | Qi-Wei GE |
| 3rd Author's Affiliation | Faculty of Education, Yamaguchi Univ. |
| Date | 2013-01-23 |
| Paper # | MSS2012-56 |
| Volume (vol) | vol.112 |
| Number (no) | 383 |
| Page | pp.pp.- |
| #Pages | 4 |
| Date of Issue | |