유사도 평가를 위한 트리 비교 알고리즘
A Tree-Compare Algorithm for Similarity Evaluation
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
기존의 트리 비교에 관한 연구는 대부분 노드에 가중치가 있거나 레이블이 있는 트리(장식이 있는 트리)에 대해서 연구되었다. 그러나 본 연구에서는 장식이 없는 서로 다른 두개의 트리를 비교하여 유사도를 평가하는 알고리즘을 제시하고 구현한다. 본 시스템에서 제시한 트리 유사도 평가 알고리즘은 비교할 두 개의 트리를 언파서에 의해 노드 스트링으로 변환된 후, 유사도 알고리즘에 의해서 평가되며, 0.0 1.0 사이의 유사 값을 돌려준다. 본 논문의 실험 부분에서는 여러 형태의 트리를 비교 분석하였으며, 두 트리 사이에 일치되는 노드와 불일치되는 노드를 시각적으로 표현하였다. 본 연구를 활용하면, 특정한 프로그램이나 문서의 유사도 및 중복 코드 발견 등에 활용할 수가 있다.
Abstract
In the previous researches, tree comparison methods are almost studied in comparing weighted or labeled tree(decorated tree). But in this paper, we propose a tree comparison and similarity evaluation algorithm can be applied to comparison of two normal trees. The algorithm converts two trees into node string using unparser, evaluates similarity and finally return similarity value from 0.0 to 1.0. In the experiment part of this paper, we visually presented matched nodes and unmatched nodes between two trees. By using this tree similarity algorithm, we can not only evaluate similarity between two specific programs or documents but also detect duplicated code.
참고문헌 (11)
- T. H. Cormen, "Introduction to Algorithms" (1994), The MIT Press
- D. Bryant, "Building Trees, Hunting for Trees, and Comparing Trees" (1997)
- D. Robinson, "Comparison of Weighted Labelled Trees", pp.119~126 (1979), In lecture notes in mathematics,
- V. C. Bhavsar, "A Weighted-Tree Similarity Algorithm for Multi-Agent Systems in E-Business Environments"
- M. Steel, "Distributions of tree comparison metrics-some new results", 42(2), pp.126~141 (1993)
- A. H. B. ledsoe, "Molecular homology and DNA hybridization", pp.425~433 (1990)
- M. S. Waterman, "On the Similarity of Dendrograms", 73, pp.789~800 (1978)
- I. D. Baxter, "Clone Detection using Abstract Syntax Trees", pp.368~378 (1998)
- A. W. Cole, "Prototype Tree Comparison Tools for Describing File Systems" (2002)
- J. Lin, "JLex Tutorial"
- S. E. Hudson, "CUP Parser Generator for Java"