一种基于KMP算法的单模板工作流优化方法

摘要

本发明公开一种基于KMP算法的单模板工作流优化方法，涉及图像文字识别领域；获取单模板工作流中模板图片，根据模板图片字符串的子串的前缀集合和后缀集合构建模板图片的字符串部分匹配表，根据字符串部分匹配表基于KMP算法匹配模板图片字符串与测试图片OCR识别字符串。

说明书

技术领域

本发明公开一种方法，涉及图像文字识别领域，具体地说是一种基于KMP算法的单模板工作流优化方法。

背景技术

单模板通常指一种可以识别单个板式图片中的文字，能够自主构建文字识别的模板。而单模板工作流能够自主构建文字识别模板，识别模板图片中的文字，提供高精度的文字识别模型，保证结构化信息提取精度，其中字符串匹配查找是单模板工作流评估应用阶段的关键步骤，但是现在单模板工作流还没有完善方法既能使模板图片字符串与OCR识别的测试图片字符高效查找匹配，又能提高单模板工作流文字识别的精度。

发明内容

本发明针对现有技术的问题，提供一种基于KMP算法的单模板工作流优化方法，涉及基于KMP算法思想的单模板工作流优化方法，提高单模板工作流评估应用阶段效果。

本发明提出的具体方案是：

一种基于KMP算法的单模板工作流优化方法，其特征是获取单模板工作流中模板图片，根据模板图片字符串的子串的前缀集合和后缀集合构建模板图片的字符串部分匹配表，根据字符串部分匹配表基于KMP算法匹配模板图片字符串与测试图片OCR识别字符串。

进一步，所述的一种基于KMP算法的单模板工作流优化方法中根据模板图片字符串的子串归类统计模板图片字符串的子串的前缀集合和后缀集合，匹配模板图片字符串的子串的前缀集合和后缀集合，获取前缀集合和后缀集合中最长公共元素长度，构建模板图片的字符串部分匹配表。

进一步，所述的一种基于KMP算法的单模板工作流优化方法中归类统计模板图片字符串的子串的前缀集合和后缀集合：

遍历模板图片字符串的所有子串，根据字符串前缀与后缀的定义归类统计模板图片字符串的子串的前缀集合和后缀集合。

进一步，所述的一种基于KMP算法的单模板工作流优化方法中匹配模板图片字符串与测试图片OCR识别字符串：

从字符串部分匹配表中获取字符串的子串对应的部分匹配值，利用已匹配的字符数减去对应的部分匹配值获得匹配过程中模板图片字符串需要移动的位数，进行模板图片字符串与测试图片OCR识别字符串匹配。

一种基于KMP算法的单模板工作流优化系统，包括获取模块、构建模块及匹配模块，

获取模块获取单模板工作流中模板图片，构建模块根据模板图片字符串的子串的前缀集合和后缀集合构建模板图片的字符串部分匹配表，匹配模块根据字符串部分匹配表基于KMP算法匹配模板图片字符串与测试图片OCR识别字符串。

进一步，所述的一种基于KMP算法的单模板工作流优化系统中构建模块根据模板图片字符串的子串归类统计模板图片字符串的子串的前缀集合和后缀集合，匹配模板图片字符串的子串的前缀集合和后缀集合，获取前缀集合和后缀集合中最长公共元素长度，构建模板图片的字符串部分匹配表。

进一步，所述的一种基于KMP算法的单模板工作流优化系统中构建模块归类统计模板图片字符串的子串的前缀集合和后缀集合：

遍历模板图片字符串的所有子串，根据字符串前缀与后缀的定义归类统计模板图片字符串的子串的前缀集合和后缀集合。

进一步，所述的一种基于KMP算法的单模板工作流优化系统中匹配模块匹配模板图片字符串与测试图片OCR识别字符串：

从字符串部分匹配表中获取字符串的子串对应的部分匹配值，利用已匹配的字符数减去对应的部分匹配值获得匹配过程中模板图片字符串需要移动的位数，进行模板图片字符串与测试图片OCR识别字符串匹配。

一种基于KMP算法的单模板工作流优化装置，包括至少一个存储器和至少一个处理器；

所述至少一个存储器，用于存储机器可读程序；

所述至少一个处理器，用于调用所述机器可读程序，执行所述的一种基于KMP算法的单模板工作流优化方法。

本发明的有益之处是：

本发明提供一种基于KMP算法的单模板工作流优化方法，通过基于KMP算法优化单模板工作流，能够实现在单模板工作流的评估应用阶段构建一种查找匹配算法模型，应用于模板图片字符串与OCR识别的测试图片字符串的快速匹配，从而提高单模板工作流文字识别模型的精度，保证结构化信息的提取效果。

附图说明

图1是本发明方法应用流程示意图；

图2是本发明方法流程示意图；

图3是本发明方法实施例中第一次匹配比对示意图；

图4是本发明方法实施例中第二次匹配比对示意图；

图5是本发明方法实施例中第三次匹配比对示意图；

图6是本发明方法实施例中第四次匹配比对示意图；

图7是本发明方法实施例中第五次匹配比对示意图；

图8是本发明方法实施例中最终匹配比对示意图。

具体实施方式

下面结合附图和具体实施例对本发明作进一步说明，以使本领域的技术人员可以更好地理解本发明并能予以实施，但所举实施例不作为对本发明的限定。

本发明提供一种基于KMP算法的单模板工作流优化方法，其特征是获取单模板工作流中模板图片，根据模板图片字符串的子串的前缀集合和后缀集合构建模板图片的字符串部分匹配表，根据字符串部分匹配表基于KMP算法匹配模板图片字符串与测试图片OCR识别字符串。

本发明方法通过基于KMP算法优化单模板工作流，能够实现在单模板工作流的评估应用阶段构建一种查找匹配算法模型，应用于模板图片字符串与OCR识别的测试图片字符串的快速匹配，从而提高单模板工作流文字识别模型的精度，保证结构化信息的提取效果。

具体应用中，在本发明的一些实施例中获取单模板工作流中模板图片后为匹配模板图片字符串与测试图片OCR识别字符串，进行如下步骤：

S1：遍历模板图片字符串的所有子串。遍历模板图片字符串的所有子串，将遍历结果添加至数组，遍历过程伪代码如下：

array＝[]//初始化前、后缀空集合

for t←0to len(string)

do prefix.append(string[:t+1])//添加所有字符子串到数组Array

repeat

end

S2：归类统计模板图片字符串的子串前、后缀集合。其中前缀是指从串首开始到某个位置结束的一个特殊子串，可利用如下公式表示：

prefix(S,i)＝S[0...i]

表示字符串S的以i结尾的前缀，真前缀指除了S本身的S的前缀。例如“纳税人识别号”的真前缀包括{“纳”，“纳税”，“纳税人”，“纳税人识”，“纳税人识别”}；

后缀是指从某个位置i开始到整个串末尾结束的一个特殊子串。可利用如下公式表示：

suffix(S,i)＝S[i..|S|-1]

表示字符串S的以i开头的后缀，真后缀指除了S本身的S的后缀。例如，”购买方”的真后缀包括{”买方”,”方”}。根据字符串前缀与后缀的定义，完成遍历模板图片字符串。根据上述字符串真前缀与真后缀的定义归类统计模板图片字符串的子串前、后缀集合。

S3：匹配模板图片字符串子串前、后缀集合，寻找子串最长公共元素长度。所有子串前缀和后缀在数量上是对称的，可以从前缀中找出一个，与后缀进行匹配，先不关心做这个匹配的意义，以模板图片字符串ABCDABD为例，寻找子串最长公共元素长度，如表1所示。

表1

其中index为5的位置，此时子字符串为ABCDAB，其前后缀分别为：

前缀：A,AB,ABC,ABCD,ABCDA

后缀：BCDAB,CDAB,DAB,AB,B

此时前后缀匹配共有元素为AB，最长公共元素长度为2。

S4：构建模板图片的字符串部分匹配表。模板图片字符串部分匹配值即是子串前后缀最长共有元素的值，比如子串前后缀共有元素为“a”、“abc”，则该子串前后缀共有元素最长的值为3，及部分匹配值(value)为3。下面以模板图片字符串ABCDABD为例构建字符串部分匹配表，如表2所示。

表2

S5：基于KMP算法模式快速匹配模板图片字符串与测试图片OCR识别字符串。基于KMP算法模式快速匹配模板图片字符串与测试图片OCR识别字符串，模板图片字符串以ABCDABD为例，测试图片字符串以ABCDAB ABCD ABCDABDE为例。

如图3所示，当空格与D不匹配时，前面六个匹配字符是"ABCDAB"，通过KMP算法设法利用已知信息，继续将模板图片字符串向后移，提高单模板工作流在评估应用阶段的效率。已知空格与D不匹配时，前面6个字符"ABCDAB"是匹配的。查模板图片字符串部分匹配表2可知，最后一个匹配字符B(即index 5)对应的"部分匹配值"为2，因此按照移动位数＝已匹配的字符数-对应的部分匹配值，这一公式计算出向后移动的位数为6-2等于4，所以向后移动4位。

如图4所示，因为空格与C不匹配，模板图片字符串还要继续往后移。这时，已匹配的字符数为2("AB")，对应的"部分匹配值"为0。所以，移动位数＝2-0，结果为2，于是将模板图片字符串向后移2位。

如图5所示，因为空格与A不匹配，像这样匹配的字符数为0，继续后移一位。

如图6所示，逐位比较，直到观察到空格与A不匹配。于是，移动位数＝4-0，继续将搜索词向后移动4位。

如图7所示，因为空格与A不匹配，像这样匹配的字符数为0，继续后移一位。

如图8所示，逐位观察比较，直到模板图片字符串的最后一位，发现与测试图片字符串完全匹配，于是匹配完成。

通过上述本发明方法通过基于KMP算法优化了单模板工作流，能够实现在单模板工作流的评估应用阶段构建查找匹配算法模型，并且应用于模板图片字符串与OCR识别的测试图片字符串的快速匹配，从而提高单模板工作流文字识别模型的精度，保证结构化信息提取效果的目的。

本发明还提供一种基于KMP算法的单模板工作流优化系统，包括获取模块、构建模块及匹配模块，

获取模块获取单模板工作流中模板图片，构建模块根据模板图片字符串的子串的前缀集合和后缀集合构建模板图片的字符串部分匹配表，匹配模块根据字符串部分匹配表基于KMP算法匹配模板图片字符串与测试图片OCR识别字符串。上述系统内的各模块之间的信息交互、执行过程等内容，由于与本发明方法实施例基于同一构思，具体内容可参见本发明方法实施例中的叙述，此处不再赘述。

同时本发明还提供一种基于KMP算法的单模板工作流优化装置，包括至少一个存储器和至少一个处理器；

所述至少一个存储器，用于存储机器可读程序；

所述至少一个处理器，用于调用所述机器可读程序，执行所述的一种基于KMP算法的单模板工作流优化方法。上述装置内的处理器的信息交互、执行可读程序过程等内容，由于与本发明方法实施例基于同一构思，具体内容可参见本发明方法实施例中的叙述，此处不再赘述。

需要说明的是，上述较佳实施例中各流程和各系统结构中不是所有的步骤和模块都是必须的，可以根据实际的需要忽略某些步骤或模块。各步骤的执行顺序不是固定的，可以根据需要进行调整。上述各实施例中描述的系统结构可以是物理结构，也可以是逻辑结构，即，有些模块可能由同一物理实体实现，或者，有些模块可能分由多个物理实体实现，或者，可以由多个独立设备中的某些部件共同实现。

以上所述实施例仅是为充分说明本发明而所举的较佳的实施例，本发明的保护范围不限于此。本技术领域的技术人员在本发明基础上所作的等同替代或变换，均在本发明的保护范围之内。本发明的保护范围以权利要求书为准。