基于有限状态机的Invoice收票自动化系统

施海昕 周雪峰 陈凯 刘云锋

摘 要：传统发票识别通常拿纸质发票扫描再采用OCR识别，识别准确率为80%至90%。而由于本案使用Word或者Excel格式转化成的pdf格式发票，文件保留了完整的字符信息和一些相对固定的格式信息。以编译原理的思维，把发票转化成的文本看作为一种编程语言，再用有限状态机去识别。实验结果表明，准确率可达99%以上，获得了满意的效果。

关键词：有限状态机;发票识别;编译原理

中图分类号：TP311

文献标志码：A

文章编号：1007-757X（2020）11-0086-04

Abstract：Traditional invoice recognitionis usually completed by scanning paper invoices and then using OCR. The recognition accuracy is about 80%-90%. For our case， the invoice files contain complete character information and some relatively fixed format information. If the text from the invoice is regarded as a programming language， it can be recognized by a finite automaton. Experimental results show that the accuracy of this method can reach more than 99%， which is a satisfactory result.

Key words：finite automaton;invoice recognition;principles of compliers

0 引言

伴隨着我国电子制造业的巨大发展，电子分销行业在最近二十年中也迅猛增长。电子分销企业每天都有大量的进口元器件交易，随之而来是大批国外invoice（发票）需要录入以便财务确认收票。

企业一般采用人工方式录入invoice信息和收票，但随着业务的不断扩大，人工录入的缺点暴露得非常明显：1）录入效率低，invoice不能及时录入，影响后续运营流程;2）错误率高，并且无法知晓错误的存在;3）工作性质枯燥，人员离职率高。

传统发票识别通常拿纸质发票扫描再采用OCR识别，识别准确率为80%至90%。而在本案中，由于invoice都是国外供应商用Word或者Excel格式转化为的pdf格式，保留了完整的字符信息和一些相对固定的格式信息，这样使得用预定义过程算法识别invoice内容成为可能。本文采用编译原理的思路，把pdf文件转化的文本看作一种编程语言进行词法分析和语法分析，从而进行invoice信息的结构化，以及后续同ERP中采购单匹配达到收票的目的。

由于纸质发票的普遍性，目前已有的众多方法都是基于纸质发票扫描再OCR识别的，如图1所示。

一种思路是基于信号处理，赵莉等[1]人使用了小波变换的方式来增加识别准确率。另一种更广泛的思路是基于神经网络。蒋冲宇等[2]人通过MobleNet去除发票上的印章，起到了降低干扰提高识别准确率的作用。蒋璎[3]使用了深度卷积神经网络和残差网络来识别发票文字。胡译枫[4]使用了HOG加上SVM来识别发票文字。

1 解决方案流程

Invoice收票自动化的流程分为3部分：序列化、结构化和匹配采购单，如图2所示。

1.1 序列化

我们先用一个开源工具pdf2text把pdf格式的invoice序列化为txt格式的文本文件[8]。直接调用开源工具。

1.2 结构化

按照一定模型把序列化的字符流还原为结构化的发票信息。这里的模型就是本文论述的重点部分。

1.3 匹配采购单

用结构化的发票信息和ERP中已有的采购信息做匹配，做收票操作。由于发票信息和采购信息中都有采购单号，这一步使用匹配算法。

2 有限自动机与正则表达式

2.1 有限自动机

有限自动机是识别3型语言（正则语言）的数学方法[5]。它可以描述从输入字符流中模式识别的过程，因此能用做构造词法分析器。有限自动机又分为确定的优先自动机和不确定的有限自动机两种。

（1） 确定的有限自动机

（2） 不确定的有限自动机

2.2 有限自动机的表示

有限自动机的一种常用表示方法是状态转换图。对于有限自动机FA，用m个节点表示FA的m个状态，如果有δ（si，a）=sj，则用有向边连接两个节点si和sj，有向边上标记输入字符a，这样构成的图成为状态转换图。

状态转换图只有唯一的一个初始状态节点和若干个（或0个）终止状态节点。初始状态节点用箭头标记，终止状态节点用双圈来表示。

2.3 正则表达式和正则集

有限自动机接受的语言可以用正则表达式来描述，它所表示的字符串集为正则集，与正则文法产生的正则语言是相同的语言类，因此正则表达式与正则文法有相同的表达能力，两者是等价的。而正则表达式给出了字符串的简洁结构表示，因此通常用正则表达式来描述字符串的词法结构。再利用正则表达式与有限自动机之间的等价变换，构造出能识别符合词法结构字符串的有限自动机。这便是编译程序中词法分析器的形式化构造方法。

2.4 有限自动机的实现

在知道有限自动机可以用状态转换图表示也可以识别正则表达式之后，再看如何用代码实现一个有限自动机[6]。

下面以一个按钮控制电灯的状态转换图为例讲解如何实现一个有限自动机，如图3所示。

1） 定义一个枚举类型变量表示状态转换图里的各个状态，并定义一个表示当前状态的变量currentState，和一个表示输入字符的变量c。

2） 程序流程的外层用for语句和if语句，其中if语句判断是否到终止状态，如果到终止状态就跳出。内层用switch-case语句描述每个状态转换函数。

用以上方法实现有限自动机的GO语言代码如下。

const （

OFF = iota

ON

END

）

func main（） {

currentState ∶= OFF

var c byte

for {

c = getNextChar（）

switch {

case currentState==OFF && c=='1'：

currentState = ON

case currentState==OFF && c=='2'：

currentState = END

case currentState==ON && c=='0'：

currentState = OFF

}

fmt.Println（"input="，c，"currentState="，currentState）

if currentState==END {

break

}

}

}

3 結构化算法

pdf文件在序列化后变为txt格式的字符流。如果把这些字符流看做一种编程语言，那么用有限自动机可以将其结构化，并还原为发票信息。

字符流的片段如下。

Customer/MFG Part No.

Description

Quantity Ordered

1 863-LM317LBZRPG

400

：LM317LBZRPG

ON Semiconductor 100mA ADJ 1.2-37 V /

US HTS：8542390001 ECCN：EAR99 COO：CN

2 520-TXO-3225-25.0T

10

：ECS-TXO-3225-250-TR

ECS 25MHz 3.3V HCMOS / TCXO

US HTS：8541600060 ECCN：EAR99 COO：KR

（省略）

Quantity Shipped

400

10

（省略）

Quantity Pending

0

0

（省略）

Unit Price

（USD）

0.271

Extended Price

（USD）

108.40

2.650

26.50

（省略）

3.1 词法分析

词法分析的目的是把一个一个的词从字符流中分离出来，并结构化。对于每一种的编程语言，创建者都会预先定义词汇类型，如标识符、保留字、常数、运算符和界符等。在本案中，我们按照实际业务情况定义了4种类型：回车、冒号、单词和常数[7]。

词法分析的状态转换图，如图4所示。

1） 回车和冒号的识别逻辑为字符匹配。

2） 单词的识别逻辑为连续的没有被空格或回车隔开的字符流。

3） 常数的识别逻辑为含小数点的数字，但不能含有字母。一旦识别到输入中有字母则从状态c转到状态b，进入单词的流程。

根据这个状态转换图，我们就可以写出词法分析的代码。

3.2 语法分析

由于pdf格式的文件只保留了有限的格式信息，invoice中的表格在序列化以后并非成为规整的按行或按列的字符流，而是成为行列混合的字符流，如图5所示。

这种字符流看起来虽有一些怪异，但由于整个invoice的表格格式都是固定的二维表格，语法上不存在递归嵌套，因此不仅是上下文无关语言，而且更近一步是正则语言。我们可以仍旧用有限自动机来进行语法分析。

语法分析的状态转换图，如图6所示。

1） 状态a是有限状态机的初始状态。状态a识别到单词Quantity Ordered，则会进入状态b，准备识别行号。

2） 状态b识别到常数，则记录为行号，并进入状态c，准备识别供应商型号。

3） 状态c识别到单词，则记录为供应商型号，并进入状态d，准备识别订购数量。

4） 状态d识别到常数，则记录为订购数量，并进入状态e，准备识别原厂型号。

5） 状态e识别到冒号和单词，则把单词记为原厂型号，并进入状态f。

6） 状态f如果识别到回车再加上常数，则说明识别到下一行的行号，进入状态c;如果识别到单词Quantity Shipped，则进入状态g，准备识别发货数量。