民航空管自动化系统相似航班号算法研究与实现

□ 民航云南空管分局 钟 海/文

2012至2018年昆明长水机场航班流量增加了近一倍，民航云南空管分局同一时刻管制范围内的航班数量也成倍增加，因此航班号拼写或者读音相似的概率也随之增加。由于同一管制区内出现相似航班号（Similar Call-sign，以下简称SC）导致的不安全事件时有发生。2018年4月1日，民航局空管局发布了《相似航空器呼号管制运行操作指引》，标志着相似航班号从理论研究阶段过渡到具体实施阶段，也给各地区空管局和空管分局提供了操作指引。本文从理论到算法对相似航班号的管制运行进行了实际研究，进一步改进和完善了相似航班号的告警应用。

目前，新版的空管自动化系统如NUMEN2000＋，NUMEN3000系统，AirNet 2.2.1及以上版本均增加了相似航班号告警功能，这些告警功能以类似二次代码重码告警的方式，在标牌上显示黄色SC告警并伴有标牌闪烁或者声音告警。但是，较早的空管自动化系统如云南空管分局使用的NUMEN2000和未升级的AirNet系统则不具备SC告警功能。因此，自主研发一套通用有效的相似航班号告警系统是非常有必要的。通过研究相似航班号告警算法，还可以进一步优化目前的告警规则，减少虚告警和发现新的告警情形，减少相似航班号带来的不安全事件发生，同时防止因为SC虚告警给管制员带来的工作负担。

相似航班号识别规则

空管自动化使用的航班号，编码规则一般是由公司代码（三字码，字母）和呼号（一般是3～4位数字）组成，根据空管局相似航班号指引文件，航班号是否相似考虑的因素主要有：①航空公司三字码字符或者呼号相近；②航班号相同或相近；③航空器呼号间相同的字符过多，相同字符位置相同，特别是末尾字符相同；④航空器呼号中字符相近；⑤航空器呼号与高度层、跑道号、无线电频率等相近或相同等8种情形，本文主要研究的是前四种情形。参考自动化厂家提供的技术方案和管制部门的经验，本文使用以下相似航班号识别规则，识别过程均采用两两比较法，以下比较的为同一扇区的任意两个航班号。

（一）航班号存在相似字符

两个航班号中公司三字码或者呼号中存在以下字符的：O（字母）和0（数字），Z和2，Z和7，I和1，Q和0，B和8，6和9，按照相同字符处理。本文的算法会将前面的字符替换为后面的字符。

（二）航班号为同一航空公司

a）航班号末尾超过2位（含）以上字符相同，且位置相同。例：CCA4156 与CCA4556；

b）4位航班号中连续3位组成的字符串含于另一航班号中。例：CCA4544与CCA4549；

c）3位航班号中连续2位组成的字符串含于另一航班号中。例：CCA985 与CCA986；

d）航班号的首尾字符相同。例：CSC8711 或 CSC8971。

（三） 航班号为不同航空公司

e）不考虑航空公司，两个航空器呼号的航班号字符完全相同。例：CHB6301与EPA6301，CQH8993与CSC8993，CSC8776 与CDC8776；

f）不考虑航空公司，某一航空器航班号构成的“字符串”包含于另一航班号。例：CCA419与CCA4419，HDA840与CSC8840；

g）不考虑航空公司，其中一个航班的航班号可以由另一航班的航班号全部字符重新排列顺序后获得。例：CQN2347与CCA4372，CSC8963与LKE9863，CQN2354与CES5432；

h）不考虑航空公司，4位航班号中3个同样位置的字符相同。如：123 位相同，例：CSC8996 与CQH8995。

两种相似航班号算法的实现与对比

本文根据相似航班号的规则，利用C++语言，使用最短编辑距离法、规则匹配法分别对上述规则进行实现，同时将算法整合到由云南空管分局开发的综合航迹处理显示系统，在该系统中增加了相应的相似航班号功能模块，该功能模块包括对相似航班号列表显示，标牌底部会显示黄色的字母“SC”。还可以选择需要告警的扇区，确认出现的相似航班号告警。通过对2种算法的性能和实际运行过程中虚警情况进行对比，选择较优的算法作为最终使用算法。

（一）最短编辑距离法

最短编辑距离法又称为Levenshtein Distance算法，是一个度量两个字符序列之间差异的字符串度量标准，两个单词之间的Levenshtein Distance是将一个单词转换为另一个单词所需的单字符编辑（插入、删除或替换）的最小数量。Levenshtein Distance是1965年由苏联数学家Vladimir Levenshtein发明的。Levenshtein Distance也被称为编辑距离（Edit Distance）。本算法的输入为两个航班号A和B，输出是这两个航班号（字符串的编辑距离，数值为0，1，2，3，0代表两个航班号相同，1代表A只需要经过1个步骤可以变为B，2代表A需要经过2个步骤变换才能变成B，3代表A需要经过3次变换才能变成B，如果返回0，1，2则认为是相似或者相同航班号；若返回3或者大于3则认为不是相似航班号）。算法大概步骤分为以下过程：

1.识别航空公司代码和航班序号

航班号一般由公司代码（空管自动化系统一般使用三字码）和航班序号（一般为3～4位数字）组成。首先将需要比较的两个航班号A和B分别拆分为两个部分，航班号A和B的公司代码coma，comb，航班号A和B的航班序号flightnoa，flightnob。识别过程中，假设前面均为字母，直到遇到数字为止则把数字前面的字母划分为航空公司代码，从第一个数字开始后面所有字符识别为航班序号。例如，CES1234，LKE4567，识别之后coma＝CES，comb＝LKE，flightnoa＝1234，flightnob＝4567。

2.替换相似字符

根据前文中a、b、c、d四条规则，假设有A，B两个航班号，分别对A、B两个航班号的每个字符进行扫描，如果同一位置出现字符刚好为以下7种情形，如O和0，Z和2，Z和7，I和1，Q和0，B和8，6和9，则认为两个字符相等，用后一个字符替换前一个字符。例如航班号A＝CES1236和B＝CES1249，则计算编辑距离时认为航班号A＝CES1239，B＝CES1249，而不更改系统实际的航班号。

3.相同航空公司代码编辑距离计算

如果航空公司代码coma与comb相同，则对航班序号flightnoa和flightnob字符串的编辑距离进行计算，如果计算之后的编辑距离小于等于2，则返回相应的数值，两个航班号为相似航班号，否则不是相似航班号。编辑距离算法大致如下(由于此算法是成熟算法，本文将此算法直接翻译为C++语言使用)。

定义：对于两个字符串a，b，长度分别为│a│，│b│，它们的Levenshtein Distance levab（│a│，│b│）为以下公式：

其中当ai＝bj，leva，b（i，j）＝0；当ai≠bj，levab（i，j）＝1。leva，b（i，j）是a的前i个字符与b的前j个字符的编辑距离。a、b的相似度Sina，b＝1－（levab（│a│，│b│）/max（│a│，│b│）)。

原理：首先考虑极端情况，当a或b长度为0时，那么需要编辑的次数就是一个字符串的长度。然后再考虑一般情况此时分为三种情况：

（1）在k个操作中，将a［1…i］转换为b［1…j－1］；

（2）在k个操作中，将a［1…i－1］转换为b［1…j］；

（3）在k个操作中，将a［1…i－1］转换为b［1…j－1］。

针对第一种情况，只需要在a［1…i］后加上字符b［j］，即可完成a［1…i］到b［1…j］的转换，总共需要的编辑次数即为k＋1。

针对第二种情况，只需要把a［i］字符从a中移除，即可完成a［1…i］到b［1…j］的转换，总共需要的编辑次数即为k＋1。

针对第三种情况，只需要将a［i］转换为b［j］，即可完成a［1…i］到b［1…j］的转换。如果a［i］与b［j］的字符相同，则总共需要的编辑次数为k，否则即为k＋1。

所以上述三种情况分别对应于插入、删除、替换操作。

为了保证将a［1…i］转换为b［1…j］的操作数总是最少的，只需要从三种情况中选择操作次数最少的情况；同理，为了保证三种情况的操作数也是最小的，只需要按此逻辑进行迭代保证每一步的操作数都是最小的即可。

4.不同航空公司代码编辑距离计算

根据前文中e、f两条规则，如果航班号A和B的航空公司代码coma，comb不相同，则对航班序号fligthnoa，flightnob进行编辑距离计算，计算方法与“相同航空公司代码编辑距离计算”相同；如果得到的编辑距离为1，则认为是相似航班号，否则返回3，不是相似航班号。

5.航班序号排序对比

根据前文中g、h两条规则，如果两个航班号的公司代码不一样，也不满足以上“相同航空公司代码编辑距离计算”和“不同航空公司代码编辑距离计算”的情形，那么对航班序号flightnoa和flightnob安装ASCII码从小到大排序（考虑到个别航班序号包含字符），排序后再对新的航班序号进行编辑距离计算。如果编辑距离为0，则认为两个航班序号从小到大排序之后相同，满足前文规则中的规则g；如果编辑距离为1则满足规则h。否则返回3（不满足），认为不是相似航班号。

由此可见，本算法需要多次使用编辑距离算法，并且同时可以覆盖一些规则中没有考虑到的情形，比如CCA9815与CCA9651也是非常相似的航班号，但是规则中没有包括。

（二）规则匹配法

此算法类似列举法，将相似航班号规则进行编号并且按照规则进行匹配计算，然后将同一扇区任意两个航班代入计算条件，如果满足则返回匹配的规则编号a～h。此算法首先是对输入的两个航班号A和B进行识别航空公司代码和航班序号、替换相似字符与编辑距离方法一样，在此基础上对a～h的8条规则一一进行计算，如果满足该规则就返回规则代码a～h：

1.判断两个航班号为同一航空公司

首先对两个航班号的公司呼号进行判断，如果公司呼号不相同则直接进入“航班号为不同航空公司”计算；如果相同，则依次对a、b、c、d四条规则进行匹配：

a规则为同一航空公司航班号末尾超过2位（含）以上字符相同，且位置相同。因此先判断两个航班序号的长度是否大于等于2，再比较航班序号的倒数第1位和倒数第2位是否同时相同，是的话返回a，否则进入下一条规则判断。

b规则为同一航空公司4位航班号中连续3位组成的字符串含于另一航班号中。该规则有些复杂，首先判断flightnoa和flightnob的长度均等于4，然后依次取flightnoa的前3个字符和后3个字符，判断是否包含在flightnob中，如果满足则返回b，否则反过来看flightnob的前3位或者后3位是否包含在flightnoa中，满足则返回b，否则进入下一条规则判断。

c规则为3位航班号连续2位组成的字符串含于另一航班号中。例：CCA985与CCA986。首先判断flightnoa与flightnob的长度均等于3，然后判断两个航班号的前2位或者后2位是否相等，满足条件则返回c，否则进入下一条规则判断。

d规则为航班号的首尾字符相同，这种情况则包含3位和4位航班号，取flightnoa和flightnob的首尾2个数字分别进行比较，如果均相同则返回d，否则返回0。算法退出，不进行下一步的计算。

2.航班号为不同航空公司

在航班号为不相同的情况下，判断航班呼号的相似度，根据前文章节，一共有e、f、g、h四条规则。根据这4条规则，一一进行匹配，返回相应的值。

e规则为两个航空器呼号的航班号字符完全相同，这种情况是比较容易混淆，比较时只需要将flightnoa与flightnob进行比较，完全相等则返回e，否则进入下一条规则判断。

f规则为其中一个航空器呼号包含于另外一个，这种情况需要先判断flightnoa是否包含于flightnob，是则返回f，否则继续比较flightnob是否包含于flightnoa，是则返回f，否则进入下一条规则判断。

g规则为其中一个航班的航班呼号可以由另一航班的航班号全部字符重新排列顺序后获得，这种情况需要对flightnoa和flightnob同时将航班号中所有字母和数字按照其对应的ASCII码从小到大正序排序，然后比较两个排序之后的航班呼号是否相同，如果相同则返回g，不相同则进入下一条规则判断。

h规则为4位航班号中3个同样位置的字符相同，首先判断两个航班呼号为4位，其次需要考虑4种情形，第一种123位相同，第二种124为相同，第三种134位相同，第四种234位相同，对4种情况依次判定，满足其中的一条则返回h，否则所有情形都计算完之后返回0。

规则匹配法的计算过程中，a～h八条规则，分成航空公司相同（a～d）和航空公司不相同（e～h）两种大规则，两种大规则只能出现一种，所以计算完其中一种大规则下的4条小规则才算结束。

测试与对比

使用以上两种方法，分别开发了两个版本1.0和2.0，安装在区调的SIPDS(综合显示系统)机器上，经过管制人员半年的测试，1.0版本可以发现更多的相似航班号，但是反应程序运行慢，2.0版本可以显示每一种告警的规则，效率更快，可以准确判断是否虚告警，以便于更好的改进规则和算法。本文使用采集的100个航班号进行批量计算，使用HP ML350服务器计算和比较，并从以下方面对两种算法进行了对比，见表1。

表1：两种算法对比

经过对比两种算法，最短编辑距离法作为比较字符串最常用的算法，可以识别管制员未考虑的相似航班号情形，比如LKE9581和LKE9858，但是算法性能不如规则匹配法，并且无法确定出现的告警对应的是哪条规则，同时该算法扩展性不如规则匹配法。因此，目前而言，采用规则匹配法更有优势。

结束语：

本文针对民航空管的相似航班号问题，采用了两种方法实现相似航班号的识别。通过对比两种方法的实现方式、性能以及可扩展性，最终将实现的相似航班号算法导入本单位自主开发的综合航迹显示系统。经过本单位区调和进近管制员长期测试，该算法功能可用、可靠。后期，主备自动化系统将升级相似航班号补丁，本文也将参考其功能进一步改进算法。