基于散列的長鏈處理算法

郁文斌

(北京全路通信信號研究設(shè)計院集團有限公司，北京 100070)

1 概述

截止2020 年底，國內(nèi)鐵路營業(yè)里程達到14 萬公里以上，其中高鐵3.6 萬公里以上。高鐵的發(fā)展已經(jīng)全面影響和提升了人們的日常出行和生活，因此，高鐵的高安全性、高可靠性尤為重要。高鐵的安全性主要由列車運行控制系統(tǒng)來保障，其中信號安全為關(guān)鍵。

列控系統(tǒng)[1]主要是通過列車與地面之間的信息傳輸來實現(xiàn)運行控制的。ATP 要實現(xiàn)超速防護必須通過計算生成連續(xù)的目標距離制動曲線，而要生成這條曲線就必須獲得地面線路的坡度、速度、限速及目標距離等參數(shù)信息。地面設(shè)備需要存儲這些地面線路數(shù)據(jù)信息，并對其進行計算將處理后生成的信息提供給ATP 用于動態(tài)速度曲線的計算。列控系統(tǒng)尤其是地面設(shè)備列控中心[2]、無線閉塞中心[3]、臨時限速服務(wù)器[4]等各產(chǎn)品功能嚴格遵循中國國家鐵路集團有限公司（簡稱國鐵集團）發(fā)布的技術(shù)條件，其基于勘查鐵路線路的數(shù)據(jù)承載上層信號功能，這些勘查的數(shù)據(jù)是具有工程屬性的復(fù)雜數(shù)據(jù)[5]，地面線路數(shù)據(jù)包含一些固定信息包括線路的坡度、閉塞分區(qū)或軌道電路長度、載頻、線路固定限速等。本文僅對其中的長鏈數(shù)據(jù)進行處理。

本文參考鐵路相關(guān)線路數(shù)據(jù)的研究[6]，以及考察了目前高鐵信號安全產(chǎn)品列控中心、無線閉塞中心、臨時限速服務(wù)器等產(chǎn)品技術(shù)條件中對于各自處理配置的線路數(shù)據(jù)中長鏈處理邏輯普遍存在的問題（例如計算的線路方向不同但配置冗余，輸入源相同但實現(xiàn)各不相同等），提出一種散列的處理算法，從而達到通過配置最少、最簡單的數(shù)據(jù)生成長鏈計算所需的關(guān)鍵信息，從而提供長鏈計算接口給用戶，使用戶不需要考慮長鏈的處理而達到提高開發(fā)效率的目的。

2 長鏈介紹

對于線路長鏈，舊規(guī)范[7]（以下簡稱規(guī)范一）停止使用，但是由于歷史原因，目前各產(chǎn)品設(shè)備的線路數(shù)據(jù)對于長鏈的處理仍舊保留對于規(guī)范一的兼容性。根據(jù)國鐵集團發(fā)布的最新規(guī)范[8]（以下簡稱規(guī)范二），長鏈定義為：鐵路線路里程斷鏈為因線路改造、復(fù)測等原因，使線路里程產(chǎn)生不連續(xù)的處所。斷鏈前后兩里程之差小于實際長度時為長鏈。

目前，按各產(chǎn)品長鏈處理共識，對于斷鏈數(shù)據(jù)輸入，根據(jù)所使用協(xié)議版本，識別長鏈點的起點、終點、長度。并對以下進行總結(jié)分析，所分類涵蓋了規(guī)范一和規(guī)范二中規(guī)定的各種情況。

根據(jù)規(guī)范一，長鏈設(shè)置及標注方法匯總?cè)缦拢?/p>

1) 百米標處存在長鏈，例如K218+700 為長鏈終點，長度為2 000 m，如表 1 所示。

2) 公里標處存在長鏈，例如K219+000 為長鏈終點，長度為2 000 m，如表 2 所示。

表1 規(guī)范一百米標存在長鏈Tab.1 Long flag at 100m post according to Standard No.1

根據(jù)規(guī)范二，長鏈設(shè)置及標注方法匯總?cè)缦拢?/p>

1) 百米標處存在長鏈，例如K218+700 為長鏈終點，長度為2 000 m，如表3 所示。

2) 公里標處存在長鏈，例如K219+000 為長鏈終點，長度為2 000 m，如表4 所示。

表2 規(guī)范一公里標存在長鏈Tab.2 Long flag at kilometer post according to Standard No.1

根據(jù)上述分類匯總得出，長鏈標志按范圍分類：

1）百米標處存在長鏈，第一個長鏈標志范圍，規(guī)范一和規(guī)范二均相同，為公里標無，百米標a；

2）百米標處存在長鏈，按規(guī)范一，長鏈標志范圍第二個起，按公里標A，百米標a；公里標B，百米標a ……，依次類推；

表3 規(guī)范二百米標存在長鏈Tab.3 Long flag at 100m post according to Standard No.2

表4 規(guī)范二公里標存在長鏈Tab.4 Long flag at kilometer post according to Standard No.2

3）百米標處存在長鏈，按規(guī)范二，長鏈標志范圍以第二個為結(jié)尾，為公里標A，百米標a；

4）公里標處存在長鏈，按規(guī)范一，長鏈標志范圍按公里標A，百米標a；公里標B，百米標a……，依次類推；

5）公里標處存在長鏈，按規(guī)范二，長鏈標志范圍僅為公里標A，百米標a。

3 長鏈算法

根據(jù)表1～4 的分析得知，長鏈計算可以制定如下規(guī)則：

1）定義公里標長鏈標志N 是以空串或者字母'A'到'Z'組合而成的字符串；

2）定義百米標長鏈標志a；

3）定義公里標長鏈標志分類規(guī)則，兼容規(guī)范一和規(guī)范二；

4）定義計算公式，將公里標長鏈標志轉(zhuǎn)換為計算機存儲的數(shù)值；

5）對于給定的長鏈點配置，定義長鏈參數(shù)集合，包含已知參數(shù)和未知的參數(shù)；

6）定義長鏈有效參數(shù)集合，其是已知參數(shù)的最小集合，有效參數(shù)必須是能進行計算的數(shù)值；

7）定義長鏈算法，根據(jù)有效參數(shù)推導(dǎo)出其他參數(shù)。

根據(jù)上述規(guī)則分別提出解決方法如下。

3.1 長鏈標志

根據(jù)公里標長鏈標志N的定義，公里標根據(jù)協(xié)議規(guī)范一和規(guī)范二的不同涉及到字母A，B，……，Z，AA，……，AZ，……，在內(nèi)部計算時需要設(shè)定規(guī)則將長鏈公里標志轉(zhuǎn)換為數(shù)字。在輸出時，再按照設(shè)備接口協(xié)議進行轉(zhuǎn)換。

因此，需要對公里標的長鏈標志進行公式轉(zhuǎn)換的設(shè)定，以存儲的數(shù)值映射其對應(yīng)的公里標長鏈標志。

以26 進制為基礎(chǔ)，定義公式如下：

其中，n為正整數(shù)，N為長鏈標志字符串。

那么，對于任意公里標長鏈標志x，根據(jù)公式（3）轉(zhuǎn)換為存儲的數(shù)值。

對于任意整數(shù)y，f-1(y)與f(x)互為反函數(shù)，返回對應(yīng)的長鏈標志字符串。但是由于進制B 和字符'Z'的數(shù)字表示都是26，所以f-1(y)反推過程中，如果遇到余數(shù)為0 時，得到的字符為'Z'，值自動減1。

其中，n為正整數(shù)，M為長鏈標志字符串，Nt到N0可以由y遞推，即f-1(y)可以通過y遞推得到，遞推公式為：

公式（3）的偽碼實現(xiàn)如圖1 所示。

圖1 公式（3）偽碼實現(xiàn)圖Fig.1 Implementation of pseudocodes of Formula (3)

公式（4）～（6）的偽碼實現(xiàn)如圖2 所示。

3.2 散列規(guī)則

根據(jù)表 1～4 的分析及長鏈規(guī)則，長鏈計算可以制定如下散列規(guī)則：

1) 定義種類集合SC={[f(x),(x,a)]|x為任意公里標長鏈標志}；

2) 依據(jù)集合SC，定義公里標長鏈標志分類序列SCS為[0，(公里標無，百米標a)]；[1，（公里標A，百米標a）]；[2，（公里標Β，百米標a）]，…[i，（f-1(i)，百米標a）]，……，依次類推；

3) 定義范圍集合SS={ [Sf(x)，Ef(x)）|x為任意公里標長鏈標志，本范圍為左閉右開區(qū)間}；

4) 對于給定一個長鏈配置，定義長鏈終點（不帶長鏈標志）LE和長度LL兩個參數(shù)為有效參數(shù)；

圖2 公式（4）（5）（6）偽碼實現(xiàn)圖Fig.2 Implementation of pseudocodes of Formula (4)(5)(6)

5) 根據(jù)LE和LL，按照協(xié)議規(guī)范一和規(guī)范二，依次遍歷SCS中每個元素按順序進行散列，確定每個元素的起點里程標和終點里程標，依據(jù)集合SS，按順序定義序列SSS為{ [0，[起點里程標值S0，終點里程標值E0)]，[1，[起點里程標值S1，終點里程標值E1）]，[2，[起點里程標值S2，終點里程標值E2）]，……，[i，[起點里程標值Si，終點里程標值Ei）]，……依次類推}，其中每個元素的范圍均為左閉右開區(qū)間；

6) 根據(jù)散列結(jié)果，定義距離參數(shù)Di為第i個長鏈標志范圍的長度，即Di=Ei-Si。一般情況下，長鏈在百米標上時，Di=1 000，i大 于0 且 不是最后一個序列；長鏈在千米標上時，Di=1 000，i大于等于0 且不是最后一個序列。

任意給定長鏈點P，定義如下計算規(guī)則：

1) 對于給定的長鏈點P，其里程標值為PV，判斷其長鏈標志落在SCS和SSS序列內(nèi)，得出是否合法；

2) 如果判斷合法，則判斷P落在長鏈標志范圍序號為i，從而得到其距離第i個長鏈標志范圍起點里程標值的絕對距離Dx=PV-Si。

則P距離長鏈起點的絕對距離為

4 算法實現(xiàn)

據(jù)此，進行算法實現(xiàn)，程序設(shè)計邏輯如圖 3 所示。

為完成上述程序邏輯，需實現(xiàn)3.1 的公式（1）、（2）、（3）、（4）、（5）及3.2 的算法，具體如表 5所示。

5 測試驗證

本節(jié)根據(jù)程序?qū)崿F(xiàn)的長鏈算法設(shè)計案例進行驗證。設(shè)計案例的原則為根據(jù)長鏈規(guī)范一和規(guī)范二的每種情況設(shè)定等價類，每種等價類需要對邊界值設(shè)定案例，同時需綜合考慮線路數(shù)據(jù)與長鏈配置的方向設(shè)定不同場景進行遍歷，以此檢驗算法的邏輯是否正確，算法是否能兼容長鏈規(guī)范一和規(guī)范二，是否能適用不同產(chǎn)品的數(shù)據(jù)處理需求，對用戶透明。設(shè)定線路如下：

圖3 程序邏輯圖Fig.3 Diagram of program logic

表5 算法實現(xiàn)功能列表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

測試結(jié)果正確，確認算法功能符合預(yù)期。

6 總結(jié)

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

同時，本文沒有對本算法在線路數(shù)據(jù)處理的具體應(yīng)用給出實例，依據(jù)本長鏈處理算法的思想，可以延伸到整個線路數(shù)據(jù)處理方法的改進?？梢葬槍δ壳案麒F路安全產(chǎn)品對于整個線路數(shù)據(jù)處理的差異、缺陷給出改進方法，此工作可以作為對于后續(xù)工作的展望。