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

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

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

本文著錄格式：陳愷. 基于改進(jìn)KMP算法的空管自動(dòng)化日志分析系統(tǒng)設(shè)計(jì)[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? 引言

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

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

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

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

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

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

本文設(shè)計(jì)的日志分析系統(tǒng)包含以下功能：

（1）人機(jī)交互界面（HMI）：包含故障查詢關(guān)鍵條件輸入（如航班號(hào)、SSR、故障類型、故障時(shí)間等），查詢結(jié)果及原因分析顯示;

（2）自動(dòng)化系統(tǒng)歷史故障案例數(shù)據(jù)庫(kù);

（3）故障關(guān)鍵字匹配和定位;

（4）故障信息與歷史故障數(shù)據(jù)庫(kù)比對(duì);

（5）解析故障信息。

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

2? 算法設(shè)計(jì)

2.1? KMP算法原理

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

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

（2）然后將P中各子串前綴后綴的公共元素最大長(zhǎng)度數(shù)值整體右移一位，并對(duì)初始值賦值為1，求出next數(shù)組;

（3）利用next數(shù)組進(jìn)行匹配，即當(dāng)模式串后綴和文本串匹配成功，但和匹配失敗時(shí)，需要讓模式串右移位，使得模式串的前綴對(duì)應(yīng)文本串，讓后綴和繼續(xù)匹配[3]。

KMP算法時(shí)間復(fù)雜度主要分為：S和P的比較次數(shù)和根據(jù)模式串計(jì)算。因此，當(dāng)模式串在大型文本數(shù)據(jù)串中進(jìn)行匹配時(shí)，如何提高匹配效率，減少匹配次數(shù)，具有一定的研究意義。

2.2? 改進(jìn)的KMP算法

其中為模式串P中字符的特征值[4]。

假設(shè)模式串P=“ababcdce”，根據(jù)（1）和（2）式推算出值如表2所示。

如果主字符串S與模式串P的一次匹配失敗，主字符串與模式串的當(dāng)前位置分別為i和j，且主字符串對(duì)應(yīng)模式串的首字符位置為，則不存在整數(shù)，使得下列

（3）式說(shuō)明，當(dāng)一次匹配失敗時(shí)，假設(shè)主字符串S對(duì)應(yīng)模式串P的首字符位置為x，則下一輪的比較從主字符串S的第x+位置開(kāi)始，與模式串P第1個(gè)字符開(kāi)始比較，使得主字符串S與模式串P比較的字符在i1的位置仍能匹配，否則，匹配失效。

因此，由（1）至（3）式得到改進(jìn)KMP匹配算法如下：

根據(jù)上述算法步驟，結(jié)合具體實(shí)例詳細(xì)說(shuō)明本算法的計(jì)算過(guò)程，假設(shè)主字符串S為“fgabafababcdcehi”，模式串P為“ababcdce”，P匹配S的過(guò)程如圖3所示。

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

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

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

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

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

//秘鑰存放路徑

String pubKeyPath ="D：＼＼Users＼＼.ssh＼＼id_rsa";

jsch.addIdentity（pubKeyPath）;

String username = "root";//登錄名

String host = "188.18.4.*";//服務(wù)器IP

Session session=jsch.getSession（username， host， 48）;//初始化鏈接

session.setConfig（"StrictHostKeyChecking"， "no"）;

session.connect（）;

3.2? 日志系統(tǒng)數(shù)據(jù)庫(kù)設(shè)計(jì)

日志系統(tǒng)數(shù)據(jù)庫(kù)用于存放歷史故障案例日志信息，存儲(chǔ)表“FaultHistoryDB”設(shè)計(jì)為2個(gè)列族：Fault_Type_DATA 和 Fault_Analysis_DATA。原始數(shù)據(jù)描述如表3所示。

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

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

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

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

//改善數(shù)組代碼

void GetNextval（char* p， int next[]）

{

int pLen = strlen（p）;

next[0] = -1;

int k = -1;

int j = 0;

while （j < pLen - 1）

{

//p[k]表示前綴，p[j]表示后綴

if （k == -1 || p[j] == p[k]）

{

++j; ++k;

if （p[j] ！= p[k]）

next[j]=k;

else

next[j] = next[k];

}

else

k = next[k];

}

}

3.4? 故障解析模塊

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

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

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

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

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

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

4? 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

5? 結(jié)論

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

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

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

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

參考文獻(xiàn)

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

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

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

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

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

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