基于有限狀態(tài)機(jī)的Invoice收票自動(dòng)化系統(tǒng)

施海昕 周雪峰 陳凱 劉云鋒

摘 要：傳統(tǒng)發(fā)票識(shí)別通常拿紙質(zhì)發(fā)票掃描再采用OCR識(shí)別，識(shí)別準(zhǔn)確率為80%至90%。而由于本案使用Word或者Excel格式轉(zhuǎn)化成的pdf格式發(fā)票，文件保留了完整的字符信息和一些相對(duì)固定的格式信息。以編譯原理的思維，把發(fā)票轉(zhuǎn)化成的文本看作為一種編程語(yǔ)言，再用有限狀態(tài)機(jī)去識(shí)別。實(shí)驗(yàn)結(jié)果表明，準(zhǔn)確率可達(dá)99%以上，獲得了滿(mǎn)意的效果。

關(guān)鍵詞：有限狀態(tài)機(jī);發(fā)票識(shí)別;編譯原理

中圖分類(lèi)號(hào)：TP311

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：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?引言

伴隨著我國(guó)電子制造業(yè)的巨大發(fā)展，電子分銷(xiāo)行業(yè)在最近二十年中也迅猛增長(zhǎng)。電子分銷(xiāo)企業(yè)每天都有大量的進(jìn)口元器件交易，隨之而來(lái)是大批國(guó)外invoice（發(fā)票）需要錄入以便財(cái)務(wù)確認(rèn)收票。

企業(yè)一般采用人工方式錄入invoice信息和收票，但隨著業(yè)務(wù)的不斷擴(kuò)大，人工錄入的缺點(diǎn)暴露得非常明顯：1）錄入效率低，invoice不能及時(shí)錄入，影響后續(xù)運(yùn)營(yíng)流程;2）錯(cuò)誤率高，并且無(wú)法知曉錯(cuò)誤的存在;3）工作性質(zhì)枯燥，人員離職率高。

傳統(tǒng)發(fā)票識(shí)別通常拿紙質(zhì)發(fā)票掃描再采用OCR識(shí)別，識(shí)別準(zhǔn)確率為80%至90%。而在本案中，由于invoice都是國(guó)外供應(yīng)商用Word或者Excel格式轉(zhuǎn)化為的pdf格式，保留了完整的字符信息和一些相對(duì)固定的格式信息，這樣使得用預(yù)定義過(guò)程算法識(shí)別invoice內(nèi)容成為可能。本文采用編譯原理的思路，把pdf文件轉(zhuǎn)化的文本看作一種編程語(yǔ)言進(jìn)行詞法分析和語(yǔ)法分析，從而進(jìn)行invoice信息的結(jié)構(gòu)化，以及后續(xù)同ERP中采購(gòu)單匹配達(dá)到收票的目的。

由于紙質(zhì)發(fā)票的普遍性，目前已有的眾多方法都是基于紙質(zhì)發(fā)票掃描再OCR識(shí)別的，如圖1所示。

一種思路是基于信號(hào)處理，趙莉等[1]人使用了小波變換的方式來(lái)增加識(shí)別準(zhǔn)確率。另一種更廣泛的思路是基于神經(jīng)網(wǎng)絡(luò)。蔣沖宇等[2]人通過(guò)MobleNet去除發(fā)票上的印章，起到了降低干擾提高識(shí)別準(zhǔn)確率的作用。蔣瓔[3]使用了深度卷積神經(jīng)網(wǎng)絡(luò)和殘差網(wǎng)絡(luò)來(lái)識(shí)別發(fā)票文字。胡譯楓[4]使用了HOG加上SVM來(lái)識(shí)別發(fā)票文字。

1?解決方案流程

Invoice收票自動(dòng)化的流程分為3部分：序列化、結(jié)構(gòu)化和匹配采購(gòu)單，如圖2所示。

1.1?序列化

我們先用一個(gè)開(kāi)源工具pdf2text把pdf格式的invoice序列化為txt格式的文本文件[8]。直接調(diào)用開(kāi)源工具。

1.2?結(jié)構(gòu)化

按照一定模型把序列化的字符流還原為結(jié)構(gòu)化的發(fā)票信息。這里的模型就是本文論述的重點(diǎn)部分。

1.3?匹配采購(gòu)單

用結(jié)構(gòu)化的發(fā)票信息和ERP中已有的采購(gòu)信息做匹配，做收票操作。由于發(fā)票信息和采購(gòu)信息中都有采購(gòu)單號(hào)，這一步使用匹配算法。

2?有限自動(dòng)機(jī)與正則表達(dá)式

2.1?有限自動(dòng)機(jī)

有限自動(dòng)機(jī)是識(shí)別3型語(yǔ)言（正則語(yǔ)言）的數(shù)學(xué)方法[5]。它可以描述從輸入字符流中模式識(shí)別的過(guò)程，因此能用做構(gòu)造詞法分析器。有限自動(dòng)機(jī)又分為確定的優(yōu)先自動(dòng)機(jī)和不確定的有限自動(dòng)機(jī)兩種。

（1） 確定的有限自動(dòng)機(jī)

（2） 不確定的有限自動(dòng)機(jī)

2.2?有限自動(dòng)機(jī)的表示

有限自動(dòng)機(jī)的一種常用表示方法是狀態(tài)轉(zhuǎn)換圖。對(duì)于有限自動(dòng)機(jī)FA，用m個(gè)節(jié)點(diǎn)表示FA的m個(gè)狀態(tài)，如果有δ（si，a）=sj，則用有向邊連接兩個(gè)節(jié)點(diǎn)si和sj，有向邊上標(biāo)記輸入字符a，這樣構(gòu)成的圖成為狀態(tài)轉(zhuǎn)換圖。

狀態(tài)轉(zhuǎn)換圖只有唯一的一個(gè)初始狀態(tài)節(jié)點(diǎn)和若干個(gè)（或0個(gè)）終止?fàn)顟B(tài)節(jié)點(diǎn)。初始狀態(tài)節(jié)點(diǎn)用箭頭標(biāo)記，終止?fàn)顟B(tài)節(jié)點(diǎn)用雙圈來(lái)表示。

2.3?正則表達(dá)式和正則集

有限自動(dòng)機(jī)接受的語(yǔ)言可以用正則表達(dá)式來(lái)描述，它所表示的字符串集為正則集，與正則文法產(chǎn)生的正則語(yǔ)言是相同的語(yǔ)言類(lèi)，因此正則表達(dá)式與正則文法有相同的表達(dá)能力，兩者是等價(jià)的。而正則表達(dá)式給出了字符串的簡(jiǎn)潔結(jié)構(gòu)表示，因此通常用正則表達(dá)式來(lái)描述字符串的詞法結(jié)構(gòu)。再利用正則表達(dá)式與有限自動(dòng)機(jī)之間的等價(jià)變換，構(gòu)造出能識(shí)別符合詞法結(jié)構(gòu)字符串的有限自動(dòng)機(jī)。這便是編譯程序中詞法分析器的形式化構(gòu)造方法。

2.4?有限自動(dòng)機(jī)的實(shí)現(xiàn)

在知道有限自動(dòng)機(jī)可以用狀態(tài)轉(zhuǎn)換圖表示也可以識(shí)別正則表達(dá)式之后，再看如何用代碼實(shí)現(xiàn)一個(gè)有限自動(dòng)機(jī)[6]。

下面以一個(gè)按鈕控制電燈的狀態(tài)轉(zhuǎn)換圖為例講解如何實(shí)現(xiàn)一個(gè)有限自動(dòng)機(jī)，如圖3所示。

1） 定義一個(gè)枚舉類(lèi)型變量表示狀態(tài)轉(zhuǎn)換圖里的各個(gè)狀態(tài)，并定義一個(gè)表示當(dāng)前狀態(tài)的變量currentState，和一個(gè)表示輸入字符的變量c。

2） 程序流程的外層用for語(yǔ)句和if語(yǔ)句，其中if語(yǔ)句判斷是否到終止?fàn)顟B(tài)，如果到終止?fàn)顟B(tài)就跳出。內(nèi)層用switch-case語(yǔ)句描述每個(gè)狀態(tài)轉(zhuǎn)換函數(shù)。

用以上方法實(shí)現(xiàn)有限自動(dòng)機(jī)的GO語(yǔ)言代碼如下。

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?結(jié)構(gòu)化算法

pdf文件在序列化后變?yōu)閠xt格式的字符流。如果把這些字符流看做一種編程語(yǔ)言，那么用有限自動(dòng)機(jī)可以將其結(jié)構(gòu)化，并還原為發(fā)票信息。

字符流的片段如下。

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?詞法分析

詞法分析的目的是把一個(gè)一個(gè)的詞從字符流中分離出來(lái)，并結(jié)構(gòu)化。對(duì)于每一種的編程語(yǔ)言，創(chuàng)建者都會(huì)預(yù)先定義詞匯類(lèi)型，如標(biāo)識(shí)符、保留字、常數(shù)、運(yùn)算符和界符等。在本案中，我們按照實(shí)際業(yè)務(wù)情況定義了4種類(lèi)型：回車(chē)、冒號(hào)、單詞和常數(shù)[7]。

詞法分析的狀態(tài)轉(zhuǎn)換圖，如圖4所示。

1） 回車(chē)和冒號(hào)的識(shí)別邏輯為字符匹配。

2） 單詞的識(shí)別邏輯為連續(xù)的沒(méi)有被空格或回車(chē)隔開(kāi)的字符流。

3） 常數(shù)的識(shí)別邏輯為含小數(shù)點(diǎn)的數(shù)字，但不能含有字母。一旦識(shí)別到輸入中有字母則從狀態(tài)c轉(zhuǎn)到狀態(tài)b，進(jìn)入單詞的流程。

根據(jù)這個(gè)狀態(tài)轉(zhuǎn)換圖，我們就可以寫(xiě)出詞法分析的代碼。

3.2?語(yǔ)法分析

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

這種字符流看起來(lái)雖有一些怪異，但由于整個(gè)invoice的表格格式都是固定的二維表格，語(yǔ)法上不存在遞歸嵌套，因此不僅是上下文無(wú)關(guān)語(yǔ)言，而且更近一步是正則語(yǔ)言。我們可以仍舊用有限自動(dòng)機(jī)來(lái)進(jìn)行語(yǔ)法分析。

語(yǔ)法分析的狀態(tài)轉(zhuǎn)換圖，如圖6所示。

1） 狀態(tài)a是有限狀態(tài)機(jī)的初始狀態(tài)。狀態(tài)a識(shí)別到單詞Quantity Ordered，則會(huì)進(jìn)入狀態(tài)b，準(zhǔn)備識(shí)別行號(hào)。

2） 狀態(tài)b識(shí)別到常數(shù)，則記錄為行號(hào)，并進(jìn)入狀態(tài)c，準(zhǔn)備識(shí)別供應(yīng)商型號(hào)。

3） 狀態(tài)c識(shí)別到單詞，則記錄為供應(yīng)商型號(hào)，并進(jìn)入狀態(tài)d，準(zhǔn)備識(shí)別訂購(gòu)數(shù)量。

4） 狀態(tài)d識(shí)別到常數(shù)，則記錄為訂購(gòu)數(shù)量，并進(jìn)入狀態(tài)e，準(zhǔn)備識(shí)別原廠型號(hào)。

5） 狀態(tài)e識(shí)別到冒號(hào)和單詞，則把單詞記為原廠型號(hào)，并進(jìn)入狀態(tài)f。

6） 狀態(tài)f如果識(shí)別到回車(chē)再加上常數(shù)，則說(shuō)明識(shí)別到下一行的行號(hào)，進(jìn)入狀態(tài)c;如果識(shí)別到單詞Quantity Shipped，則進(jìn)入狀態(tài)g，準(zhǔn)備識(shí)別發(fā)貨數(shù)量。