基于索引和序列匹配的代碼克隆檢測(cè)技術(shù)研究.pdf

1、在軟件開(kāi)發(fā)過(guò)程中，各種拷貝-粘貼-修改的編輯操作非常普遍。這種方式的代碼重用往往使得代碼基中出現(xiàn)很多重復(fù)或者相似的代碼片段，也就是所謂的克隆代碼。它雖然方便了開(kāi)發(fā)者,但是也帶來(lái)了一定的資源消耗，增加了軟件維護(hù)的難度。學(xué)術(shù)界和工業(yè)界早在上世紀(jì)90年代就開(kāi)始對(duì)代碼克隆進(jìn)行分析并研究代碼克隆的檢測(cè)方法，并且取得了不錯(cuò)的效果。但是隨著軟件規(guī)模的不斷增長(zhǎng)，先前的方法便出現(xiàn)了資源使用的瓶頸甚至無(wú)法在單機(jī)上工作。例如，由于需要把由不同公司或者組織開(kāi)發(fā)

2、的上千萬(wàn)行的軟件代碼進(jìn)行相似度的比較，如果不能在一個(gè)合適的時(shí)間范圍內(nèi)獲取代碼克隆將使檢測(cè)方法的有效性大打折扣。
　　本文在論述了傳統(tǒng)克隆代碼檢測(cè)方法的基本原理和關(guān)鍵技術(shù)的基礎(chǔ)上，提出了新的基于索引和改進(jìn)的字符序列匹配的克隆代碼檢測(cè)方法，并通過(guò)實(shí)驗(yàn)證實(shí)了本文方法在大規(guī)模軟件代碼檢測(cè)中具有較好的效果。主要工作包括：
　?。?）提出了基于索引的克隆代碼檢測(cè)方法。該方法將代碼文本依次規(guī)范化為lexeme序列和語(yǔ)句段，利用語(yǔ)句段哈希值

3、查找文本以及結(jié)構(gòu)相似的克隆代碼。由于在檢測(cè)過(guò)程中 lexeme序列被持久化，避免了重復(fù)生成中間序列和再次分段從而大大提高了檢測(cè)速度。
　?。?）提出了基于改進(jìn)的Smith-Waterman算法的代碼克隆檢測(cè)方法，即在lexeme序列表示的基礎(chǔ)上利用序列匹配算法檢測(cè)文本或者結(jié)構(gòu)相似的克隆代碼。該方法通過(guò)調(diào)整得分矩陣有效解決了傳統(tǒng) Smith-Waterman算法中存在的馬賽克問(wèn)題，同時(shí)通過(guò)改進(jìn)回溯過(guò)程可獲取最佳的局部代碼相似序列。<