非結(jié)構(gòu)化表格文檔數(shù)據(jù)抽取與組織模型研究

張元鳴，陳 苗，陸佳煒，徐 俊，肖 剛

(1.浙江工業(yè)大學 計算機科學與技術(shù)學院,浙江 杭州 310023；2.浙江工業(yè)大學 機械工程博士后流動站,浙江 杭州 310014)

?

非結(jié)構(gòu)化表格文檔數(shù)據(jù)抽取與組織模型研究

張元鳴1,2，陳 苗1，陸佳煒1，徐 俊1，肖 剛1,2

(1.浙江工業(yè)大學 計算機科學與技術(shù)學院,浙江 杭州 310023；2.浙江工業(yè)大學 機械工程博士后流動站,浙江 杭州 310014)

針對現(xiàn)有文檔數(shù)據(jù)抽取方法無法抽取多值屬性且靈活性不高的問題，提出了一種面向非結(jié)構(gòu)化表格文檔的數(shù)據(jù)抽取方法與組織模型.在分析文檔結(jié)構(gòu)特征和數(shù)據(jù)流特征的基礎(chǔ)上，定義了數(shù)據(jù)流生成基本規(guī)則，給出了一個基于規(guī)則的數(shù)據(jù)抽取流程，包括邏輯結(jié)構(gòu)抽取、文檔預處理、數(shù)據(jù)抽取和數(shù)據(jù)組織等主要步驟，設(shè)計實現(xiàn)了單值區(qū)域與多值區(qū)域數(shù)據(jù)抽取算法；從文檔中抽取的數(shù)據(jù)被組織成適合于MapReduce分析的結(jié)構(gòu)化數(shù)據(jù)模型，該模型能夠為大數(shù)據(jù)分析提供模型支持.實驗結(jié)果表明：該抽取方法具有較高的準確率與召回率，數(shù)據(jù)組織模型也能夠有效地支持大數(shù)據(jù)分析.

非結(jié)構(gòu)化表格文檔；數(shù)據(jù)抽??；結(jié)構(gòu)化數(shù)據(jù)模型；數(shù)據(jù)分析

隨著辦公自動化的深入實施，表格文檔被廣泛應(yīng)用于企事業(yè)和政務(wù)日常事務(wù)處理中，如調(diào)查表、業(yè)績表、考核表、職稱評審表、審批表和申請書等，這些表格通過辦公自動化軟件(如Word，WPS，Excel等)編輯而來.由于可編輯的表格文檔安全性較低、可移植性也較差，在正式發(fā)布或提交之前，往往將其轉(zhuǎn)換為安全性高、可移植強的只讀格式的文檔，如PDF格式.通過解析這些文件可知，其數(shù)據(jù)流已不包含可編輯模式下的制表符，僅包括空格和換行符分隔符.將不包含特殊制表符的表格文檔稱為非結(jié)構(gòu)化表格文檔，這些文檔往往從Word表格、HTML表格和Excel表格等半結(jié)構(gòu)化表格文檔轉(zhuǎn)換得到，具有以下特征：1) 非結(jié)構(gòu)化.不同于Word表格、HTML表格和Excel表格等半結(jié)構(gòu)化表格文檔的數(shù)據(jù)流中含有特殊的制表符，非結(jié)構(gòu)化表格的數(shù)據(jù)流中往往不包含特殊的制表符，數(shù)據(jù)僅以空格或換行作為分隔符，是一種較典型的非結(jié)構(gòu)化數(shù)據(jù)；2) 樣式不固定.非結(jié)構(gòu)化表格與實際應(yīng)用緊密相關(guān)，不同應(yīng)用設(shè)計的表格樣式往往不同，導致表格樣式靈活多樣，沒有固定的樣式；3) 數(shù)據(jù)混雜.非結(jié)構(gòu)化表格中的數(shù)據(jù)從類別上可以分為標題區(qū)和數(shù)據(jù)區(qū)，從形式上又可以進一步分為單值區(qū)域和多值區(qū)域，橫向排列和縱向排列兼而有之，數(shù)據(jù)較為混雜；4)價值稀疏.表格文檔往往包含了多方面的數(shù)據(jù)，這些數(shù)據(jù)混合在一起，價值提取的目標數(shù)據(jù)僅僅是某一局部的數(shù)據(jù)，價值相對稀疏.

大數(shù)據(jù)背景下，海量的非結(jié)構(gòu)化表格文檔存儲著豐富的有價值的數(shù)據(jù)，對海量非結(jié)構(gòu)化表格文檔分析具有重要的實際意義，而數(shù)據(jù)抽取和數(shù)據(jù)組織是實現(xiàn)價值提取的關(guān)鍵步驟[1].數(shù)據(jù)抽取的目標是從非結(jié)構(gòu)化表格文檔中抽取出完整的語義數(shù)據(jù)，而數(shù)據(jù)組織的目標是對抽取的數(shù)據(jù)通過某種邏輯結(jié)構(gòu)組織起來，為數(shù)據(jù)分析奠定基礎(chǔ).在分析非結(jié)構(gòu)化表格文檔結(jié)構(gòu)特征和數(shù)據(jù)流特征的基礎(chǔ)上，提出了一種基于規(guī)則的數(shù)據(jù)抽取方法，并將數(shù)據(jù)抽取結(jié)果組織為適合于MapReduce并行編程模型分析的結(jié)構(gòu)化數(shù)據(jù)模型，所提出的方法已經(jīng)在大量非結(jié)構(gòu)化表格文檔中進行了實驗，具有較高的數(shù)據(jù)抽準率和召回率，數(shù)據(jù)組織模型也能滿足基于MapReduce的分析需求.

1 相關(guān)研究

一般地，電子文檔可以分為半結(jié)構(gòu)化文檔和非結(jié)構(gòu)化文檔，學術(shù)界已對兩類文檔數(shù)據(jù)抽取方法進行了相關(guān)研究.

半結(jié)構(gòu)化文檔的數(shù)據(jù)抽取主要是利用文檔中固有的特殊制表符(分隔符)進行數(shù)據(jù)抽取.潘小燕[2]將最大嫡模型應(yīng)用于表格數(shù)據(jù)的抽取，利用DOM Tree模型提取表格數(shù)據(jù)；宋強等[3]提出了一種非標記化表格抽取算法，實現(xiàn)了非標記化表格數(shù)據(jù)抽取；王允富[4]提出了一種基于指令系統(tǒng)的Excel表單數(shù)據(jù)抽取模型，實現(xiàn)了Excel表單數(shù)據(jù)的自動抽取和自動加載；黃豫清等[5-6]提出了基于XML的數(shù)據(jù)抽取方法，能夠抽取Web中的數(shù)據(jù)；李澎林等[7]設(shè)計了一種基于雙字Hash和List相結(jié)合的三層詞典數(shù)據(jù)結(jié)構(gòu)，改進最大匹配分詞算法提高了抽取的準確度和效率.一般地，對半結(jié)構(gòu)化數(shù)據(jù)抽取的研究主要是對單元格內(nèi)的數(shù)據(jù)進行抽取，不再對同一單元格內(nèi)的數(shù)據(jù)再次切分，因此實現(xiàn)較為容易.

非結(jié)構(gòu)化文檔的數(shù)據(jù)抽取主要是對文檔中包含的實體屬性、關(guān)鍵詞等的抽取，抽取的準確性依賴于分詞技術(shù)和實體識別技術(shù).宋艷娟[8]開發(fā)了一種對HTML和PDF抽取的系統(tǒng)，能夠抽取科研論文中的重要數(shù)據(jù)；霍焰[9]設(shè)計了一套實體抽取算法，可以抽取業(yè)務(wù)工作中有用的實體；王云鵬[10]開發(fā)了一個基于非結(jié)構(gòu)化數(shù)據(jù)的抽取與分析系統(tǒng)，并以可視化的方式展示數(shù)據(jù)抽取結(jié)果；CHANG等[11]利用關(guān)系表中的屬性值對實體集合進行劃分，以從中抽取相關(guān)實體；劉端陽等[12-13]提對關(guān)鍵詞和評論觀點的提取方法進行了研究.

非結(jié)構(gòu)化表格文檔是一種特殊的非結(jié)構(gòu)化文檔，形式上具有半結(jié)構(gòu)化文檔的特征，但數(shù)據(jù)流實際上是非結(jié)構(gòu)化的，其數(shù)據(jù)抽取既不同于半結(jié)構(gòu)化文檔的數(shù)據(jù)抽取，也不同于非結(jié)構(gòu)化文檔的數(shù)據(jù)抽取.張伯[14]提出了一種基于文字流的表格識別技術(shù)，設(shè)計并實現(xiàn)了針對某類表格的識別系統(tǒng)，但該技術(shù)不適用于處理合并單元格的情況，而且也無法抽取表格列間距過大和豎排表格的情況；劉力[15]提出了針對項目申報書的數(shù)據(jù)抽取方法，該方法基于模板技術(shù)和文本定位算法，該方法僅適用于抽取單值屬性的數(shù)據(jù)；ZHOU等[16-17]將啟發(fā)式規(guī)則應(yīng)用于列劃分和對表格特征進行細化，解決了表格內(nèi)容抽取的問題，但不適用于存在特殊列結(jié)構(gòu)的表格.

在非結(jié)構(gòu)化數(shù)據(jù)組織方面，萬里鵬[18]設(shè)計了一種非結(jié)構(gòu)化到結(jié)構(gòu)化數(shù)據(jù)轉(zhuǎn)換系統(tǒng)，該系統(tǒng)不支持PDF文檔以及結(jié)構(gòu)復雜的文本文件、Word和Excel等格式的文檔；馮亞麗等[19]提出了一種基于規(guī)則庫的非結(jié)構(gòu)化數(shù)據(jù)轉(zhuǎn)換方法，對非結(jié)構(gòu)化數(shù)據(jù)進行了統(tǒng)一轉(zhuǎn)換，不足之處在于正確率不高；鄒波[20]開發(fā)了一種海量非結(jié)構(gòu)化數(shù)據(jù)組織管理系統(tǒng)，能夠?qū)Ａ糠墙Y(jié)構(gòu)化數(shù)據(jù)進行組織和管理；PENG等[21-22]將XML應(yīng)用于文檔結(jié)構(gòu)的提取和匹配，較好地實現(xiàn)了對表格文本數(shù)據(jù)的轉(zhuǎn)換和組織.

數(shù)據(jù)抽取和數(shù)據(jù)組織是實現(xiàn)海量非結(jié)構(gòu)化表格文檔數(shù)據(jù)分析的關(guān)鍵步驟，在對大量非結(jié)構(gòu)化表格文檔進行分析比較的基礎(chǔ)上，給出了一種實現(xiàn)簡單、準確率高的數(shù)據(jù)抽取方法，并針對MapReduce設(shè)計了一種分布式環(huán)境下的結(jié)構(gòu)化數(shù)據(jù)組織模型，為下一步的數(shù)據(jù)分析奠定了良好的基礎(chǔ).

2 非結(jié)構(gòu)化表格文檔特征分析

非結(jié)構(gòu)化表格文檔從形式上看與半結(jié)構(gòu)化表格(如Word表格，Excel表格等)基本相同，但是其生成的數(shù)據(jù)流卻是非結(jié)構(gòu)化的，圖1中除了文檔中的數(shù)據(jù)以外，原來的表格線全部被空格和換行符所替換，真實的數(shù)據(jù)與這些空格和換行符混為一體.

從數(shù)據(jù)類別看，非結(jié)構(gòu)化表格文檔中的數(shù)據(jù)可分為標題區(qū)和數(shù)據(jù)區(qū)，標題區(qū)表示數(shù)據(jù)的性質(zhì)和類別，數(shù)據(jù)區(qū)表示數(shù)據(jù)實際取值，如“姓名”為標題區(qū)，“陳建偉”為數(shù)據(jù)區(qū).數(shù)據(jù)抽取的任務(wù)是提取表格中的所有標題區(qū)和數(shù)據(jù)區(qū)，數(shù)據(jù)組織的任務(wù)是要建立標題區(qū)和數(shù)據(jù)區(qū)的語義聯(lián)系，以及相關(guān)標題區(qū)之間的語義關(guān)系.

從表格的結(jié)構(gòu)特征看，可分為單值區(qū)域和多值區(qū)域，單值區(qū)域的一個標題區(qū)對應(yīng)一個數(shù)據(jù)區(qū)，即一對一關(guān)系；多值表格的一個標題區(qū)對應(yīng)一個或多個數(shù)據(jù)區(qū)，即一對多關(guān).圖1為程序自動生成的單值區(qū)域表格文檔，單值區(qū)域的標題區(qū)與數(shù)據(jù)區(qū)緊密相聯(lián).

姓 名陳建偉推薦晉升(轉(zhuǎn)評)職務(wù)小中高單 位杭州市新福小學性別男出生年月1976年12月14日參加工作時間1995年7月教齡19年其中中專中學小學現(xiàn)任教年級三年級19任教學科數(shù)學現(xiàn)專業(yè)技術(shù)職務(wù)任職資格小學教師審定時間2004年12月聘任職務(wù)小學高級教師資格證書號05011-004-2010-21221聘任時間2004年12月何時何校何專業(yè)畢業(yè)(肄業(yè))及修業(yè)年限1995年6月于杭州師范學院普師專業(yè)畢業(yè)修業(yè)年限3年最高學歷(何年何校何專業(yè)畢業(yè))2005年6月于杭州師范學院數(shù)學本科畢業(yè)

圖1 單值區(qū)域表格文檔結(jié)構(gòu)特征

表1為多值區(qū)域表格，多值區(qū)域的一個標題區(qū)對應(yīng)多個數(shù)據(jù)區(qū)，數(shù)據(jù)區(qū)在數(shù)據(jù)流中被切分成多行.

為了說明表格文檔中單元格對應(yīng)生成的數(shù)據(jù)流特征，先定義表格文檔的內(nèi)容和其生成的數(shù)據(jù)流，然后給出生成規(guī)則：

設(shè)表中單元格的每行字符串為一個六元組，即

S=(V，L，N，E，F(xiàn)，LC)

其中：V為該行字符串的值；L={s，m}表示該行所屬單元格為單行(s)或多行(m)；N={s，m}表示該行所屬單元格的下一個單元格內(nèi)容為單行(s)或多行(m)；E={s，h}表示該行包括軟回車(s)或硬回車(h)；F={y，n}表示該行為當前單元格的最后一行(y)或不是最后一行(n)；LC={y，n}表示該行所屬單元格為表格該行的最后一個單元格(y)或者不是最后一個單元格(n).

再設(shè)表格中單元格的每行字符串轉(zhuǎn)換得到的數(shù)據(jù)流為一個二元組，即

D=(V，A)

其中：V為該行字符串的值；A={sp，e，se}表示轉(zhuǎn)換后在V后新增的分隔符，sp為空格，e為換行，se為空格及換行.

則表格中單元格的字符串根據(jù)不同情況生成的數(shù)據(jù)流規(guī)則為

S=(V，s，s，Null，Null，Null)→D=(V,sp)

S=(V，s，m， Null，Null，Null) →D=(V,se)

S=(V，m，Null，h， Null，Null) →D=(V,se)

S=(V，m，Null，s，y，Null) →D=(V,se)

S=(V，m，Null，s，n，Null) →D=(V,e)

S=(V，Null，Null，Null，Null，y) →D=(V,se) 以上多元組中的Null值表示可以取對應(yīng)元素取值集合中的任意值，這些規(guī)則是從非結(jié)構(gòu)化數(shù)據(jù)流中抽取表格標題區(qū)與數(shù)據(jù)區(qū)的重要依據(jù).

3 數(shù)據(jù)抽取流程及算法

為了提高數(shù)據(jù)抽取的準確度和靈活性，提出了一種基于規(guī)則的非結(jié)構(gòu)化表格文檔抽取方法，數(shù)據(jù)抽取流程如圖2所示，包括邏輯結(jié)構(gòu)抽取、文檔預處理、數(shù)據(jù)抽取、數(shù)據(jù)組織和大數(shù)據(jù)分析等主要步驟，在該流程中，包括一個數(shù)據(jù)字典，其作用是存儲文檔的標題區(qū)，作為判定標題區(qū)與數(shù)據(jù)區(qū)的基本依據(jù).

圖2 非結(jié)構(gòu)化表格文檔數(shù)據(jù)抽取流程Fig.2 The data extraction process of unstructured form document

3.1 邏輯結(jié)構(gòu)抽取

邏輯結(jié)構(gòu)抽取的任務(wù)是識別表格的標題區(qū)，并建立標題區(qū)之間的邏輯關(guān)系.一般地，非結(jié)構(gòu)化表格的各標題區(qū)不是孤立的，而是存在一定的語義聯(lián)系，如基本信息中包括姓名、性別和年齡等，工作經(jīng)歷中包括起止時間、工作單位和工作崗位等，需要針對這些標題區(qū)域構(gòu)建較為統(tǒng)一的邏輯結(jié)構(gòu)，為后面的數(shù)據(jù)抽取提供框架.定義了一個五元組表示表格的邏輯結(jié)構(gòu)：

定義1 非結(jié)構(gòu)化表格邏輯結(jié)構(gòu)可以表示為一個五元組TableStru= 集合，其中，ID表示文檔的標識；TupleID表示元組的標識；Title表示標題區(qū)；Type ={Single, Multiple}，表示標題區(qū)的類型，Single表示“單值區(qū)域”，Multiple表示“多值區(qū)域”；Parent表示該標題的父標題區(qū).

邏輯結(jié)構(gòu)提取的輸入是一個不包含任何實際數(shù)據(jù)的非結(jié)構(gòu)化表格文檔，通過匹配數(shù)據(jù)字典，抽取表格各標題區(qū)，并建立邏輯關(guān)系，抽取的結(jié)果保存在邏輯結(jié)構(gòu)庫中.

3.2 單值區(qū)域數(shù)據(jù)抽取

數(shù)據(jù)抽取是基于表格的結(jié)構(gòu)特征和數(shù)據(jù)流特征，提取表格中的數(shù)據(jù)區(qū)并建立與標題區(qū)的語義聯(lián)系.根據(jù)表格的結(jié)構(gòu)特征，定義以下數(shù)據(jù)抽取規(guī)則：

定義2 若標題區(qū)后是數(shù)據(jù)區(qū)，則該區(qū)域為單值區(qū)域；若標題區(qū)后是連續(xù)的標題區(qū)，則該區(qū)域為多值區(qū)域.

定義3 標題區(qū)和數(shù)據(jù)區(qū)是一對一的關(guān)系，且數(shù)據(jù)區(qū)位于標題區(qū)之后.

定義4 從當前字符開始的最大字符串如果與數(shù)據(jù)字典中的某一字符串匹配，則該字符串為一個具有完整語義的標題區(qū)，在單值區(qū)域中介于兩個標題區(qū)之間的字符串為數(shù)據(jù)區(qū).

根據(jù)區(qū)域劃分規(guī)則可以將數(shù)據(jù)流劃分為單值區(qū)域和多值區(qū)域；根據(jù)單值區(qū)域規(guī)則和正向最大匹配規(guī)則可以抽取出標題區(qū)，如果在兩個標題區(qū)之間的字符串不為空，則是一個數(shù)據(jù)區(qū).

單值區(qū)域數(shù)據(jù)抽取的算法是以空格作為分隔符對數(shù)據(jù)流進行切分，得到一個字符串列表；按順序?qū)ψ址斜磉M行分析，將當前字符串與數(shù)據(jù)字典中的標題區(qū)進行匹配；利用正向最大匹配規(guī)則，將當前字符串與上次的字符串進行拼接得到一個新的字符串，與數(shù)據(jù)字典中的標題區(qū)進行匹配；根據(jù)匹配結(jié)果執(zhí)行不同的操作：1) 若拼接字符串匹配成功，則拼接字符串作為標題區(qū)；2) 若拼接字符串匹配失敗，上次匹配和本次匹配均成功，則上次標題區(qū)所對應(yīng)的數(shù)據(jù)區(qū)為空；3) 若拼接字符串匹配失敗，上次匹配成功，本次匹配失敗，則本次字符串作為數(shù)據(jù)區(qū)內(nèi)容；4) 若拼接字符串匹配失敗，上次匹配失敗，本次匹配成功，則輸出一個包括標題區(qū)和數(shù)據(jù)區(qū)的結(jié)構(gòu)化多元組；5) 若拼接字符串匹配失敗，上次匹配和本次匹配均失敗，則拼接字符串作為數(shù)據(jù)區(qū)內(nèi)容，根據(jù)以上匹配結(jié)果即可抽取出數(shù)據(jù)區(qū)；最后，將生成的多元組集合輸出到文件中.

3.3 多值區(qū)域數(shù)據(jù)抽取

根據(jù)多值區(qū)域的數(shù)據(jù)流特征，定義多值區(qū)域抽取規(guī)則.

定義5 每行的標題區(qū)個數(shù)與數(shù)據(jù)區(qū)個數(shù)相同且順序一致，一個標題區(qū)可以擁有多個數(shù)據(jù)區(qū).

根據(jù)多值區(qū)域規(guī)則，將多值區(qū)域定義為一個(m+1)n的矩陣，即

其中：m+1為多值區(qū)域的行數(shù)；n為多值區(qū)域的列數(shù)；aij為多值區(qū)域中的字符串值，當i=1時，aij為標題區(qū)，當i>1時，aij為數(shù)據(jù)區(qū).

多值區(qū)域數(shù)據(jù)抽取方法是根據(jù)前述定義的數(shù)據(jù)流生成規(guī)則，將抽取的字符串與多值區(qū)域矩陣的元素建立對應(yīng)關(guān)系，其基本策略是：若表格中的單元格內(nèi)容僅是單行字符串或由軟回車構(gòu)成的多行字符串，可以通過空格和換行符對多值區(qū)域的數(shù)據(jù)區(qū)進行切分，并依次填入多值區(qū)域矩陣.若表格中單元格內(nèi)容包含具有硬回車的多行字符串，在這種情況下數(shù)據(jù)流中將產(chǎn)生冗余的空格和換行符，此時可按照空格和回車符識別數(shù)據(jù)區(qū)的個數(shù)，同時基于啟發(fā)式規(guī)則進行抽取，常見的啟發(fā)式規(guī)則有：1)成對的符合一般屬于同一數(shù)據(jù)區(qū)，如《》,(),“”,‘’等；2)位于特殊符號兩邊的字符串一般也屬于同一數(shù)據(jù)區(qū)，如-,/等；3)含有年、月等語義含義的也屬于同一數(shù)據(jù)區(qū).根據(jù)這些啟發(fā)式規(guī)則，合并相應(yīng)數(shù)據(jù)區(qū).

多值區(qū)域數(shù)據(jù)抽取的算法是將數(shù)據(jù)流轉(zhuǎn)換為一個字符串列表，按順序?qū)⒆址斜碇械淖址c數(shù)據(jù)字典進行匹配，得到多值區(qū)域矩陣的列數(shù)及其標題名稱，再以空格和換行符作為分隔符對多值區(qū)域的數(shù)據(jù)區(qū)進行切分，搜索切分后的字符串是否含有空格，若有，則空格的前后內(nèi)容分別是兩個數(shù)據(jù)區(qū)的內(nèi)容，并將它們填入矩陣對應(yīng)位置，且對應(yīng)位置不再填入字符串，接下來基于前述的抽取規(guī)則和語義規(guī)則對切分后的字符串切分為若干個數(shù)據(jù)區(qū)，寫入多值區(qū)域矩陣的數(shù)據(jù)區(qū)的相應(yīng)位置；最后，將多值區(qū)域矩陣轉(zhuǎn)換為一個多元組集合輸出到文件中.

以上算法中所采用的啟發(fā)式規(guī)則適用于含有特殊字符或者特殊漢字的數(shù)據(jù)區(qū)抽取，對于純文字的數(shù)據(jù)區(qū)，由于沒有數(shù)據(jù)區(qū)劃分的規(guī)則，準確抽取較為困難，這個問題將在實驗與分析一節(jié)中進一步討論.

4 數(shù)據(jù)組織模型及數(shù)據(jù)分析

4.1 數(shù)據(jù)組織模型

數(shù)據(jù)抽取的任務(wù)是從非結(jié)構(gòu)化數(shù)據(jù)流中抽取出標題區(qū)與數(shù)據(jù)區(qū)，而數(shù)據(jù)組織的任務(wù)則是將這些數(shù)據(jù)組織起來，生成結(jié)構(gòu)化數(shù)據(jù)，為數(shù)據(jù)分析奠定基礎(chǔ).

在抽取算法中已經(jīng)說明將提取的數(shù)據(jù)區(qū)連同標題區(qū)輸出一個結(jié)構(gòu)化多元組，該多元組作為一種結(jié)構(gòu)化數(shù)據(jù)模型用來組織標題區(qū)、數(shù)據(jù)區(qū)以及它們之間的關(guān)系，下面給出該結(jié)構(gòu)化數(shù)據(jù)模型的定義：

定義6 結(jié)構(gòu)化數(shù)據(jù)模型可以表示為一個六元組DataStru=(ID，TupleID，TitleArea，DataArea， Relation，F(xiàn)oreign)，其中，ID表示文檔的惟一性標識；TupleID表示元組的惟一性標識；TitleArea表示標題區(qū)的值；DataArea表示數(shù)據(jù)區(qū)的值，它既可以是標題區(qū)字符串也可以是數(shù)據(jù)區(qū)字符串；Relation={1，0}，當值為1時,表示DataArea是TitleArea的子標題，當值為0時，表示DataArea是TitleArea對應(yīng)的數(shù)據(jù)區(qū)；Foreign表示該標題區(qū)的父標題區(qū).

根據(jù)以上定義，從非結(jié)構(gòu)化表格文檔中抽取得到的多元組集合可以保存在分布式文件中，為數(shù)據(jù)分析奠定基礎(chǔ).為了說明如何利用得到的數(shù)據(jù)集，下一節(jié)將給出基于MapReduce并行編程模型的數(shù)據(jù)分析算法.

單值區(qū)域表格抽取得到的結(jié)構(gòu)化數(shù)據(jù)集如下所示：

1. (1,1,“姓名”,“陳建偉”,0,0)

2. (1,2,“推薦晉升(轉(zhuǎn)評)職務(wù)”,“小中高”,0,0)

3. (1,8,“其中”,“中?！?1,0)

4. (1,9,“其中”,“中學”,1,0)

5. (1,10,“其中”,“小學”,1,0)

6. (1,11,“中?！?“”,0,8)

7. (1,12,“中學”,“”,0,9)

8. (1,13,“小學”,“19”,0,10)

多值區(qū)域表格抽取得到的結(jié)構(gòu)化數(shù)據(jù)集如下所示：

1. (1,27,“起止時間”,“2009.12.14—16”,0,0)

2. (1,28,“培訓項目”,“建筑抗震與設(shè)計對策”, 0,0)

3. (1,29,“組織單位”,“浙江省建筑設(shè)計研究院”, 0,0)

4. (1,30,“學習情況”,“必修課，60學時，成績合格”,0,0)

5. (1,31,“起止時間”,“2009.12.14—16”,0,0)

6. (1,32,“培訓項目”,“巖土工程設(shè)計安全度”, 0,0)

7. (1,33,“組織單位”,“浙江省建筑設(shè)計研究院”, 0,0)

8. (1,34,“學習情況”,“必修課，60學時，成績合格”,0,0)

4.2 基于MapReduce的數(shù)據(jù)分析

MapReduce是一種非常流行的分布式并行計算模型，被廣泛應(yīng)用于離線海量數(shù)據(jù)的分析.該模型主要包括Map過程、Reduce兩個過程，MapReduce節(jié)點接收數(shù)據(jù)片段，執(zhí)行用戶自定義的Map過程，輸出(Key，Value)鍵值對集合，經(jīng)過混洗和排序，把具有相同Key值的中間結(jié)果進行歸并，將歸并的結(jié)果傳輸給Reduce節(jié)點，最后執(zhí)行用戶自定義的Reduce過程，生成輸出結(jié)果.

分析的數(shù)據(jù)來自某省專業(yè)技術(shù)資格(職務(wù))評審綜合表，內(nèi)容涵蓋申報對象的基本數(shù)據(jù)、教學數(shù)據(jù)、論文數(shù)據(jù)、項目數(shù)據(jù)和獲獎數(shù)據(jù)等，根據(jù)前面的數(shù)據(jù)抽取和數(shù)據(jù)組織方法將這些文檔轉(zhuǎn)換為一個結(jié)構(gòu)化數(shù)據(jù)集，數(shù)據(jù)集中的每行包括六個字段：文件標識、行標識、標題區(qū)、數(shù)據(jù)區(qū)、關(guān)系和外鍵.下面給出兩個較為常見的MapReduce分析算法，一個是統(tǒng)計每個申報對象發(fā)表的科技論文數(shù)，另一個是統(tǒng)計所有申報對象的平均年齡.

//key:行號

//value:行字符串，對應(yīng)六元組

Map(String key,String value,Content content):

text =value.split(“,”,2)

EmitIntermediate(text[0],text[1])

//key:文件標識// values: {<行標識，標題區(qū)，數(shù)據(jù)區(qū)，關(guān)系，外鍵>}

Reduce(String key,Iterator values,Content content):

int number=0

for each v in values:

records = v.split(“,”)

if(record[1]="姓名")then

name=record[2]

if(record[1]="論文名稱")then

number++

Emit(name, number)

為了統(tǒng)計所有申報對象的平均年齡，先由Map函數(shù)按標題區(qū)對結(jié)果集重新組織，輸入為<行號，行字符串 >，輸出中間結(jié)果為<標題區(qū)，{<數(shù)據(jù)區(qū)，關(guān)系，外鍵>}>鍵值對；然后由Reduce函數(shù)對中間結(jié)果通過匹配“出生年月”關(guān)鍵字得到具體的值，最后輸出申報對象平均年齡，實現(xiàn)的算法如下：

//key:行號

//value:行字符串，對應(yīng)六元組

Map(String key,String value,Content content):

text=value.split(“,”,4)

EmitIntermediate(text[2],text[3])

//key:標題區(qū)

//values: {<數(shù)據(jù)區(qū)，關(guān)系，外鍵>}

Reduce(Stringkey,Iteratorvalues,Contentcontent):

if(key=“出生年月”)then

introws=0

doublesum=0

foreachvinvalues:

values=v.split(“,”)

rows++

sum+=nowDate-ParseDate(values[0])

Emit(age,sum/rows)

5 實驗與分析

將所提出的數(shù)據(jù)抽取與數(shù)據(jù)組織方法應(yīng)用于某省專業(yè)技術(shù)資格(職務(wù))綜合表文檔的處理，這些文檔通過某省申報與評審云平臺[23]提交，為了防止文檔被篡改在提交時都已經(jīng)轉(zhuǎn)換成PDF格式的文檔，是典型的非結(jié)構(gòu)化表格文檔，具有3個顯著特點：1) 文檔格式多樣，不同申報系列具有不同的格式，如高校教師系列、教授級高工系列、高級經(jīng)濟師系列等100余個評審系統(tǒng)的綜合表文檔幾乎都不相同；2) 文檔內(nèi)數(shù)據(jù)豐富，包括了申報對象的基本數(shù)據(jù)、教學數(shù)據(jù)、科研數(shù)據(jù)、獲獎數(shù)據(jù)、工程項目等多種類別的數(shù)據(jù)；3) 文檔體量較大，每年提交的文檔近十萬份，數(shù)據(jù)逐年疊加.

表2 非結(jié)構(gòu)化表格文檔基本信息Table 2 The basic information of unstructured form document 個

為了方便說明問題，從中選取了高校教師綜合表、教授級高工綜合表、高級經(jīng)濟師綜合表等典型的10種類型的綜合表進行數(shù)據(jù)抽取，每種類型包括200份文檔，總計2 000份文檔，表2給出了這些文檔的單值標題區(qū)、單值數(shù)據(jù)區(qū)、多值標題區(qū)、多值數(shù)據(jù)區(qū)的統(tǒng)計數(shù)據(jù)，表中的信息點表示標題區(qū)或數(shù)據(jù)區(qū).

兩個常見的評價數(shù)據(jù)抽取方法的指標是準確率與召回率.準確率用于度量抽取出來的數(shù)據(jù)中正確的比例，召回率用于度量數(shù)據(jù)被正確抽取出來的比例.一般情況下，召回率和準確率相互影響，對于同一次抽取的結(jié)果，隨著召回率的提高，準確率呈下降趨勢，隨著準確率的提高，召回率呈下降趨勢，為了綜合評價這兩個指標，通常還計算召回率R和準確率P的加權(quán)幾何平均值Fβ.其計算公式分別為

其中β為召回率和準確率的相對權(quán)重，取值一般為1/2，1，2.β=1時，二者同樣重要；β>1時，準確率更重要一些；β<1時，召回率更重要一些.

5.1 單值區(qū)域抽取結(jié)果

用單值區(qū)域抽取算法對上述2 000份文檔的單值區(qū)域進行抽取，得到了如圖3所示的實驗結(jié)果，根據(jù)該圖可以發(fā)現(xiàn)其準確率、召回率和加權(quán)幾何平均值F1(β=1)值都非常高，其中準確率最大值為99.91%，最小值為99.42%，平均值為99.64%；召回率最大值為99.90%，最小值為99.23%，平均值為99.50%；F1最大值為99.90%，最小值為99.38%，平均值為99.57%.這表明該算法對單值區(qū)域的數(shù)據(jù)抽取非常有效，其原因在于單值標題區(qū)與數(shù)據(jù)區(qū)相鄰，且標題區(qū)與數(shù)據(jù)區(qū)一一對應(yīng)，結(jié)構(gòu)較為清晰，實現(xiàn)較為容易.

圖3 單值區(qū)域數(shù)據(jù)抽取結(jié)果Fig.3 The data extraction results of single-value area

造成單值標題區(qū)及數(shù)據(jù)區(qū)抽取出錯的原因主要來源于用戶修改了綜合表中已經(jīng)定義好的標題區(qū)，這使得該標題區(qū)在數(shù)據(jù)字典里無法正確匹配，從而導致系統(tǒng)無法正確抽取.如有些申報對象將標題區(qū)的“聯(lián)系電話”修改為了“手機號碼聯(lián)系電話”，這一修改導致單值數(shù)據(jù)區(qū)“手機號碼聯(lián)系電話”抽取出錯.

5.2 多值區(qū)域抽取結(jié)果

用多值區(qū)域抽取算法對上述2 000份文檔的多值區(qū)域進行抽取，實驗結(jié)果如圖4所示.由于多值標題區(qū)結(jié)構(gòu)較為復雜，一個標題區(qū)對應(yīng)多個數(shù)據(jù)區(qū)，分屬于不同標題區(qū)的多個數(shù)據(jù)區(qū)緊密相連，一旦一個數(shù)據(jù)區(qū)抽取出錯將會導致抽取出錯連鎖效應(yīng)，所以在對多值標題區(qū)和數(shù)據(jù)區(qū)抽取時，其出錯的概率比單值標題區(qū)和數(shù)據(jù)區(qū)抽取出錯概率要大，其準確率、召回率和加權(quán)幾何平均值F1(β=1)值相比單值標題區(qū)和數(shù)據(jù)區(qū)抽取有所下降.其中準確率最大值為95.26%，最小值為93.85%，平均值為94.54%；召回率最大值為94.42%，最小值為92.83%，平均值為93.32%；F1最大值為94.36%，最小值為93.54%，平均值為93.92%.

圖4 多值區(qū)域數(shù)據(jù)抽取結(jié)果Fig.4 The data extraction results of multi-value area

導致多值區(qū)域數(shù)據(jù)抽取出錯的主要原因有以下幾個：

1) 包含硬回車的數(shù)據(jù)區(qū).若數(shù)據(jù)區(qū)的第一行字符串后有一個硬回車，則將無法判定后邊的一行字符串是屬于當前單元格還是屬于后面一個單元格，同時該數(shù)據(jù)區(qū)也不含有特殊字符，也無法利用啟發(fā)式規(guī)則.

2) 包含冗余空格的數(shù)據(jù)區(qū).若數(shù)據(jù)區(qū)的數(shù)據(jù)之間包含冗余的空格，也可能會誤將這些字符串分割為兩個數(shù)據(jù)區(qū).

3) 沒有橫向表格線的數(shù)據(jù)區(qū).若表格的各數(shù)據(jù)區(qū)之間沒有橫向表格線，則此時會將其當成一個數(shù)據(jù)區(qū)來處理，導致不正確的抽取結(jié)果.

上述3種情況是導致多值數(shù)據(jù)區(qū)域抽取出錯的主要原因，可以看出這些錯誤都是由于填寫表格不太規(guī)范導致的，這也是多值區(qū)域數(shù)據(jù)抽取算法今后需要進一步改進的地方，使數(shù)據(jù)抽取更加智能和準確.

6 結(jié) 論

非結(jié)構(gòu)化表格文檔是一類被廣泛應(yīng)用的文檔類型，具有非結(jié)構(gòu)化、樣式不固定、數(shù)據(jù)混雜和價值系統(tǒng)等特征，海量的這類文檔中存儲著豐富的有價值的數(shù)據(jù)，而數(shù)據(jù)抽取與數(shù)據(jù)組織是實現(xiàn)數(shù)據(jù)分析的重要步驟.為此，提出了一種面向非結(jié)構(gòu)化表格文檔的數(shù)據(jù)抽取方法與組織模型，在分析文檔結(jié)構(gòu)特征以及數(shù)據(jù)流特征的基礎(chǔ)上，給出了詳細的數(shù)據(jù)抽取流程和數(shù)據(jù)抽取算法，并將數(shù)據(jù)抽取的結(jié)果組織成一種適合于分布式環(huán)境下MapReduce處理的結(jié)構(gòu)化數(shù)據(jù)模型，大量實驗表明所提出的方法具有很高的準確率與召回率，具有較強的實際應(yīng)用價值.

[1] 孟小峰，慈祥.大數(shù)據(jù)管理概念、技術(shù)與挑戰(zhàn)[J].計算機研究與發(fā)展，2013，50(1)：146-169.

[2] 潘小燕.半結(jié)構(gòu)化文本中的表格信息抽取技術(shù)的研究[D].哈爾濱：哈爾濱工業(yè)大學，2007.

[3] 宋強，徐鵬，李涓子.半結(jié)構(gòu)化文檔中非標記化表格的抽取[J].計算機工程，2005，31(18)：81-83.

[4] 王允富.半結(jié)構(gòu)化文本信息抽取方法研究及應(yīng)用[D].鎮(zhèn)江：江蘇科技大學，2014.

[5] 黃豫清，戚廣志.從WEB文檔中構(gòu)造半結(jié)構(gòu)化信息的抽取器[J].軟件學報，2000，11(1)：73-78.

[6] HAMMER J, GARCIA M H, CHO J, et al. Extracting semistructured information from the web[C]// Workshop on Management of Semistructured Data. Berlin：Springer，2002：18-25.

[7] 李澎林，張獻力，李偉.基于雙字Hash機制的交通信息分詞算法研究[J].浙江工業(yè)大學學報，2014，42(6)：596-600.

[8] 宋艷娟.基于XML的HTML和PDF數(shù)據(jù)抽取技術(shù)的研究[D].福州：福州大學，2005.

[9] 霍焰.基于非結(jié)構(gòu)化文檔數(shù)據(jù)的抽取與分析系統(tǒng)的數(shù)據(jù)抽取[D].天津：天津大學，2011.

[10] 王云鵬.非結(jié)構(gòu)化文檔數(shù)據(jù)抽取與分析系統(tǒng)的設(shè)計與實現(xiàn)[D].天津：天津大學，2011.

[11] CHANG C C，HE B，LI C，et al. Structured databases on the web: observations and implications[J]. ACM sigmod record, 2004,33(3)：61-70.

[12] 劉端陽，王良芳.基于語義詞典和詞匯鏈的關(guān)鍵詞提取算法[J].浙江工業(yè)大學學報,2013,41(5):545-551.

[13] 張健，錢杰，徐茂興.網(wǎng)絡(luò)評論觀點抽取的研究[J].浙江工業(yè)大學學報,2010,38(4):415-419.

[14] 張伯.基于PDF文字流的表格識別技術(shù)的研究[D].北京：北京工業(yè)大學，2010.

[15] 劉力.科技文檔信息抽取與格式化技術(shù)研究[D].長沙：中南大學，2010.

[16] ZHOU J. Table structure recognition based on robust block segmentation[C]//The International Society for Optical Engineering. United States: SPIE, 1999, 3305：22-32.

[17] NEVES L，CARVALHO J M，F(xiàn)ACON J，et al. A table-form extraction with artefact removal[C]// Symposium on Applied Computing. Korea:ACM，2007：622-626.

[18] 萬里鵬.非結(jié)構(gòu)化到結(jié)構(gòu)化數(shù)據(jù)轉(zhuǎn)換的研究與實現(xiàn)[D].成都：西南交通大學，2013.

[19] 馮亞麗，張汝坤.基于規(guī)則庫的非結(jié)構(gòu)化數(shù)據(jù)格式轉(zhuǎn)換技術(shù)研究[J].云南師范大學學報，2012，32(2)：58-61.

[20] 鄒波.海量非結(jié)構(gòu)化數(shù)據(jù)的組織研究與實現(xiàn)[D].武漢：華中科技大學，2008.

[21] PENG T，SUN L Y，BAO H. Research of unstructured data transformation based on XML[C]//Internet Technology and Applications. Wuhan:IEEE，2010：1-4.

[22] MANSURI I R, SARAWAGI S. Integrating unstructured data into relational databases[C]// International Conference on Data Engineering. Atlanta：IEEE，2006：29-29.

[23] ZHANG Y M，NI K，LU J W，et al. DOGCP: a domain-oriented government cloud platform based on paas[C]// International Conference on Cyber Security and Cloud Computing. New York：IEEE，2015：115-120.

(責任編輯：劉 巖)

Research on data extraction and organization model for unstructured form document

ZHANG Yuanming1,2, CHEN Miao1, LU Jiawei1, XU Jun1, XIAO Gang1,2

(1.College of Computer Science and Technology， Zhejiang University of Technology， Hangzhou 310023, China；2.Post-Doctoral Research Center of Mechanical Engineering, Zhejiang University of Technology, Hangzhou 310014, China)

In order to improve the flexibility of data extraction from complex unstructured form document, this paper proposes an extraction approach and a structured data model. The document structural features and data flow characteristics of unstructured form document are studied in details. A set of data flow generation rules are concluded. A data extraction process including logical structure extraction, document preprocessing, data extraction, and data organization, is designed. Two extraction algorithms for single-value area and multi-value area of document are implemented. The extracted data are organized into a structured data model that is designed to facilitate data analysis by MapReduce. Experimental results show that the proposed approach has great accuracy rate and recall rate. The structured data model also can effectively meet the requirements of data analysis by MapReduce.

unstructured form document; data extraction; structured data model, data analysis

2016-01-23

浙江省錢江人才計劃D類項目 (QJD1302009)；浙江省重大科技專項資助項目(2014C01408)

張元鳴 (1977—)，男，河南濮陽人，副教授，博士，研究方向為大數(shù)據(jù)處理、服務(wù)計算和并行計算等，E-mail：zym@zjut.edu.cn.

TP391

A

1006-4303(2016)05-0487-08

每個申報對象發(fā)表的論文數(shù)，先由Map函數(shù)對結(jié)果集中的行按文件標識進行重組，其輸入為<行號，行字符串>，輸出中間結(jié)果是<文件標識，{<行標識，標題區(qū)，數(shù)據(jù)區(qū)，關(guān)系，外鍵>}>；然后由Reduce函數(shù)根據(jù)前面的中間結(jié)果查找申報對象姓名并計算發(fā)表的論文數(shù)，方法是通過匹配“姓名”關(guān)鍵字得到姓名的值，通過匹配“論文名稱”等關(guān)鍵字計算論文數(shù)量，最后將姓名和論文數(shù)量作為鍵值對輸出，實現(xiàn)算法如下：