基于FTP教學(xué)平臺(tái)的代碼相似度檢測(cè)的研究

摘要：本文利用FTP教學(xué)平臺(tái)，實(shí)現(xiàn)了一個(gè)代碼相似度檢測(cè)的在線應(yīng)用，所用到的最長公共子序列算法是對(duì)于文本匹配的動(dòng)態(tài)規(guī)劃。

關(guān)鍵詞：FTP；教學(xué)；代碼；相似度

中圖分類號(hào)：TP393.01 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9599 (2012) 09-0000-02

一、前言

隨著信息技術(shù)的快速發(fā)展，各大高校紛紛設(shè)置程序語言或數(shù)據(jù)庫管理等信息化課程。個(gè)別學(xué)生利用他人資源，通過簡單的復(fù)制粘貼來完成作業(yè)。為了遏制這種抄襲現(xiàn)象，教師需要花費(fèi)大量的時(shí)間來批閱作業(yè)，在一定程度上會(huì)影響教學(xué)進(jìn)度。有的抄襲文本對(duì)代碼進(jìn)行了加注釋和換行來欲蓋彌彰，可能會(huì)影響批判的準(zhǔn)確性。同時(shí)，教師在閱讀代碼時(shí)往往先要將學(xué)生的代碼下載到本地后再打開查看，如果能在線進(jìn)行閱讀就能節(jié)省一部分的時(shí)間和精力。

本文采用了最長公共子序列算法。該算法是對(duì)于文本匹配的動(dòng)態(tài)規(guī)劃[1]，目的是找出兩個(gè)序列中最長公共子序列，在媒體流的相似比較、圖形樣式的相似處理、生物基因研究等方面應(yīng)用廣泛。

在網(wǎng)絡(luò)時(shí)代中，相比于利用移動(dòng)存儲(chǔ)設(shè)備等交互方式而言，在網(wǎng)上進(jìn)行信息的傳輸更為頻繁。FTP（File Transfer Protocol），也就是文件傳輸協(xié)議，是在TCP/IP網(wǎng)絡(luò)和INTERNET上最早使用的協(xié)議之一。目前FTP服務(wù)相對(duì)成熟，將其應(yīng)用在高校的信息化知識(shí)教育中，有利于資源共享，效率提高，管理方便[2]。

二、算法簡介

（一）定義

代碼在檢測(cè)的過程中可以被提取為連續(xù)的字符串，即字符序列。

假設(shè)有序列X=x1，x2，…，xn，Y=y1，y2，…，yn。

如果有序列Z=z1，z2，…，zn以及單調(diào)遞增的整數(shù)序列m1

（二）計(jì)算

令X含有的元素?cái)?shù)量為L(X)，L(T(X，Y))記為L(X，Y)，那么

此時(shí)，數(shù)組L[X，Y]中最大的值便是X和Y的最長公共子序列的長度，依據(jù)該數(shù)組回溯，便可找出最長公共子序列。

假設(shè)X=a，b，c，d，a，c，b，Y=b，d，c，a，b，那么序列C1=b，c，d是X和Y的公共子序列，但不是最長公共子序列，而序列C2=b，c，a，b和C3=b，d，c，b都是公共子序列，并且均為最長公共子序列，長度為4。

算法的流程如圖1所示，記m=L(X)，n=L(Y)，L(i，j)為二維數(shù)組（0≤i≤m，0≤j≤n）

圖1 流程圖

（三）結(jié)果

最后，兩個(gè)序列的相似度可以用最長公共子序列的長度在整個(gè)序列中所占的百分比表示，如公式1-1[3]：

公式1-1

其中，Len（X，Y）就是序列X和序列Y的最長公共子序列的長度。

三、實(shí)現(xiàn)方法

（一）創(chuàng)建WEB項(xiàng)目

本文的FTP應(yīng)用是基于Java語言開發(fā)的Web應(yīng)用，將充分利用Java程序“一次編寫，到處運(yùn)行”(Write once，run anywhere)[4]的優(yōu)點(diǎn)，同時(shí)使用了最新的基于MVC的Web應(yīng)用開發(fā)框架Struts2[5]。

（二）添加框架和相關(guān)開發(fā)包

導(dǎo)入使用Struts2所必須的類庫，以及訪問FTP所需的Jar文件（commons-net）。

（三）設(shè)計(jì)交互頁面

（四）編寫控制層

類名功能描述

CompareAction.java調(diào)用算法以檢測(cè)代碼相似度

LoginAction.java登錄并顯示資源列表

（五）實(shí)現(xiàn)業(yè)務(wù)邏輯

類名功能描述

Comparer.java算法實(shí)現(xiàn)

MyFtpClient.javaFTP登錄和資源訪問

TextReader.java代碼獲取

四、系統(tǒng)實(shí)現(xiàn)

（一）開發(fā)環(huán)境

本系統(tǒng)在Windows環(huán)境下開發(fā)，開發(fā)工具為Eclipse3.6和Tomcat6.0，JDK版本為J2SE 6.0。

（二）功能實(shí)現(xiàn)

1.進(jìn)入檢測(cè)系統(tǒng)，使用已有賬戶訪問FTP服務(wù)；

2.讀取FTP資源列表，選擇目錄；

3.選擇代碼文件進(jìn)行相似度檢測(cè)；

4.顯示檢測(cè)結(jié)果，對(duì)照原文進(jìn)行查看。如圖2左邊顯示進(jìn)行比較的兩個(gè)代碼文件，右邊顯示經(jīng)過比較以后的相似文本序列。