如何測量兩個python代碼塊之間的相似度？

Question

許多人想要測量代碼相似性來捕捉剽竊，但是我的意圖是將一組python代碼塊（對相同編程問題的答案進行說明）分爲不同的類別並區分學生採用的不同方法。

如果您有任何想法如何實現這一目標，我將不勝感激，如果你在這裏分享它。

Answer 1

一種方法是計算函數，對象，關鍵字的數量，可能分組爲諸如分支，創建，操縱等類別，和每個類型的數量變量。不依賴於被稱爲相同名稱的方法和變量。

對於一個給定的問題，類似的方法往往會出現這些類似的分數，例如：使用決策樹的學生會有大量的分支語句，而使用決策表的學生則要低得多。

這種方法比解析代碼結構和比較結果要快得多。

Answer 2

你可以選擇任何方式你喜歡，基本上散列代碼塊的內容，並用相同的哈希地方的代碼塊同一類別。

當然，如果你定義了散列函數，那麼相似性將會非常高。例如，一個真正愚蠢的散列函數H（代碼）== 0將把所有內容放在同一個bin中。

一個棘手的問題是找到一種散列函數，它以自然意義上類似的方式對代碼塊進行分類。有大量的研究，沒有人還沒有找到更好的判斷這個比我會知道他們是否相似，當我看到他們。

你肯定不希望它依賴於佈局/縮進/空格/評論，或輕微的這些變化會有不同的分類塊，即使它們的語義內容是相同的。

還有人常用來找到重複的（或類似）代碼三大方案：

• 度量爲基礎的計劃，它通過計算度量計算各種類型符和操作數的計算哈希值。 （注意：這使用詞法標記）。這些通常只在功能級別上運行。我知道沒有基於此的實用工具。基於詞法的方案將輸入流分解爲詞位，將標識符和文字轉換爲固定的特殊常量（例如，將它們視爲未分化的），然後將N-grams（一系列N個令牌）序列。基本上這個想法有很多克隆檢測器;他們工作得很好，但也找到了愚蠢的匹配，因爲沒有任何東西與程序結構邊界一致。 序列

  return ID; } void ID (int ID) { 
  

是11克這經常發生在像語言C，但顯然不是一個有用的克隆）。其結果是誤報傾向於發生，例如，你可以在沒有人的情況下聲稱匹配。

• 基於抽象語法樹的匹配（對子樹進行散列）通過使用直接代表語言結構的AST自動將克隆與語言邊界對齊。 （我是原創論文的作者，並基於這個想法構建了一個商業產品CloneDR，請參閱我的論文）。這些工具的優點是它們可以匹配包含匹配中間不同長度的標記序列的代碼，例如，一個語句（任意大小）被替換爲另一個語句。

本文提供了各種技術的調查：http://www.cs.usask.ca/~croy/papers/2009/RCK_SCP_Clones.pdf。它表明，基於AST的克隆檢測工具似乎是最有效的克隆產物，人們認爲這些克隆是類似的代碼塊，這似乎是OP特別關注的關鍵;見表14.

[有基於圖的方案匹配控制和數據流圖。他們應該可以產生更好的比賽，但在實踐中表面上看起來效果並不好。]