【摘要】：在互聯(lián)網(wǎng)高速發(fā)展的今天,計(jì)算機(jī)軟件越來(lái)越多的融入了我們的生活,開(kāi)源軟件源代碼的不斷增長(zhǎng)也是這個(gè)行業(yè)快速發(fā)展的原動(dòng)力之一,但是在這樣的背景下,也產(chǎn)生了源代碼抄襲、侵犯軟件著作權(quán)等一系列問(wèn)題,這時(shí)我們看到軟件同源性比對(duì)技術(shù)的研究是十分必要的。目前比較主流的軟件同源性比對(duì)技術(shù)主要有基于文本的、基于Token的、基于圖的等等,基于文本和Token的比對(duì)方法沒(méi)有考慮到源代碼的結(jié)構(gòu),使用起來(lái)比較局限,而基于圖的比對(duì)方法在圖的生成方面又顯得相對(duì)復(fù)雜,本文基于源代碼的抽象語(yǔ)法樹(shù),提出了一種考慮到代碼結(jié)構(gòu)但又相對(duì)簡(jiǎn)單的同源性比對(duì)算法。本文首先對(duì)同源性比對(duì)技術(shù)進(jìn)行了簡(jiǎn)單的介紹,隨后對(duì)基于抽象語(yǔ)法樹(shù)的同源性比對(duì)算法進(jìn)行了比較細(xì)致的分析。接著提出了本文的索引存儲(chǔ)結(jié)構(gòu),通過(guò)將比對(duì)過(guò)程轉(zhuǎn)換成兩級(jí)來(lái)減少比對(duì)次數(shù),并使用實(shí)際數(shù)據(jù)說(shuō)明了這種改進(jìn)的可行性以及對(duì)算法比對(duì)次數(shù)的有效減少�？紤]到目前計(jì)算機(jī)的CPU都是多核的,本文又提出了一種多線程的優(yōu)化方案,從而實(shí)現(xiàn)對(duì)CPU的充分利用,進(jìn)而實(shí)現(xiàn)對(duì)同源性比對(duì)效率的提升,通過(guò)這兩種優(yōu)化方案,本文實(shí)現(xiàn)了對(duì)基于抽象語(yǔ)法樹(shù)的同源性比對(duì)算法的優(yōu)化,隨后的章節(jié)設(shè)計(jì)實(shí)現(xiàn)了優(yōu)化算法的各個(gè)功能模塊。最后通過(guò)將算法的工程實(shí)現(xiàn)與比較出名的同類軟件進(jìn)行了一些準(zhǔn)確率的比對(duì)測(cè)試,表明算法的可靠性,然后對(duì)多線程的優(yōu)化方案也進(jìn)行了實(shí)際的效果驗(yàn)證。緊接著,本文對(duì)后續(xù)的研究做出了一些建設(shè)性的展望與分析。綜上所述,本文對(duì)同源性比對(duì)方面的相關(guān)研究有一定的幫助。
[Abstract]:With the rapid development of the Internet, computer software is more and more integrated into our life. The increasing source code of open source software is also one of the driving forces of the rapid development of the industry, but in this context, It also produces a series of problems, such as plagiarism of source code, infringement of software copyright and so on. At this time, we see that the research of software homology comparison technology is very necessary. At present, the mainstream software homology comparison techniques are mainly text-based, Token based, graph-based and so on. The comparison method based on text and Token does not take into account the structure of source code, so its use is relatively limited. In this paper, based on the abstract syntax tree of the source code, a simple homology matching algorithm considering the code structure is proposed. In this paper, the homology alignment technology is introduced briefly, and then the algorithm based on abstract syntax tree is analyzed in detail. Then the index storage structure of this paper is proposed to reduce the number of times of comparison by converting the comparison process into two levels. The feasibility of the improvement and the effective reduction of the times of comparison of the algorithm are illustrated by using the actual data. Considering that the current computer CPU is multi-core, this paper proposes a multi-thread optimization scheme, which can make full use of CPU and improve the efficiency of homology comparison. In this paper, the algorithm of homology alignment based on abstract syntax tree is optimized, and each functional module of the optimization algorithm is designed and implemented in the following chapters. Finally, the engineering implementation of the algorithm is compared with the well-known software of the same kind of software, which shows the reliability of the algorithm, and then the multi-thread optimization scheme is verified. Then, this paper makes some constructive outlook and analysis on the follow-up research. To sum up, this paper is helpful to the research of homology comparison.
【學(xué)位授予單位】：北京郵電大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：TP311.5

【參考文獻(xiàn)】

相關(guān)期刊論文 前4條

1 熊浩;晏海華;赫建營(yíng);趙長(zhǎng)海;;一種基于靜態(tài)詞法樹(shù)的程序相似性檢測(cè)方法[J];計(jì)算機(jī)應(yīng)用研究;2009年04期

2 張鵬;王國(guó)胤;陶春梅;羅海;;基于本體粗糙集的程序代碼相似度度量方法[J];重慶郵電大學(xué)學(xué)報(bào)(自然科學(xué)版);2008年06期

3 趙長(zhǎng)海;晏海華;金茂忠;;基于編譯優(yōu)化和反匯編的程序相似性檢測(cè)方法[J];北京航空航天大學(xué)學(xué)報(bào);2008年06期

4 張文典,任冬偉;程序抄襲判定系統(tǒng)[J];小型微型計(jì)算機(jī)系統(tǒng);1988年10期

相關(guān)碩士學(xué)位論文 前1條

1 王春暉;程序代碼抄襲檢測(cè)中串匹配算法的研究與實(shí)現(xiàn)[D];內(nèi)蒙古師范大學(xué);2008年

，

本文編號(hào)：2307039