一种基于动态规划技术的复杂文档比较方法

摘要

本发明为一种基于动态规划技术的复杂文档比较方法，用于对比文档A及文档B，包括以下步骤：将要比较的两份文档按照区域分成若干份，在每个区域内部，按照区域进行分割，区域的分割根据段落层及元素层，并将相似的段落层进行元素层比较，并得出结果，将步骤3中的结果进行整理形成结果集，对包含有段落、页眉页脚、内嵌文本框等复杂结构的文档，以分区域、分层次的方式将文档进行拆分，按照区域进行对应；对应区域内部包含的文字、图形、图片等复杂元素，进行统一化处理，再结合动态规划算法进行比较，得出差异部分，实现高效的复杂文档比较。

说明书

技术领域

本发明涉及文档处理技术领域，具体为一种基于动态规划技术的复杂文档比较方法。

背景技术

现有的文档比较技术，是基于字符的全文比对，无法实现对文档中页眉、页脚等文档结构的处理；也无法兼容包含有图片、图形、文本框以及文本样式等复杂元素的处理；且在处理时，若文档内容较多时，对临时性存储空间的要求极大，速度较慢。

发明内容

(一)解决的技术问题

针对现有技术的不足，本发明提供了一种解决文档中文本外的其他复杂元素的兼容性问题，使文档无需经过处理即可直接比较的基于动态规划技术的复杂文档比较方法。

(二)技术方案

为实现上述目的，本发明提供如下技术方案：一种基于动态规划技术的复杂文档比较方法，用于对比文档A及文档B，包括以下步骤：

步骤1、将要比较的两份文档按照区域分成若干份，文档A的每个区域与文档B的对应区域进行比较。

步骤2、在每个区域内部，按照区域进行分割，区域的分割根据段落层及元素层，段落层拥有行距、字间距属性；段落层包含有若干文本、图片及文本框元素，每种元素拥有自己的属性，共同构成元素层。

步骤3、对段落层进行比较，并得出段落层的比较中文字相似度阀值，并将相似的段落层进行元素层比较，并得出结果。

步骤4、将步骤3中的结果进行整理形成结果集。

本发明改进有，所述步骤1中，文档A及文档B分为页眉、页脚、标题、正文部分。

本发明改进有，所述步骤3中的段落层的比较具体步骤如下：

步骤3-1、将文档A区域中含有的段落层编入段落链表A1，将文档B区域中含有的段落层全部编入段落链表A2；

步骤3-2、将A1和A2进行纯文本的最长子序列的获取，获取的比较算法使用获取相似度的方式，若相似度高于预先设定的相似度阈值，则认定为两段落为同一段落，

步骤3-3，同一段落中，N为当前元素在A1中的序号，M为当前元素在A2中的序号，将A1(0-N)和A2(0-M)的元素分别存入链表B1和B2，并进行相识度的比较，判定为相同段落的标记为SAME，其余部分标记为NORMAL；

步骤3-4，B1和B2即为以相似度阈值为基础的包含有文档A和文档B的最长子序列信息的结果集，标记为SAME的部分即段落层级上相同的部分，将B1与B2中，标记为SAME的对应元素，进行格式比较，得到格式差异G1。

本发明改进有，所述元素层的比较具体步骤如下：

步骤4-1，根据字词或字符为基础单位，将B1和B2中标记为SAME的部分取出，按照段落比较的结果一一对应，存入C[X][2]的数组；

步骤4-2，以0-X为变量循环处理该数组，将C[0][0]以字词/字符为元素，拆分得到链表C1；将C[0][1]以字词/字符为元素，拆分得到链表C2；拆分时如若遇到图片、文本框等其他元素，以标识符的形式记录到链表中；

步骤4-3，拆分完成后，将C1和C2进行纯文本的最长子序列的获取，比较算法中使用文本全等认定为相同的方式进行比较，若遇到特殊元素标识符，特殊元素与文本元素之间认定为不等，特殊元素之间则根据元素种类与属性进行比较；对于文本框等内部包含有文本的特殊元素，内部文本也按照规则拆分然后比较，比较完成后，得到标记有SAME和NORMAL的结果链表D1、D2，将D1与D2中，标记为SAME的对应元素，进行格式比较，得到格式差异G2。

本发明改进有，步骤4中结构整理具体如下：对B1、B2、D1、D2、G1、G2进行整理：将B1中标记为NORMAL的部分存入链表R，并标记为DELETE；B2中标记为NORMAL的部分存入R，标记为INSERT；B1和B2中标记为SAME的部分，结合G1，对段落的格式差异进行标记；D1中标记为NORMAL的部分存入R，标记为DELETE，D2中标记为NORMAL的部分存入R，标记为INSERT；D1和D2中标记为SAME的部分，结合G2，对元素的格式差异进行标记，得到的链表R。

(三)有益效果

与现有技术相比，本发明提供了一种基于动态规划技术的复杂文档比较方法，具备以下有益效果：

在适应性方面，传统的处理方式无法解决复杂结构多元素混杂排版的复杂文档的比较，只能将复杂结构和元素去除后，提取出文本部分进行比较，然后再还原。技术复杂且效率低下。本方法解决了复杂结构和多元素的适应性问题，简化了整个流程。

在性能方面，传统方式所需的时间、空间复杂度均为两文档字符数的乘积，对机器性能和存储空间有较高要求。本方法通过分层拆分的方式，将所需资源压缩到的最小区域内部的字符数乘积，提升了性能表现并缩减了空间占用。

附图说明

图1为本发明的方法流程图；

图2为本发明段落层比较流程图；

图3为本发明的结果找整理流程图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

请参阅图1-3，一种基于动态规划技术的复杂文档比较方法，包括以下步骤：

第一步，将要比较的两份文档按照区域分成若干份，如页眉、页脚、标题、正文等部分。在比较时，文档1的每个区域只与文档2的对应区域进行比较。

第二步，在每个区域内部，按照区域进行分割，然后进行比较，下面以正文区域为例，详细描述这个过程。

正文包含若干段落，段落本身拥有行距、字间距等属性；段落包含有若干文本、图片、文本框等元素，每种元素也都拥有自己的属性。在比较时，由上至下分为：段落、元素两层，逐层进行比较，其他区域与正文区域类似，可以根据需要不同的段落层及元素层进行适应性修改，本发明并不做具体赘述。

首先比较段落层，流程如图2所示，如图1所示，将文档1正文的段落层全部编入段落链表A1，将文档2正文的段落层全部编入段落链表A2，将A1和A2进行纯文本的最长子序列的获取，在获取时，比较算法使用获取相似度的方式，若相似度高于预先设定的相似度阈值，则认定为两段落为同一段落。N为当前元素在A1中的序号，M为当前元素在A2中的序号，将A1(0-N)和A2(0-M)的元素分别存入链表B1和B2，判定为相同段落的标记为SAME，其余部分标记为NORMAL。比较完成后，B1和B2即为以相似度阈值为基础的包含有文档1和文档2的最长子序列信息的结果集，标记为SAME的部分即段落层级上我们认定两文档相同的部分。将B1与B2中，标记为SAME的对应元素，进行格式比较，得到格式差异G1。至此，段落层级的比较完成。

然后比较元素层。根据设定元素层可以字词为基础单位，也可以字符为基础单位。将B1和B2中标记为SAME的部分取出，按照段落比较的结果一一对应，存入C[X][2]的数组，如图3所示。以0-X为变量循环处理该数组，以Num＝0时为例：将C[0][0]以字词(字符)为元素，拆分得到链表C1；将C[0][1]以字词(字符)为元素，拆分得到链表C2；拆分时如若遇到图片、文本框等其他元素，以标识符的形式记录到链表中。拆分完成后，将C1和C2进行纯文本的最长子序列的获取，比较算法中使用文本全等认定为相同的方式进行比较，若遇到特殊元素标识符，特殊元素与文本元素之间认定为不等，特殊元素之间则根据元素种类与属性进行比较；对于文本框等内部包含有文本的特殊元素，内部文本也按照规则拆分然后比较。比较完成后，得到标记有SAME和NORMAL的结果链表D1、D2。将D1与D2中，标记为SAME的对应元素，进行格式比较，得到格式差异G2。至此，元素层级比较完成。

第三步，整理结果集。

参照附图3，对B1、B2、D1、D2、G1、G2进行整理：将B1中标记为NORMAL的部分存入链表R，并标记为DELETE；B2中标记为NORMAL的部分存入R，标记为INSERT；B1和B2中标记为SAME的部分，结合G1，对段落的格式差异进行标记；D1中标记为NORMAL的部分存入R，标记为DELETE，D2中标记为NORMAL的部分存入R，标记为INSERT；D1和D2中标记为SAME的部分，结合G2，对元素的格式差异进行标记。得到的链表R，即为我们想要的结果集。

尽管已经示出和描述了本发明的实施例，对于本领域的普通技术人员而言，可以理解在不脱离本发明的原理和精神的情况下可以对这些实施例进行多种变化、修改、替换和变型，本发明的范围由所附权利要求及其等同物限定。