孔金凤， 王 煜

(中国民用航空飞行学院，四川 广汉 618307)

基于异或编辑距离算法的航班号相似度研究*

孔金凤*， 王 煜

(中国民用航空飞行学院，四川 广汉 618307)

航班号是执行运输航空任务航空器的主用识别标志，但相似航班号会严重影响管制运行效率和航空安全.目前，相似航班号的判断主要依赖管制员的管制经验，对其尚无相关定量研究方法.该文在用于文本相似度定量比较的编辑距离算法基础上，提出了航班号相似度计算的异或编辑距离算法，并利用北京区域管制中心的实际运行数据验证了该算法的可行性.根据该方法计算了国内主要航空公司的平均相似度，相关结果可为航班号的分配提供定量参考.

航班号;相似度;异或编辑距离;LD算法

航班号是执行运输航空飞行任务航空器的主用识别标志，一般由航空公司代码和3～4位数字组成(国内4位：1000～9999，国际3位:100～999)，尽管其总体具有唯一性，但随着航空公司和航班数量的增加，不同航空公司之间航班号的数字相同、相同或不同航空公司之间航班号数字相近的这类航班号出现概率会不断加大.当这类航班号出现在同一空域时，一方面管制员需要投入更多的精力来区分；另一方面，还极易导致管制员口误或飞行员误听致使航空器执行本不属于它的管制指令，从而影响管制运行效率和航空安全.

目前，航班号相似度仍停留在从定性角度进行研究，该类方法主要依赖管制员的管制经验和技能水平，并且会存在个体差异而导致不能统一标准，使得其无法进行大范围推广应用.因此，展开对航班号相似度的定量研究，统一标准，从航班号分配源头上降低相似航班号在同一空域中出现的概率，对提高管制运行效率和航空安全具有重要意义.

向量空间模型[1]广泛用于文本的相似度计算，它主要是将文档转换成具有n个特征的空间向量，通过计算两个向量之间的余弦值，即可得知两个文档之间的相似度.余弦值越大，向量夹角越小，文档相似度越高.但对于航班号文本，考虑其特征项难以提取，使用此方法较为困难.编辑距离(Levenshtein Distance，LD)算法通常被用于短字符串的快速匹配.国内学者对其也有许多的研究和改进[2～7].编辑距离算法首先以矩阵形式求解两个文本之间的编辑距离，而后利用相关方法获得其相似度.但对于航班号这种超短文本，其并不具备完好的适用性.在航班号相似度应用时编辑距离算法需要大量重复计算.为解决此问题，结合航班号的特性，本文提出了基于异或编辑距离的航班号相似度算法，并利用北京区域管制中心实际运行数据验证了该算法的可行性.又根据该方法计算了国内主要航空公司的平均相似度.最后对航班号的使用及管理给出了相关建议.

1 LD算法及相似度计算

1.1 LD算法

LD算法又称为编辑距离算法[7，8]，是指字符串A通过插入字符、删除字符、替换字符变换成字符串B所需要的最小操作次数.操作次数的大小即表示出字符串A和B之间的差异.

设有字符串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的求解规则如下所示

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矩阵可以求出两个字符串之间的编辑距离，若需求出字符串之间的匹配结果，需要对LD矩阵回溯.回溯步骤如下：

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

(2) 若ai=bj，回溯至左上角单元格；若ai≠bj，回溯到左上角、上边、左边中值最小的单元格，若有相同最小值的单元格，按照左上角、上边、左边的优先级顺序选择.

(3) 根据回溯路径，写出匹配字符串.

1.3 基于编辑距离的相似度计算

LD距离本身的大小可以反映出两个字符串之间的差异程度.一般而言LD距离越大，字符串之间的差异程度越明显，字符串的相似程度越低.文献[5，6]提出了基于编辑距离计算文本相似程度的公式：

(2)

(3)

其中ld为字符串之间的LD距离,m和n表示字符串的长度.

2 基于异或编辑距离的航班号相似度算法与计算步骤

2.1 基于异或编辑距离的航班号相似度求解算法

假设1 航班号相似度计算中数字只记为字符处理，并无大小意义.

假设2 如果两个航班号串长度不等，按照从右向左的优先级顺序排列.

定义 异或编辑距离：将两个字符串按位异或的结果求和，记为XLD(Xor Levenshtein Distance).

设有两个字符串F[m]=f1f2…fm，P[n]=b1b2…bn.R[q]为字符串F[m]与P[n]按位异或结果，则两个字符串的异或编辑距离为：

(4)

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

参照公式(2)，可以得到基于异或编辑距离的相似度计算为：

(5)

例如，有两个航班号F[m]=JAL785，P[n]=AAR583.根据上述方法可以得到R[q]=[101101]，XLD=4，XSim=0.667.

2.2 航空公司航班号平均相似度计算步骤

根据已分配给航空公司航班号段的规律，其航班号差异程度矩阵M如下.其中λi(i=1,2,3,4)表示航空公司的航班号段有i种差别.

根据航班号差异程度矩阵，航空公司航班号平均相似度计算为：

(6)

其中ωi表示航空公司每一种航班号段差异类别所占的权重.

根据上述规则，基于异或编辑距离的航班号相似度计算主要包括三个方面内容：分析航空公司航班号片段的差异程度种类、根据差异类别确定其相似度取值、求解航空公司航班号片段平均相似度.其具体计算步骤如下：

步骤一：初始化航班号分配数据.

步骤二：确定每一航空公司航班号片段差异程度和权重.

步骤三：根据上述方法，计算每一种差异类别的相似度取值.

步骤四：计算航空公司平均相似度.

步骤五：重复上述步骤，计算第k个航空公司航班号段的平均相似度.

步骤六：计算完成，分析计算结果.

3 实验与结果分析

为验证本文提出的航班号相似度计算方法的可行性，实验数据分别选取北京区域管制范围内以经验方式定性描述相似航班号的12组航班号对和国内部分航空航班号片段作为分析对象.其计算结果分别如表1和表2所示.

从表1可知编辑距离算法和本文算法所求得的航班号相似度量值有部分差异,如图1所示，但数值分别在0.7和0.65以上，计算数值处于较高的程度，这一结果与以经验方式定义相似程度高低是一致的.可以认为把本文算法应用在航班号相似度分析中是可行的，通过此方法求得的航班号相似度可以作为航班号分类的依据.

表1 计算结果对比

表2 航空公司平均相似度计算结果

考虑到航班号分配的规律，同一航空公司已分配的号段差异程度取值集合为{“有一位数值差异”，“有两位数值差异”、“有三位数值差异”、“有四位数值差异”}.若使用编辑距离算法求解航空公司航班号平均相似度，需要大量的计算，并且相似程度结果偏高.若根据本文提出的计算方法，航空公司航班号平均相似度取值只有两种情况：公司代码为两位，航空公司航班号平均相似度取值集合为{0.917 0.833 0.750 0.667}.公司代码为三位，航空公司航班号平均相似度取值集合为{0.929 0.857 0.786 0.714}.根据此方法，国内部分航空公司的平均相似度计算结果如表2所示.

通过表2可以发现，目前选取的航空公司航班号平均相似度水平较高，不同航空公司之间的平均相似度差异较为明显，如图2所示.随着航空公司的航班号片段数目增多，其平均相似度有所降低.对于航班号管理部门，这一变化规律可以作为其分配航班号段的参考，也即尽量给每家航空公司分配较多的航班号片段以降低整体的相似度.

4 总 结

在编辑距离算法的基础上，结合航班号的特性，提出了一种定量的航班号相似度算法——异或编辑距离算法，利用实际运行数据验证了该算法的可行性，避免了定性研究方法的不足.根据相关研究内容，计算了航空公司航班号平均相似度.结合目前我国航班号使用及管理现状给出以下建议：①管制员和飞行员在陆空通话中，应严格按照标准规范读取航班号内容.②航空公司在安排航班计划时，应将相似度高的航班号按照目的地、时隙进行区分.③在当前航班号基数无法改变下，航班号管理部门应尽量给每家航空公司分配较多的航班号片段.

仅通过字面的相似度比较会造成少量的航班号相似度与实际情况有差别.通过语义相似比较会更加符合实际的管制工作需要，下一步任务就需根据语义相似找出航班号相似度的研究方法.

[1] 唐明伟,卞艺杰,陶飞飞.基于语义向量空间模型的文档检索系统研究[J]. 情报杂志, 2010, 29(5):167-170.

[2] 刁兴春,谭明超,曹建军.一种融合多种编辑距离的字符串相似度计算方法[J]. 计算机应用研究, 2010, 27(12):4 523-4 525.

[3] 叶焕倬,吴迪.基于改进编辑距离的相似重复记录清理算法[J].现代图书情报技术, 2011:82-90.

[4] 王博,胡晓勤.基于归一化编辑距离的自由文本击键特征分类识别方法[J]. 计算机安全, 2014(10)：15-21.

[5] 周汉平.Levenshtein距离在编程题自动评阅中的应用研究[J].计算机应用与软件, 2011, 28(5):209-212.

[6] 赵作鹏,尹志民,王潜平,等.一种改进的编辑距离算法及其在数据处理中的应用[J]. 计算机应用, 2009, 29(2):424-426.

[7] 刘宝艳,林鸿飞,赵晶.基于改进编辑距离和依存文法的汉语句子相似度计算[J].计算机应用与软件, 2008, 25(7):33-34.

[8] 姜华,韩安琪,王美佳,等.基于改进编辑距离的字符串相似度求解算法[J].计算机工程,2014,40(1):222-227.

责任编辑：龙顺潮

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