基于后綴數(shù)組的克隆代碼檢測(cè)研究.pdf

1、克隆代碼是指軟件中相同或相似的源代碼段，其在軟件開(kāi)發(fā)與維護(hù)中具有重要的影響。近十年來(lái)，克隆代碼的檢測(cè)已成為軟件維護(hù)中的一項(xiàng)重要研究?jī)?nèi)容。學(xué)者們也相繼提出了許多克隆檢測(cè)方法與技術(shù)，也實(shí)現(xiàn)了一些優(yōu)秀的檢測(cè)工具。然而，隨著軟件規(guī)模不斷增大，現(xiàn)有克隆檢測(cè)技術(shù)在時(shí)空效率上仍然不高。
　　本文基于后綴數(shù)組這一簡(jiǎn)單而高效的數(shù)據(jù)結(jié)構(gòu)，結(jié)合Type-1和Type-2函數(shù)克隆的句法特征，以重點(diǎn)開(kāi)展具有低時(shí)空復(fù)雜度的克隆檢測(cè)技術(shù)的設(shè)計(jì)研究。首先，根據(jù)函

2、數(shù)克隆的相似性定義，設(shè)計(jì)相應(yīng)的詞法分析程序以消除源代碼表面上的差異，識(shí)別并標(biāo)記其中的函數(shù)或方法，進(jìn)而轉(zhuǎn)換成標(biāo)準(zhǔn)化的Token串。其次，采用前綴倍增算法構(gòu)造Token串的后綴數(shù)組。然后，根據(jù)比較單元為函數(shù)這一特征，改進(jìn)現(xiàn)有的計(jì)算最長(zhǎng)公共前綴算法，以構(gòu)造出公共函數(shù)前綴數(shù)組。接著，設(shè)計(jì)重復(fù)函數(shù)子串的查找算法，進(jìn)而檢測(cè)出Token串中所有的重復(fù)函數(shù)子串。最后，結(jié)合詞法分析階段的位置信息，以克隆群的形式過(guò)濾并反饋軟件中的函數(shù)克隆。
　　基于