程式的相似判斷不像文字那麼複雜，比起文字的語法來說，程式的文法更有
規則性。程式相似判斷的應用上有很多方面，在實際教學應用上，最常用來作抄
襲的檢測。但我們發現在可以參考範例的考試或作業下，可能因為修改自相同的
範例程式，因此雖然找出大量相似片段組，但有很多相似是因為參考範例本身而
相似，不具抄襲意義。另一方面，在資訊檢索領域有IDF (Inverse Document
Frequency, 反轉文件頻率法)的概念，發生頻率高的片段較不具意義，發生頻率
低的片段較具意義。因此我們提出以IDF 為主的新方法，幫助我們找出發生頻率
低的相似片段組，視為較有抄襲可能性之片段。並用開放式(open book)的一次考
試和一次作業程式來作驗證。

Similarity detection on programs is simpler than on text documents. Compared to
text documents, the grammar used in program languages is easier to define. As a
result, more and more applications are developed to detect program similarity. One
practical use of these appications is to detect plagiarism for educational purposes. In
particular, when students have test or homework on programs where they can open
books to consult the examples, they may copy from the example programs without
much thinking and rewriting. In this case, we will find many similar code tiles that are
copied from the same example but of little value in plagiarism detection. So in this
paper based on the IDF (Inverse Document Frequency) concept from information
retrieval ,we propose a new method to reduce the influence of high frequency code
tiles, and compare with traditional non-IDF result using the datasets from an
open-book program test and a homework.

第一章 緒論 1
第一節 動機與目的 1
第二節 論文貢獻 2
第三節 論文章節概要 2
第二章 文獻探討 4
第一節 屬性比對 4
第二節 結構度量(STRUCTURE METRIC) 5
第三章 相似度與抄襲的定義 11
第一節 程式碼相似度的比對 11
第二節 程式相似度的應用 11
第三節 程式相似度在抄襲的運用 12
第四章 問題定義與實驗限制 15
第一節 程式相似範圍定義 15
第二節 YAP 在可參考範例下的誤判 15
第三節 引入IDF 的概念 15
第四節 引入曾氏演算法 16
第五節 實驗限制 16
第六節 利用相似度來做抄襲判斷 17
第五章 系統架構 18
第一節 系統模組圖 19
第二節 參數設定 20
第三節 前處理：程式轉為符號序列 21
第四節 比對過程：曾氏演算法 21
第五節 評分公式 22
第六章 實驗結果分析與討論 25
第一節 能力分析 25
第二節 抄襲片段排名分析 28
第三節 召回率和準確率計算 32
第七章 結論與未來研究方向 33
表格目錄
表一 結構度量常用系統方法之比較	9
表二 結構度量常用系統能力之比較	9
表三 不同最小比對長度值下本系統與YAP的比較	26
表四 兩系統與人工的排名差異量	29
表五 考試程式用本系統和YAP做出的前40名片段	29
表六 作業程式用本系統和YAP做出的前40名片段	30
表七 召回率和準確率計算結果	32
圖形目錄
圖一：FAIDHI的六個等級程式改寫	14
圖二：系統模組圖	19
圖三：相似門檻值和有效相似門檻值區間	20
圖四：最小比對長度=7下，與第1支程式的相似度	27
圖五：最小比對長度=7下，與第8支程式的相似度	27
圖六：最小比對長度=7下，與第15支程式的相似度	28

1. P.Clough, “Plagiarism in Natural and Programming Languages: an Overview of
Current Tools and Technologies”, Department of Computer Science, University
of Sheffield, July 2000.
2. X. Chen, M. Li, B. Mckinnon and A. Seker, “A Theory of Uncheatable Program
Plagiarism Detection and Its Practical Implementation”, University of California,
Santa Barbara, May 5, 2002.
3. J.L. Donaldson, A.M. Lancaster and P.H. Sposato,” A Plagiarism Detection
System”, Proceedings of The 12 SIGCSE Technical Symposium on Computer
Science Education, p.21-25 , 1981.
4. J. A. Faidhi and S. K. Robinson, “An empirical approach for detecting program
similarity and plagiarism within a university programming environment”,
Computing in Education, (11):1:, p11-19, 1987.
5. M. Ghosh, B. Verma and A. Nguyen,” An Automatic Assessment Marking and
Plagiarism Detection “, Internation Conference on Information Techonology and
Applications 2002 Theme 5,p.274-275, 2002.
6. D. Gitchell and N. Tran, “Sim: A Utility for Detecting Similarity in Computer
Programs”, SIGCSE Bulletin (31):1, p.266-270, 1999.
7. A. Granville, “Detecting Plagiarism in Java Code”, Undergraduate Project
Dissertation , The University of Sheffield, May 04,2002.
8. S. Grier,” A Tool That Detects Plagiarism in Pascal Programs”, SIGCSE
Bulletin (13):1, p.15-20, 1981.
9. M.H. Halstead, Elements of Software Science, 1977, New York, Elsevier, 127
pages.
10. E.L. Jones, “Metrics Based Plagiarism Monitoring”, Proceedings of The 6
Annual CCSC Northeastern Conference on The Journal of Computing in Small
Colleges, p.253-261, May 2001.
11. R.J. Leach, “Using Metrics to Evaluate Student Programs”, SIGCSE Bulletin
(27):2, p41-43, June 1995.
12. G. Mishne, “Source Code Retrieval Using Conceptual Graphs”, Master of Logic
Thesis , University of Amsterdam , December 2003.
13. A. Parker and J. Hamblen, “Computer algorithms for Plagiarism Detection”,
IEEE Transactions on Education (32):2, p.94-99, May 1989.
14. L. Prechelt, G. Malpohl and M. Phlippsen,” JPlag: Finding Plagiarisms Among a
Set of Programs”, University of Karlsruhe, March 28, 2000.
15. L. Prechelt, G. Malpohl and M. Philippsen, “Finding Plagiarisms Among a Set of
Programs With JPlag”, Journal of Universal Computer Science (8):11,
p.1016-1038 , November 28, 2002.
16. S. Schleimer, D. S. Wilkerson and A. Aiken, “Winnowing: Local Algorithms for
Document Fingerprinting”, Proceedings of SIGMOD, p76-85, 2003.
17. M. L. Soffa and S.S. Robinson,” An Instructional Aid for Student Programs”,
Procceedings of The 11th SIGCSE Technical Symposium on Computer Science
Education, p.118-129, 1980.
18. S.D. Stephens, “Using Metrics to Detect Plagiarism”, Proceedings of The 7th
Annual Consortium for Computing in Small Colleges Central Plains Conference
on The Journal of Computing in Small Colleges, p.191-196, March 2001.
19. Y.H. Tseng, “Multilingual Keyword Extraction for Term Suggestion”,
Proceedings of The 21st Annual International ACM SIGIR Conference on
Research and Development in Information Retrieval, p.377-378, 1998.
20. G. Whale, “Identification of Plagiarism Similarity in Large Population”, The
Computer Journal, (33):2, p.140-146, April 1990.
21. M.J. Wise, “Detection of Similarities in Student Programs: YAP’ing Maybe
Preferable to Plague’ing”, Procceedings of The 23st SIGCSE Technical
Symposium on Computer Science Education, p.268-271, 1992.
22. M. J. Wise, “YAP3: Improved Detection of Similarities in Computer Program
and Other Texts”, Proceedings of the 27th SIGCSE Technical Symposium on
Computer Science Education, p130-134, 1996.
23. 孫士烘, “使用Edit-Distance比對C程式碼相似度”, 私立中原大學資訊工程
學系碩士論文, July 2002
24. 李昶宏, “利用序列比對演算法辨識抄襲之C 程式作業”, 國立暨南國際大
學資訊工程學系碩士論文, May 28 ,2004