[發明專利]一種基于序列結構的程序代碼聚類方法

有效

• 申請號: 201810083403.5
• 申請日: 2018-01-29
• 公開（公告）號: CN108399193B
• 公開（公告）日: 2022-03-04
• 發明（設計）人: 李海波;童俊成;孫映川;林湯權
• 申請（專利權）人: 華僑大學
• 主分類號: G06F16/35
• 分類號: G06F16/35
• 代理公司: 廈門市首創君合專利事務所有限公司 35204
• 代理人: 張松亭

本發明公開了一種基于序列結構的程序代碼聚類方法，首以函數為單位，基于程序代碼的序列結構計算一對樣本，即兩份程序代碼之間的函數相似度；在此基礎上，再計算出兩份程序代碼的相似度與距離；對任意一個樣本空間，按上述步驟計算出任意兩份程序代碼的距離方陣后，采用凝聚型層次聚類的思想對數據進行聚類分析，在聚類過程中無需憑借人工經驗輸入閾值，而是通過樣本數據的特征自動判斷是否滿足聚類終止條件，最終得到程序代碼的聚類結果。本發明可用于程序代碼的自動聚類，如高校編程類作業的聚類等提供依據。

技術領域

本發明涉及數據分析及處理領域，特別涉及一種基于序列結構的程序代碼聚類方法。

背景技術

近年來，教育信息化的進程隨著互聯網+的快速推廣而不斷加快，在線教育與測試系統的出現為高校師生提供了一個方便快捷的作業布置與提交的平臺。另一方面，各大高校對基礎程序語言教學的重視逐漸提高，使之成為本科階段必修課程之一。而在基礎編程教學中，對于代碼編程題的考察最能體現學生掌握編程技巧與思想的程度。

程序語言與自然語言在適用領域上有明顯差異，其語言雖然都有詞法、語法規則等，但程序語言不會出現一詞多義，一義多詞的情況。程序語言只有固定的關鍵字，標識符編寫規則，功能實現結構等，所以它的識別較于自然語言更容易一些。因此，國內外出現了一些比較成熟的對程序代碼進行查重檢測的系統，如使用比較廣泛的Online Judge(OJ)系統。

現有的對程序代碼查重主要可以分為屬性計數法和程序結構度量法兩種方法。單方面只考慮屬性計數而忽略程序的結構組成，得出的代碼相似度比值準確率往往較低。并且，現有的代碼查重系統都只關注于一對代碼樣本間的相似情況，而沒有分析整個代碼樣本空間的分組情況，這樣高校教師難以知道某次編程作業在整體分布上的學生完成的情況，無法知道該次編程作業有幾種不同寫法。

發明內容

本發明的目的在于克服現有技術的不足，提出一種基于序列結構的程序代碼聚類方法，通過對序列結構的分析計算任意一組代碼之間的相似度，進而通過凝聚型層次聚類對整個代碼樣本空間進行聚類分析；在聚類過程中無需輸入經驗閾值，通過樣本數據的特征自動判斷是否滿足終止條件，最終得到聚類結果，幫助高校教師發現編程作業的分組情況，了解學生在完成該次作業中所采用的不同寫法情況。

本發明的核心思想是首先基于序列結構計算任意兩份代碼的相似度，然后利用自動層次聚類的方法對代碼進行分簇，并尋找出每一簇的聚類中心。

本發明解決其技術問題所采用的技術方案是：

步驟1，基于序列結構計算不同程序代碼間任意兩函數的相似度；

步驟1.1，去除注釋內容；去除代碼中常見的函數名(如printf，scanf，cin，cout等)，去除運算符號(算術運算符、關系運算符和邏輯運算符等)與變量類型等；

步驟1.2，計算一個函數中每一個變量的相對位置數值序列。其中，變量的相對位置為同一變量在該函數中相鄰位置之差，由變量的相對位置有序形成的序列為變量的相對位置序列；

步驟1.3，基于編輯距離(Levenshtein距離)，計算兩個函數間任意兩個字符的相似度，字符相似度公式(1)如下：

Sim(S₁,S₂)＝1-Dis(S₁,S₂)/max(|S₁|,|S₂|) (1)

其中，(S₁,S₂)為兩變量相對位置序列，Dis(S₁,S₂)為兩序列的編輯距離，max(|S₁|,|S₂|)為兩序列間長度的最大值；