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

孔金鳳， 王 煜

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

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

孔金鳳*， 王 煜

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

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

航班號(hào);相似度;異或編輯距離;LD算法

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

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

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

1 LD算法及相似度計(jì)算

1.1 LD算法

LD算法又稱(chēng)為編輯距離算法[7，8]，是指字符串A通過(guò)插入字符、刪除字符、替換字符變換成字符串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矩陣可以求出兩個(gè)字符串之間的編輯距離，若需求出字符串之間的匹配結(jié)果，需要對(duì)LD矩陣回溯.回溯步驟如下：

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

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

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

1.3 基于編輯距離的相似度計(jì)算

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

(2)

(3)

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

2 基于異或編輯距離的航班號(hào)相似度算法與計(jì)算步驟

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

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

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

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

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

(4)

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

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

(5)

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

2.2 航空公司航班號(hào)平均相似度計(jì)算步驟

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

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

(6)

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)與結(jié)果分析

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

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

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

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

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

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

4 總 結(jié)

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

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

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

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

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

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

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

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

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

[8] 姜華,韓安琪,王美佳,等.基于改進(jìn)編輯距離的字符串相似度求解算法[J].計(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— ),男，湖南 瀏陽(yáng)人，副教授.E-mail:kong_jin_feng@126.com

V324

A

1000-5900(2015)02-0116-05