施海昕 周雪峰 陳凱 劉云鋒

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

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

中圖分類號：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?引言

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

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

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

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

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

1?解決方案流程

Invoice收票自動化的流程分為3部分：序列化、結構化和匹配采購單，如圖2所示。

1.1?序列化

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

1.2?結構化

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

1.3?匹配采購單

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

2?有限自動機與正則表達式

2.1?有限自動機

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

（1） 確定的有限自動機

（2） 不確定的有限自動機

2.2?有限自動機的表示

有限自動機的一種常用表示方法是狀態(tài)轉換圖。對于有限自動機FA，用m個節(jié)點表示FA的m個狀態(tài)，如果有δ（si，a）=sj，則用有向邊連接兩個節(jié)點si和sj，有向邊上標記輸入字符a，這樣構成的圖成為狀態(tài)轉換圖。

狀態(tài)轉換圖只有唯一的一個初始狀態(tài)節(jié)點和若干個（或0個）終止狀態(tài)節(jié)點。初始狀態(tài)節(jié)點用箭頭標記，終止狀態(tài)節(jié)點用雙圈來表示。

2.3?正則表達式和正則集

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

2.4?有限自動機的實現(xiàn)

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

下面以一個按鈕控制電燈的狀態(tài)轉換圖為例講解如何實現(xiàn)一個有限自動機，如圖3所示。

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

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

用以上方法實現(xiàn)有限自動機的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文件在序列化后變?yōu)閠xt格式的字符流。如果把這些字符流看做一種編程語言，那么用有限自動機可以將其結構化，并還原為發(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?詞法分析

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

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

1） 回車和冒號的識別邏輯為字符匹配。

2） 單詞的識別邏輯為連續(xù)的沒有被空格或回車隔開的字符流。

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

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

3.2?語法分析

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

這種字符流看起來雖有一些怪異，但由于整個invoice的表格格式都是固定的二維表格，語法上不存在遞歸嵌套，因此不僅是上下文無關語言，而且更近一步是正則語言。我們可以仍舊用有限自動機來進行語法分析。

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

1） 狀態(tài)a是有限狀態(tài)機的初始狀態(tài)。狀態(tài)a識別到單詞Quantity Ordered，則會進入狀態(tài)b，準備識別行號。

2） 狀態(tài)b識別到常數(shù)，則記錄為行號，并進入狀態(tài)c，準備識別供應商型號。

3） 狀態(tài)c識別到單詞，則記錄為供應商型號，并進入狀態(tài)d，準備識別訂購數(shù)量。

4） 狀態(tài)d識別到常數(shù)，則記錄為訂購數(shù)量，并進入狀態(tài)e，準備識別原廠型號。

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

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