基于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］.