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

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

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