algorithm - 使用子树查找相似的代码段

Question

我一直在阅读这篇标题为 Clone Detection using Abstract Syntax Trees 的论文艾拉·D·巴克斯特 (Ira D. Baxter) 等人。我在下面转载了论文中的一段:

In principle, finding sub-tree clones is easy: compare every subtree to every other sub-tree for equality. In practice, several problems arise: near-miss clone detection, sub-clones and scale. ...

When locating near-miss clones, hashing on complete subtrees fails precisely because good hashing functions include all elements of the tree, and thus sorts tress with minor differences into different buckets. We solved this problem by choosing an artificially bad hash function. This function must be characterized in such a way that the main properties one wants to find on near-miss clones are preserved. Near miss clones are usually created by copy and paste procedures followed by small modifications. These modifications usually generate small changes to the shape of the tree associated with the copied piece of code. Therefore, we argue that this kind of near-miss clone often have only some different small sub-trees. Based on this observation, a hash function that ignores small sub-trees is a goodchoice. In the experiment presented here, we used a hash function that ignores only the identifier names (leaves in the tree). Thus our hashing function puts trees which are similar modulo identifiers into the same hash bins for comparison.

我正在尝试实现本文中讨论的技术，但一直试图理解这一段(不幸的是在本文的开头)。我理解这段话的意思，但作者没有提到要选择什么哈希函数或如何实际哈希 AST。有人可以从实现的角度用一个简单的例子来解释这个吗？

Answer 1

作者自己应该回答的阴影。 StackOverflow 不是很棒吗:-?

散列函数的要点在于，您选择哪个并不重要，只要它能将输入值均匀分布在大量桶中即可。你需要一个可以应用于整棵树的散列函数；通常的技术是以任何可能的方式序列化树(例如，通过有序树访问)，然后将哈希函数应用于由此产生的值流(树节点)。 (这个想法来自关于检测公共(public)子表达式的编译器文献，这是最初 CloneDR 的灵感来源)。如果这一点不清楚，您需要花更多的精力来了解哈希函数如何应用于复杂的数据结构。维基百科 hashing是一个很好的起点；如果这还不够，你需要找一本关于算法的书来学习。

输入哈希函数的内容由您决定。我在论文中提出的观点是，您可以计算忽略 AST 标识符叶子的哈希函数，这将导致具有相同结构但不同标识符的树散列到同一个桶。因此，相似模标识符的树很容易匹配，因为它们出现在同一个哈希桶中。

当然，整个克隆检测算法还有很多只是匹配树模标识符。您需要担心匹配参数化序列(这是论文中的重点)，报告结果，当然您需要一个高质量的语言解析器来处理您想要应用的任何语言

您可以看到 CloneDR 的结果用于多种不同的语言。