摘 ?要： 研究并提出一種改進KMP算法，該算法每次比較字符不匹配時，可根據(jù)模式串的當(dāng)前字符特征值U，使得主字符串指針自動前進至U位置，且保持模式串指針在起始位置，加快了字符串匹配速度。利用所研究的算法設(shè)計了一套空管自動化日志分析系統(tǒng)，使用 KMP算法對自動化系統(tǒng)日志信息進行故障關(guān)鍵字匹配，達(dá)到快速定位故障原因的效果。文中詳細(xì)給出了系統(tǒng)的設(shè)計原理與軟件設(shè)計流程，并進行查詢性能分析。實驗結(jié)果表明：改進KMP算法應(yīng)用于空管自動化日志分析系統(tǒng)使得查詢性能顯著優(yōu)于同類系統(tǒng)和人工查詢方式，所設(shè)計的系統(tǒng)可高效、準(zhǔn)確進行故障查詢，在空管單位和地方機場塔臺具有廣泛的應(yīng)用前景。

關(guān)鍵詞： 自動化系統(tǒng);改進的KMP算法;日志分析;故障關(guān)鍵字

中圖分類號： TP391.41 ???文獻(xiàn)標(biāo)識碼： A ???DOI：10.3969/j.issn.1003-6970.2020.09.005

本文著錄格式：陳愷. 基于改進KMP算法的空管自動化日志分析系統(tǒng)設(shè)計[J]. 軟件，2020，41（09）：1922+71

【Abstract】： Through research， an improved KMP algorithm is proposed. Each time the comparison characters do not match， the algorithm can string the characteristic value U of the current character according to the pattern， so that the main string pointer automatically advances to the U position， and keeping the pattern string pointer at the starting position， speeding up the string matching speed. With the help of the researched algorithm， a set of ATC log analysis system is designed， and the KMP algorithm is adopted to match the fault keywords of the automated system log information to quickly locate the cause of the fault. In this paper， the design principle and software design process of the system are given in detail， and the query performance is analyzed. The experimental results show that the improved KMP algorithm is applied to the automated log analysis system， which makes the query performance significantly better than similar systems and manual query methods. In addition， the designed system has the ability to perform fault inquiries efficiently and accurately， and has a wide application prospect in air traffic control units and local airport towers.

【Key words】： ATC; Improved KMP algorithm; Log analysis; Fault keywords

0 ?引言

空管自動化系統(tǒng)是實現(xiàn)雷達(dá)管制最為核心的設(shè)備，在對空指揮任務(wù)的安全實施中發(fā)揮著重要的作用，隨著民航機場空中流量不斷提升，對空管自動化系統(tǒng)運行穩(wěn)定性和魯棒性提出更高的要求。萊斯和華泰自動化系統(tǒng)作為國內(nèi)主流空管自動化系統(tǒng)，在實際運行過程（特別是在雷雨繞飛或軍航活動頻繁等復(fù)雜情況）出現(xiàn)不少異常問題，需要技術(shù)維護人員通過歷史數(shù)據(jù)回放或日志查詢等方式人工排查故障原因，查詢效率低。對于重復(fù)或類似故障現(xiàn)象沒有一套具備自動聚類分析功能的日志分析系統(tǒng)，加重了技術(shù)維護人員工作負(fù)擔(dān)。

在日志分析過程中，異常關(guān)鍵字定位是解決自動化系統(tǒng)出現(xiàn)異常情況最為快捷、有效的辦法。關(guān)鍵字和被查詢?nèi)罩緝?nèi)容可分別等效為字符匹配關(guān)系中的模式串與文本串[1]，通常采用的方法有基于BF算法、RF算法、KMP算法和基于編程語言內(nèi)嵌的字符串匹配函數(shù)，其中效率最高的是KMP 模式匹配算法[2]。

對于自動化系統(tǒng)日志，特別是飛行計劃[3]信息類日志，通常會出現(xiàn)很多類似關(guān)鍵字，導(dǎo)致關(guān)鍵字（模式串）與被查詢?nèi)罩拘畔ⅲㄎ谋敬┲貜?fù)地作不必要字符比較的情形。因此，一種改進的KMP匹配算法在自動化日志查詢過程中能更好地提升查詢效率，快速定位故障原因。

針對上述原因，本文旨在設(shè)計并實現(xiàn)一種基于改進KMP算法的自動化日志分析系統(tǒng)。首先，對日志分析系統(tǒng)的實現(xiàn)原理和設(shè)計架構(gòu)進行介紹，包含系統(tǒng)的功能分析和系統(tǒng)運行機制分析;其次，詳細(xì)闡述本設(shè)計所采用的改進KMP算法原理及運算過程，給出了具體實例說明算法的時效性和可行性;再次，對系統(tǒng)重要功能模塊的軟件設(shè)計進行描述;最后結(jié)合系統(tǒng)實際運行情況，給出具體結(jié)果與性能評估。

1 ?系統(tǒng)實現(xiàn)原理和設(shè)計架構(gòu)

國內(nèi)空管自動化系統(tǒng)一般將日志數(shù)據(jù)按照固定時間格式定期存放于日志服務(wù)器（如萊斯自動化的LGP，華泰自動化的TRACE）進行存檔。本文所設(shè)計的自動化日志分析系統(tǒng)通過TCP/IP協(xié)議，遠(yuǎn)程登錄至自動化系統(tǒng)日志服務(wù)器將相關(guān)日志信息進行封裝，并將數(shù)據(jù)傳送回日志分析系統(tǒng)進行解析，解析結(jié)果呈現(xiàn)給前臺用戶，其系統(tǒng)架構(gòu)圖如圖1所示。

日志分析系統(tǒng)歷史故障案例數(shù)據(jù)庫（HistoryDB）存放以往故障案例，技術(shù)維護人員定期將最新故障案例的日志關(guān)鍵字和log日志排查順序通過前臺界面輸入至后臺數(shù)據(jù)庫，作為后續(xù)故障調(diào)查的歷史匹配數(shù)據(jù)源。日志分析系統(tǒng)會根據(jù)HMI界面輸入的查詢關(guān)鍵字進行相關(guān)日志的封裝，并將所獲取日志存放在分析系統(tǒng)對應(yīng)目錄。為了提高故障查詢速度，減少系統(tǒng)運行負(fù)荷，采用改進的KMP算法對故障關(guān)鍵字與log日志內(nèi)容進行匹配，將日志中的關(guān)鍵信息與歷史案例進行相似度分析和語義分析，解析故障信息，最終將故障原因返回前臺呈現(xiàn)給用戶，其設(shè)計流程圖如圖2所示。

2 ?算法設(shè)計

2.1 ?KMP算法原理

KMP算法常用于在一個文本串S內(nèi)查找一個模式串P的出現(xiàn)位置，如果完全匹配，則返回模式串在該文本串的具體位置，否則返回0值。其核心思想分為以下幾步：

（1）尋找模式串中長度最大且相等的前綴和后綴，具體解析如表1所示（假設(shè)定義模式串為“ABCAB”）：

3 ?系統(tǒng)軟件設(shè)計

日志分析系統(tǒng)基于JAVA和Swing技術(shù)，采用C/S開發(fā)框架和模塊化的程序設(shè)計思想，可提高系統(tǒng)的可維護性和魯棒性。

3.1 ?數(shù)據(jù)鏈接模塊

該模塊包含遠(yuǎn)程鏈接和數(shù)據(jù)封裝。日志分析系統(tǒng)為了建立穩(wěn)定有效的訪問鏈接，通過TCP/IP協(xié)議無密鑰遠(yuǎn)程鏈接至自動化系統(tǒng)日志服務(wù)器，根據(jù)前臺輸入的查詢條件自動讀取服務(wù)器對應(yīng)路徑下的相關(guān)日志，并通過SHELL腳本語言將相關(guān)日志封裝打包傳送回日志分析系統(tǒng)對應(yīng)的存儲目錄。

遠(yuǎn)程無密鑰通信鏈接關(guān)鍵設(shè)置步驟如下：（1）根據(jù)遠(yuǎn)程主機的IP地址，用戶名和端口，建立會話（Session）;（2）設(shè)置用戶信息（包括密碼），然后連接session;（3）在session上建立指定類型的通道;（4）設(shè)置channel上需要遠(yuǎn)程執(zhí)行的腳本;（5）讀取遠(yuǎn)程執(zhí)行腳本的輸出，最后依次斷開channel和session的鏈接。其部分代碼如下：

故障類型與前臺查詢輸入故障類型保持一致（如：AIDC移交失敗、STCA告警異常等），系統(tǒng)通過故障類型（表單主鍵值）自動匹配到故障關(guān)鍵字，同一種故障類型或不同故障類型的關(guān)鍵字代表不同的故障含義。

3.3 ?故障關(guān)鍵字匹配模塊

日志分析系統(tǒng)故障分析準(zhǔn)確率和分析效率均是衡量系統(tǒng)穩(wěn)定性的重要指標(biāo)。本設(shè)計提出的改進KMP算法旨在減少模式串與文本串的比較次數(shù)，縮短故障查詢時間，特別適用于自動化系統(tǒng)日志文本中所存在大量相似字符串信息的情況。

因此，本模塊代碼核心設(shè)計主要就是減少的匹配范圍，即進行新一輪匹配時， 主字符串指針在處，模式串指針在處，推算存在相似字符串情況下，可減少重復(fù)比較次數(shù)為，其主要代碼如下：

3.4 ?故障解析模塊

故障關(guān)鍵字解析是實現(xiàn)日志分析系統(tǒng)自動檢索并分析故障的關(guān)鍵功能。系統(tǒng)會按照前臺界面所錄入歷史故障相似日志的預(yù)定故障分析排序，逐一按照log日志關(guān)鍵字進行各環(huán)節(jié)故障分析，若某環(huán)節(jié)滿足故障特征，則直接將故障關(guān)鍵字解析成故障原因，呈現(xiàn)給前臺用戶。

現(xiàn)以萊斯自動化系統(tǒng)拍發(fā)落地報異常為例，詳細(xì)闡述系統(tǒng)將故障關(guān)鍵字與歷史故障數(shù)據(jù)庫比對過程，實現(xiàn)故障原因自動分析，如圖4所示。萊斯自動化系統(tǒng)完整的落地報拍發(fā)過程為：自動化系統(tǒng)實時計算目標(biāo)運動態(tài)勢，當(dāng)目標(biāo)準(zhǔn)備進入降落判定區(qū)域時，首先在CETC_TPP模塊記錄目標(biāo)降落判定區(qū)的日志信息，然后CETC_TPP模塊通知飛行計劃處理模塊CETC_FDP接收降落判定信息，最后CETC_FDP模塊通知報文組裝模塊CETC_ADO進行相關(guān)城市對地址的落地電報拍發(fā)。以上任意環(huán)節(jié)未正常執(zhí)行，均導(dǎo)致萊斯自動化系統(tǒng)自動拍發(fā)落地報異常。因此，通過KMP算法依次匹配關(guān)鍵字的步驟如下：

（1）“時間戳+航班號+觸發(fā)ARR”作為模式串字符匹配在線系統(tǒng)航跡融合服務(wù)器（SDP）/home/atc/log/ tpp_log路徑下對應(yīng)日志信息（作為主字符串）;

（2）“AUTO_SEND_ARR：：航班號+Successfully”作為模式串字符匹配在線飛行計劃處理服務(wù)器（FDP）/home/atc/log/fdp_log路徑下對應(yīng)的日志信息;

（3）“DEPARR：： output”作為模式串字符匹配在線FDP/home/atc/log/aftn_log路徑下對應(yīng)的日志信息;

（4）步驟1至3出現(xiàn)任意匹配失敗，日志分析系統(tǒng)則直接給出對應(yīng)的故障解析信息。

4 ?實驗結(jié)果與分析

按照上述設(shè)計方案研制了基于改進KMP算法的空管自動化日志分析系統(tǒng)，驗證系統(tǒng)的可行性與可靠性。圖 4是萊斯自動化日志分析系統(tǒng)主界面，用戶通過輸入航班號、故障類型、時間等查詢條件，系統(tǒng)實時獲取相關(guān)日志信息，按照歷史故障案例庫所預(yù)設(shè)的排查步驟進行故障關(guān)鍵字定位和故障原因分析，耗時9秒將本次AIDC（電子移交）異常原因反饋至前臺用戶。

圖5是采用不同算法對相同日志信息進行故障查詢所花費時間的性能分析圖。為方便分析，分別采樣了9種日志信息（包含報文處理異常、AIDC異常、計劃和航跡相關(guān)異常等常規(guī)日志）。與此同時，系統(tǒng)繪制了基于傳統(tǒng)的工程實現(xiàn)方式：JAVA編程字符串定位函數(shù)[6]int indexOf（String str）、KMP算法以及本系統(tǒng)算法的折線圖。從圖中可知，當(dāng)日志內(nèi)容較少（類型1和9），三種算法定位故障關(guān)鍵字所耗費時間相差不大;當(dāng)日志內(nèi)容較多，重復(fù)性或類似關(guān)鍵字較多時，本系統(tǒng)算法比KMP算法優(yōu)越，定位故障關(guān)鍵字所消耗時間遠(yuǎn)遠(yuǎn)小于JAVA編程嵌套的index（）函數(shù)方法;在類型6日志（航跡和計劃異常去相關(guān)）中，由于涉及關(guān)聯(lián)日志較多，查詢檢索信息與其它日志相比更為復(fù)雜，本系統(tǒng)算法的查詢效率在這種情況下明顯優(yōu)于其它兩種算法，而且誤差率僅為5.6%，其他方法誤差率皆大于10%。

對于日常維護常規(guī)故障排查，采用本系統(tǒng)進行故障查詢耗時與用戶人工查詢耗時作為對比指標(biāo)，其對比結(jié)果如表4所示。

分析表4可知，日志分析系統(tǒng)故障查詢平均耗時遠(yuǎn)遠(yuǎn)少于人工查詢平均耗時。

5 ?結(jié)論

采用JAVA和Swing編程技術(shù)設(shè)計了一套基于改進KMP算法的自動化日志分析系統(tǒng)。目前該系統(tǒng)應(yīng)用于民航廣西空管分局萊斯主用自動化系統(tǒng)，現(xiàn)場用戶體驗良好，故障查詢效率高，誤差率低，提高技術(shù)維護人員工作效率，極大地降低空管自動化系統(tǒng)整體運行風(fēng)險，在空管單位地方機場塔臺具有廣泛的應(yīng)用前景。但系統(tǒng)仍存在不足之處：

（1）由于飛行計劃信息和航跡信息實時變化，自動化系統(tǒng)處理的數(shù)據(jù)復(fù)雜程度較高，系統(tǒng)出現(xiàn)故障的案例不盡相同，技術(shù)維護人員需將更多故障案例錄入日志分析系統(tǒng)，使得系統(tǒng)分析誤差率進一步降低;

（2）完善日志分析系統(tǒng)切換功能，即當(dāng)華泰自動化作為主用系統(tǒng)時，日志分析系統(tǒng)可同時在線切換，進行另外一套自動化系統(tǒng)日志分析;

（3）在模式串中重復(fù)子串較多情況下，減少比較次數(shù)，進一步提高KMP算法的運算精度和速度。

參考文獻(xiàn)

[1]俞松， 鄭駿， 胡文心.一種改進的KMP算法[J]. 華東師范大學(xué)學(xué)報（自然科學(xué)版）， 2009（04）： 92-97.

[2]安冬， 榮超群， 楊丹等. 基于PSOA聚類和KMP算法的說話人識別方法[J]. 儀器儀表學(xué)報， 2013， 34（06）： 107-112.

[3]中華人民共和國民用航空行業(yè)標(biāo)準(zhǔn). 民用航空空中交通管制自動化系統(tǒng)第3部分： 飛行數(shù)據(jù)交換： MH-T_4029.3： 17-20[S]. 北京： 中國民航局， 2015.

[4]李莉， 江育娥， 林劼， 等. 基于KMP算法的改進算法KMPP[J]. 計算機工程與應(yīng)用， 2016， 52（08）： 33-37.

[5]周昊， 韓彥李斌， 殷曉玲. 并行KMP算法的研究[J]. 赤峰學(xué)院學(xué)報（自然科學(xué)版）， 2019， 35（05）： 30-32.

[6]李剛. 瘋狂Java講義[M]. 5版. 北京： 電子工業(yè)出版社， 2019： 123-125.