張游杰　馬俊明　張清萍

(中國電子科技集團(tuán)公司第三十三研究所　山西 太原 030006)

?

基于文件比較的電子公文痕跡保留方法

張游杰馬俊明張清萍

(中國電子科技集團(tuán)公司第三十三研究所山西 太原 030006)

傳統(tǒng)的電子公文痕跡保留方法，在用戶對文本進(jìn)行頻繁修改時，痕跡保留結(jié)果容易變得混亂。針對這種情況，提出基于文本比較的痕跡保留方法。該方法以基于遞進(jìn)式逐字比較的最長公共子串匹配算法為核心，通過遞歸調(diào)用方式找出兩個文本的所有公共子串，并以此為基礎(chǔ)實(shí)現(xiàn)痕跡保留。分析和實(shí)驗(yàn)結(jié)果表明，該方法能夠比較真實(shí)地反映文本修改過程和用戶的修改意圖，并可以在普通計算機(jī)上快速完成萬字以內(nèi)的文本比較，適用于電子公文流轉(zhuǎn)中的痕跡保留。

電子政務(wù)痕跡保留文本比較最長公共子串

0　引　言

隨著我國信息化進(jìn)程的不斷推進(jìn)，電子政務(wù)已成為政務(wù)部門提升履行職責(zé)能力和水平的重要途徑[1]。電子公文流轉(zhuǎn)作為電子政務(wù)建設(shè)的核心和基礎(chǔ)，已成為政務(wù)部門信息化的重要內(nèi)容[2]。在電子公文流轉(zhuǎn)過程中，根據(jù)業(yè)務(wù)需求，會有不同環(huán)節(jié)的人員對其內(nèi)容進(jìn)行修改?；谛畔⑼暾浴踩苑矫娴囊?，每個人的修改痕跡必須保留[3-6]。

目前，最常用的痕跡保留方法是在客戶端使用MicrosoftWord進(jìn)行文檔編輯，并將公文保存為Word文檔，利用Word自帶的文檔修訂功能實(shí)現(xiàn)公文流轉(zhuǎn)過程中各個環(huán)節(jié)的痕跡保留[3-7]；第二種方法是在客戶端安裝WebOffice控件，公文同樣以Word文檔形式保存，利用WebOffice提供的在線修訂功能，實(shí)現(xiàn)痕跡保留[8]；第三種方法是基于ZEN的痕跡保留方法，其原理是利用JavaScript腳本分析客戶端所有對文檔的修改操作，并將這些操作歸納為增加和刪除兩種類型，然后對增加和刪除的內(nèi)容分別做出標(biāo)記，從而達(dá)到痕跡保留的目的[9]。

這些方法有一個共同特點(diǎn)：保留的痕跡是用戶的操作過程，即用戶刪除一段文本時，做一個刪除標(biāo)記，用戶增加一段文本時，做一個插入標(biāo)記。經(jīng)常有這種情況：用戶刪除一個字，然后發(fā)現(xiàn)刪除錯誤，又重新輸入這個字。雖然用戶在實(shí)質(zhì)上并沒有更改這些文字，但其痕跡保留的結(jié)果將顯示刪除和插入兩個標(biāo)記，這就造成了過度標(biāo)記。當(dāng)用戶對文本做頻繁修改時，其痕跡保留結(jié)果將顯得十分混亂。為解決此問題，本文提出一種基于文本比較的痕跡保留方法。其原理是：比較原文本和修改后的文本，得出修改后的文本是在原文本基礎(chǔ)上插入了哪些字符串，刪除了哪些字符串，最后將插入和刪除的部分分別做出標(biāo)記，進(jìn)而實(shí)現(xiàn)痕跡保留。

1　文本比較方法

常用的文本比較方法有編輯距離算法LD(LevenshteinDistance)、最長公共子序列LCS(LongestCommonSubsequences)算法、Nakatsu算法等[10-15]。其中LD算法的需要構(gòu)建一個M+2行N+2列的矩陣(其中M和N分別為需比較的兩個文本的長度)，并且從矩陣的左上依次迭代計算到右下，其空間復(fù)雜度為O(MN)[10,11]，其時間復(fù)雜度也為O(MN)[10]；LCS算法與LD算法思想上一致，其空間復(fù)雜度也為O(MN),其時間復(fù)雜度不小于O(MLog(N))[12]。這兩種方法在兩個文本均較短時比較有用，但當(dāng)文本較長時，其占用空間太大，難以適用[11]。而Nakatsu相較前兩種算法在時間和空間上有了很大的改善，但只能求解部分最長的公共子串，不能求解所有最佳匹配[11]。

這些方法常用于字符串相似度分析[10-15]，不適于電子公文痕跡保留中的文本比較。因此，本文提出一種基于最長公共子串匹配的文本比較算法，為表述方便并與LCS算法區(qū)別，命名為LCSS(LongestCommonSubstring)算法。

2　LCSS算法

2.1最長公共子串匹配算法

最長公共子串匹配的方法有動態(tài)規(guī)劃方法[15]、雙向比較方法[16]等。這里給出一種比較易于理解和程序?qū)崿F(xiàn)的遞進(jìn)式逐字比較匹配方法。如圖1所示，有兩個字符串S_1和S_2(圖1中以細(xì)實(shí)線表示)，其中S_1的長度為m,S_2的長度為n，m

圖1　最長公共子串匹配原理

第一步，如圖1(a)所示，從S_1的起始位置和S_2的起始位置開始，一個字符一個字符逐一比較，對應(yīng)位置的字符相同則記錄下來，連續(xù)相同的字符就構(gòu)成了公共子串。逐一比較完成后，可找出這種對應(yīng)關(guān)系下的所有子串，記錄其最長的一個Pmax_1，并將Pmax_1賦給P。

第二步，如圖1(b)所示，將S_1向右移一個字符位置，則S_1與S_2的對應(yīng)關(guān)系變成S_1的第1個字符對應(yīng)S_2的第2個字符，然后按照第一步所述方法逐一比較，得到這種對應(yīng)關(guān)系下的最長公共子串Pmax_2。然后S_1繼續(xù)右移，并計算Pmax_i(i為S_1右移的次數(shù)減1)， 直到S_1與S_2沒有對應(yīng)字符或?qū)?yīng)字符的總數(shù)小于等于P的長度。在此過程中，每得出一個Pmax_i,都需要比較其長度是否大于P的長度，如果大于則將Pmax_i賦給P，以保證P中保存了S_1和S_2的最長公共子串。

2.2LCSS算法工作流程

假設(shè)將修改前的文本(源文本)記為Str_1，修改后的文本(目標(biāo)文本)記為Str_2。那么，LCSS算法的工作流程如圖2所示。

圖2　LCSS算法工作過程

第一步，將Str_1作為文本1，Str_2作為文本2。

第二步,用S_1存儲文本1，S_2存儲文本2(圖2中以細(xì)實(shí)線表示)，利用上述最長公共子串匹配算法找出S_1和S_2中最長的公共子串P(圖2中以粗實(shí)線表示)，并記錄P分別在S_1和S_2中所處的開始位置和長度。此時，P會將S_1分割為L_S_1和R_S_1兩個子串，將S_2分割為L_S_2和R_S_2兩個子串,如圖2(a)所示。

第三步，如圖2(b)所示，將L_S_1和L_S_2分別作為文本1和文本2，重復(fù)第二步的過程，繼續(xù)查找其最長公共子串，并將其再次分割為兩部分, 直到?jīng)]有剩余部分或剩余部分沒有公共子串。同理R_S_1和R_S_2也需要如此處理。

第二步和第三步循環(huán)進(jìn)行，最終將產(chǎn)生S_1和S_2的一系列公共子串，如圖2(c)所示。將這些子串按其在S_1中的位置順序進(jìn)行從小到大排列，表示為P1,P2,…,Pk，此時，其在S_2中的位置也是按符合從小到大的順序。S_1中，Pi(1≤i≤k)將字符串分割為k+1段，記為D1,D2,…,Dk+1,同理，S_2中，Pi(1≤i≤k)也將字符串分割為k+1段，記為A1,A2,…,Ak+1。其中，Di(1≤i≤k+1) 和Ai(1≤i≤k+1)可以是空字符串。如圖2(c)中A1、A4和Dk+1就是空字符串。

通過Di、Ai和Pi，就可以表示出從S_1到S_2的修改痕跡：Di是被刪除的部分，Ai是被增加的部分，而Pi則是被保留的部分。

根據(jù)上述過程，LCSS算法程序流程如圖3所示。

圖3　LCSS算法程序流程圖

圖3中，LCSS()為本圖所示流程所表示的過程，通過遞歸調(diào)用實(shí)現(xiàn)所有公共子串的查找；MaxSub()為最長公共子串匹配函數(shù)，MaxSub(S_1,S_2)可求得S_1與S_2的最長公共子字符；Len()為獲取字符串長度的函數(shù)，Len(P)可求得P的長度；SubStr()為獲取子串的函數(shù)，SubStr(S_1,0,Sp2)可求得S_1的從開始到Sp1的子串，SubStr(S_1,Sp1)可求得S_1的從Sp1開始直到末尾的子串；InsertPnt()是一個過程，用于記錄Sp1,Sp2以及P的長度。

為了保存每一次查找的結(jié)果，需要定義一個結(jié)構(gòu)體，以C++語言表示為：

typedefstruct

{

longs1;

//P在Str_1中的起始位置，對應(yīng)Sp1

longs2;

//P在Str_2中的起始位置，對應(yīng)Sp2

longlen;

//P的長度，對應(yīng)Len(P)

}MAXSAMEPOINT;

然后，還需要定義一個動態(tài)鏈表，該鏈表的每個節(jié)點(diǎn)都是一個MAXSAMEPOINT。每執(zhí)行一次InsertPnt()將向動態(tài)鏈表中插入一個節(jié)點(diǎn)P，其過程是：首先根據(jù)P.s1的大小找到動態(tài)鏈表中的適當(dāng)?shù)奈恢?保證動態(tài)鏈表中每個節(jié)點(diǎn)的s1按從小到大的順序排列，然后將P插入到該位置。

圖3所示流程執(zhí)行完畢后，該動態(tài)鏈表中的節(jié)點(diǎn)就按順序保存了前文所述的Pi(1≤i≤k)，根據(jù)每個節(jié)點(diǎn)中的s1和len，就可得到Di(1≤i≤k+1)，同理，根據(jù)每個節(jié)點(diǎn)的s2和len也可得到Ai(1≤i≤k+1)。最后，利用Pi、Di和Ai對Str_2做標(biāo)記，就可以展現(xiàn)出從Str_1至Str_2的變化，從而實(shí)現(xiàn)痕跡保留。

3　LCSS算法性能分析

根據(jù)前文的描述，LCSS算法所比較的兩個文本為Str_1和Str_2，假設(shè)其長度分別為M和N，且M

3.1空間復(fù)雜度

在LCSS算法的核心是最長公共子串匹配，在匹配過程中需要分別為兩個字符串分配空間。由于每次匹配時使用的都是這兩個字符串空間，不需要重新分配，因此，LCSS算法的空間復(fù)雜度為O(M+N)。

3.2時間復(fù)雜度

根據(jù)前文的假設(shè)，最長公共子串匹配的兩個字符串為S_1和S_2，其長度分別為m和n，m

(1)

式(1)經(jīng)變換可得：

(2)

這只是最糟糕的情況，在實(shí)際的過程中可能不需完成所有的循環(huán)。在最好的情況下，S_1正好是S_2最左邊的子串，此時只需要比較m次即可。

LCSS算法還需要通過遞歸方式不斷進(jìn)行最長公共子串匹配，以找出所有的公共子串。其調(diào)用最長公共子串匹配函數(shù)的次數(shù)也不是一個固定值。

最好的情況是：S_1正好是S_2的子串，此時只需調(diào)用一次最長公共子串匹配函數(shù)即可。在這種情況下，LCSS算法的時間復(fù)雜度為O(m)。

最糟糕的情況有很多種，例如：Str_1的長度M為偶數(shù)，S_1中每個奇數(shù)位置個字符都正好與S_2中對應(yīng)位置的字符相同，每個偶數(shù)位置的字符都在S_2中找不到相同的字符，比如S_1為″azbzczdz″,S_2為″axbxcxdxxx″。這種情況下，需要調(diào)用M次最長公共子串匹配函數(shù)。

為了便于推導(dǎo)出時間復(fù)雜度公式，將調(diào)用最長公共子串匹配函數(shù)的順序做一個調(diào)整。針對此例，其調(diào)用順序調(diào)整為(以最長公共子串匹配函數(shù)中的S_1/S_2表示)：″azbzczdz″/″axbxcxdxxx″、″bzczdz″/″bxcxdxxx″、″czdz″/″cxdxxx″、″dz″/″dxxx″、″a″后的″z″/″a″后的″x″、″b″后的″z″/″b″后的″x″、″c″后的″z″/″c″后的″x″、″d″后的″z″/″d″后的″xxx″。由此，可推導(dǎo)出：

前M/2次調(diào)用，其第j(1≤j≤M/2)次調(diào)用時，S_1的長度為m=M-2(j-1)，S_2的長度為n=N-2(j-1)；后M/2-1次調(diào)用，其S_1的長度m=1,S_2的長度n=1；最后一次調(diào)用時；S_1的長度m=1，S_2的長度n=N-M+1。從而，可得出LCSS算法在這種情況下的比較次數(shù)為：

(3)

該式化簡可得：

(4)

因此，最糟糕的情況下，LCSS算法的時間復(fù)雜度為：

4　實(shí)驗(yàn)結(jié)果

4.1痕跡保留效果

例：源文本為：ABBCCCDDDDEEEFFG

目標(biāo)文本為：AXXCCCXDDDXEEXFFXXG

痕跡保留結(jié)果為：ABBXXCCCXDDDDXEEEXFFXXG

該結(jié)果中，有下劃線的是被增加的文本，有刪除線的是被刪除的文本。由此結(jié)果可看出，這種方法基本上可以反映對文本修改的真實(shí)情況。

4.2效率分析

將LCSS算法以VC6.0編程實(shí)現(xiàn)，生成一個COM組件，在html文件中使用調(diào)用該組件進(jìn)行文本比較，并利用Javascript計時。實(shí)驗(yàn)環(huán)境為：CPU為Intel四核2.4GHz，內(nèi)存為2GB，操作系統(tǒng)為WindowsXP,Web瀏覽器為IE6.0。

以三篇方案設(shè)計文本的不同版本做比較，其結(jié)果如表1所示。由此可看出，文本較短(比如一萬字以內(nèi))時，其所用時間很?。划?dāng)文本較長(如大于六萬字)時，其所用時間會隨著修改次數(shù)的增加而快速變大。

表1　文本比較結(jié)果分析表

在電子公文流轉(zhuǎn)過程中，大部分公文的文本長度都會在一萬字以內(nèi)，因此，這種方法可以適用于電子公文流轉(zhuǎn)中的痕跡保留。

5　結(jié)　語

本文提出的基于LCSS文本比較算法的電子公文痕跡保留方法，與傳統(tǒng)的方法相比，能更真實(shí)地反映用戶的修改意圖。實(shí)驗(yàn)結(jié)果表明，這種方法可以在普通計算機(jī)上快速完成萬字以內(nèi)的文本比較，適用于電子公文流轉(zhuǎn)中的痕跡保留。同時，這種方法易于理解，C、C#、Java、Javascript等編程語言均可實(shí)現(xiàn)，不需要依賴第三方控件，可廣泛應(yīng)用于各種辦公自動化和行政審批系統(tǒng)中。

[1] 孫松濤,郁禮興,鎖曉東.“2+1”的電子政務(wù)績效評估指標(biāo)體系[J].信息化建設(shè),2013(5):22-24.

[2] 馬映紅,趙卓.一種安全的電子公文流轉(zhuǎn)系統(tǒng)的研究與設(shè)計[J].計算機(jī)應(yīng)用與軟件,2011,28(4):294-297.

[3] 朱愛紅,李連,馬賽紅.在線電子文檔全文批注及痕跡保留實(shí)現(xiàn)技術(shù)研究[J].計算機(jī)應(yīng)用與軟件,2010,27(9):184-186,199.

[4] 韓曉櫻,蘭華永.基于Domino/Notes平臺的集團(tuán)公文系統(tǒng)的設(shè)計應(yīng)用[J].福建電腦,2014,30(4):131-135.

[5] 周隆明.基于LotusDomino的辦公自動化系統(tǒng)的公文留痕處理分析[J].硅谷,2008(21):49-50.

[6] 楊洋.OA系統(tǒng)中公文痕跡保留的探討[J].柳鋼科技,2007(1):51-52.

[7] 紀(jì)宏偉.Word文檔保護(hù)策略及其修改痕跡保留的方式[J].辦公自動化:綜合月刊,2011(4):33-34.

[8] 馬秀麟,朱艷濤,張倩.對作業(yè)在線評閱及其批注與痕跡保留技術(shù)的研究[J].中國教育信息化:基礎(chǔ)教育,2013(1):78-81.

[9] 王芳,李光明,郭文強(qiáng).基于ZEN的公文流轉(zhuǎn)痕跡保留的實(shí)現(xiàn)[J].商場現(xiàn)代化,2009(14):390.

[10] 姜華,韓安琪,王美佳,等.基于改進(jìn)編輯距離的字符串相似度求解算法[J].計算機(jī)工程,2014,40(1):222-227.

[11] 趙明芳,王學(xué)明,劉銳.文本比較算法分析[J].電子世界,2014(4):174.

[12] 牛永潔,張成.多種字符串相似度算法的比較研究[J].計算機(jī)與數(shù)字工程,2012,40(3):14-17.

[13] 周漢平.Levenshtein距離在編程題自動評閱中的應(yīng)用研究[J].計算機(jī)應(yīng)用與軟件,2011,28(5):209-212.

[14] 杜利峰,牛永潔.字符串相似度在自動評分系統(tǒng)中的應(yīng)用[J].電子設(shè)計工程,2011,19(7):42-44.

[15] 李健豪,章品正.相似單詞查找方法研究與實(shí)現(xiàn)[J].微計算機(jī)信息,2012(9):417-418.

[16] 王開云.兩種基于雙向比較的最長公共子串算法[J].中國工程物理研究院科技年報,2013(1):167-170.

ELECTRONICDOCUMENTSTRACESRETENTIONMETHODBASEDONTEXTCOMPARISON

ZhangYoujieMaJunmingZhangQingping

(No.33 Research Institute of China Electronics Technology Group Corporation,Taiyuan 030006,Shanxi,China)

Traditionalelectronicdocumentstracesretentionmethodiseasytomaketheretentionresultsclutterwhenusersfrequentlymodifyingthetext.Inviewofthis,weproposedatextcomparison-basedtracesretentionmethod.Themethodtakesthelongestcommonsubstringmatchingalgorithm,whichisbasedonprogressiveandverbatimcomparison,asthecore,andfindsoutallcommonsubstringsoftwotextsbythewayofrecursiveinvoking,andfurtherrealisestracesretentionbasedonthese.Analysisandexperimentalresultsshowedthatthemethodcouldquitetrulyreflectthetextamendmentprocessandtheamendingintentionofuser,andcouldcompletetextscomparisonwithintenthousandscharactersonordinarycomputerquickly.Itissuitablefortracesretentionintheflowofelectronicdocuments.

ElectronicgovernanceTracesretentionTextcomparisonLongestcommonsubstring

2014-11-17。張游杰，高工，主研領(lǐng)域：計算機(jī)應(yīng)用，系統(tǒng)集成。馬俊明，高工。張清萍，高工。

TP311.5

ADOI:10.3969/j.issn.1000-386x.2016.03.026