程式碼比對可以分為語彙層及語法層兩種比對技術。語彙層比對：以符號為單位，依兩程式之間的相同符號之多寡，決定兩者相似度語法層比對：必須將程式碼轉換成結構圖或流程圖，再將圖形依節點互相比對，找出最相似的兩個節點，決定程式相似度程式碼比對的應用方向包括協助查詢相似範例程式，加速開發速度偵測重複程式，有利程式精簡及合併偵測抄襲，利於版權維護本文將程式碼比對應用於協助程式教學。在班級眾多學生程式中，如何偵測相似寫法給予一致分數，一直是批改程式作業之困擾。本文將利用程式相似度，對學生程式作業進行分群，以輔助作業批改之給分一致性。本文將實作此程式分群系統，並評估其分群正確性。Whale(1990)綜合各種語彙及語法層的程式碼比對技術，將其大致區分為兩類：屬性比對結構比對六個數值維度比對程式相似度(Sallisetal.,1996)容積(Volume)(Halstead,1997)結構(Structure)資料相依(DataDependency)迴圈深度(NestingDepth)控制結構(ControlStructure)控制流程(ControlFlow)結構比對:以如下幾個實際系統為例MOSS(MeasureOfSoftwareSimilarity)YAP(YetAnotherPlague)JPlagSID(SoftwareIntegrityDiagnosissystem)SIM(softwareSIMilaritytester)MOSS(MeasureOfSoftwareSimilarity)(Schleimeretal.,2003)將程式的符號字串(tokenstring)，每相鄰k個符號合併成一個長度k片段(k-gram)，計算其雜湊值。程式有n個符號，將可計算出n-1個片段的雜湊值這些雜湊值集合選擇其部分子集合可形成程式的指紋(fingerprint)依照雜湊原理，不相同子串得到相同雜湊值的碰撞機率很小，因此若兩程式有一個或更多個雜湊值相同，則表示其有相同的長度k片段YAP(YetAnotherPlague)(Wise,1992)可以偵測程式中相似片段使用Running-Karp-RabinGreedy-String-Tiling(RKR-GST)演算法分為兩個階段前處理階段比對階段前處理階段移除註解和固定字串轉換大寫字母為小寫字母將同義字對應到通用格式依照呼叫順序重新排列function次序。並把第一次呼叫到的function展開，之後的呼叫則以FUN替代移除非程式語言字彙的字詞比對階段片段(tile)需為兩程式共有之子字串當一個符號成為片段一部份，將作標記(marked)，不再重複使用定義MaxM為最大匹配相似片段，表示兩程式目前找到的最大相似片段定義MinML為最小匹配長度，凡是比MinML小的片段皆忽略之GST演算法找出兩程式間最大相似片段先找出兩程式中相同而不重疊，且大於MinML的子字串再將片段能覆蓋到的符號擴大到最大數量JPlag(Precheltetal.,2002)採用GST演算法排除空白，註解，和變數命名，並將語義概念放入符號，例如用BEGIN_METHOD符號表示方法開頭大括號為一線上使用系統，程式要上傳到JPlag主機比對，再透過網頁顯示比對結果SID(SoftwareIntegrityDiagnosisSystem)(Chenetal.,2002)一種利用壓縮找尋程式相似片段的作法分為兩階段第一階段將程式轉換成符號字串第二階段則改用壓縮器(compressor)找出兩程式的相似片段可避免受大量插入無意義敘述，例如:intx=1;之干擾SIM(softwareSIMilaritytester)(Gitchell,1999)利用DNA序列排比方式來計算程式間的相似性定義每種序列排比的得分，再由動態規畫找出其中分數最高者，而得最佳排比方式。利用此最佳排比得分，可以比較兩程式相似度相似比對工具YAP最小比對長度和相似門檻值最小比對長度(MinimalMatchLength,MML)相似門檻值(THresholdofSimilarity,THS)相似度計算sFile,tFile分別是來源程式和目標程式的符號序列每一片段t之符號長度為lengtht分數大小介於0跟1之間，愈接近1表示兩程式相似性愈高單次無階層分群法隨機挑某程式作第1群找出和程式i群相似度大於THS群集合i加入群集合中最近一群若群集合為空，則i另成一群實驗方法：資料集:淡江大學資管系大學部JAVA程式課四題程式作業，每題約100份作業。其中，三題供