語法分析與糾錯相結(jié)合的文檔結(jié)構(gòu)重構(gòu)方法

張 真，李 寧，田英愛，耿 思，許 潔

(1.北京信息科技大學(xué) 計算機學(xué)院，北京 100101；2.中國電子技術(shù)標(biāo)準(zhǔn)研究院, 北京 100007)

0 引言

流式文檔結(jié)構(gòu)承載著大量寶貴的語義信息[1]，對文檔理解有著重要作用。例如計算機自動提取文檔的大綱時，需要文檔結(jié)構(gòu)。文檔的邏輯構(gòu)件表示文檔段落的語義信息(例如“摘要”，“一級標(biāo)題”等),文檔邏輯構(gòu)件之間的關(guān)系形成文檔結(jié)構(gòu)。由于流式文檔排版格式的復(fù)雜性，大部分的流式文檔都存在一定的錯誤，如標(biāo)題式樣錯誤、圖表錯誤等，會導(dǎo)致文檔邏輯構(gòu)件的缺失、冗余、位置錯誤等。以往不包含容錯的文檔結(jié)構(gòu)重構(gòu)算法無法處理上述情況。因此流式文檔的結(jié)構(gòu)重構(gòu)算法中，高效的容錯算法至關(guān)重要。

1 相關(guān)研究

目前，學(xué)者們在文檔結(jié)構(gòu)重構(gòu)上進行了一些研究。文獻[2]將邏輯構(gòu)件建立為有向圖表示的文檔結(jié)構(gòu)，通過有向圖的單源最短路徑算法過濾多余的有向圖，得到文檔結(jié)構(gòu)，但是該方法必須確保文檔構(gòu)件識別的準(zhǔn)確性；文獻[3]構(gòu)造了一個有限狀態(tài)自動機，根據(jù)狀態(tài)轉(zhuǎn)移函數(shù)控制文檔結(jié)構(gòu)識別的順序，該方法雖然能夠?qū)ξ臋n進行整體結(jié)構(gòu)識別，但沒有考慮構(gòu)件缺失、多余及順序顛倒等情況。如前所述，已有的方法雖然能對流式文檔的結(jié)構(gòu)進行重構(gòu)，但前提是文檔構(gòu)件不存在錯誤。文獻[4]提出文檔結(jié)構(gòu)識別問題為序列標(biāo)注問題，使用條件隨機場來對文檔進行序列標(biāo)注，具有一定的容錯性，但只針對特定類型的文檔，靈活性較差；文獻[5]定義了一個具有容錯能力的文檔模型，通過概率松弛的啟發(fā)式相似度度量方法計算待查文檔與文檔模型的相似度，并選擇最佳優(yōu)先搜索方法構(gòu)建文檔邏輯結(jié)構(gòu)。在語義標(biāo)注容錯處理研究中，通常使用語義角色標(biāo)注系統(tǒng)融合來減輕句法分析錯誤對語義角色標(biāo)注的影響，文獻[6]提出一種最小錯誤加權(quán)的系統(tǒng)融合方法，對每個系統(tǒng)的標(biāo)注結(jié)果給予不同的權(quán)值，標(biāo)注結(jié)果越可信其權(quán)值越高。在文本自動校對的研究中，文獻[7]提出語法分析和詞匹配相結(jié)合的方法，通過統(tǒng)計與規(guī)則相結(jié)合，對散串進行語法分析和詞匹配，從而發(fā)現(xiàn)候選錯誤字串；文獻[8]首先使用精確匹配方法和中文串模糊相似度算法對中文文本進行精確切分和模糊切分，建立詞圖，然后使用最短路徑方法來進行錯誤的自動發(fā)現(xiàn)和自動糾正；文獻[9]提出一種基于領(lǐng)域問答系統(tǒng)的錯別字自動發(fā)現(xiàn)方法，通過多字詞和合并串進行相似詞串聚類，對相似串的上下文語境進行分析，從而發(fā)現(xiàn)錯誤；文獻[10]提出一種基于語義搭配知識庫和證據(jù)理論的語義錯誤偵測方法，首先構(gòu)造語義搭配知識庫，然后使用自頂向下的方法發(fā)現(xiàn)可能的錯誤，結(jié)合語義搭配以及規(guī)則獲取詞語的語義搭配關(guān)聯(lián)度。上述方法主要針對的是中文文本和語義角色標(biāo)注中的錯誤，雖然研究領(lǐng)域不同，但是研究方法上有一定的參考價值。

綜上所述，當(dāng)流式文檔中出現(xiàn)邏輯構(gòu)件的缺失、冗余、位置錯誤等情況時，將使文檔結(jié)構(gòu)重構(gòu)方法難以處理。本文提出了一種性能更優(yōu)的算法，使流式文檔結(jié)構(gòu)重構(gòu)在文檔邏輯構(gòu)件存在錯誤的情況下，仍然能高效地分析出符合預(yù)定義排版規(guī)則的結(jié)構(gòu)。

2 文檔元數(shù)據(jù)模型的構(gòu)建

在進行文檔結(jié)構(gòu)重構(gòu)過程中，文檔元數(shù)據(jù)模型需要確定文檔中邏輯構(gòu)件的出現(xiàn)順序、出現(xiàn)次數(shù)以及嵌套結(jié)構(gòu)，最終形成一棵規(guī)則語法樹，用于分析文檔邏輯結(jié)構(gòu)的正確性。文檔元數(shù)據(jù)模型的構(gòu)建一般有基于模板[11]和基于語法[12]的方法。當(dāng)使用模板的方法時，一旦編寫模板出現(xiàn)錯誤，則會對文檔結(jié)構(gòu)重構(gòu)產(chǎn)生一定影響；基于語法的方法中，使用XML Schema可定義文檔元數(shù)據(jù)的屬性、數(shù)據(jù)類型、元素及其包含關(guān)系，便于解析，所以本文使用XML Schema來構(gòu)建文檔元數(shù)據(jù)模型。以學(xué)位論文為例，邏輯構(gòu)件集合為{摘要，正文，關(guān)鍵詞，一級標(biāo)題，列表，圖，表，圖題，表題}，則其邏輯構(gòu)件的排版規(guī)則語法樹如圖1所示。

圖1 學(xué)位論文邏輯構(gòu)件排版規(guī)則語法樹圖舉例

每篇論文包含頭部和章節(jié)兩部分，并且按順序出現(xiàn)。頭部包含摘要、正文和關(guān)鍵詞，正文最少出現(xiàn)1次，最多出現(xiàn)3次。章節(jié)這部分可重復(fù)出現(xiàn)多次，包含一級標(biāo)題、內(nèi)容和二級章節(jié)，其中內(nèi)容和二級章節(jié)是可選節(jié)點。該部分的描述和章節(jié)部分的結(jié)構(gòu)是相似的，只是級別不同。

3 基于左角分析法的文檔結(jié)構(gòu)重構(gòu)

在文檔邏輯構(gòu)件重構(gòu)過程中，需要避免大量的、無謂的節(jié)點遍歷。在自然語言處理中，結(jié)構(gòu)重構(gòu)的方法一般有3種，即自頂向下的方法、自底向上的方法以及兩者相結(jié)合的左角分析法[13-14]。使用左角分析法，既可以避免純粹的自頂向下分析算法窮盡式擴展非終結(jié)符節(jié)點，又可以避免自底向上分析中盲目歸約當(dāng)前節(jié)點導(dǎo)致父節(jié)點找錯的問題，可以有效解決文檔邏輯構(gòu)件遍歷過程中的問題。本文使用左角分析法進行文檔結(jié)構(gòu)重構(gòu)。

在文檔結(jié)構(gòu)重構(gòu)中，“左角”是指文檔結(jié)構(gòu)樹中任何子樹的左下角符號。例如在圖1中，“一級標(biāo)題”是“章節(jié)”的左角?；谧蠼欠治龇ǖ闹貥?gòu)過程由語法樹進行引導(dǎo)，定義所有的非葉子節(jié)點為需要判斷的狀態(tài)節(jié)點，使用左角分析法來對每個狀態(tài)節(jié)點進行判斷，從根節(jié)點在語法樹中的位置開始，沿著樹的左側(cè)邊，展開非葉子節(jié)點，一直到這棵樹最底部最左的非葉子節(jié)點。判斷當(dāng)前輸入的邏輯標(biāo)簽是否是最底部最左狀態(tài)節(jié)點的左角，如果不是，通過查找該狀態(tài)節(jié)點的兄弟節(jié)點，對該兄弟節(jié)點進行判斷；如果是，則跳入該子結(jié)構(gòu)繼續(xù)判斷識別。當(dāng)子結(jié)構(gòu)的所有葉節(jié)點都判斷完以后，該子結(jié)構(gòu)識別結(jié)束，使用XML儲存識別子結(jié)構(gòu)的結(jié)果。算法通過堆棧先進后出的功能來保留狀態(tài)節(jié)點信息。具體描述如下：

算法1基于左角分析法的狀態(tài)節(jié)點結(jié)構(gòu)判斷算法

將狀態(tài)節(jié)點state1節(jié)點壓入棧stack中;

構(gòu)建以state1為根節(jié)點的XML文件state1XML；

if(當(dāng)前邏輯構(gòu)件是state1的子孫節(jié)點){

if(currentLabel的父節(jié)點是state1){

將currentLabel加入到state1XML；

While(棧不為空){

將下一個構(gòu)件輸入到stack中;

else if(棧頂為α,B→αγ)：

}

if(state1有兄弟節(jié)點)

遞歸調(diào)用算法1對兄弟節(jié)點進行判斷；

else

返回state1的XML結(jié)構(gòu);

}

例如邏輯標(biāo)簽集合{摘要，正文，關(guān)鍵詞}，狀態(tài)節(jié)點集合為{論文，頭部，一級章節(jié)，二級章節(jié)，三級標(biāo)題}，首先對根節(jié)點‘論文’進行判斷，沿著最左側(cè)展開為頭部，通過判斷當(dāng)前輸入的邏輯標(biāo)簽摘要是頭部的左角，對頭部狀態(tài)節(jié)點進行判斷，具體分析過程如表1所示。

表1 左角分析法分析過程舉例

4 基于糾錯規(guī)則的容錯處理

由于用戶在寫作過程中一般會出現(xiàn)一些錯誤；另外，機器對構(gòu)件的識別結(jié)果也可能不準(zhǔn)確，容易造成第3節(jié)中文檔結(jié)構(gòu)分析過程無法進行或分析結(jié)果不準(zhǔn)確。所以在使用左角分析法分析文檔結(jié)構(gòu)的過程中，需要考慮錯誤處理，從而生成盡可能符合用戶寫作意圖的結(jié)構(gòu)。為解決以往結(jié)構(gòu)重構(gòu)方法在遇到錯誤時無法進行重構(gòu)的問題，本文將加入糾錯規(guī)則，使得文檔分析在邏輯構(gòu)件出錯的情況下能繼續(xù)做出正確判斷，生成盡可能符合作者意圖的結(jié)構(gòu)。

4.1 錯誤分析

結(jié)構(gòu)分析中的錯誤主要有兩類：一類是作者寫作時產(chǎn)生的錯誤；一類是機器識別構(gòu)件時產(chǎn)生的錯誤。本文參照北京信息科技大學(xué)的學(xué)位論文規(guī)范對300篇北京信息科技大學(xué)的學(xué)位論文中的錯誤進行統(tǒng)計。經(jīng)過人工統(tǒng)計，發(fā)現(xiàn)內(nèi)容缺失類錯誤包括標(biāo)題、摘要、參考文獻等關(guān)鍵字的丟失；標(biāo)題順序類錯誤包括各級標(biāo)題的順序不連續(xù)；表題、圖題類錯誤包括表題、圖題不規(guī)范；大綱級別類錯誤包括標(biāo)題大綱級別與其所屬的級別不符。我們對每一篇文檔進行人工判斷，統(tǒng)計上述錯誤數(shù)量，發(fā)現(xiàn)標(biāo)題錯誤和圖表錯誤是文檔結(jié)構(gòu)重構(gòu)常見的錯誤。其中標(biāo)題錯誤、題注的缺失、圖表與相應(yīng)題注的位置顛倒在所有錯誤中占比分別為42%、33%、18%，因此本文針對上述3種錯誤制定糾錯規(guī)則。

4.2 糾錯規(guī)則的構(gòu)建

文檔結(jié)構(gòu)分析過程中，由于含有錯誤的構(gòu)件集合無法滿足排版規(guī)則，將造成左角分析法無法進行或分析結(jié)果不準(zhǔn)確。本文從左角分析法的文檔結(jié)構(gòu)重構(gòu)分析過程中來發(fā)現(xiàn)這些錯誤，并且進行相對應(yīng)的處理，制定了以下規(guī)則來判斷分析。

[規(guī)則1]重構(gòu)分析過程中，如果發(fā)現(xiàn)當(dāng)前判斷狀態(tài)節(jié)點和待查構(gòu)件是祖父關(guān)系時，利用以下算法進行處理。

算法2狀態(tài)節(jié)點與待查構(gòu)件是祖父關(guān)系錯誤處理算法

if(當(dāng)前邏輯構(gòu)件currentLabel是下一個邏輯構(gòu)件nextLabel的父節(jié)點)

將currentLabel,nextLabel位置互換；

else{

統(tǒng)計下文中與當(dāng)前邏輯構(gòu)件級別相同的個數(shù)count，直到出現(xiàn)不同級別的邏輯構(gòu)件為止；

if(count>1)

在currentLabel之前添加currentLabel的上一級構(gòu)件；

else

將currentLabel的級別設(shè)為上一級；

}

該規(guī)則多應(yīng)用于標(biāo)題的缺失、冗余、位置錯亂處理中，例如構(gòu)件集合{一級標(biāo)題，三級標(biāo)題，正文}，可以使用以上規(guī)則發(fā)現(xiàn)二級標(biāo)題的缺失并糾正。

[規(guī)則2]重構(gòu)分析過程中，如果發(fā)現(xiàn)當(dāng)前待查邏輯構(gòu)件是當(dāng)前判斷狀態(tài)非第一個孩子的子節(jié)點時，使用以下算法進行處理，偽代碼如下:

算法3構(gòu)件是狀態(tài)節(jié)點的子節(jié)點且非第一個孩子節(jié)點的處理算法

if(下一個邏輯構(gòu)件nextLabel是當(dāng)前狀態(tài)state的第一個子節(jié)點)

將nextLabel和當(dāng)前邏輯構(gòu)件currentLabel互換；

else

添加與state第一個子節(jié)點相匹配的邏輯構(gòu)件；

[規(guī)則3]重構(gòu)生成后的文件保存為XML文件，但是該XML文件使用Schema校驗時出現(xiàn)校驗失敗時，使用以下方法處理。

由于在Schema中限制了章節(jié)可出現(xiàn)的次數(shù)，當(dāng)XML校驗失敗則說明該XML文檔結(jié)構(gòu)不完整，返回缺少章節(jié)的名稱。讀取XML中該章節(jié)的標(biāo)題T，查找其上級邏輯構(gòu)件S，通過比較上下兩級標(biāo)題的相似度來判斷來進行糾正分析。其定義如下：

(1)

(2)

式中：S和T的長度分別為m、n；矩陣Dij為長度為i的邏輯構(gòu)件S轉(zhuǎn)變?yōu)殚L度為j的邏輯構(gòu)件T所需要的編輯距離。

最終，字符串S和T的編輯距離D(S,T)即為矩陣中右下角Dmn的值。其相似度定義為

(3)

式中：sim(S,T)為S、T的相似度；|S|為S的字符串長度；|T|為T的字符串長度。如果Sim(S,T)的相似度為1，說明2個邏輯構(gòu)件名稱完全相同，則認(rèn)為T多余；否則，比較T與nextLabel的相似度，如果Sim(T,nextLabel)大于等于0.5，則認(rèn)為nextLabel存在級別錯誤，應(yīng)與T級別相同；否則，認(rèn)為T為多余邏輯構(gòu)件。

4.3 容錯處理

具有容錯能力的文檔結(jié)構(gòu)重構(gòu)算法將容錯規(guī)則和第3節(jié)的方法結(jié)合起來.在使用左角分析法過程中，通過對狀態(tài)節(jié)點與當(dāng)前輸入構(gòu)件的關(guān)系進行分析，判斷該構(gòu)件是否有錯，如果發(fā)現(xiàn)當(dāng)前輸入構(gòu)件是狀態(tài)節(jié)點的左角，則使用第3節(jié)的方法繼續(xù)分析文檔結(jié)構(gòu)；否則判定為構(gòu)件錯誤，調(diào)用相應(yīng)的規(guī)則進行處理。算法描述如下。

算法4添加糾錯規(guī)則的結(jié)構(gòu)重構(gòu)算法

if (當(dāng)前輸入邏輯構(gòu)件currentLabel是當(dāng)前判斷狀態(tài)state的子孫節(jié)點){

if(state是currentLabel父節(jié)點){

if(currentlabel是state的第一個孩子節(jié)點){

算法1分析文檔結(jié)構(gòu)；

else

按規(guī)則2處理；

}

else

按規(guī)則1處理；

}

算法4中，使用規(guī)則1和規(guī)則2對常見錯誤進行具體分析和糾錯，糾錯以后繼續(xù)使用左角分析法識別文檔結(jié)構(gòu)，直到分析出狀態(tài)節(jié)點的子結(jié)構(gòu)；同時為了能夠確保每個狀態(tài)節(jié)點子結(jié)構(gòu)識別的準(zhǔn)確性，將每個狀態(tài)節(jié)點的子結(jié)構(gòu)識別結(jié)果分別以XML形式存儲，并調(diào)用預(yù)先設(shè)定的Schema進行驗證，如果校驗失敗按照規(guī)則3對其進行改正。

5 實驗

本實驗采用北京信息科技大學(xué)的學(xué)位論文來驗證容錯處理能力方面的識別效果。我們選擇了50篇共含有108個錯誤測試點的文本結(jié)構(gòu)樣例。由于文檔的保密要求，本文選擇了在github上公布的68篇數(shù)據(jù)(https://github.com/COSLab)。每篇樣例都含有一個或多個錯誤。我們利用左角分析法和糾錯規(guī)則相結(jié)合的算法進行糾錯，共糾正錯誤96個，其中真正的錯誤89個，準(zhǔn)確率為92.71%，召回率為82.41%。對于常見的錯誤處理情況如表2所示。

本文方法在處理文檔中的常見錯誤時，一旦發(fā)現(xiàn)錯誤，對錯誤的識別準(zhǔn)確率較高。對于標(biāo)題缺失和表題位置顛倒的錯誤，這些邏輯構(gòu)件的缺失或順序錯亂，使用以往的流式文檔重構(gòu)方法如有限狀態(tài)機和有向圖的方法，因為無法找到與文檔排版相匹配的規(guī)則都會造成重構(gòu)失?。欢鴮τ跇?biāo)題冗余的錯誤會造成重構(gòu)結(jié)果不符合寫作意圖；但是本文方法通過容錯規(guī)則都能準(zhǔn)確識別。

表2 常見錯誤的識別效果 %

對于文檔結(jié)構(gòu)識別結(jié)果，本文方法與基于有限狀態(tài)自動機的方法[3]和基于有向圖[2]的方法進行比較。采用上述相同的語料集合，評價指標(biāo)選用正確率來評價文檔結(jié)構(gòu)識別的效果。最后發(fā)現(xiàn)，基于有限狀態(tài)自動機的方法準(zhǔn)確率為94.22%，基于有向圖的方法為97.38%，本文方法的正確率為98.86%。本文方法相比于基于有限狀態(tài)機的方法和基于有向圖的方法識別結(jié)果都要好。究其原因，是因為本文方法通過排版規(guī)則可以對文檔結(jié)構(gòu)進行全面的分析，充分考慮每一種邏輯構(gòu)件轉(zhuǎn)移的可能性，增強了文檔結(jié)構(gòu)理解的容錯性，提高了文檔結(jié)構(gòu)理解的正確性。

6 結(jié)束語

本文針對目前流式文檔結(jié)構(gòu)重構(gòu)方法容錯能力不足的問題，提出一種語法分析與糾錯規(guī)則結(jié)合的流式文檔結(jié)構(gòu)重構(gòu)方法。實驗表明，本文方法能處理常見錯誤，一定程度上解決了以往方法遇到錯誤無法處理或者識別錯誤的問題，提高了結(jié)構(gòu)重構(gòu)的容錯能力。但是本文方法中也存在一些問題，將來可以考慮增加對文本內(nèi)容的語義分析從而將不常見的錯誤加入進來，因此加入語義信息來分析文檔結(jié)構(gòu)錯誤是未來研究的重點。