我一直在閱讀Ira D. Baxter等人的題爲Clone Detection using Abstract Syntax Trees的論文。有從紙張一個段落,我抄錄如下:使用子樹查找類似的代碼段
原則,發現樹克隆 很簡單:每個子樹比較 所有其他子樹平等。在 的實踐中,出現了幾個問題: 未遂克隆檢測,亞克隆 和規模。 ...
在定位未遂 克隆,散列的完整的子樹 失敗,正是因爲良好的散列 功能包括 樹中的所有元素,因此排序髮辮輕微 差異爲不同的桶。我們 通過選擇 人爲壞哈希函數解決了這個問題。此功能必須這樣一種方式,主要性能 人希望找到似是而非的克隆 保留特徵 。臨近想念克隆 通常通過複製和粘貼 創建程序,然後按小 修改。這些修改 通常會生成與 複製的代碼片段關聯的樹形狀的小改動。因此,我們 爭辯說,這種幾乎錯過 克隆往往只有一些不同的小子樹 。基於這個觀察, 忽略小型子樹的散列函數是一個好選擇。 在這裏介紹的實驗 ,我們使用了哈希函數 忽略只有 標識符名稱(葉樹)。 因此,我們的哈希函數把樹 是相似的模標識符 到相同的散列桶的 比較。
我試圖實施本文討論的技術,但我堅持試圖理解這一段(不幸的是在本文開頭)。我明白段落的意思,但作者沒有提到要選擇什麼樣的散列函數或如何實際散列AST。有人可以從實施的角度以一個簡單的例子來解釋嗎?
SO搜索引擎非常好,或者我非常幸運能夠得到作者的回覆。無論哪種方式,這對我來說都是雙贏的:)你的解釋澄清了我的問題。作爲最終的請求,我會在閱讀完畢後向你的論文推薦任何後續工作嗎? (在開發人員戴帽子之前,您認爲我應該熟悉這方面的任何最先進的工作)。順便說一下,一篇非常棒的論文! – Legend 2011-04-12 02:21:02
@傳奇:克隆檢測識字的好指標可以在http://students.cis.uab.edu/tairasr/clones/literature/找到。自從我的論文發表以來,寫了很多。大部分的論點是a)你如何檢測克隆,b)你如何使它很好地擴展。 Elmar Juergen的論文在縮放方面表現出色,但他放棄參數化可以很好地擴展。我很高興地說,還有其他的樹木檢測論文,但是CloneDR幾乎經受住了時間的考驗。商業版本並不像文章那樣工作,但細節將不會公佈。 – 2011-04-12 02:38:32
@Legend:如果您想聽聽最新的技術,您需要參加五月份在夏威夷舉行的軟件工程國際會議上的軟件克隆研討會。此外,它是一次旅行的絕佳選擇: - }在那裏見! – 2011-04-12 02:47:50