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

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

中圖分類號：TP393.01 文獻標識碼：A 文章編號：1007-9599 (2012) 09-0000-02

一、前言

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

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

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

二、算法簡介

（一）定義

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

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

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

（二）計算

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

此時，數(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é)果

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

公式1-1

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

三、實現(xiàn)方法

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

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

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

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

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

（四）編寫控制層

類名功能描述

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

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

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

類名功能描述

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

MyFtpClient.javaFTP登錄和資源訪問

TextReader.java代碼獲取

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

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

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

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

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

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

3.選擇代碼文件進行相似度檢測；

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