基于改進KMP算法的空管自動化日志分析系統設計

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

關鍵詞： 自動化系統;改進的KMP算法;日志分析;故障關鍵字

中圖分類號： TP391.41? ? 文獻標識碼： A? ? DOI：10.3969/j.issn.1003-6970.2020.09.005

本文著錄格式：陳愷. 基于改進KMP算法的空管自動化日志分析系統設計[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? 引言

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

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

對于自動化系統日志，特別是飛行計劃[3]信息類日志，通常會出現很多類似關鍵字，導致關鍵字（模式串）與被查詢日志信息（文本串）重復地作不必要字符比較的情形。因此，一種改進的KMP匹配算法在自動化日志查詢過程中能更好地提升查詢效率，快速定位故障原因。

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

1? 系統實現原理和設計架構

國內空管自動化系統一般將日志數據按照固定時間格式定期存放于日志服務器（如萊斯自動化的LGP，華泰自動化的TRACE）進行存檔。本文所設計的自動化日志分析系統通過TCP/IP協議，遠程登錄至自動化系統日志服務器將相關日志信息進行封裝，并將數據傳送回日志分析系統進行解析，解析結果呈現給前臺用戶，其系統架構圖如圖1所示。

本文設計的日志分析系統包含以下功能：

（1）人機交互界面（HMI）：包含故障查詢關鍵條件輸入（如航班號、SSR、故障類型、故障時間等），查詢結果及原因分析顯示;

（2）自動化系統歷史故障案例數據庫;

（3）故障關鍵字匹配和定位;

（4）故障信息與歷史故障數據庫比對;

（5）解析故障信息。

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

2? 算法設計

2.1? KMP算法原理

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

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

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

（3）利用next數組進行匹配，即當模式串后綴和文本串匹配成功，但和匹配失敗時，需要讓模式串右移位，使得模式串的前綴對應文本串，讓后綴和繼續匹配[3]。

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

2.2? 改進的KMP算法

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

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

如果主字符串S與模式串P的一次匹配失敗，主字符串與模式串的當前位置分別為i和j，且主字符串對應模式串的首字符位置為，則不存在整數，使得下列

（3）式說明，當一次匹配失敗時，假設主字符串S對應模式串P的首字符位置為x，則下一輪的比較從主字符串S的第x+位置開始，與模式串P第1個字符開始比較，使得主字符串S與模式串P比較的字符在i1的位置仍能匹配，否則，匹配失效。

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

根據上述算法步驟，結合具體實例詳細說明本算法的計算過程，假設主字符串S為“fgabafababcdcehi”，模式串P為“ababcdce”，P匹配S的過程如圖3所示。

3? 系統軟件設計

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

3.1? 數據鏈接模塊

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

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

//秘鑰存放路徑

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

jsch.addIdentity（pubKeyPath）;

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

String host = "188.18.4.*";//服務器IP

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

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

session.connect（）;

3.2? 日志系統數據庫設計

日志系統數據庫用于存放歷史故障案例日志信息，存儲表“FaultHistoryDB”設計為2個列族：Fault_Type_DATA 和 Fault_Analysis_DATA。原始數據描述如表3所示。

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

3.3? 故障關鍵字匹配模塊

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

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

//改善數組代碼

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? 故障解析模塊

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

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

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

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

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

（4）步驟1至3出現任意匹配失敗，日志分析系統則直接給出對應的故障解析信息。

4? 實驗結果與分析

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

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

對于日常維護常規故障排查，采用本系統進行故障查詢耗時與用戶人工查詢耗時作為對比指標，其對比結果如表4所示。

分析表4可知，日志分析系統故障查詢平均耗時遠遠少于人工查詢平均耗時。

5? 結論

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

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

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

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

參考文獻

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

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

[3]中華人民共和國民用航空行業標準. 民用航空空中交通管制自動化系統第3部分： 飛行數據交換： MH-T_4029.3： 17-20[S]. 北京： 中國民航局， 2015.

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

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

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