文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 计算机软件及应用 > SOURCE CODE RETRIEVAL USING SEQUENCE BASED SIMILARITY
侵权投诉

SOURCE CODE RETRIEVAL USING SEQUENCE BASED SIMILARITY

can be roughly classified into four main groups, i.e., text-based, token-based, structure-based, and metrics-based.

(1) Text-based approaches

In this approach, the target source program is considered as a sequence of strings. Baker [2] described an approach that identifies all pairs of matching “parameterized” code fragments. Johnson [7] proposed an approach to extract repetitions of text and a matching mechanism using fingerprints on a substring of the source code. Although these methods achieve high performance, they are sensitive to lexical aspects, such as the presence or absence of new lines and the ordering of matching lines.

(2) Token-based approaches

In the token-based detection approach, the entire source system is transformed into a sequence of tokens, which is then analyzed to identify duplicate subsequences. A sub-string matching algorithm is generally used to find common subsequences. CCFinder [22] adopts the token-based technique to efficiently detect “copy and paste” code clones. In CCFinder, the similarity metric between two sets of source code files is defined based on the concept of “correspondence.” CP-Miner [11] uses a frequent subsequence mining technique to identify a similar sequence of tokenized statements. Token-based approaches are typically more robust against code changes compared to text-based approaches.

(3) Structure-based approaches

In this approach, a program is parsed into an abstract syntax tree (AST) or program dependency graph (PDG). Because ASTs and PDGs contain structural information about the source code, sophisticated methods can be applied to ASTs and PDGs for the clone detection. CloneDR [3] is one of the pioneering AST-based clone techniques. Wahler et al. [21] applied frequent itemset data mining techniques to ASTs represented in XML to detect clones with minor changes. DECKARD [6] also employs a tree-based approach in which certain characteristic vectors are computed to approximate the structural information within ASTs in Euclidean space.

Typically, a PDG is defined to contain the control flow and data flow information of a program. An isomorphic subgraph matching algorithm is applied to identify similar subgraphs. Komondoor et al. [8] have also proposed a tool for C programs that finds clones. They use PDGs and a program slicing technique to find clones. Krinke [10] uses an iterative approach (k-length patch matching) to determine maximal similar subgraphs. Structure-based approaches are generally robust to code changes, such as reordered, inserted, and deleted code. However, they are not scalable to large programs.

(4) Metrics-based approaches

Metrics-based approaches calculate metrics from code fragments and compare these metric vectors rather than directly comparing source code. Kontogiannis et al. [9] developed an abstract pattern matching tool to measure similarity between two programs using Markov models. Some common metrics in this approach include a set of software metrics called “fingerprinting” [7], a

58

上一页第2页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email