基于局部敏感性哈希的代碼相似性檢測(cè)技術(shù)研究.pdf

1、隨著社會(huì)的進(jìn)步，軟件系統(tǒng)被廣泛運(yùn)用在日常生活的各個(gè)方面，軟件系統(tǒng)的代碼量不斷提升。各類軟件系統(tǒng)都有可能面臨系統(tǒng)重構(gòu)和知識(shí)產(chǎn)權(quán)保護(hù)的需求，這就需要對(duì)于軟件系統(tǒng)源代碼進(jìn)行相似性檢測(cè)。但是，近些年提出的檢測(cè)技術(shù)對(duì)檢測(cè)效率的提升還有進(jìn)一步提高的空間。
　　本文通過(guò)將局部敏感性哈希應(yīng)用在高維源代碼關(guān)鍵信息矩陣中的近鄰搜索，從而快速的得到相似對(duì)查詢結(jié)果。源代碼會(huì)首先被進(jìn)行預(yù)處理，將源代碼轉(zhuǎn)換成q-gram的標(biāo)識(shí)序列。代碼段的q-gram標(biāo)識(shí)序

2、列集合通過(guò)基于Jplag的相似代碼塊檢測(cè)技術(shù)進(jìn)行分類并利用局部敏感性哈希算法將分類結(jié)果放置到不同的桶中，在桶中的數(shù)據(jù)會(huì)被重新組織為前綴樹(shù)形式的數(shù)據(jù)結(jié)構(gòu)。為了定位不同代碼集合中的相似代碼對(duì)，需要對(duì)查詢代碼段進(jìn)行相同的哈希運(yùn)算，可以得到相似概率大于給定閾值的代碼塊前綴樹(shù)，利用前綴樹(shù)的搜索算法對(duì)相似代碼對(duì)進(jìn)行準(zhǔn)確的定位。由于在使用局部敏感性哈希進(jìn)行分類的過(guò)程中就已經(jīng)將相似的代碼塊分到同一個(gè)桶中，所以可以有效的降低無(wú)效查找的時(shí)間成本，提高處理效