基于Multilevel CodingTree 模型的公路數字化檔案標識編碼研究*

羅 竟 唐修益 黃汝維 陳寧江 閆承鑫 劉曉東 高愛樂

（1.廣西交通職業技術學院，廣西南寧，530023；2.廣西紅河公路有限公司，廣西南寧，530022；3.廣西大學計算機與電子信息學院，廣西南寧，530004）

高速公路檔案信息化建設，其任務就是將建設期間收集到的各類表格、文檔轉換為電子文檔，實現工程檔案數字化。通過計算機實現檔案數字化管理，其必要條件是建立與工程檔案的立卷歸檔材料類別、材料組卷方式和檔案查詢方式相關聯的標識編碼。因此，標識編碼是實現公路工程檔案數字化建設的基礎，是檔案信息化建設的重要內容。

國內普遍采用格式化表格來記錄工程質量數據、原始施工等信息。但是表格類別差異大，格式多樣，內容專業，種類復雜，為高速公路檔案數字化建立唯一性標識編碼造成了巨大障礙。其差異性主要體現在表格類別、表格格式、表格欄目、內容設置、表格用語、表格名稱和表格編號的不同；公路建設投資主體的多元化帶來行業習慣差異；同一地區內不同的業主所使用的表格不統一。目前已有的編碼方案，無法滿足高速公路檔案管理的編碼需要。因此，制定出能指導全國公路行業檔案管理的標識編碼規則，顯得十分困難。針對此問題，本文提出了一種基于Multilevel CodingTree 模 型 的“項目代號+屬性+類別+流水號”四段位編碼方案，能夠有效地實現對高速公路檔案文件的編碼。

本文第1 部分分析了國內外現有的編碼方案，指出它們并不適合我國高速公路數字化檔案管理的需求；第2 部分提出了一種基于Multilevel CodingTree 模 型 的“項目代號+屬性+類別+流水號”四段位編碼方案；第3 部分通過概率分析、實驗測試和命題證明等手段驗證了該編碼方案的唯一性；最后一部分進行了總結。

1 工作背景

現有的高速公路紙質文檔通常包含了高速公路路線名字，所在省份，起訖地名，公路工程檔案的立卷單位，材料類別等信息。按照歸檔材料性質，《公路試驗檢測數據報告編制導則》將歸檔材料分為綜合文件、決算和審計文件、監理資料、施工資料、科研和新技術資料等五部分。同時，公路營運后，管養資料也相應形成項目文件，需要歸檔入庫；按照文檔的類型，又可以把文檔分為單位分部分項工序類、年度批次類、獨立成冊的散裝文件類、圖紙類、聲像類及其他等六大類。如何將以上信息都反映到一個數學模型上，這是設計高速公路文檔的標識編碼要解決的核心問題。

2 現有相關工作

目前國內外各領域已有一些較為成熟的編碼方案可借參考學習，其特點如表1 所示。

除表中所示，王勝明等針對物資編碼中的不等長編碼問題，提出了純數字不等長編碼系統的設計方案，有效地提高了編碼效率，但是無法表示出高速公路所在省、所屬單位的信息［1］。唐敏基于南寧市的空間結構及道路特征，提出了適應南寧市實際情況的道路元素編碼方案，解決了由于數據維護而引發的編碼相對溢出的問題。但可擴展性不強，只適應南寧市［2］。范策基于區間碼（FSC）提出了一種無前綴編碼（UPC），便于記憶，可操作性強。但無法處理高速公路檔案中的散裝材料［3］。盧志毅提出了帶有校驗碼的特種設備全國唯一性識別代碼兩種編碼方案和校驗碼的算法。但是不能體現出高速公路所在省、路段信息［4］。Chenying Wang 等提出新的XML樹的編號方案BNF，避免了XML樹更新時重復編碼的問題。但是無法處理高速公路檔案中的影像資料和散裝材料［5］。Yimin Shen等提出了Serial-number Coding Scheme（SCS），能夠從本質上縮短染色體編碼長度；但不能體現出高速公路檔案中的類別字段［6］。

結合高速公路文檔的特點，并借鑒上述的編碼方案，本文設計了一種基于Multilevel CodingTree 模型的“項目代號+屬性+類別+流水號”四段位編碼方案［7］。該編碼方案的創新性體現在：

（1）涵蓋高速公路檔案數字化建設中所涉及的各類文件、表格、圖紙、影像資料，建立唯一性標識編碼；對于可能產生重復的字段，進行單獨處理，確保編碼的有效性。

（2）通 過 采 用 Multilevel CodingTree 模型結構反映高速公路的各類文檔之間的類別關系，具有較好的擴展性，是一種能夠服務全國公路行業檔案管理的標識編碼。

表1 七種編碼方案特點

3 編碼模型

依據《公路工程竣（交）工驗收辦法實施細則》［8］《公路建設項目文件材料立卷歸檔管理辦法》［9］等相關文件，我們將高速公路的歸檔材料按照圖1 所示的樹型結構進行組織。該樹型結構對應了一種由項目代號、屬性、類別、流水號構成的編碼方案。

項目代號字段分為三級，第一級為路線名稱代號；第二級為《中華人民共和國行政區劃代碼》［10］中規定的省、自治區、直轄市特別行政區的字母碼；第三級為建設項目具體段落代號，采用路段起訖位置地名的第一個拼音字母碼組合。

屬性字段分為兩級，第一級為文檔類型，分為六種類型，每種類型賦予一個編號，如表2 所示。第二級為立卷單位，同時也表征案卷的段落屬性，其代號按路線前進方向采用兩位流水號。

類別字段分為兩級，第一級將立卷歸檔材料劃分為單位分部分項工序類、年度批次類、獨立成冊的散裝文件類、圖紙類、聲像類及其他等六大類；第二級為材料類別型號。

流水號字段采用阿拉伯數字編碼。流水號統一定義為3 位，不足3 位，用00 或0 補足。

根據以上分析可知，高速公路文檔的標識符分多級進行編碼。我們定義Multilevel CodingTree（多級編碼樹）來表示這種編碼關系。

Multilevel CodingTree =（Root，Nodes，Leaves），其中：

（1）Root 是根結點，代表一條高速公路的代號。

（2）Nodes 是非根、非葉子結點的集合，該類結點代表各類檔案文件的分類。

（3）Leaves 是葉子結點的集合，該類結點代表具體的檔案文件。

（4）nodei.father 表 示 結 點nodei 的父結點。

（5）nodei.child［j］表 示 結 點nodei 的第j 個孩子結點。

圖1 編碼的樹型結構

表2 歸檔材料的類別及代號

（6）nodei.value 表示結點nodei的值。

（7）任取nodei 和nodej（nodei?Root 且nodej ?Root），如 果nodei.father=nodej.father，則nodei.value=nodej.value。

（8）nodei.path 是從根結點開始到結點nodei 的完整路徑，即該結點在整個樹型結構中的編碼，即nodei.path=root.value +…+ nodei.father.value+nodei.value，“+”表示字符串的連接運算。

根據Multilevel CodingTree 定義中的（7）可知，任何結點沒有兩個值相同的結點，從而確保了編碼的唯一性。 這也是Multilevel CodingTree 區別于一般多叉樹結構的地方。

基于Multilevel CodingTree 模型，我們設計了“項目代號+屬性+類別+流水號”四段位編碼方案。每段位的構成規則：（1）項目代號段位由路線名稱、代號字母碼、建設項目、具體段落代號構成。（2）屬性段位由文檔類型、立卷單位構成。（3）類別段位由立卷歸檔材料的類別、材料類別型號構成。（4）流水號段位統一定義為3 位，不足3 位，用00 或0 補足。編碼示例如圖2 和圖3。

圖2 的編碼含義為：省高速公路網廣西來賓至馬山高速公路（S52），廣西壯族自治區（GX），來賓至馬山段（LM），項目業主歸檔的綜合文件（100），建設依據類第1 件（201），第一頁（001），第65 案卷（065）。

圖3 的編碼含義為：省高速公路網廣西武宣至平果高速公路（S52），廣西壯族自治區（GX），來賓至馬山段（LM）；施工資料第1標（401）；質量評定（3），路基單位工程（J01），路基土石方分部工程（A01），土方路基分項工程（A01），工序（0），分項工程質量檢驗評定表（W01），第1 頁（001）；第65 案卷。

設計高速公路文檔標識編碼的目的是要實現歸檔材料的“一卷（頁、件）一碼”，因此必須證明標識編碼具有唯一性。通過以上論述，本編碼方案需要進行唯一性論證的問題有：

（1）在建設項目具體段落代號部分，采用路段起訖位置地名的首字拼音字母碼組合可能會出現重復。

（2）“項目代號+屬性+類別+流水號”四個段位連在一起的唯一性。

圖2 項目標識符編碼

圖3 項目標識符編碼

4 項目編碼唯一性驗證

為了保證四段位編碼方案能夠順利地應用到實際生產中，我們設計證明方案驗證其唯一性。證明方案包括建設項目具體段落代號的唯一性證明、“項目代號+屬性+類別+流水號”四個段位連在一起的編碼的唯一性。證明思路如下：（1）首先將起訖、地名首字拼音字母組合，判斷是否有新的項目起訖地名重名。如有，則再取起點或終點地名第二個拼音字母組合，依次類推。其概率符合二項分布理論，故采取基于二項分布的概率統計方法進行概率分析，并結合全國各省的數據進行實驗分析。（2）分別分析四個段位的唯一性，然后根據Multilevel CodingTree 的結構用反證法證明四段位編碼具有唯一性。

4.1 建設項目具體段落代號唯一性的驗證

建設項目具體段落代號編碼的構成分為兩種情況：一是采用路段起訖位置地名的第一個字母碼組合，如：來賓至馬山段（LM）；二是當起訖地名首字母組合同名時再取起點或終點地名第二個字母加入組合，如：來賓至馬山段（LAM）。我們將通過概率分析和實驗測試的方法來分析這兩種情況下字母碼組合的重復率。

（1）采用二項分布理論計算重復概率

二項分布的定義：重復n 次獨立的伯努利試驗（是在同樣的條件下重復地、各次之間相互獨立地進行的一種試驗），在每次實驗中只有兩種可能的結果，而且兩種結果發生與否互相對立且獨立，與其它各次實驗結果無關，事件發生與否的概率在每一次獨立實驗中都保持不變。如果事件發生的概率是p，則不發生的概率q=1-p，n 次獨立重復試驗中發生k 次的概率是：

參考二項分布的定義，將項目的起訖位置地名字母碼組合的比較當成抽取實驗。抽取實驗是每次從若干個字母中任取兩個構成一個字母對，重復n 次，然后對抽取結果進行比較并統計有多少個字母對重復。抽取實驗只有兩種互斥且獨立的結果，即重復與不重復。每次抽取實驗都相互獨立，并且對于同一數據集其重復的概率不會發生變化。通過以上分析可見，進行n 次項目的起訖位置地名字母對的比較，字母對發生重復的k 次是一個服從二項分布B（n，p）的隨機變量。

設項目的起訖位置地名字母碼組合的樣本空間為Ω={A1，A2，A3，…，An}，在地名數量為m（m>1）的情況下，

由于重復次數大于兩次的概率值極小，所以在概率計算時僅計算重復一次和兩次的情況。下面分別針對建設項目具體段落代號編碼的兩種構成情況進行討論。

①在采用路段起訖位置地名的第一個字母碼組合的情況下，假設用p1表示每次比較發生重復的概率，q1是每次比較不重復的概率，則有：

其中，p1表示先從m 個地名中隨機抽取一個地名的首字母作為起始地首字母，再從m-1 個地名中隨機抽取一個地名的首字母作為終點首字母，由于結果要么重復，要么不重復，因此再相乘。所以，第一種情況下比較n 次發生重復的概率如下：

②當起訖地名首字母組合同名時取起點或終點地名第二個字母碼的情況下，假設用p2表示每次比較發生重復的概率，q2是每次比較不重復的概率，則有：

其中，p2表示先從m 個地名中隨機抽取一個地名的首字母作為起始地首字母，由于同一個地名的第二個字母可能與第一個字母不一樣，因此可看成再從m 個字母中抽取一個作為起始地的第二個字母，接著從m-1 個地名中隨機抽取一個地名的首字母作為終點首字母，由于結果要么重復，要么不重復，因此再相乘。所以，第二種情況下比較n 次發生重復的概率如下：

我國現行體制下同一條公路通常不會出現跨省建設、管養和營運。故通過統計全國各省、自治區和直轄市內包含的所有地名來計算概率即可。根據《中華人民共和國行政區劃代碼》［10］《國家高速公路網命名和編號規則》［11］等資料文件統計了全國各省內的市縣級地名數目，如表3 所示。

根據公式（4-2）至（4-8），分別計算兩種情況下各省起訖地名的重復概率（%），結果如表4 所示。

通過表4 可知，第一種情況下重復的概率最大為2.3*10－1%，第二種情況下重復的概率最大為3.8*10－2%。可見，從概率論的角度來看，采用路段起訖位置地名的第一個字母碼組合或第一和第二個字母碼組合的方式表示建設項目具體段落代號是有可能出現重復現象的。但是總的來看，①重復的概率是較低的，例如在第一種情況下，進行1000 次不同地名首字母組合的比較才會出現2 個重復的地名；②采用路段起訖位置地名的第一個字母碼對與起點或終點的第二個字母碼組合的方式的確可以有效地減小重復概率。

根據《公路建設項目文件材料立卷歸檔管理辦法》［9］《中華人民共和國行政區劃代碼》［10］《國家高速公路網命名和編號規則》［11］等資料文件，選取全國29 個省、直轄市、自治區的2315 個地名和途徑以上地區的592 條高速公路的數據作為樣本空間，分兩種情況進行統計分析：一是統計每個省的路段起訖位置地名拼音的第一個字母碼對，計算其在樣本空間內的重復率（%）；二是統計每個省的路段起訖位置地名的第一個字母碼對與起點或終點的第二個字母碼組合，計算其在樣本空間內的重復率（%）。統計結果如表5 所示。

根據表5 可知，第一種情況的重復率最大為4.8*10－3%；第二種情況的重復率都為0。所以在實際的應用中，采用路段起訖位置地名的第一個字母碼與對應起點或終點的第二個字母碼組合的方式可以消除重復現象，使唯一性得到了保障。

表3 各省地名數目統計

表4 兩種情況的重復概率（%）

4.2 項目代號+屬性+類別+流水號唯一性的證明

四段位編碼分別由項目代號、屬性、類別和流水號這四部分組成，下面分別考慮每一部分的唯一性。

（1）項目代號字段分為三級，第一級為路線代號，第二級為省、自治區、直轄市、特別行政區的字母碼，第三級為建設項目具體段落代號。對于路線代號，根據《國家高速公路網命名和編號規則》［11］可知，每條公路的代號是固定唯一的，因此線路代號是唯一的；對于省、自治區、直轄市、特別行政區的字母碼，此部分是嚴格參照《省、自治區、直轄市特別行政區代碼表》［12］，因此每個省的代碼是唯一的；建設項目段落代號編碼在4.1 中已經證明可以實現其編碼的唯一性。所以，項目代號字段的編碼是唯一的。

（2）屬性字段第一級對應于文獻的文檔類型，分別是綜合文件、決算和審計文件、監理資料、施工資料、科研和新技術資料、管養資料等六種類型，每種類型賦予一個不同的編號（1-6 中的一個數字）。因此每種立卷材料的類型代碼是唯一的。第二級對應立卷單位或施工段落的流水號，為00～99 兩位數字。因為各參建單位序號是唯一且固定的，所以第二級是唯一的。由于屬性字段的第一級和第二級是唯一確定的，因此屬性字段的編碼是唯一的。

（3）類別字段也分為兩級，第一級按照綜合文件、決算和審計文件、監理資料、施工資料、科研和新技術資料的各第一層次的綱，具有唯一性。第二級將立卷歸檔材料劃分為單位分部分項工序類、年度批次類、獨立成冊的散裝文件類、圖紙類、聲像類及其他等六大類。因此類別字段的編碼是唯一的。

（4）流水號字段采用阿拉伯數字編碼，統一定義為3 位，表示000-999 之間的數字，每一個該類型的歸檔文件分配一個不同的流水號，保證同類文件流水號的唯一性。

通過分別考察分析四個段位可知，每個段位的編碼都是唯一的。由于四段位編碼是基于Multilevel CodingTree 模型設計的，因此接下來將根據Multilevel CodingTree 模型的定義，證明四段位編碼的唯一性。

命題：在Multilevel CodingTree模型中，不存在編碼相同的葉子結點。

證明：用反證法。假設結點nodei 和 nodej （nodei∈Leaves，nodej∈Leaves，且i≠j）的編碼是相同的，記為e1e2…em（m>1）。由于編碼有m 位，可知nodei 和nodej 同為第m 層的結點，又因為i≠j，所以nodei 和nodej 或者是兄弟結點，或者是堂兄弟結點。下面將分兩種情況進行分析。

表5 實驗的重復概率（%）

表6 實際生產效果

①nodei 和nodej 是兄弟結點

因為nodei 和nodej 具有相同的編碼e1e2…em，根據Multilevel CodingTree 的定義可知，

nodei.value=nodej.value=em 且nodei.father=nodej.father。

又根據Multilevel CodingTree的定義，如果nodei.father=nodej.father，則nodei.value=nodej.value。這與 nodei.value=nodej.value=em的結論相矛盾。

所示nodei 和nodej 是兄弟結點時，它們的編碼不會相同。

②nodei 和nodej 是堂兄弟結點

因為nodei 和nodej 必然具有至少一個不同的祖先結點，假設從第k 層（1

又因為nodei 和nodej 具有相同的編碼e1e2…em，則有nodeki.value=nodekj.value =ek，這與前面推 出nodeki.value≠nodekj.value 的結論相矛盾。

所以nodei 和nodej 是堂兄弟結點時，它們的編碼不會相同。

根據①②可得，在Multilevel CodingTree 模型中，不存在編碼相同的葉子結點，即保證了編碼的唯一性。

綜上所述，基于Multilevel CodingTree 模型的四段位編碼方案能夠實現編碼的唯一性。

4.3 實際效果的驗證

目前，本編碼方案已經成功應用到“高速公路檔案管理系統”中，保存了廣西來賓至馬山、馬山至平果共200km 的高速公路工程數字化檔案，其六大類材料總共100270 件，共計184.6G 數據，產生編碼100270 條。統計結果如表6。

從實際產生的統計結果可以看出，本編碼具有較好的唯一性，能夠滿足實際工作。

通過以上的概率分析、實驗測試、命題證明和實際生產測試等手段，驗證了編碼的唯一性。該編目具有較好的推廣性，當應用到其他省市、自治區、直轄市中，將項目代號中第一級路線名稱代號、第二級字母碼、第三級建設項目具體段落代號進行替換即可。當建設項目具體段落代號發生重復時，采用路段起訖位置地名的第一個字母碼對應起點或終點的第二個字母碼組合的方式進行處理，保證編碼容錯性。總之，該編碼能夠創造良好的社會價值，為以后同類編碼和其他編碼起到指導和借鑒作用。

5 結論

通過分析目前國內外現有的編碼方案，可以發現這些編碼方案都不能完全適用于公路電子檔案編碼。為此，我們提出了基于Multilevel CodingTree 模型的“項目代號+屬性+類別+流水號”的四段位編碼方案。根據該編碼的結構，設計證明方案，可以驗證編碼的唯一性。目前，該編碼方案已經投入到“高速公路檔案管理系統”中使用，實現了文件的“一件一碼”，取得了較好的應用效果。本方案具有較好的推廣性，為以后同類編碼和其他類型編碼起到指導和借鑒作用。

［1］王勝明，等.不等長編碼系統的設計與實現［J］.華北電力大學學報，2002（1）：29.

［2］唐敏.南寧市城市道路數據庫編碼設計研究［J］.城市建設理論研究，2013：18.

［3］范策.一種無前綴編碼（UPC）［J］.計算機學報，2002（2）：25。

［4］盧志毅.特種設備全國唯一性識別代碼研究［J］.中國特種設備安全，2006，22（03）：14-18

［5］Chenying Wang，Xiaojie Yuan and Xin Wang.An Ef f i cient Numbering Scheme for Dynamic XMLTrees.Proc.2008 International Conference on Computer Science and Software Engineering，2008，704-707.

［6］Yimin Shen，Yushun，FanSen Zeng.Switching Serial-Number Coding Scheme and Its Application in FFS Scheduling Problem with Inter-Stage Constraints.Proc.Natural Computation，2007，375-379.

［7］羅竟，等.公路數字化檔案唯一性標識編碼詞典［P］.廣西：南寧，2014.

［8］交公路發［2010］65號，公路工程竣（交）工驗收辦法實施細則［S］.

［9］交辦發［2010］382號，公路建設項目文件材料立卷歸檔管理辦法［S］.

［10］GB/T 2260-2007，中華人民共和國行政區劃代碼［S］.

［11］JTG A03-2007，國家高速公路網命名和編號規則［S］.

［12］GB/T 2260-1999，省、自治區、直轄市行政區劃代碼表［S］.