基于散列的長鏈處理算法

郁文斌

(北京全路通信信號研究設計院集團有限公司，北京 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 總結

本文主要通過分析長鏈規范一和規范二，對目前各產品處理長鏈功能差異進行分析，根據分析結果，提出以公里標長鏈標志為基礎的散列算法，以對各產品在線路處理中對于長鏈功能處理提供一種便捷的解決方案。本算法以最簡單的長鏈配置規則，實現對于給定任意長鏈點的校驗、處理、計算，從而簡化線路數據的處理，使用戶處理線路數據時以模塊化的方式加入長鏈功能，同時不影響既有功能。因此，提供了一種統一、高效、靈活、簡便的長鏈處理方法，并以模塊化的方式進行直接應用，能最大程度提高開發、數據配置、測試上線路數據的處理效率。

同時，本文沒有對本算法在線路數據處理的具體應用給出實例，依據本長鏈處理算法的思想，可以延伸到整個線路數據處理方法的改進。可以針對目前各鐵路安全產品對于整個線路數據處理的差異、缺陷給出改進方法，此工作可以作為對于后續工作的展望。