- 學位論文
使用Edit-Distance比對C程式碼相似度
Compare the similarity of C source code using Edit-Distance
摘要
程式碼差異度的比對一直以來，都是由人去比對程式的程式碼是否相同，而目前一般常用的程式碼比對工具就是Diff 。但是Diff的比對並沒有考慮程式的語法結構，而得到的不是最小的差異，若將程式碼稍微的修改一下變數名稱，將上一些註解或是不影響程式結果的文字，很容易的就可以使得Diff將這些程式碼視為不同的，而這些細小的改變可以經由人輕易的判斷出來，但是電腦便不行，而這些程式碼的改變使得人們必須花上很多的時間和精力去用眼睛做判斷，為了改善這種情況我們就開始著手對程式碼的差異程度去做分析比較並且利用Edit-Distance 找出較小的差異。 而本論文就是針對C語法設計一個程式比對的系統，將相同意義但是不同表示法的語法加以改寫，因為這些程式碼所使用的時間和所佔的空間都是一樣的，雖然表示方法不一樣但代表的實際意義卻是一樣的。並且我們處理空白換行以及註解，轉換成固定格式的語法，並根據程式的名稱儲存所需的暫存檔。再將這些檔案根據程式function執行的順序建立程式碼的流程，並且根據變數之間的依賴性，和程式之間的關連性加以重寫，且將所用到的變數根據binding之後可以產生最小的Edit-Distance 為基準做變數binding，再利用字串比對的方法加以比對以得到最小的Edit-Distance，也就是程式碼之間的相似度，藉由相似度的差異，我們可以找出相似的C程式。
關鍵字
程式碼相似度並列摘要
The differences of source codes are compared by people for a long time , and the useful tools we can find is Diff. But Diff didn’t compare the syntax of source code and get the minimal difference. If we change the source code’s parameters name to difference then we will get difference result from Diff. This small change can be judged by people but without by computer. And these source codes will cost many time to judge. We started to analysis the difference of C source code using Edit-Distance for this state. In this thesis, we design a comparative system to rewrite the syntax of the same means but different expression because their cost of time and space are the same. And we deal with the space’s problems and transduce source codes to temporal files. Then we rewrite file according the code’s data flow, variable’s dependence , and code’s relationship to get the minimal Edit-Distance. Finally , we use string’s match algorithm to get the minimal Edit-Distance ( the source code’s similarity ) to find the same C source code.