基于有限狀態機的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，準備識別發貨數量。