民航空管自動化系統相似航班號算法研究與實現

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

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，但是算法性能不如規則匹配法，并且無法確定出現的告警對應的是哪條規則，同時該算法擴展性不如規則匹配法。因此，目前而言，采用規則匹配法更有優勢。

結束語：

本文針對民航空管的相似航班號問題，采用了兩種方法實現相似航班號的識別。通過對比兩種方法的實現方式、性能以及可擴展性，最終將實現的相似航班號算法導入本單位自主開發的綜合航跡顯示系統。經過本單位區調和進近管制員長期測試，該算法功能可用、可靠。后期，主備自動化系統將升級相似航班號補丁，本文也將參考其功能進一步改進算法。