张游杰　马俊明　张清萍

(中国电子科技集团公司第三十三研究所　山西 太原 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