基于Multilevel CodingTree 模型的公路數(shù)字化檔案標(biāo)識(shí)編碼研究*

羅 竟 唐修益 黃汝維 陳寧江 閆承鑫 劉曉東 高愛(ài)樂(lè)

（1.廣西交通職業(yè)技術(shù)學(xué)院，廣西南寧，530023；2.廣西紅河公路有限公司，廣西南寧，530022；3.廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院，廣西南寧，530004）

高速公路檔案信息化建設(shè)，其任務(wù)就是將建設(shè)期間收集到的各類表格、文檔轉(zhuǎn)換為電子文檔，實(shí)現(xiàn)工程檔案數(shù)字化。通過(guò)計(jì)算機(jī)實(shí)現(xiàn)檔案數(shù)字化管理，其必要條件是建立與工程檔案的立卷歸檔材料類別、材料組卷方式和檔案查詢方式相關(guān)聯(lián)的標(biāo)識(shí)編碼。因此，標(biāo)識(shí)編碼是實(shí)現(xiàn)公路工程檔案數(shù)字化建設(shè)的基礎(chǔ)，是檔案信息化建設(shè)的重要內(nèi)容。

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

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

1 工作背景

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

2 現(xiàn)有相關(guān)工作

目前國(guó)內(nèi)外各領(lǐng)域已有一些較為成熟的編碼方案可借參考學(xué)習(xí)，其特點(diǎn)如表1 所示。

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

結(jié)合高速公路文檔的特點(diǎn)，并借鑒上述的編碼方案，本文設(shè)計(jì)了一種基于Multilevel CodingTree 模型的“項(xiàng)目代號(hào)+屬性+類別+流水號(hào)”四段位編碼方案［7］。該編碼方案的創(chuàng)新性體現(xiàn)在：

（1）涵蓋高速公路檔案數(shù)字化建設(shè)中所涉及的各類文件、表格、圖紙、影像資料，建立唯一性標(biāo)識(shí)編碼；對(duì)于可能產(chǎn)生重復(fù)的字段，進(jìn)行單獨(dú)處理，確保編碼的有效性。

（2）通 過(guò) 采 用 Multilevel CodingTree 模型結(jié)構(gòu)反映高速公路的各類文檔之間的類別關(guān)系，具有較好的擴(kuò)展性，是一種能夠服務(wù)全國(guó)公路行業(yè)檔案管理的標(biāo)識(shí)編碼。

表1 七種編碼方案特點(diǎn)

3 編碼模型

依據(jù)《公路工程竣（交）工驗(yàn)收辦法實(shí)施細(xì)則》［8］《公路建設(shè)項(xiàng)目文件材料立卷歸檔管理辦法》［9］等相關(guān)文件，我們將高速公路的歸檔材料按照?qǐng)D1 所示的樹型結(jié)構(gòu)進(jìn)行組織。該樹型結(jié)構(gòu)對(duì)應(yīng)了一種由項(xiàng)目代號(hào)、屬性、類別、流水號(hào)構(gòu)成的編碼方案。

項(xiàng)目代號(hào)字段分為三級(jí)，第一級(jí)為路線名稱代號(hào)；第二級(jí)為《中華人民共和國(guó)行政區(qū)劃代碼》［10］中規(guī)定的省、自治區(qū)、直轄市特別行政區(qū)的字母碼；第三級(jí)為建設(shè)項(xiàng)目具體段落代號(hào)，采用路段起訖位置地名的第一個(gè)拼音字母碼組合。

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

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

流水號(hào)字段采用阿拉伯?dāng)?shù)字編碼。流水號(hào)統(tǒng)一定義為3 位，不足3 位，用00 或0 補(bǔ)足。

根據(jù)以上分析可知，高速公路文檔的標(biāo)識(shí)符分多級(jí)進(jìn)行編碼。我們定義Multilevel CodingTree（多級(jí)編碼樹）來(lái)表示這種編碼關(guān)系。

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

（1）Root 是根結(jié)點(diǎn)，代表一條高速公路的代號(hào)。

（2）Nodes 是非根、非葉子結(jié)點(diǎn)的集合，該類結(jié)點(diǎn)代表各類檔案文件的分類。

（3）Leaves 是葉子結(jié)點(diǎn)的集合，該類結(jié)點(diǎn)代表具體的檔案文件。

（4）nodei.father 表 示 結(jié) 點(diǎn)nodei 的父結(jié)點(diǎn)。

（5）nodei.child［j］表 示 結(jié) 點(diǎn)nodei 的第j 個(gè)孩子結(jié)點(diǎn)。

圖1 編碼的樹型結(jié)構(gòu)

表2 歸檔材料的類別及代號(hào)

（6）nodei.value 表示結(jié)點(diǎn)nodei的值。

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

（8）nodei.path 是從根結(jié)點(diǎn)開(kāi)始到結(jié)點(diǎn)nodei 的完整路徑，即該結(jié)點(diǎn)在整個(gè)樹型結(jié)構(gòu)中的編碼，即nodei.path=root.value +…+ nodei.father.value+nodei.value，“+”表示字符串的連接運(yùn)算。

根據(jù)Multilevel CodingTree 定義中的（7）可知，任何結(jié)點(diǎn)沒(méi)有兩個(gè)值相同的結(jié)點(diǎn)，從而確保了編碼的唯一性。 這也是Multilevel CodingTree 區(qū)別于一般多叉樹結(jié)構(gòu)的地方。

基于Multilevel CodingTree 模型，我們?cè)O(shè)計(jì)了“項(xiàng)目代號(hào)+屬性+類別+流水號(hào)”四段位編碼方案。每段位的構(gòu)成規(guī)則：（1）項(xiàng)目代號(hào)段位由路線名稱、代號(hào)字母碼、建設(shè)項(xiàng)目、具體段落代號(hào)構(gòu)成。（2）屬性段位由文檔類型、立卷單位構(gòu)成。（3）類別段位由立卷歸檔材料的類別、材料類別型號(hào)構(gòu)成。（4）流水號(hào)段位統(tǒng)一定義為3 位，不足3 位，用00 或0 補(bǔ)足。編碼示例如圖2 和圖3。

圖2 的編碼含義為：省高速公路網(wǎng)廣西來(lái)賓至馬山高速公路（S52），廣西壯族自治區(qū)（GX），來(lái)賓至馬山段（LM），項(xiàng)目業(yè)主歸檔的綜合文件（100），建設(shè)依據(jù)類第1 件（201），第一頁(yè)（001），第65 案卷（065）。

圖3 的編碼含義為：省高速公路網(wǎng)廣西武宣至平果高速公路（S52），廣西壯族自治區(qū)（GX），來(lái)賓至馬山段（LM）；施工資料第1標(biāo)（401）；質(zhì)量評(píng)定（3），路基單位工程（J01），路基土石方分部工程（A01），土方路基分項(xiàng)工程（A01），工序（0），分項(xiàng)工程質(zhì)量檢驗(yàn)評(píng)定表（W01），第1 頁(yè)（001）；第65 案卷。

設(shè)計(jì)高速公路文檔標(biāo)識(shí)編碼的目的是要實(shí)現(xiàn)歸檔材料的“一卷（頁(yè)、件）一碼”，因此必須證明標(biāo)識(shí)編碼具有唯一性。通過(guò)以上論述，本編碼方案需要進(jìn)行唯一性論證的問(wèn)題有：

（1）在建設(shè)項(xiàng)目具體段落代號(hào)部分，采用路段起訖位置地名的首字拼音字母碼組合可能會(huì)出現(xiàn)重復(fù)。

（2）“項(xiàng)目代號(hào)+屬性+類別+流水號(hào)”四個(gè)段位連在一起的唯一性。

圖2 項(xiàng)目標(biāo)識(shí)符編碼

圖3 項(xiàng)目標(biāo)識(shí)符編碼

4 項(xiàng)目編碼唯一性驗(yàn)證

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

4.1 建設(shè)項(xiàng)目具體段落代號(hào)唯一性的驗(yàn)證

建設(shè)項(xiàng)目具體段落代號(hào)編碼的構(gòu)成分為兩種情況：一是采用路段起訖位置地名的第一個(gè)字母碼組合，如：來(lái)賓至馬山段（LM）；二是當(dāng)起訖地名首字母組合同名時(shí)再取起點(diǎn)或終點(diǎn)地名第二個(gè)字母加入組合，如：來(lái)賓至馬山段（LAM）。我們將通過(guò)概率分析和實(shí)驗(yàn)測(cè)試的方法來(lái)分析這兩種情況下字母碼組合的重復(fù)率。

（1）采用二項(xiàng)分布理論計(jì)算重復(fù)概率

二項(xiàng)分布的定義：重復(fù)n 次獨(dú)立的伯努利試驗(yàn)（是在同樣的條件下重復(fù)地、各次之間相互獨(dú)立地進(jìn)行的一種試驗(yàn)），在每次實(shí)驗(yàn)中只有兩種可能的結(jié)果，而且兩種結(jié)果發(fā)生與否互相對(duì)立且獨(dú)立，與其它各次實(shí)驗(yàn)結(jié)果無(wú)關(guān)，事件發(fā)生與否的概率在每一次獨(dú)立實(shí)驗(yàn)中都保持不變。如果事件發(fā)生的概率是p，則不發(fā)生的概率q=1-p，n 次獨(dú)立重復(fù)試驗(yàn)中發(fā)生k 次的概率是：

參考二項(xiàng)分布的定義，將項(xiàng)目的起訖位置地名字母碼組合的比較當(dāng)成抽取實(shí)驗(yàn)。抽取實(shí)驗(yàn)是每次從若干個(gè)字母中任取兩個(gè)構(gòu)成一個(gè)字母對(duì)，重復(fù)n 次，然后對(duì)抽取結(jié)果進(jìn)行比較并統(tǒng)計(jì)有多少個(gè)字母對(duì)重復(fù)。抽取實(shí)驗(yàn)只有兩種互斥且獨(dú)立的結(jié)果，即重復(fù)與不重復(fù)。每次抽取實(shí)驗(yàn)都相互獨(dú)立，并且對(duì)于同一數(shù)據(jù)集其重復(fù)的概率不會(huì)發(fā)生變化。通過(guò)以上分析可見(jiàn)，進(jìn)行n 次項(xiàng)目的起訖位置地名字母對(duì)的比較，字母對(duì)發(fā)生重復(fù)的k 次是一個(gè)服從二項(xiàng)分布B（n，p）的隨機(jī)變量。

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

由于重復(fù)次數(shù)大于兩次的概率值極小，所以在概率計(jì)算時(shí)僅計(jì)算重復(fù)一次和兩次的情況。下面分別針對(duì)建設(shè)項(xiàng)目具體段落代號(hào)編碼的兩種構(gòu)成情況進(jìn)行討論。

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

其中，p1表示先從m 個(gè)地名中隨機(jī)抽取一個(gè)地名的首字母作為起始地首字母，再?gòu)膍-1 個(gè)地名中隨機(jī)抽取一個(gè)地名的首字母作為終點(diǎn)首字母，由于結(jié)果要么重復(fù)，要么不重復(fù)，因此再相乘。所以，第一種情況下比較n 次發(fā)生重復(fù)的概率如下：

②當(dāng)起訖地名首字母組合同名時(shí)取起點(diǎn)或終點(diǎn)地名第二個(gè)字母碼的情況下，假設(shè)用p2表示每次比較發(fā)生重復(fù)的概率，q2是每次比較不重復(fù)的概率，則有：

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

我國(guó)現(xiàn)行體制下同一條公路通常不會(huì)出現(xiàn)跨省建設(shè)、管養(yǎng)和營(yíng)運(yùn)。故通過(guò)統(tǒng)計(jì)全國(guó)各省、自治區(qū)和直轄市內(nèi)包含的所有地名來(lái)計(jì)算概率即可。根據(jù)《中華人民共和國(guó)行政區(qū)劃代碼》［10］《國(guó)家高速公路網(wǎng)命名和編號(hào)規(guī)則》［11］等資料文件統(tǒng)計(jì)了全國(guó)各省內(nèi)的市縣級(jí)地名數(shù)目，如表3 所示。

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

通過(guò)表4 可知，第一種情況下重復(fù)的概率最大為2.3*10－1%，第二種情況下重復(fù)的概率最大為3.8*10－2%?？梢?jiàn)，從概率論的角度來(lái)看，采用路段起訖位置地名的第一個(gè)字母碼組合或第一和第二個(gè)字母碼組合的方式表示建設(shè)項(xiàng)目具體段落代號(hào)是有可能出現(xiàn)重復(fù)現(xiàn)象的。但是總的來(lái)看，①重復(fù)的概率是較低的，例如在第一種情況下，進(jìn)行1000 次不同地名首字母組合的比較才會(huì)出現(xiàn)2 個(gè)重復(fù)的地名；②采用路段起訖位置地名的第一個(gè)字母碼對(duì)與起點(diǎn)或終點(diǎn)的第二個(gè)字母碼組合的方式的確可以有效地減小重復(fù)概率。

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

根據(jù)表5 可知，第一種情況的重復(fù)率最大為4.8*10－3%；第二種情況的重復(fù)率都為0。所以在實(shí)際的應(yīng)用中，采用路段起訖位置地名的第一個(gè)字母碼與對(duì)應(yīng)起點(diǎn)或終點(diǎn)的第二個(gè)字母碼組合的方式可以消除重復(fù)現(xiàn)象，使唯一性得到了保障。

表3 各省地名數(shù)目統(tǒng)計(jì)

表4 兩種情況的重復(fù)概率（%）

4.2 項(xiàng)目代號(hào)+屬性+類別+流水號(hào)唯一性的證明

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

（1）項(xiàng)目代號(hào)字段分為三級(jí)，第一級(jí)為路線代號(hào)，第二級(jí)為省、自治區(qū)、直轄市、特別行政區(qū)的字母碼，第三級(jí)為建設(shè)項(xiàng)目具體段落代號(hào)。對(duì)于路線代號(hào)，根據(jù)《國(guó)家高速公路網(wǎng)命名和編號(hào)規(guī)則》［11］可知，每條公路的代號(hào)是固定唯一的，因此線路代號(hào)是唯一的；對(duì)于省、自治區(qū)、直轄市、特別行政區(qū)的字母碼，此部分是嚴(yán)格參照《省、自治區(qū)、直轄市特別行政區(qū)代碼表》［12］，因此每個(gè)省的代碼是唯一的；建設(shè)項(xiàng)目段落代號(hào)編碼在4.1 中已經(jīng)證明可以實(shí)現(xiàn)其編碼的唯一性。所以，項(xiàng)目代號(hào)字段的編碼是唯一的。

（2）屬性字段第一級(jí)對(duì)應(yīng)于文獻(xiàn)的文檔類型，分別是綜合文件、決算和審計(jì)文件、監(jiān)理資料、施工資料、科研和新技術(shù)資料、管養(yǎng)資料等六種類型，每種類型賦予一個(gè)不同的編號(hào)（1-6 中的一個(gè)數(shù)字）。因此每種立卷材料的類型代碼是唯一的。第二級(jí)對(duì)應(yīng)立卷單位或施工段落的流水號(hào)，為00～99 兩位數(shù)字。因?yàn)楦鲄⒔▎挝恍蛱?hào)是唯一且固定的，所以第二級(jí)是唯一的。由于屬性字段的第一級(jí)和第二級(jí)是唯一確定的，因此屬性字段的編碼是唯一的。

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

（4）流水號(hào)字段采用阿拉伯?dāng)?shù)字編碼，統(tǒng)一定義為3 位，表示000-999 之間的數(shù)字，每一個(gè)該類型的歸檔文件分配一個(gè)不同的流水號(hào)，保證同類文件流水號(hào)的唯一性。

通過(guò)分別考察分析四個(gè)段位可知，每個(gè)段位的編碼都是唯一的。由于四段位編碼是基于Multilevel CodingTree 模型設(shè)計(jì)的，因此接下來(lái)將根據(jù)Multilevel CodingTree 模型的定義，證明四段位編碼的唯一性。

命題：在Multilevel CodingTree模型中，不存在編碼相同的葉子結(jié)點(diǎn)。

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

表5 實(shí)驗(yàn)的重復(fù)概率（%）

表6 實(shí)際生產(chǎn)效果

①nodei 和nodej 是兄弟結(jié)點(diǎn)

因?yàn)閚odei 和nodej 具有相同的編碼e1e2…em，根據(jù)Multilevel CodingTree 的定義可知，

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

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

所示nodei 和nodej 是兄弟結(jié)點(diǎn)時(shí)，它們的編碼不會(huì)相同。

②nodei 和nodej 是堂兄弟結(jié)點(diǎn)

因?yàn)閚odei 和nodej 必然具有至少一個(gè)不同的祖先結(jié)點(diǎn)，假設(shè)從第k 層（1

又因?yàn)閚odei 和nodej 具有相同的編碼e1e2…em，則有nodeki.value=nodekj.value =ek，這與前面推 出nodeki.value≠nodekj.value 的結(jié)論相矛盾。

所以nodei 和nodej 是堂兄弟結(jié)點(diǎn)時(shí)，它們的編碼不會(huì)相同。

根據(jù)①②可得，在Multilevel CodingTree 模型中，不存在編碼相同的葉子結(jié)點(diǎn)，即保證了編碼的唯一性。

綜上所述，基于Multilevel CodingTree 模型的四段位編碼方案能夠?qū)崿F(xiàn)編碼的唯一性。

4.3 實(shí)際效果的驗(yàn)證

目前，本編碼方案已經(jīng)成功應(yīng)用到“高速公路檔案管理系統(tǒng)”中，保存了廣西來(lái)賓至馬山、馬山至平果共200km 的高速公路工程數(shù)字化檔案，其六大類材料總共100270 件，共計(jì)184.6G 數(shù)據(jù)，產(chǎn)生編碼100270 條。統(tǒng)計(jì)結(jié)果如表6。

從實(shí)際產(chǎn)生的統(tǒng)計(jì)結(jié)果可以看出，本編碼具有較好的唯一性，能夠滿足實(shí)際工作。

通過(guò)以上的概率分析、實(shí)驗(yàn)測(cè)試、命題證明和實(shí)際生產(chǎn)測(cè)試等手段，驗(yàn)證了編碼的唯一性。該編目具有較好的推廣性，當(dāng)應(yīng)用到其他省市、自治區(qū)、直轄市中，將項(xiàng)目代號(hào)中第一級(jí)路線名稱代號(hào)、第二級(jí)字母碼、第三級(jí)建設(shè)項(xiàng)目具體段落代號(hào)進(jìn)行替換即可。當(dāng)建設(shè)項(xiàng)目具體段落代號(hào)發(fā)生重復(fù)時(shí)，采用路段起訖位置地名的第一個(gè)字母碼對(duì)應(yīng)起點(diǎn)或終點(diǎn)的第二個(gè)字母碼組合的方式進(jìn)行處理，保證編碼容錯(cuò)性?？傊?，該編碼能夠創(chuàng)造良好的社會(huì)價(jià)值，為以后同類編碼和其他編碼起到指導(dǎo)和借鑒作用。

5 結(jié)論

通過(guò)分析目前國(guó)內(nèi)外現(xiàn)有的編碼方案，可以發(fā)現(xiàn)這些編碼方案都不能完全適用于公路電子檔案編碼。為此，我們提出了基于Multilevel CodingTree 模型的“項(xiàng)目代號(hào)+屬性+類別+流水號(hào)”的四段位編碼方案。根據(jù)該編碼的結(jié)構(gòu)，設(shè)計(jì)證明方案，可以驗(yàn)證編碼的唯一性。目前，該編碼方案已經(jīng)投入到“高速公路檔案管理系統(tǒng)”中使用，實(shí)現(xiàn)了文件的“一件一碼”，取得了較好的應(yīng)用效果。本方案具有較好的推廣性，為以后同類編碼和其他類型編碼起到指導(dǎo)和借鑒作用。

［1］王勝明，等.不等長(zhǎng)編碼系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)［J］.華北電力大學(xué)學(xué)報(bào)，2002（1）：29.

［2］唐敏.南寧市城市道路數(shù)據(jù)庫(kù)編碼設(shè)計(jì)研究［J］.城市建設(shè)理論研究，2013：18.

［3］范策.一種無(wú)前綴編碼（UPC）［J］.計(jì)算機(jī)學(xué)報(bào)，2002（2）：25。

［4］盧志毅.特種設(shè)備全國(guó)唯一性識(shí)別代碼研究［J］.中國(guó)特種設(shè)備安全，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，F(xiàn)anSen Zeng.Switching Serial-Number Coding Scheme and Its Application in FFS Scheduling Problem with Inter-Stage Constraints.Proc.Natural Computation，2007，375-379.

［7］羅竟，等.公路數(shù)字化檔案唯一性標(biāo)識(shí)編碼詞典［P］.廣西：南寧，2014.

［8］交公路發(fā)［2010］65號(hào)，公路工程竣（交）工驗(yàn)收辦法實(shí)施細(xì)則［S］.

［9］交辦發(fā)［2010］382號(hào)，公路建設(shè)項(xiàng)目文件材料立卷歸檔管理辦法［S］.

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

［11］JTG A03-2007，國(guó)家高速公路網(wǎng)命名和編號(hào)規(guī)則［S］.

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