基于散列的长链处理算法

郁文斌

(北京全路通信信号研究设计院集团有限公司，北京 100070)

1 概述

截止2020 年底，国内铁路营业里程达到14 万公里以上，其中高铁3.6 万公里以上。高铁的发展已经全面影响和提升了人们的日常出行和生活，因此，高铁的高安全性、高可靠性尤为重要。高铁的安全性主要由列车运行控制系统来保障，其中信号安全为关键。

列控系统[1]主要是通过列车与地面之间的信息传输来实现运行控制的。ATP 要实现超速防护必须通过计算生成连续的目标距离制动曲线，而要生成这条曲线就必须获得地面线路的坡度、速度、限速及目标距离等参数信息。地面设备需要存储这些地面线路数据信息，并对其进行计算将处理后生成的信息提供给ATP 用于动态速度曲线的计算。列控系统尤其是地面设备列控中心[2]、无线闭塞中心[3]、临时限速服务器[4]等各产品功能严格遵循中国国家铁路集团有限公司（简称国铁集团）发布的技术条件，其基于勘查铁路线路的数据承载上层信号功能，这些勘查的数据是具有工程属性的复杂数据[5]，地面线路数据包含一些固定信息包括线路的坡度、闭塞分区或轨道电路长度、载频、线路固定限速等。本文仅对其中的长链数据进行处理。

本文参考铁路相关线路数据的研究[6]，以及考察了目前高铁信号安全产品列控中心、无线闭塞中心、临时限速服务器等产品技术条件中对于各自处理配置的线路数据中长链处理逻辑普遍存在的问题（例如计算的线路方向不同但配置冗余，输入源相同但实现各不相同等），提出一种散列的处理算法，从而达到通过配置最少、最简单的数据生成长链计算所需的关键信息，从而提供长链计算接口给用户，使用户不需要考虑长链的处理而达到提高开发效率的目的。

2 长链介绍

对于线路长链，旧规范[7]（以下简称规范一）停止使用，但是由于历史原因，目前各产品设备的线路数据对于长链的处理仍旧保留对于规范一的兼容性。根据国铁集团发布的最新规范[8]（以下简称规范二），长链定义为：铁路线路里程断链为因线路改造、复测等原因，使线路里程产生不连续的处所。断链前后两里程之差小于实际长度时为长链。

目前，按各产品长链处理共识，对于断链数据输入，根据所使用协议版本，识别长链点的起点、终点、长度。并对以下进行总结分析，所分类涵盖了规范一和规范二中规定的各种情况。

根据规范一，长链设置及标注方法汇总如下：

1) 百米标处存在长链，例如K218+700 为长链终点，长度为2 000 m，如表 1 所示。

2) 公里标处存在长链，例如K219+000 为长链终点，长度为2 000 m，如表 2 所示。

表1 规范一百米标存在长链Tab.1 Long flag at 100m post according to Standard No.1

根据规范二，长链设置及标注方法汇总如下：

1) 百米标处存在长链，例如K218+700 为长链终点，长度为2 000 m，如表3 所示。

2) 公里标处存在长链，例如K219+000 为长链终点，长度为2 000 m，如表4 所示。

表2 规范一公里标存在长链Tab.2 Long flag at kilometer post according to Standard No.1

根据上述分类汇总得出，长链标志按范围分类：

1）百米标处存在长链，第一个长链标志范围，规范一和规范二均相同，为公里标无，百米标a；

2）百米标处存在长链，按规范一，长链标志范围第二个起，按公里标A，百米标a；公里标B，百米标a ……，依次类推；

表3 规范二百米标存在长链Tab.3 Long flag at 100m post according to Standard No.2

表4 规范二公里标存在长链Tab.4 Long flag at kilometer post according to Standard No.2

3）百米标处存在长链，按规范二，长链标志范围以第二个为结尾，为公里标A，百米标a；

4）公里标处存在长链，按规范一，长链标志范围按公里标A，百米标a；公里标B，百米标a……，依次类推；

5）公里标处存在长链，按规范二，长链标志范围仅为公里标A，百米标a。

3 长链算法

根据表1～4 的分析得知，长链计算可以制定如下规则：

1）定义公里标长链标志N 是以空串或者字母'A'到'Z'组合而成的字符串；

2）定义百米标长链标志a；

3）定义公里标长链标志分类规则，兼容规范一和规范二；

4）定义计算公式，将公里标长链标志转换为计算机存储的数值；

5）对于给定的长链点配置，定义长链参数集合，包含已知参数和未知的参数；

6）定义长链有效参数集合，其是已知参数的最小集合，有效参数必须是能进行计算的数值；

7）定义长链算法，根据有效参数推导出其他参数。

根据上述规则分别提出解决方法如下。

3.1 长链标志

根据公里标长链标志N的定义，公里标根据协议规范一和规范二的不同涉及到字母A，B，……，Z，AA，……，AZ，……，在内部计算时需要设定规则将长链公里标志转换为数字。在输出时，再按照设备接口协议进行转换。

因此，需要对公里标的长链标志进行公式转换的设定，以存储的数值映射其对应的公里标长链标志。

以26 进制为基础，定义公式如下：

其中，n为正整数，N为长链标志字符串。

那么，对于任意公里标长链标志x，根据公式（3）转换为存储的数值。

对于任意整数y，f-1(y)与f(x)互为反函数，返回对应的长链标志字符串。但是由于进制B 和字符'Z'的数字表示都是26，所以f-1(y)反推过程中，如果遇到余数为0 时，得到的字符为'Z'，值自动减1。

其中，n为正整数，M为长链标志字符串，Nt到N0可以由y递推，即f-1(y)可以通过y递推得到，递推公式为：

公式（3）的伪码实现如图1 所示。

图1 公式（3）伪码实现图Fig.1 Implementation of pseudocodes of Formula (3)

公式（4）～（6）的伪码实现如图2 所示。

3.2 散列规则

根据表 1～4 的分析及长链规则，长链计算可以制定如下散列规则：

1) 定义种类集合SC={[f(x),(x,a)]|x为任意公里标长链标志}；

2) 依据集合SC，定义公里标长链标志分类序列SCS为[0，(公里标无，百米标a)]；[1，（公里标A，百米标a）]；[2，（公里标Β，百米标a）]，…[i，（f-1(i)，百米标a）]，……，依次类推；

3) 定义范围集合SS={ [Sf(x)，Ef(x)）|x为任意公里标长链标志，本范围为左闭右开区间}；

4) 对于给定一个长链配置，定义长链终点（不带长链标志）LE和长度LL两个参数为有效参数；

图2 公式（4）（5）（6）伪码实现图Fig.2 Implementation of pseudocodes of Formula (4)(5)(6)

5) 根据LE和LL，按照协议规范一和规范二，依次遍历SCS中每个元素按顺序进行散列，确定每个元素的起点里程标和终点里程标，依据集合SS，按顺序定义序列SSS为{ [0，[起点里程标值S0，终点里程标值E0)]，[1，[起点里程标值S1，终点里程标值E1）]，[2，[起点里程标值S2，终点里程标值E2）]，……，[i，[起点里程标值Si，终点里程标值Ei）]，……依次类推}，其中每个元素的范围均为左闭右开区间；

6) 根据散列结果，定义距离参数Di为第i个长链标志范围的长度，即Di=Ei-Si。一般情况下，长链在百米标上时，Di=1 000，i大 于0 且 不是最后一个序列；长链在千米标上时，Di=1 000，i大于等于0 且不是最后一个序列。

任意给定长链点P，定义如下计算规则：

1) 对于给定的长链点P，其里程标值为PV，判断其长链标志落在SCS和SSS序列内，得出是否合法；

2) 如果判断合法，则判断P落在长链标志范围序号为i，从而得到其距离第i个长链标志范围起点里程标值的绝对距离Dx=PV-Si。

则P距离长链起点的绝对距离为

4 算法实现

据此，进行算法实现，程序设计逻辑如图 3 所示。

为完成上述程序逻辑，需实现3.1 的公式（1）、（2）、（3）、（4）、（5）及3.2 的算法，具体如表 5所示。

5 测试验证

本节根据程序实现的长链算法设计案例进行验证。设计案例的原则为根据长链规范一和规范二的每种情况设定等价类，每种等价类需要对边界值设定案例，同时需综合考虑线路数据与长链配置的方向设定不同场景进行遍历，以此检验算法的逻辑是否正确，算法是否能兼容长链规范一和规范二，是否能适用不同产品的数据处理需求，对用户透明。设定线路如下：

图3 程序逻辑图Fig.3 Diagram of program logic

表5 算法实现功能列表Tab.5 List of algorithm functions

线路方向上分别有里程标系KA=1，KB=9，KC=11，KD=12，KE=13，范围分别为（K A10+000，K A238+752），（K B239+123，K B302+000），（K C20+000，K C10+000），（K D20+000，K D10+000），（K E10+000，KE20+000），长链配置点分别以（长链终点，长链长度）给出，为LG1=（KA15+200，50），LG2=（KA18+000,50），LG3=（KB242+300，2000），LG4=（KB271+000，2200），LG5=（KB302+000，900），L G6=（K D20+000，1000），L G7=（KE15+000，1000）。

选 取 以LG3=（KB242+300，2000）和LG6=（KD20+000，1000）为场景，制定案例如表6 所示。

表6 长链功能测试案例Tab.6 Test cases of long-flag functions

测试结果正确，确认算法功能符合预期。

6 总结

本文主要通过分析长链规范一和规范二，对目前各产品处理长链功能差异进行分析，根据分析结果，提出以公里标长链标志为基础的散列算法，以对各产品在线路处理中对于长链功能处理提供一种便捷的解决方案。本算法以最简单的长链配置规则，实现对于给定任意长链点的校验、处理、计算，从而简化线路数据的处理，使用户处理线路数据时以模块化的方式加入长链功能，同时不影响既有功能。因此，提供了一种统一、高效、灵活、简便的长链处理方法，并以模块化的方式进行直接应用，能最大程度提高开发、数据配置、测试上线路数据的处理效率。

同时，本文没有对本算法在线路数据处理的具体应用给出实例，依据本长链处理算法的思想，可以延伸到整个线路数据处理方法的改进。可以针对目前各铁路安全产品对于整个线路数据处理的差异、缺陷给出改进方法，此工作可以作为对于后续工作的展望。