基于改进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.