民航空管自動(dòng)化系統(tǒng)相似航班號(hào)算法研究與實(shí)現(xiàn)

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

2012至2018年昆明長水機(jī)場(chǎng)航班流量增加了近一倍，民航云南空管分局同一時(shí)刻管制范圍內(nèi)的航班數(shù)量也成倍增加，因此航班號(hào)拼寫或者讀音相似的概率也隨之增加。由于同一管制區(qū)內(nèi)出現(xiàn)相似航班號(hào)（Similar Call-sign，以下簡(jiǎn)稱SC）導(dǎo)致的不安全事件時(shí)有發(fā)生。2018年4月1日，民航局空管局發(fā)布了《相似航空器呼號(hào)管制運(yùn)行操作指引》，標(biāo)志著相似航班號(hào)從理論研究階段過渡到具體實(shí)施階段，也給各地區(qū)空管局和空管分局提供了操作指引。本文從理論到算法對(duì)相似航班號(hào)的管制運(yùn)行進(jìn)行了實(shí)際研究，進(jìn)一步改進(jìn)和完善了相似航班號(hào)的告警應(yīng)用。

目前，新版的空管自動(dòng)化系統(tǒng)如NUMEN2000＋，NUMEN3000系統(tǒng)，AirNet 2.2.1及以上版本均增加了相似航班號(hào)告警功能，這些告警功能以類似二次代碼重碼告警的方式，在標(biāo)牌上顯示黃色SC告警并伴有標(biāo)牌閃爍或者聲音告警。但是，較早的空管自動(dòng)化系統(tǒng)如云南空管分局使用的NUMEN2000和未升級(jí)的AirNet系統(tǒng)則不具備SC告警功能。因此，自主研發(fā)一套通用有效的相似航班號(hào)告警系統(tǒng)是非常有必要的。通過研究相似航班號(hào)告警算法，還可以進(jìn)一步優(yōu)化目前的告警規(guī)則，減少虛告警和發(fā)現(xiàn)新的告警情形，減少相似航班號(hào)帶來的不安全事件發(fā)生，同時(shí)防止因?yàn)镾C虛告警給管制員帶來的工作負(fù)擔(dān)。

相似航班號(hào)識(shí)別規(guī)則

空管自動(dòng)化使用的航班號(hào)，編碼規(guī)則一般是由公司代碼（三字碼，字母）和呼號(hào)（一般是3～4位數(shù)字）組成，根據(jù)空管局相似航班號(hào)指引文件，航班號(hào)是否相似考慮的因素主要有：①航空公司三字碼字符或者呼號(hào)相近；②航班號(hào)相同或相近；③航空器呼號(hào)間相同的字符過多，相同字符位置相同，特別是末尾字符相同；④航空器呼號(hào)中字符相近；⑤航空器呼號(hào)與高度層、跑道號(hào)、無線電頻率等相近或相同等8種情形，本文主要研究的是前四種情形。參考自動(dòng)化廠家提供的技術(shù)方案和管制部門的經(jīng)驗(yàn)，本文使用以下相似航班號(hào)識(shí)別規(guī)則，識(shí)別過程均采用兩兩比較法，以下比較的為同一扇區(qū)的任意兩個(gè)航班號(hào)。

（一）航班號(hào)存在相似字符

兩個(gè)航班號(hào)中公司三字碼或者呼號(hào)中存在以下字符的：O（字母）和0（數(shù)字），Z和2，Z和7，I和1，Q和0，B和8，6和9，按照相同字符處理。本文的算法會(huì)將前面的字符替換為后面的字符。

（二）航班號(hào)為同一航空公司

a）航班號(hào)末尾超過2位（含）以上字符相同，且位置相同。例：CCA4156 與CCA4556；

b）4位航班號(hào)中連續(xù)3位組成的字符串含于另一航班號(hào)中。例：CCA4544與CCA4549；

c）3位航班號(hào)中連續(xù)2位組成的字符串含于另一航班號(hào)中。例：CCA985 與CCA986；

d）航班號(hào)的首尾字符相同。例：CSC8711 或 CSC8971。

（三） 航班號(hào)為不同航空公司

e）不考慮航空公司，兩個(gè)航空器呼號(hào)的航班號(hào)字符完全相同。例：CHB6301與EPA6301，CQH8993與CSC8993，CSC8776 與CDC8776；

f）不考慮航空公司，某一航空器航班號(hào)構(gòu)成的“字符串”包含于另一航班號(hào)。例：CCA419與CCA4419，HDA840與CSC8840；

g）不考慮航空公司，其中一個(gè)航班的航班號(hào)可以由另一航班的航班號(hào)全部字符重新排列順序后獲得。例：CQN2347與CCA4372，CSC8963與LKE9863，CQN2354與CES5432；

h）不考慮航空公司，4位航班號(hào)中3個(gè)同樣位置的字符相同。如：123 位相同，例：CSC8996 與CQH8995。

兩種相似航班號(hào)算法的實(shí)現(xiàn)與對(duì)比

本文根據(jù)相似航班號(hào)的規(guī)則，利用C++語言，使用最短編輯距離法、規(guī)則匹配法分別對(duì)上述規(guī)則進(jìn)行實(shí)現(xiàn)，同時(shí)將算法整合到由云南空管分局開發(fā)的綜合航跡處理顯示系統(tǒng)，在該系統(tǒng)中增加了相應(yīng)的相似航班號(hào)功能模塊，該功能模塊包括對(duì)相似航班號(hào)列表顯示，標(biāo)牌底部會(huì)顯示黃色的字母“SC”。還可以選擇需要告警的扇區(qū)，確認(rèn)出現(xiàn)的相似航班號(hào)告警。通過對(duì)2種算法的性能和實(shí)際運(yùn)行過程中虛警情況進(jìn)行對(duì)比，選擇較優(yōu)的算法作為最終使用算法。

（一）最短編輯距離法

最短編輯距離法又稱為Levenshtein Distance算法，是一個(gè)度量兩個(gè)字符序列之間差異的字符串度量標(biāo)準(zhǔn)，兩個(gè)單詞之間的Levenshtein Distance是將一個(gè)單詞轉(zhuǎn)換為另一個(gè)單詞所需的單字符編輯（插入、刪除或替換）的最小數(shù)量。Levenshtein Distance是1965年由蘇聯(lián)數(shù)學(xué)家Vladimir Levenshtein發(fā)明的。Levenshtein Distance也被稱為編輯距離（Edit Distance）。本算法的輸入為兩個(gè)航班號(hào)A和B，輸出是這兩個(gè)航班號(hào)（字符串的編輯距離，數(shù)值為0，1，2，3，0代表兩個(gè)航班號(hào)相同，1代表A只需要經(jīng)過1個(gè)步驟可以變?yōu)锽，2代表A需要經(jīng)過2個(gè)步驟變換才能變成B，3代表A需要經(jīng)過3次變換才能變成B，如果返回0，1，2則認(rèn)為是相似或者相同航班號(hào)；若返回3或者大于3則認(rèn)為不是相似航班號(hào)）。算法大概步驟分為以下過程：

1.識(shí)別航空公司代碼和航班序號(hào)

航班號(hào)一般由公司代碼（空管自動(dòng)化系統(tǒng)一般使用三字碼）和航班序號(hào)（一般為3～4位數(shù)字）組成。首先將需要比較的兩個(gè)航班號(hào)A和B分別拆分為兩個(gè)部分，航班號(hào)A和B的公司代碼coma，comb，航班號(hào)A和B的航班序號(hào)flightnoa，flightnob。識(shí)別過程中，假設(shè)前面均為字母，直到遇到數(shù)字為止則把數(shù)字前面的字母劃分為航空公司代碼，從第一個(gè)數(shù)字開始后面所有字符識(shí)別為航班序號(hào)。例如，CES1234，LKE4567，識(shí)別之后coma＝CES，comb＝LKE，flightnoa＝1234，flightnob＝4567。

2.替換相似字符

根據(jù)前文中a、b、c、d四條規(guī)則，假設(shè)有A，B兩個(gè)航班號(hào)，分別對(duì)A、B兩個(gè)航班號(hào)的每個(gè)字符進(jìn)行掃描，如果同一位置出現(xiàn)字符剛好為以下7種情形，如O和0，Z和2，Z和7，I和1，Q和0，B和8，6和9，則認(rèn)為兩個(gè)字符相等，用后一個(gè)字符替換前一個(gè)字符。例如航班號(hào)A＝CES1236和B＝CES1249，則計(jì)算編輯距離時(shí)認(rèn)為航班號(hào)A＝CES1239，B＝CES1249，而不更改系統(tǒng)實(shí)際的航班號(hào)。

3.相同航空公司代碼編輯距離計(jì)算

如果航空公司代碼coma與comb相同，則對(duì)航班序號(hào)flightnoa和flightnob字符串的編輯距離進(jìn)行計(jì)算，如果計(jì)算之后的編輯距離小于等于2，則返回相應(yīng)的數(shù)值，兩個(gè)航班號(hào)為相似航班號(hào)，否則不是相似航班號(hào)。編輯距離算法大致如下(由于此算法是成熟算法，本文將此算法直接翻譯為C++語言使用)。

定義：對(duì)于兩個(gè)字符串a(chǎn)，b，長度分別為│a│，│b│，它們的Levenshtein Distance levab（│a│，│b│）為以下公式：

其中當(dāng)ai＝bj，leva，b（i，j）＝0；當(dāng)ai≠bj，levab（i，j）＝1。leva，b（i，j）是a的前i個(gè)字符與b的前j個(gè)字符的編輯距離。a、b的相似度Sina，b＝1－（levab（│a│，│b│）/max（│a│，│b│）)。

原理：首先考慮極端情況，當(dāng)a或b長度為0時(shí)，那么需要編輯的次數(shù)就是一個(gè)字符串的長度。然后再考慮一般情況此時(shí)分為三種情況：

（1）在k個(gè)操作中，將a［1…i］轉(zhuǎn)換為b［1…j－1］；

（2）在k個(gè)操作中，將a［1…i－1］轉(zhuǎn)換為b［1…j］；

（3）在k個(gè)操作中，將a［1…i－1］轉(zhuǎn)換為b［1…j－1］。

針對(duì)第一種情況，只需要在a［1…i］后加上字符b［j］，即可完成a［1…i］到b［1…j］的轉(zhuǎn)換，總共需要的編輯次數(shù)即為k＋1。

針對(duì)第二種情況，只需要把a(bǔ)［i］字符從a中移除，即可完成a［1…i］到b［1…j］的轉(zhuǎn)換，總共需要的編輯次數(shù)即為k＋1。

針對(duì)第三種情況，只需要將a［i］轉(zhuǎn)換為b［j］，即可完成a［1…i］到b［1…j］的轉(zhuǎn)換。如果a［i］與b［j］的字符相同，則總共需要的編輯次數(shù)為k，否則即為k＋1。

所以上述三種情況分別對(duì)應(yīng)于插入、刪除、替換操作。

為了保證將a［1…i］轉(zhuǎn)換為b［1…j］的操作數(shù)總是最少的，只需要從三種情況中選擇操作次數(shù)最少的情況；同理，為了保證三種情況的操作數(shù)也是最小的，只需要按此邏輯進(jìn)行迭代保證每一步的操作數(shù)都是最小的即可。

4.不同航空公司代碼編輯距離計(jì)算

根據(jù)前文中e、f兩條規(guī)則，如果航班號(hào)A和B的航空公司代碼coma，comb不相同，則對(duì)航班序號(hào)fligthnoa，flightnob進(jìn)行編輯距離計(jì)算，計(jì)算方法與“相同航空公司代碼編輯距離計(jì)算”相同；如果得到的編輯距離為1，則認(rèn)為是相似航班號(hào)，否則返回3，不是相似航班號(hào)。

5.航班序號(hào)排序?qū)Ρ?/p>

根據(jù)前文中g(shù)、h兩條規(guī)則，如果兩個(gè)航班號(hào)的公司代碼不一樣，也不滿足以上“相同航空公司代碼編輯距離計(jì)算”和“不同航空公司代碼編輯距離計(jì)算”的情形，那么對(duì)航班序號(hào)flightnoa和flightnob安裝ASCII碼從小到大排序（考慮到個(gè)別航班序號(hào)包含字符），排序后再對(duì)新的航班序號(hào)進(jìn)行編輯距離計(jì)算。如果編輯距離為0，則認(rèn)為兩個(gè)航班序號(hào)從小到大排序之后相同，滿足前文規(guī)則中的規(guī)則g；如果編輯距離為1則滿足規(guī)則h。否則返回3（不滿足），認(rèn)為不是相似航班號(hào)。

由此可見，本算法需要多次使用編輯距離算法，并且同時(shí)可以覆蓋一些規(guī)則中沒有考慮到的情形，比如CCA9815與CCA9651也是非常相似的航班號(hào)，但是規(guī)則中沒有包括。

（二）規(guī)則匹配法

此算法類似列舉法，將相似航班號(hào)規(guī)則進(jìn)行編號(hào)并且按照規(guī)則進(jìn)行匹配計(jì)算，然后將同一扇區(qū)任意兩個(gè)航班代入計(jì)算條件，如果滿足則返回匹配的規(guī)則編號(hào)a～h。此算法首先是對(duì)輸入的兩個(gè)航班號(hào)A和B進(jìn)行識(shí)別航空公司代碼和航班序號(hào)、替換相似字符與編輯距離方法一樣，在此基礎(chǔ)上對(duì)a～h的8條規(guī)則一一進(jìn)行計(jì)算，如果滿足該規(guī)則就返回規(guī)則代碼a～h：

1.判斷兩個(gè)航班號(hào)為同一航空公司

首先對(duì)兩個(gè)航班號(hào)的公司呼號(hào)進(jìn)行判斷，如果公司呼號(hào)不相同則直接進(jìn)入“航班號(hào)為不同航空公司”計(jì)算；如果相同，則依次對(duì)a、b、c、d四條規(guī)則進(jìn)行匹配：

a規(guī)則為同一航空公司航班號(hào)末尾超過2位（含）以上字符相同，且位置相同。因此先判斷兩個(gè)航班序號(hào)的長度是否大于等于2，再比較航班序號(hào)的倒數(shù)第1位和倒數(shù)第2位是否同時(shí)相同，是的話返回a，否則進(jìn)入下一條規(guī)則判斷。

b規(guī)則為同一航空公司4位航班號(hào)中連續(xù)3位組成的字符串含于另一航班號(hào)中。該規(guī)則有些復(fù)雜，首先判斷flightnoa和flightnob的長度均等于4，然后依次取flightnoa的前3個(gè)字符和后3個(gè)字符，判斷是否包含在flightnob中，如果滿足則返回b，否則反過來看flightnob的前3位或者后3位是否包含在flightnoa中，滿足則返回b，否則進(jìn)入下一條規(guī)則判斷。

c規(guī)則為3位航班號(hào)連續(xù)2位組成的字符串含于另一航班號(hào)中。例：CCA985與CCA986。首先判斷flightnoa與flightnob的長度均等于3，然后判斷兩個(gè)航班號(hào)的前2位或者后2位是否相等，滿足條件則返回c，否則進(jìn)入下一條規(guī)則判斷。

d規(guī)則為航班號(hào)的首尾字符相同，這種情況則包含3位和4位航班號(hào)，取flightnoa和flightnob的首尾2個(gè)數(shù)字分別進(jìn)行比較，如果均相同則返回d，否則返回0。算法退出，不進(jìn)行下一步的計(jì)算。

2.航班號(hào)為不同航空公司

在航班號(hào)為不相同的情況下，判斷航班呼號(hào)的相似度，根據(jù)前文章節(jié)，一共有e、f、g、h四條規(guī)則。根據(jù)這4條規(guī)則，一一進(jìn)行匹配，返回相應(yīng)的值。

e規(guī)則為兩個(gè)航空器呼號(hào)的航班號(hào)字符完全相同，這種情況是比較容易混淆，比較時(shí)只需要將flightnoa與flightnob進(jìn)行比較，完全相等則返回e，否則進(jìn)入下一條規(guī)則判斷。

f規(guī)則為其中一個(gè)航空器呼號(hào)包含于另外一個(gè)，這種情況需要先判斷flightnoa是否包含于flightnob，是則返回f，否則繼續(xù)比較flightnob是否包含于flightnoa，是則返回f，否則進(jìn)入下一條規(guī)則判斷。

g規(guī)則為其中一個(gè)航班的航班呼號(hào)可以由另一航班的航班號(hào)全部字符重新排列順序后獲得，這種情況需要對(duì)flightnoa和flightnob同時(shí)將航班號(hào)中所有字母和數(shù)字按照其對(duì)應(yīng)的ASCII碼從小到大正序排序，然后比較兩個(gè)排序之后的航班呼號(hào)是否相同，如果相同則返回g，不相同則進(jìn)入下一條規(guī)則判斷。

h規(guī)則為4位航班號(hào)中3個(gè)同樣位置的字符相同，首先判斷兩個(gè)航班呼號(hào)為4位，其次需要考慮4種情形，第一種123位相同，第二種124為相同，第三種134位相同，第四種234位相同，對(duì)4種情況依次判定，滿足其中的一條則返回h，否則所有情形都計(jì)算完之后返回0。

規(guī)則匹配法的計(jì)算過程中，a～h八條規(guī)則，分成航空公司相同（a～d）和航空公司不相同（e～h）兩種大規(guī)則，兩種大規(guī)則只能出現(xiàn)一種，所以計(jì)算完其中一種大規(guī)則下的4條小規(guī)則才算結(jié)束。

測(cè)試與對(duì)比

使用以上兩種方法，分別開發(fā)了兩個(gè)版本1.0和2.0，安裝在區(qū)調(diào)的SIPDS(綜合顯示系統(tǒng))機(jī)器上，經(jīng)過管制人員半年的測(cè)試，1.0版本可以發(fā)現(xiàn)更多的相似航班號(hào)，但是反應(yīng)程序運(yùn)行慢，2.0版本可以顯示每一種告警的規(guī)則，效率更快，可以準(zhǔn)確判斷是否虛告警，以便于更好的改進(jìn)規(guī)則和算法。本文使用采集的100個(gè)航班號(hào)進(jìn)行批量計(jì)算，使用HP ML350服務(wù)器計(jì)算和比較，并從以下方面對(duì)兩種算法進(jìn)行了對(duì)比，見表1。

表1：兩種算法對(duì)比

經(jīng)過對(duì)比兩種算法，最短編輯距離法作為比較字符串最常用的算法，可以識(shí)別管制員未考慮的相似航班號(hào)情形，比如LKE9581和LKE9858，但是算法性能不如規(guī)則匹配法，并且無法確定出現(xiàn)的告警對(duì)應(yīng)的是哪條規(guī)則，同時(shí)該算法擴(kuò)展性不如規(guī)則匹配法。因此，目前而言，采用規(guī)則匹配法更有優(yōu)勢(shì)。

結(jié)束語：

本文針對(duì)民航空管的相似航班號(hào)問題，采用了兩種方法實(shí)現(xiàn)相似航班號(hào)的識(shí)別。通過對(duì)比兩種方法的實(shí)現(xiàn)方式、性能以及可擴(kuò)展性，最終將實(shí)現(xiàn)的相似航班號(hào)算法導(dǎo)入本單位自主開發(fā)的綜合航跡顯示系統(tǒng)。經(jīng)過本單位區(qū)調(diào)和進(jìn)近管制員長期測(cè)試，該算法功能可用、可靠。后期，主備自動(dòng)化系統(tǒng)將升級(jí)相似航班號(hào)補(bǔ)丁，本文也將參考其功能進(jìn)一步改進(jìn)算法。