孔金鳳， 王 煜

(中國民用航空飛行學(xué)院，四川 廣漢 618307)

基于異或編輯距離算法的航班號相似度研究*

孔金鳳*， 王 煜

(中國民用航空飛行學(xué)院，四川 廣漢 618307)

航班號是執(zhí)行運輸航空任務(wù)航空器的主用識別標(biāo)志，但相似航班號會嚴(yán)重影響管制運行效率和航空安全.目前，相似航班號的判斷主要依賴管制員的管制經(jīng)驗，對其尚無相關(guān)定量研究方法.該文在用于文本相似度定量比較的編輯距離算法基礎(chǔ)上，提出了航班號相似度計算的異或編輯距離算法，并利用北京區(qū)域管制中心的實際運行數(shù)據(jù)驗證了該算法的可行性.根據(jù)該方法計算了國內(nèi)主要航空公司的平均相似度，相關(guān)結(jié)果可為航班號的分配提供定量參考.

航班號;相似度;異或編輯距離;LD算法

航班號是執(zhí)行運輸航空飛行任務(wù)航空器的主用識別標(biāo)志，一般由航空公司代碼和3～4位數(shù)字組成(國內(nèi)4位：1000～9999，國際3位:100～999)，盡管其總體具有唯一性，但隨著航空公司和航班數(shù)量的增加，不同航空公司之間航班號的數(shù)字相同、相同或不同航空公司之間航班號數(shù)字相近的這類航班號出現(xiàn)概率會不斷加大.當(dāng)這類航班號出現(xiàn)在同一空域時，一方面管制員需要投入更多的精力來區(qū)分；另一方面，還極易導(dǎo)致管制員口誤或飛行員誤聽致使航空器執(zhí)行本不屬于它的管制指令，從而影響管制運行效率和航空安全.

目前，航班號相似度仍停留在從定性角度進(jìn)行研究，該類方法主要依賴管制員的管制經(jīng)驗和技能水平，并且會存在個體差異而導(dǎo)致不能統(tǒng)一標(biāo)準(zhǔn)，使得其無法進(jìn)行大范圍推廣應(yīng)用.因此，展開對航班號相似度的定量研究，統(tǒng)一標(biāo)準(zhǔn)，從航班號分配源頭上降低相似航班號在同一空域中出現(xiàn)的概率，對提高管制運行效率和航空安全具有重要意義.

向量空間模型[1]廣泛用于文本的相似度計算，它主要是將文檔轉(zhuǎn)換成具有n個特征的空間向量，通過計算兩個向量之間的余弦值，即可得知兩個文檔之間的相似度.余弦值越大，向量夾角越小，文檔相似度越高.但對于航班號文本，考慮其特征項難以提取，使用此方法較為困難.編輯距離(Levenshtein Distance，LD)算法通常被用于短字符串的快速匹配.國內(nèi)學(xué)者對其也有許多的研究和改進(jìn)[2～7].編輯距離算法首先以矩陣形式求解兩個文本之間的編輯距離，而后利用相關(guān)方法獲得其相似度.但對于航班號這種超短文本，其并不具備完好的適用性.在航班號相似度應(yīng)用時編輯距離算法需要大量重復(fù)計算.為解決此問題，結(jié)合航班號的特性，本文提出了基于異或編輯距離的航班號相似度算法，并利用北京區(qū)域管制中心實際運行數(shù)據(jù)驗證了該算法的可行性.又根據(jù)該方法計算了國內(nèi)主要航空公司的平均相似度.最后對航班號的使用及管理給出了相關(guān)建議.

1 LD算法及相似度計算

1.1 LD算法

LD算法又稱為編輯距離算法[7，8]，是指字符串A通過插入字符、刪除字符、替換字符變換成字符串B所需要的最小操作次數(shù).操作次數(shù)的大小即表示出字符串A和B之間的差異.

設(shè)有字符串A=a1a2…am,B=b1b2…bn.字符串A和B建立的LD(m+1,n+1)矩陣可用公式(1)表示：

LD(m+1,n+1)={dij}， (0≤i≤m,0≤j≤n),

(1)

其中dij表示字符串A和B之間的LD距離.dij的求解規(guī)則如下所示

LD(i,j)=j, 若i=0,

LD(i,j)=i, 若j=0，

LD(i,j)=LD(i-1,j-1), 若ai=bj，

LD(i,j)=min(LD(i-1,j-1),LD(i-1,j),LD(i,j-1))+1,若ai≠bj.

1.2 LD回溯路徑

LD矩陣可以求出兩個字符串之間的編輯距離，若需求出字符串之間的匹配結(jié)果，需要對LD矩陣回溯.回溯步驟如下：

(1) 定位LD矩陣的右下角dij.

(2) 若ai=bj，回溯至左上角單元格；若ai≠bj，回溯到左上角、上邊、左邊中值最小的單元格，若有相同最小值的單元格，按照左上角、上邊、左邊的優(yōu)先級順序選擇.

(3) 根據(jù)回溯路徑，寫出匹配字符串.

1.3 基于編輯距離的相似度計算

LD距離本身的大小可以反映出兩個字符串之間的差異程度.一般而言LD距離越大，字符串之間的差異程度越明顯，字符串的相似程度越低.文獻(xiàn)[5，6]提出了基于編輯距離計算文本相似程度的公式：

(2)

(3)

其中l(wèi)d為字符串之間的LD距離,m和n表示字符串的長度.

2 基于異或編輯距離的航班號相似度算法與計算步驟

2.1 基于異或編輯距離的航班號相似度求解算法

假設(shè)1 航班號相似度計算中數(shù)字只記為字符處理，并無大小意義.

假設(shè)2 如果兩個航班號串長度不等，按照從右向左的優(yōu)先級順序排列.

定義 異或編輯距離：將兩個字符串按位異或的結(jié)果求和，記為XLD(Xor Levenshtein Distance).

設(shè)有兩個字符串F[m]=f1f2…fm，P[n]=b1b2…bn.R[q]為字符串F[m]與P[n]按位異或結(jié)果，則兩個字符串的異或編輯距離為：

(4)

其中，q=max(m,n).

參照公式(2)，可以得到基于異或編輯距離的相似度計算為：

(5)

例如，有兩個航班號F[m]=JAL785，P[n]=AAR583.根據(jù)上述方法可以得到R[q]=[101101]，XLD=4，XSim=0.667.

2.2 航空公司航班號平均相似度計算步驟

根據(jù)已分配給航空公司航班號段的規(guī)律，其航班號差異程度矩陣M如下.其中λi(i=1,2,3,4)表示航空公司的航班號段有i種差別.

根據(jù)航班號差異程度矩陣，航空公司航班號平均相似度計算為：

(6)

其中ωi表示航空公司每一種航班號段差異類別所占的權(quán)重.

根據(jù)上述規(guī)則，基于異或編輯距離的航班號相似度計算主要包括三個方面內(nèi)容：分析航空公司航班號片段的差異程度種類、根據(jù)差異類別確定其相似度取值、求解航空公司航班號片段平均相似度.其具體計算步驟如下：

步驟一：初始化航班號分配數(shù)據(jù).

步驟二：確定每一航空公司航班號片段差異程度和權(quán)重.

步驟三：根據(jù)上述方法，計算每一種差異類別的相似度取值.

步驟四：計算航空公司平均相似度.

步驟五：重復(fù)上述步驟，計算第k個航空公司航班號段的平均相似度.

步驟六：計算完成，分析計算結(jié)果.

3 實驗與結(jié)果分析

為驗證本文提出的航班號相似度計算方法的可行性，實驗數(shù)據(jù)分別選取北京區(qū)域管制范圍內(nèi)以經(jīng)驗方式定性描述相似航班號的12組航班號對和國內(nèi)部分航空航班號片段作為分析對象.其計算結(jié)果分別如表1和表2所示.

從表1可知編輯距離算法和本文算法所求得的航班號相似度量值有部分差異,如圖1所示，但數(shù)值分別在0.7和0.65以上，計算數(shù)值處于較高的程度，這一結(jié)果與以經(jīng)驗方式定義相似程度高低是一致的.可以認(rèn)為把本文算法應(yīng)用在航班號相似度分析中是可行的，通過此方法求得的航班號相似度可以作為航班號分類的依據(jù).

表1 計算結(jié)果對比

表2 航空公司平均相似度計算結(jié)果

考慮到航班號分配的規(guī)律，同一航空公司已分配的號段差異程度取值集合為{“有一位數(shù)值差異”，“有兩位數(shù)值差異”、“有三位數(shù)值差異”、“有四位數(shù)值差異”}.若使用編輯距離算法求解航空公司航班號平均相似度，需要大量的計算，并且相似程度結(jié)果偏高.若根據(jù)本文提出的計算方法，航空公司航班號平均相似度取值只有兩種情況：公司代碼為兩位，航空公司航班號平均相似度取值集合為{0.917 0.833 0.750 0.667}.公司代碼為三位，航空公司航班號平均相似度取值集合為{0.929 0.857 0.786 0.714}.根據(jù)此方法，國內(nèi)部分航空公司的平均相似度計算結(jié)果如表2所示.

通過表2可以發(fā)現(xiàn)，目前選取的航空公司航班號平均相似度水平較高，不同航空公司之間的平均相似度差異較為明顯，如圖2所示.隨著航空公司的航班號片段數(shù)目增多，其平均相似度有所降低.對于航班號管理部門，這一變化規(guī)律可以作為其分配航班號段的參考，也即盡量給每家航空公司分配較多的航班號片段以降低整體的相似度.

4 總 結(jié)

在編輯距離算法的基礎(chǔ)上，結(jié)合航班號的特性，提出了一種定量的航班號相似度算法——異或編輯距離算法，利用實際運行數(shù)據(jù)驗證了該算法的可行性，避免了定性研究方法的不足.根據(jù)相關(guān)研究內(nèi)容，計算了航空公司航班號平均相似度.結(jié)合目前我國航班號使用及管理現(xiàn)狀給出以下建議：①管制員和飛行員在陸空通話中，應(yīng)嚴(yán)格按照標(biāo)準(zhǔn)規(guī)范讀取航班號內(nèi)容.②航空公司在安排航班計劃時，應(yīng)將相似度高的航班號按照目的地、時隙進(jìn)行區(qū)分.③在當(dāng)前航班號基數(shù)無法改變下，航班號管理部門應(yīng)盡量給每家航空公司分配較多的航班號片段.

僅通過字面的相似度比較會造成少量的航班號相似度與實際情況有差別.通過語義相似比較會更加符合實際的管制工作需要，下一步任務(wù)就需根據(jù)語義相似找出航班號相似度的研究方法.

[1] 唐明偉,卞藝杰,陶飛飛.基于語義向量空間模型的文檔檢索系統(tǒng)研究[J]. 情報雜志, 2010, 29(5):167-170.

[2] 刁興春,譚明超,曹建軍.一種融合多種編輯距離的字符串相似度計算方法[J]. 計算機(jī)應(yīng)用研究, 2010, 27(12):4 523-4 525.

[3] 葉煥倬,吳迪.基于改進(jìn)編輯距離的相似重復(fù)記錄清理算法[J].現(xiàn)代圖書情報技術(shù), 2011:82-90.

[4] 王博,胡曉勤.基于歸一化編輯距離的自由文本擊鍵特征分類識別方法[J]. 計算機(jī)安全, 2014(10)：15-21.

[5] 周漢平.Levenshtein距離在編程題自動評閱中的應(yīng)用研究[J].計算機(jī)應(yīng)用與軟件, 2011, 28(5):209-212.

[6] 趙作鵬,尹志民,王潛平,等.一種改進(jìn)的編輯距離算法及其在數(shù)據(jù)處理中的應(yīng)用[J]. 計算機(jī)應(yīng)用, 2009, 29(2):424-426.

[7] 劉寶艷,林鴻飛,趙晶.基于改進(jìn)編輯距離和依存文法的漢語句子相似度計算[J].計算機(jī)應(yīng)用與軟件, 2008, 25(7):33-34.

[8] 姜華,韓安琪,王美佳,等.基于改進(jìn)編輯距離的字符串相似度求解算法[J].計算機(jī)工程,2014,40(1):222-227.

責(zé)任編輯：龍順潮

Research on Flight Numbers Similarity Based on Xor Levenshtein Distance Algorithm

KONGJin-feng*,WANGYu

(Civil Aviation Flight University of China, Guanghan 618307 China)

Flight numbers is the main identification of aircraft that performs the transportation task, however, similarity flight numbers will affect the control operational efficiency and aviation security. Currently the criterion of similarity flight numbers mainly depends on controllers’ experience, there are still no relevant quantitative research methods. This paper proposed the Xor Levenshtein Distance algorithm that used in flight numbers similarity calculation on the basis of Levenshtein Distance which used in text similarity quantitative comparison. It proved that this method is feasible by the actual data calculation of Beijing control area. And then we calculate the average similarity of domestic major airlines, the results have quantitative reference in flight numbers assignment.

flight numbe; similarity; Xor Levenshtein Distance；LD algorithm

2014-12-10

孔金鳳(1973— ),男，湖南 瀏陽人，副教授.E-mail:kong_jin_feng@126.com

V324

A

1000-5900(2015)02-0116-05