基于有限狀態(tài)機模型的供電故障斷電區(qū)間快速提取方法

楊濤存，郭劍峰，杜文然，徐貴紅

（1.中國鐵道科學研究院集團有限公司電子計算技術(shù)研究所，北京100081；2.中國鐵道科學研究院集團有限公司基礎(chǔ)設(shè)施檢測研究所，北京100081；3.中國鐵道科學研究院研究生部，北京100081）

1 背景

鐵路供電故障數(shù)據(jù)分析中，需要計算斷電區(qū)間長度，供電故障數(shù)據(jù)大多以非結(jié)構(gòu)化文字描述形式記錄存儲，需從中提取斷電區(qū)間起始位置、終止位置，計算兩者里程差值，得到故障區(qū)間長度，再根據(jù)線路復線數(shù)量，計算此區(qū)間需乘的倍率系數(shù)。在實際生產(chǎn)中遇到供電故障問題時，從故障描述中提取斷點區(qū)間起始位置、終止位置和倍率系數(shù)往往需要人工閱讀提取，耗費大量時間、精力，使供電故障數(shù)據(jù)分析成本大幅提升。

隨著自然語言處理技術(shù)在鐵路領(lǐng)域的應(yīng)用，研究如何從非結(jié)構(gòu)化數(shù)據(jù)中提取特定信息是文本信息處理中的重要問題。有限狀態(tài)機算法能夠描述對象在生命周期內(nèi)所經(jīng)歷的狀態(tài)序列，作為一種有效的信息提取方法，被廣泛用于多個領(lǐng)域。朱華炳等［1］在數(shù)控技術(shù)領(lǐng)域，通過分析STEP-NC數(shù)據(jù)流和STEP-NC程序模型，提出了基于有限狀態(tài)機的STEP-NC信息提取系統(tǒng)實現(xiàn)方案；吳春成等［2］在航空領(lǐng)域有限狀態(tài)機算法的基礎(chǔ)上，對飛行控制軟件進行測試，提高了檢測錯誤的能力；王煥民等［3］在鐵路運輸領(lǐng)域，以有限狀態(tài)機模型為基礎(chǔ)，開發(fā)了一套檢修業(yè)務(wù)流程建模與管理系統(tǒng)。在此，通過對目標文本進行預處理，獲得關(guān)鍵詞集，再對關(guān)鍵詞集中的對象關(guān)鍵詞進行特征信息提取，獲得關(guān)鍵詞特征集，結(jié)合模式識別或機器學習相關(guān)方法，達到快速提取文本中特定信息的目的。

2 相關(guān)技術(shù)

文本關(guān)鍵信息提取是自然語言處理專業(yè)中重要的研究內(nèi)容，又稱信息抽取，是把文本中包含的非結(jié)構(gòu)化信息提取出來，形成結(jié)構(gòu)化信息。把原始文本輸入關(guān)鍵信息提取系統(tǒng)，系統(tǒng)輸出固定格式的結(jié)構(gòu)化信息表。通常，信息提取技術(shù)不需要全面理解整篇文檔，只對文檔中包含相關(guān)信息的部分進行解析?；谟邢逘顟B(tài)機的模式識別方法是一種經(jīng)典的信息提取方法，具有速度快、準確率高、魯棒性好等特點，廣泛用于自然語言處理、信息提取的各種研究中。

2.1 有限狀態(tài)機

有限狀態(tài)機是一種用來進行對象行為建模的工具，主要作用是描述對象在生命周期內(nèi)所經(jīng)歷的狀態(tài)序列，以及如何響應(yīng)來自外界的各種事件。在計算機科學中，有限狀態(tài)機被廣泛用于建模應(yīng)用行為、硬件電路系統(tǒng)設(shè)計、軟件工程、編譯器、網(wǎng)絡(luò)協(xié)議和計算與語言的研究。

2.2 正則匹配

正則表達式由美國數(shù)學家Stephen Kleene于1956年提出，又稱正規(guī)表示法、正規(guī)式，主要用于描述正則集代數(shù)［4］。它是提供給計算機操作和檢驗所要提取字符串數(shù)據(jù)的一種強大工具，是1串特定意義字符組成的字符串，表示某種匹配的規(guī)則［5］。正則表達式最基本的3種功能是匹配、替換和提取。匹配功能是利用設(shè)定好的匹配表達式與數(shù)據(jù)文件中的目標文本進行比較，根據(jù)比較結(jié)果判斷1個串是否含有某種子串、將匹配的子串做替換或者從某個串中取出符合某個條件的子串等。正則表達式匹配在文本編輯、生物信息學、模式識別等領(lǐng)域有重要的應(yīng)用，幾乎所有的主流高級語言都可以支持其運行［6］。

利用正則表達式快速匹配文本的特點進行信息提取。供電故障記錄文件是非結(jié)構(gòu)化的文本文件，而生產(chǎn)系統(tǒng)的記錄文件是半結(jié)構(gòu)化甚至非結(jié)構(gòu)化的文本文件，因此利用正則表達式進行文本信息降維處理、匹配特征項，實現(xiàn)文本數(shù)據(jù)自動閱讀和信息提取是切實可行的方法。

2.3 自然語言處理

自然語言處理是大規(guī)模文本數(shù)據(jù)自動分析的基礎(chǔ)。常用的自然語言處理技術(shù)主要有中文分詞、詞性標注、未登錄詞識別、句法分析、文本聚類、信息提取和檢索等技術(shù)［7］。自然語言處理研究提供的各種理論和工具，可以為深入分析文本內(nèi)容提供可能的應(yīng)用［8］。

中文分詞是中文信息處理的基礎(chǔ)，現(xiàn)有的分詞算法大致可分為三大類：基于字符串匹配、基于理解、基于統(tǒng)計的分詞方法?；谧址ヅ涞姆衷~方法具有算法簡單、分詞效率高的特點，因此常常綜合運用于其他分詞算法中［9］。這類算法是按照一定策略將待分析的漢字串與一個“充分大的”機器詞典中的詞條進行匹配，若在詞典中找到這個字符串，則匹配成功（識別出一個詞）。由于這類算法都要用到一個詞典，因此查詢效率是影響這類算法的一個關(guān)鍵因素［9］，為了快速對查詢子串進行“詞”判斷，使用有限狀態(tài)機算法對詞典進行快速查詢。

供電故障描述數(shù)據(jù)按結(jié)構(gòu)化組織，但描述內(nèi)容是文本形式，屬于非結(jié)構(gòu)化的數(shù)據(jù)，同時數(shù)據(jù)中包括專業(yè)術(shù)語、英文符號、數(shù)字及特殊字符等，內(nèi)容相對雜亂，因此文本數(shù)據(jù)挖掘方法的選擇是工作重點和難點。

3 方法設(shè)計

提出基于有限狀態(tài)機的自動化特征信息提取方法，供電故障信息首先經(jīng)過分詞預處理，形成中文單詞，然后利用基于有限狀態(tài)機的匹配模型，結(jié)合正則表達式技術(shù)，進行提取匹配，提取出斷電區(qū)間起始位置、終止位置和倍率系數(shù)。

3.1 問題描述

供電故障數(shù)據(jù)以結(jié)構(gòu)化方式存儲，包括十幾個字段信息，供電區(qū)間相關(guān)信息只來自局別、線別和斷電區(qū)間字段，方法實現(xiàn)過程中，只考慮這些字段，不與其他字段交互。

需求的目標是從相關(guān)字段中，自動提取匹配出線別、斷電區(qū)間起始位置、斷電區(qū)間終止位置和倍率系數(shù)。斷電區(qū)間起始及終止位置，可能是某車站或某線路的某里程點；倍率系數(shù)是計算斷電區(qū)間長度時，由于復線等因素影響，斷電區(qū)間終止到起始位置長度需要相乘系數(shù)，例如單線鐵路或只有上、下行單個行別斷電的故障，倍率系數(shù)就是1，若雙線鐵路上、下行均同時停電，倍率系數(shù)是2。

匹配得到斷電區(qū)間起始位置、終止位置和倍率系數(shù)后，再根據(jù)線路設(shè)備臺賬，查詢斷電線路中斷電區(qū)間起始位置、終止位置的對應(yīng)里程，用里程數(shù)差值乘以倍率系數(shù)，得到最終斷電區(qū)間長度。

用L表示斷點區(qū)間長度，ms表示斷電區(qū)間起始里程，me表示斷點區(qū)間終點里程，γ表示倍率系數(shù)，則L可表示為三者的函數(shù)，其表達式如下：

3.2 分詞預處理

由于需求中所描述的問題屬于中文自然語言處理問題，采用分詞技術(shù)對數(shù)據(jù)進行預處理是數(shù)據(jù)處理的第一個步驟［10］。所謂中文分詞是將1個漢字序列切分成多個單獨的詞。分詞就是將連續(xù)的字序列按照一定的規(guī)范重新組合成詞序列的過程。當前主流的中文分詞方法可分為三大類：基于字符串匹配、基于理解、基于統(tǒng)計的分詞方法。

采用一種基于Trie樹［11］結(jié)構(gòu)的算法，Trie樹也稱前綴樹，是一種有序樹，是專門用來處理字符串匹配的數(shù)據(jù)結(jié)構(gòu)，解決在1組字符串集合中快速查找某個字符串的問題。這種方法高效實現(xiàn)詞圖掃描，得到句子中漢字的所有成詞可能，并且將所有成詞可能的情況構(gòu)成有向無環(huán)圖（DAG）。在該圖中查找最大概率路徑，在實現(xiàn)過程中，不僅將字典生成Trie樹，同時把每個詞的出現(xiàn)次數(shù)轉(zhuǎn)換為頻率，再采用動態(tài)規(guī)劃查找法，找出基于詞頻的最大切分組合。對于分詞詞典中未出現(xiàn)的詞，即未登錄詞，采用Viterbi算法［12］，將問題抽象為最優(yōu)選擇問題，每一步的所有選擇都保存了前面所有步驟到當前選擇的最小總代價，以及當前代價情況下前面步驟的選擇。依次計算完所有步驟后，通過回溯的方法找到最優(yōu)選擇路徑［4］，將這種方法用于漢字成詞的HMM模型，估計其成詞概率，再進行分詞［13］。

3.3 有限狀態(tài)機匹配模型

經(jīng)過分詞預處理后的斷電區(qū)間數(shù)據(jù)，成為單詞流序列數(shù)據(jù)，適用于建立有限狀態(tài)機匹配模型，對其中斷電區(qū)間起始位置、終止位置和倍率系數(shù)3個信息進行提取。

由于任務(wù)是從1個結(jié)構(gòu)化字段中提取3個信息，對原始數(shù)據(jù)觀察，數(shù)據(jù)中自然存在特定分隔符，可以將這3部分中的1部分或2部分自然分隔，因此數(shù)據(jù)匹配時，首先對斷電區(qū)間數(shù)據(jù)利用分隔符字典中定義的分隔符進行切分，使之成為2個或3個文本區(qū)段，再進行信息匹配。分隔符字典定義見表1。

表1 分隔符字典定義表

文本數(shù)據(jù)經(jīng)分隔符分割后，處理成前、后2段，從前段中提取斷電區(qū)間起始位置信息，從后段中提取斷電區(qū)間終止位置和倍率系數(shù)信息。斷電區(qū)間起始位置信息提取時，經(jīng)過特殊、無效、提示字符去除，進入線路所匹配模式或線路匹配模式，在相應(yīng)匹配模式中，去除非站名相關(guān)字符，匹配得相應(yīng)站名。斷電區(qū)間終止位置提取時，與斷電區(qū)間起始位置提取步驟相同，經(jīng)過特殊、無效、提示字符去除，進入線路所匹配模式或線路匹配模式，在相應(yīng)匹配模式中，去除非站名相關(guān)字符，匹配得相應(yīng)站名。倍率系數(shù)提取時，根據(jù)關(guān)鍵字，判斷進入行別匹配模式或復線匹配模式，再匹配線數(shù)量，得到倍率系數(shù)。

信息提取過程，抽象為有限狀態(tài)機模型，不同匹配步驟作為有限狀態(tài)機的狀態(tài)，根據(jù)數(shù)據(jù)特征及業(yè)務(wù)需求，抽象為9個狀態(tài)，由S加數(shù)字0到8表示，有限狀態(tài)機狀態(tài)定義見表2。

表2 有限狀態(tài)機狀態(tài)定義表

匹配過程符合有限狀態(tài)機狀態(tài)轉(zhuǎn)移過程，各狀態(tài)接受不同條件輸入，得到不同輸出及發(fā)生狀態(tài)轉(zhuǎn)移，有限狀態(tài)機模型狀態(tài)轉(zhuǎn)移見圖1。

圖1 有限狀態(tài)機模型狀態(tài)轉(zhuǎn)移圖

狀態(tài)轉(zhuǎn)移條件即輸入的字符或單詞，根據(jù)不同條件輸入，按照狀態(tài)轉(zhuǎn)移圖中的各有向邊，由一個狀態(tài)轉(zhuǎn)移至另一個狀態(tài)。用ε符號表示空輸入，EOF表示輸入結(jié)束符，狀態(tài)轉(zhuǎn)移條件矩陣定義見表3。

表3 狀態(tài)轉(zhuǎn)移條件矩陣定義表

4 試驗驗證

多種高級語言均支持有限狀態(tài)機模型［14］，試驗部分基于Python框架實現(xiàn)上述有限狀態(tài)機模型，并對此模型準確率及運行速度開展測試，試驗所用系統(tǒng)軟、硬件環(huán)境見表4。

表4 試驗環(huán)境列表

4.1 數(shù)據(jù)選取

選取某段時間內(nèi)某地區(qū)高速鐵路供電故障數(shù)據(jù)，對上述模型進行測試。數(shù)據(jù)以結(jié)構(gòu)化方式存儲，模型所處理的字段為局別、線別、斷電區(qū)間共3個字段，斷電區(qū)間描述中，基本涵蓋生產(chǎn)系統(tǒng)中各種常見的故障描述方式。

4.2 試驗結(jié)果

分別對基于Python框架的有限狀態(tài)機自動識別模型進行準確率、運行速度測試，采用典型評價指標評價結(jié)果。

4.2.1 準確率

利用模型進行準確率測試，準備測試數(shù)據(jù)共200條，按批測試，每批40條，分別統(tǒng)計計算斷電區(qū)間起始位置、終止位置和倍率系數(shù)準確率，模型提取結(jié)果與正確標簽直接對比，內(nèi)容完全一致，認為識別正確，任何字符不一致認為識別錯誤，按此計算識別準確率。模型準確率測試結(jié)果見表5。

表5 模型準確率測試結(jié)果 %

斷電區(qū)間字段經(jīng)過2次切分形成3個部分，斷電區(qū)間起始位置識別準確率達到92.0%；由于斷電區(qū)間終止位置位于文本數(shù)據(jù)中部，較易出現(xiàn)切分錯誤導致的識別不準確，雖然與斷電區(qū)間起始位置識別算法相近，斷電區(qū)間終止位置識別準確率大幅低于起始位置準確率，但仍能達到79.0%；倍率系數(shù)字段處于文本數(shù)據(jù)末端，受切分算法影響較小，利用有限狀態(tài)機模型，也基本吻合數(shù)據(jù)，提取準確率能達到91.5%。

4.2.2 運行速度

在準確率測試中，模型運行可在短時間內(nèi)完成。為進一步測試模型運行速度，選取某較大供電故障數(shù)據(jù)集，共7 000條數(shù)據(jù)，每500條作為1批數(shù)據(jù)，輸入模型，測試其運行時間。

模型平均運行時間測試見圖2，每500條最長運行時間27.0 ms，最短運行時間16.0 ms，平均運行時間為20.2 ms，不同批次間運行時間差距不大，基本穩(wěn)定在20 ms左右，每千條數(shù)據(jù)處理時間為40 ms。

模型累積運行時間測試見圖3，分3個批次測試模型處理2 000條數(shù)據(jù)的累計運行時間，3次模型處理2 000條數(shù)據(jù)執(zhí)行時間分別為87.96 ms、76.94 ms和77.97 ms，每執(zhí)行500條數(shù)據(jù)記錄一次執(zhí)行時間，可見運行時間與執(zhí)行條數(shù)大致呈線性正相關(guān)關(guān)系，每500條數(shù)據(jù)執(zhí)行時間約20 ms，與模型平均運行時間測試結(jié)果接近。

供電故障生產(chǎn)數(shù)據(jù)集條數(shù)在103數(shù)量級，根據(jù)測試結(jié)果可知，模型運行速度較快，且無需前期訓練或擬合，可滿足在短時間內(nèi)處理大量數(shù)據(jù)特征信息提取的需求。

圖2 模型平均運行時間測試

圖3 模型累計運行時間測試

5 結(jié)束語

基于有限狀態(tài)機的自動化特征信息提取方法，結(jié)合當前主流的自然語言處理分詞技術(shù)，并利用正則匹配技術(shù)構(gòu)建模式識別模型，能夠處理非結(jié)構(gòu)化文字描述的供電故障信息，應(yīng)用于實際生產(chǎn)數(shù)據(jù)測試時，可準確、快速地完成斷電區(qū)間特征信息提取工作，代替人工整理計算，節(jié)約時間、降低精力耗費。

供電故障斷電區(qū)間自動化特征信息提取與計算方法依托于鐵路信息化理念和整體框架，并且隨生產(chǎn)系統(tǒng)不斷更新、日趨完善，具有一定的技術(shù)含量，能產(chǎn)生相應(yīng)的經(jīng)濟效益，同時踐行鐵路安全管理信息化、科學化，有助于提升鐵路運營安全數(shù)據(jù)分析效率。