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

張游杰　馬俊明　張清萍

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

?

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

張游杰馬俊明張清萍

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

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

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

0　引　言

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

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

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

1　文本比較方法

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

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

2　LCSS算法

2.1最長公共子串匹配算法

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

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

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

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

2.2LCSS算法工作流程

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

圖2　LCSS算法工作過程

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

第二步,用S_1存儲文本1，S_2存儲文本2(圖2中以細實線表示)，利用上述最長公共子串匹配算法找出S_1和S_2中最長的公共子串P(圖2中以粗實線表示)，并記錄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，重復第二步的過程，繼續查找其最長公共子串，并將其再次分割為兩部分, 直到沒有剩余部分或剩余部分沒有公共子串。同理R_S_1和R_S_2也需要如此處理。

第二步和第三步循環進行，最終將產生S_1和S_2的一系列公共子串，如圖2(c)所示。將這些子串按其在S_1中的位置順序進行從小到大排列，表示為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則是被保留的部分。

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

圖3　LCSS算法程序流程圖

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

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

typedefstruct

{

longs1;

//P在Str_1中的起始位置，對應Sp1

longs2;

//P在Str_2中的起始位置，對應Sp2

longlen;

//P的長度，對應Len(P)

}MAXSAMEPOINT;

然后，還需要定義一個動態鏈表，該鏈表的每個節點都是一個MAXSAMEPOINT。每執行一次InsertPnt()將向動態鏈表中插入一個節點P，其過程是：首先根據P.s1的大小找到動態鏈表中的適當的位置,保證動態鏈表中每個節點的s1按從小到大的順序排列，然后將P插入到該位置。

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

3　LCSS算法性能分析

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

3.1空間復雜度

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

3.2時間復雜度

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

(1)

式(1)經變換可得：

(2)

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

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

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

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

為了便于推導出時間復雜度公式，將調用最長公共子串匹配函數的順序做一個調整。針對此例，其調用順序調整為(以最長公共子串匹配函數中的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″。由此，可推導出：

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

(3)

該式化簡可得：

(4)

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

4　實驗結果

4.1痕跡保留效果

例：源文本為：ABBCCCDDDDEEEFFG

目標文本為：AXXCCCXDDDXEEXFFXXG

痕跡保留結果為：ABBXXCCCXDDDDXEEEXFFXXG

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

4.2效率分析

將LCSS算法以VC6.0編程實現，生成一個COM組件，在html文件中使用調用該組件進行文本比較，并利用Javascript計時。實驗環境為：CPU為Intel四核2.4GHz，內存為2GB，操作系統為WindowsXP,Web瀏覽器為IE6.0。

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

表1　文本比較結果分析表

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

5　結　語

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

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

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

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

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

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

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

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

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

[9] 王芳,李光明,郭文強.基于ZEN的公文流轉痕跡保留的實現[J].商場現代化,2009(14):390.

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

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

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

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

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

[15] 李健豪,章品正.相似單詞查找方法研究與實現[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。張游杰，高工，主研領域：計算機應用，系統集成。馬俊明，高工。張清萍，高工。

TP311.5

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