基于编辑距离的大规模流程工厂模型局部检索算法

温 蕊，唐卫清，2，苏智勇

（1.南京理工大学 计算机科学与工程学院，江苏 南京 210094；2.中国科学院 计算技术研究所，北京 100190；3.南京理工大学 自动化学院，江苏 南京 210094）

0 引言

随着现代社会对流程工厂建设投资的增加以及应用范围的扩大，流程工厂模型的数量和复杂性也不断增大，其中模型的复杂性主要表现在巨大的构件数量和复杂的拓扑结构上。在实际工程应用中，一般的流程工厂模型动辄包含数以万计的构件，并且工厂设计要求准确表达基本构件在三维空间中的位置和拓扑连接关系，否则将给模型的后续处理（如图纸的生成）造成不必要的困难［1］。当前流程工厂模型的构建方式是，设计人员在设计平台所展示的三维空间中，根据实际工程需要，从工程数据库中选择并逐一添加构件。这种设计模式过分依赖于设计人员的工作经验，使模型的复杂性增加，不但加大了设计难度，而且导致建模过程中的疏忽与错误愈发难以发现，直接影响最终模型的质量。

由于流程工厂模型中包含大量的组合构件，在相同的工程应用背景下，许多表达固定功能的组合构件会有较高的使用频率，此时流程工厂模型的局部检索在以下三方面具有重要意义：

（1）重用 在流程工厂的初步设计阶段，设计人员会根据用户需求，逐步求精地制订出详细的工艺流程，此时流程工厂模型的拓扑结构已知。若在构建新模型的过程中，设计人员根据已制定好的模型结构，重用已校验模型中可利用的组合构件，则不但可以减少设计人员的重复工作、缩短产品开发周期，而且在一定程度上可以避免因设计人员经验不足造成不必要的错误，保证模型的质量。

（2）校验 由于实际工程需要，原有模型中的组合构件需要进行改动，在大规模的流程工厂模型中手动查找组合构件必定耗时耗力。若系统可以根据所需修改的组合构件，在目标模型中自动定位到与之匹配的局部模型，再由设计人员对其进行校验或修改，则不仅可以提高设计人员的工作效率，而且有助于保证设计的一致性。

（3）建筑信息模型 建筑信息模型［2］（Building Information Modeling，BIM）是集成了建筑工程项目中各种相关信息的工程数据模型。当前，随着BIM 在建筑工程领域的应用逐渐增多，其在流程工厂领域也引起了广泛的关注与推广。BIM 技术的核心是通过在计算机中建立虚拟的工程三维模型，利用数字化技术，为该模型提供完整的、与实际情况一致的工程信息库［3］。流程工厂模型中包含大量具有固定功能的组合构件，通过模型的局部检索技术可以得到这些组合构件，再将它们存储到工程信息库中。此时，由于BIM 汇总了各项目的所有工程信息，不仅可以消除项目中的信息孤岛，还可以将得到的信息结合工程模型进行整理和存储，以备产品全生命周期中的各方随时使用，这不仅有益于设计人员间的协同合作，还有利于提高设计效率。因此，流程工厂模型的局部检索研究对于BIM 应用的研究与发展具有推动作用。

目前，国内外已有针对CAD 模型的局部检索研究［4-8］，主要集中于模型间几何信息的相似性比较，如模型间曲线、曲面等几何特征的提取与匹配计算。但尚无关于流程工厂模型局部检索的相关文献。由于流程工厂模型的构件数量巨大，基于几何信息的检索方法在提取模型的几何特征及计算几何相似性等方面的时间复杂度较高。另一方面，流程工厂设计的重点在于拓扑结构的正确表达，对具体构件的几何形状没有过多要求［9］。因此，以几何特征为基础的局部检索算法并不适用于流程工厂模型，相比之下，以拓扑结构为基础的模型检索更为合适。

基于图的模型相似性重点关注构成三维模型的组成成分是如何连接在一起的［10］，因此将图相似性与流程工厂模型相结合，将有利于流程工厂模型的局部检索研究。本文以图相似性的相关思想为基础，提出一种基于编辑距离的流程工厂模型局部检索算法。算法首先对待检索模型和历史流程工厂模型进行预处理，将它们分别转化为属性图结构；然后设定编辑距离阈值；最后计算待检索模型与历史流程工厂模型对应的属性图之间的最小编辑距离，并结合编辑距离阈值衡量历史流程工厂模型中是否包含与待检索模型相似的局部模型。

1 流程工厂模型

流程工厂是用来制造化学或物理制成品的反应容器、管线及其支撑的集合。流程工厂模型是实际工厂的抽象表示，主要包括工厂中所有元件和构件的工程信息、几何信息、拓扑连接信息。模型中的基本构件主要包括设备、管子、管件、阀门和仪表等，这些基本构件由图1所示的14 种基本体元组成［11］，依次为圆柱、斜截圆柱、多棱柱、偏心圆台、同心圆台、天圆地方、矩形断面台、长方体、圆形断面圆环、矩形断面圆环、球、直角楔形体、马鞍形和椭球封头。图2展示了两个不同工程应用背景下的流程工厂模型实例，模型中元件与元件之间拓扑连接关系的数量统计结果如表1 所示。可见流程工厂模型所包含的元件数量巨大，整体拓扑结构复杂。

表1 模型数据统计

工厂CAD 模型中的基本构件通常都已经标准化、系列化，除设备、管子等基本构件外，还有针对不同工程应用背景的专业构件类型，如电器、土建等。因此，很多工程CAD 软件系统都配有专用的工程数据库管理系统，不同的工程应用背景使用其专业的工程数据库。

流程工厂设计的重点在于设计对象的结构和拓扑描述，因此要求三维模型能够准确表达工厂的拓扑结构。基于对偶点和智能线的表示方法是目前应用较广泛的一种流程工厂模型拓扑结构表示方法。在该表示方法中，对偶点描述管件之间的拓扑连接，智能线描述通过将管件、管子抽象为三维线段或圆弧，建立管件、管子之间的关系约束［1］。一个简单的对偶点与智能线的示例如图3所示。

不同的工厂CAD 系统对于流程工厂拓扑结构的表示方法不同，但其本质都是相同的，即流程工厂模型是结构化的数据模型，可以表示为复杂的空间图结构。

2 基于编辑距离的大规模流程工厂模型局部检索算法

由于拓扑结构是流程工厂模型的核心，流程工厂设计人员在模型检索时，更关注模型拓扑结构间的相似性。基于图的模型相似性度量主要关注模型间拓扑结构的相似程度［10］，因此图相似性的相关思想有助于解决流程工厂模型的局部检索问题。图相似性的度量方法主要有最小编辑距离法［12-13］和最大公共子图法［14］。尽管计算最小编辑距离和最大公共子图均是NP 完全问题，但在已知对应节点的情况下，计算最小编辑距离的复杂度可以简化为O（节点数+边数）［15］。而且与最大公共子图法相比，最小编辑距离法具有应用灵活、易操作等优点。因此本文尝试采用最小编辑距离的相关思想解决流程工厂模型的局部检索问题。

2.1 最小编辑距离

简单的无向图G可以表示为G=（V，ΣV），其中：V是节点的集合，ΣV是节点间连接关系的集合。

（1）最小编辑距离 图G1和G2的最小编辑距离是将G1转化为从而使的最少操作步骤［12］，记作ed（G1，G2）。

图的编辑操作主要有6种［13］：①插入一个带标识的独立节点；②删除一个独立节点；③置换一个节点的标识；④两个节点之间插入一条边；⑤删除一条边；⑥置换一条边的标识。因此，将图G1转化为G2实际为执行一系列编辑操作的过程，如。该过程可以有多种操作顺序和操作数量，其中最小的操作数量为G1和G2的最小编辑距离。

（2）图的相似性查询 假设需要查询的图为Gq，图的集合D=｛G1，G2，…，G｜D｜｝，编辑距离阈值为τ，则图的相似性查询即为查找D中所有的图Gi，使Gi满足ed（Gq，Gi）≤τ［12］。

图4是基于编辑距离的图相似性计算实例。经过多次计算和筛选，可以得到Gq与图G1、G2的最小编辑距离分别为ed（Gq，G1）=1，ed（Gq，G2）=5，其中图G1和G2中需要执行编辑操作的节点或边已用虚线标注。假设编辑距离阈值τ=3，根据图的相似性查询定义，由于Gq与G1的最小编辑距离小于τ而Gq与G2的最小编辑距离大于τ，认为只有G1与Gq相似。

2.2 算法详情

工程CAD 系统中不同的工程应用背景使用其专业的工程数据库，且数据库中的类型名称字段是设计人员在建模过程中用于判别所选构件是否为目标类型构件的重要依据，因此，算法将构件的类型名称作为属性图中节点的主要标识。在流程工厂模型转化为属性图的过程中，以模型中的构件作为属性图的节点，以构件的类型作为节点的属性标识，构件之间的拓扑连接关系为属性图的边，即流程工厂模型M可以表示为属性图GM=｛C，ΣC｝，其中：C为模型中构件的集合，ΣC为各构件的拓扑连接关系集合。此时流程工厂模型的局部检索问题转化为属性图的子图查询问题，通过比较两模型对应属性图中节点的属性标识与节点间连接关系的相似性，可以判断历史模型中是否包含与待检索模型相似的局部模型。

结合2.1节所述最小编辑距离的相关思想，本文所提出的局部检索算法流程如图5所示。其中，设置编辑距离阈值为τ（τ≥0），初始化编辑距离ed（Gp，Gq）=0。根据不同的检索应用，待检索模型可能会以构件间的拓扑关系或三维模型的形式表述，本文将它们统称为待检索模型。算法具体步骤如下：

步骤1 对待检索模型Mq和历史流程工厂模型Mp进行预处理，分别转化为属性图Gq和Gp。

步骤2 遍历Gq中未被遍历的节点C，在Gp中随机地查找与C类型标识相同的节点C′，并执行步骤3；若Gq的遍历完成，则执行步骤5。

步骤3 遍历节点C的邻居节点中还未被遍历的节点N，查看C′中是否存在相同类型标识的邻居节点N′。若存在，则继续遍历C的邻居节点中还未被遍历的节点，执行步骤3；否则编辑距离ed（Gp，Gq）+1，执行步骤4；若C的邻居节点遍历完成，则执行步骤2。

步骤4 若ed（Gp，Gq）≤τ，表示当前编辑距离在设置的可接受范围内，则继续遍历C的邻居节点，执行步骤3；若ed（Gp，Gq）＞τ，表示当前编辑距离超过了可接受范围，则停止C与C′的邻居比较，并将Gq和Gp中已遍历的节点全部标识为未遍历，执行步骤2。

步骤5 此时Gq的遍历完成，且当前的编辑距离满足ed（Gp，Gq）≤τ，表示Gp中存在与Gq相似的子图，即Mp中存在与Mq相似的局部模型，输出该局部模型。

3 实验

实验以PDSOFT®3DPiping 与Visual Studio 2008为平台，历史模型集为不同工程应用背景的流程工厂模型集合，包含的元件总数为126 325，待检索模型为随机选择的组合构件模型，平均包含的元件数量为60。

3.1 预处理

如2.2节中的算法所示，将流程工厂模型转化为属性图时，需要对模型进行预处理。模型的预处理和各构件的表示遵循如下原则：①所有模型中的构件类型均有唯一的标识；②模型中各构件均有唯一的标识；③各构件均对应唯一的类型标识；④各构件最多有一个拓扑连接关系构件集合，若构件无关联关系、独立存在，则无关联关系构件集合。

将历史模型集中的所有流程工厂模型和待检索模型进行如上所述的预处理，其中待检索模型图6a、图6b与历史流程工厂模型图2a、图2b的预处理结果（即对应的属性图信息）如表2所示。

表2 模型预处理结果统计

3.2 实验结果分析

由于本文所提算法的检索效率会被算法中所产生的随机数影响，综合整理待检索模型在历史模型集中不同阈值下的100次检索结果。表3统计了历史模型集的规模以及历史模型集中相关局部模型的个数，并综合所有检索结果计算了不同阈值下检索结果的查全率和查准率。表中：模型的规模为所包含元件的数量；查全率=（检索结果的个数／历史模型集中相关局部模型的个数）×100%，反映了检索出相关局部模型的成功率；查准率=（检索结果中相关局部模型的相似度之和／检索结果的个数）×100%，反映了检索结果的准确程度，即与待检索模型之间的平均相似程度。表4 和表5 展示了具有代表性的若干检索结果的检索详情。表中，平均遍历次数为得到一个检索结果时待检索模型被遍历的平均次数，相似度为检索结果与待检索模型之间的相似程度。

表3 检索结果的查全率与查准率

表4 待检索模型图6a在历史模型集中的局部结构相似性检索结果

表5 待检索模型图6b在历史模型集中的局部结构相似性检索结果

从表3的实验结果可以得出如下结论：

（1）待检索模型为图6a时，检索结果的查全率和查准率均为100%，表明检索出了所有相关的局部模型，且检索结果与待检索模型在拓扑结构上完全相似。

（2）针对待检索模型图6b的检索结果，当阈值为0时，检索结果的查全率较低；当阈值为4时，查全率提高至100%。表明阈值增大时，检索结果的范围有所扩大，算法检索到了更多的相关模型。

（3）从模型图6b的实验结果可以看出，当阈值增大至4时，检索结果的查准率有所降低。原因在于阈值的增大使局部检索的精度下降，导致检索结果与待检索模型的相似度降低。

从表4和表5的实验结果可以得出如下结论：

（1）从表4 可以看出，在相同的编辑距离阈值下，本文所提出的算法可以检索出不同的局部模型，且这些检索结果是阈值范围内与待检索模型拓扑结构相似的局部模型。

（2）按2.2节算法所述，当阈值为0时，要求检索结果与待检索模型的拓扑结构完全相同。如表4的实验结果所示，阈值为0时，待检索模型与检索结果间拓扑结构的相似性为1.0，符合当前的检索要求。

（3）从表5可以看出，对于相同的检索结果，编辑距离阈值不同时，其执行效率会有所不同。平均遍历次数会随着阈值的增大而减少，检索时间缩短。

（4）对比表4和表5的实验结果可以看出，本文算法的执行效率与待检索模型的规模成反比。从表2可知，待检索模型图6b的规模大于模型图6a，即使表5中的编辑距离阈值大于表3，模型图6b的平均遍历次数仍旧大于模型图6a。原因在于待检索模型的规模较大时，判断节点和边是否相似的次数随之增加，模型间的最小编辑距离超过阈值的可能性也会增大，因此检索的效率有所降低。

3.3 算法分析

3.3.1 性能分析

算法将构件的类型作为属性图节点的主要标识，可以降低三维模型局部检索的复杂度。相比模型的几何外形，流程工厂设计人员更加关注模型的拓扑结构，而数据库中的类型名称字段是设计人员在建模过程中用于判别所选构件是否为目标类型构件的重要依据。因此，在流程工厂模型转化为属性图的过程中，以构件类型代替构件的几何信息，使得在后续的模型相似性度量中略去了较为繁琐的几何特征提取及相似性比较，不但简化了模型局部检索的复杂度，而且同样可以得到与待检索模型相似的检索结果。

本文所提出的流程工厂模型局部检索算法是一种启发式算法。通过设定编辑距离阈值，算法可以在有限时间内得到用户可接受范围内的匹配模型。这种由用户设定的模糊查询无疑可以提高局部检索的计算效率，使得在对包含数以万计以上构件的流程工厂模型进行检索时，算法依旧有较好的检索性能。

若待检索模型的构件数量为n，拓扑连接关系数量为e，编辑距离阈值为τ，则该算法的最小计算次数为（n+e-τ），此时仅遍历一次待检索模型就查找到历史模型中与待检索模型相似的局部模型。若待检索模型中首个被遍历构件C1所对应的类型T（C1）在历史模型中出现的频率为｜T（C1）｜，则本文所提算法的时间复杂度为O（｜T（C1）｜·（n+e））。

在流程工厂模型局部检索时，｜T（C1）｜的大小会影响局部模型的检索效率。由于历史模型中存在许多类型相同的构件，若在局部检索的过程中，随机选择的构件恰好与待检索模型中的目标构件相匹配，则可以缩短检索时间；否则，多余的遍历会导致检索时间延长。因此，根据历史模型中各构件类型的数量，适当地调整待检索模型中构件的遍历顺序，优先遍历历史模型集中类型较少的构件，在一定程度上有助于提高算法的检索效率。

3.3.2 阈值分析

算法中编辑距离阈值的大小会影响局部模型的重用和校验。编辑距离阈值可以影响模型局部检索的精确度，即检索结果与待检索模型的相似程度。若阈值偏大，则虽然降低了模型相似性的评定标准，提高了算法的执行效率，但可能导致检索结果中存在设计人员不需要的局部模型。若阈值偏小，则虽然提高了模型相似性的评定标准，但可能导致检索结果遗漏。检索结果的缺失或多余在一定程度上会影响模型的重用或校验效率，因此阈值的大小需要由设计人员综合考虑待检索模型的特点以及检索的需求后合理设定。根据最小编辑距离的定义，设计人员可以根据检索需求，分析检索时待检索模型中可以忽略的构件或构件间拓扑连接关系的数量，以此预估当前检索应用下的编辑距离阈值。

4 结束语

本文分析了流程工厂模型的局部检索对于提高流程工厂设计效率、保证模型质量的重要作用，并进行了针对流程工厂模型的局部检索研究。由于拓扑结构是流程工厂模型的核心，而基于图的模型相似性重点研究模型拓扑结构之间的相似程度，结合图相似性的相关思想，本文提出一种基于编辑距离的流程工厂模型局部检索算法。该算法首先将流程工厂模型转化为属性图结构：将构件作为属性图的节点，将构件的类型作为节点标识，将构件之间的连接关系作为边；然后设置了编辑距离阈值，并计算了待检索模型与历史模型对应的属性图之间的最小编辑距离：若编辑距离小于或等于编辑距离阈值，则认为历史模型包含与待检索模型结构相似的局部模型，并返回历史模型中的该局部模型。实验结果表明，本文所提算法可以在历史模型集中检索到符合检索要求的局部模型，且根据不同的检索应用需求，通过设置不同的编辑距离阈值，能够得到精细度不同的局部模型。这些检索结果有助于新模型构建过程中组合构件模型的重用以及模型校验过程中局部模型的快速定位，对提高流程工厂设计效率、保证模型质量、缩短产品开发周期具有重要意义。

本文提出算法的思想同样可以应用于其他工程CAD 模型的局部检索。在未来的研究中，将努力改进现有的局部检索算法，进一步提高检索效率，使待检索模型的规模更大时算法能够保持较好的检索性能。

［1］DAI Xiaofeng.The research on AEC CAD modeling technology based on enhanced graph and multi-state model［D］.Beijing：Institute of Computing Technology，Chinese Academy of Sciences，2000（in Chinese）.［戴肖锋.基于扩展图与多态模型的工程CAD建模技术研究［D］.北京：中国科学院计算技术研究所，2000.］

［2］AZHAR S.Building information modeling（BIM）：trends，benefits，risks，and challenges for the AEC industry［J］.Leadership and Management in Engineering，2011，11（3）：241-252.

［3］GUO Jun.Application types of BIM in a building's lifecycle［J］.Building Structure，2012，42（3）：10003-10006（in Chinese）.［过 俊.BIM 在国内建筑全生命周期的典型应用［J］.建筑结构，2012，42（3）：10003-10006.］

［4］ZHANG Kaixing，ZHANG Shusheng，LI Liang.Partial matching algorithm of 3D CAD model［J］.Computer Integrated Manufacturing Systems，2011，17（9）：1880-1886（in Chinese）.［张开兴，张树生，李 亮.一种三维CAD 模型局部匹配算法［J］.计算机集成制造系统，2011，17（9）：1880-1886.］

［5］ZHANG Kaixing，ZHANG Shusheng，LI Liang.A method of 3DCAD model retrieval based on ant colony algorithm［J］.Journal of Computer-Aided Design &Computer Graphics，2011，23（4）：633-639（in Chinese）.［张开兴，张树生，李 亮.基于蚁群算法的三维CAD模型检索［J］.计算机辅助设计与图形学学报，2011，23（4）：633-639.］

［6］SUN Changle，NING Dayong，XIONG Wei，et al.Featurebased CAD model retrieval technique in engineering field［J］.Computer Integrated Manufacturing Systems，2014，20（4）：747-754（in Chinese）.［孙长乐，宁大勇，熊 伟，等.基于特征的工程领域CAD 模型检索技术［J］.计算机集成制造系统，2014，20（4）：747-754.］

［7］TAO S，HUANG Z，MA L，et al.Partial retrieval of CAD models based on local surface region decomposition［J］.Computer-Aided Design，2013，45（11）：1239-1252.

［8］YOU C F，TSAI Y L.3Dsolid model retrieval for engineering reuse based on local feature correspondence［J］.The International Journal of Advanced Manufacturing Technology，2010，46（5／6／7／8）：649-661.

［9］HUANG Xiaojian.Research on fast rendering techniques in engineering CAD［D］.Beijing：Institute of Computing Technology，Chinese Academy of Sciences，2002（in Chinese）.［黄晓剑.工程CAD中的快速绘制技术研究［D］.北京：中国科学院计算技术研究所，2002.］

［10］TANGELDER J W H，VELTKAMP R C.A survey of content based 3Dshape retrieval methods［J］.Multimedia Tools and Applications，2008，39（3）：441-471.

［11］ZHOU Jian，TANG Weiqing，ZHU Yaoqin，et al.Multiresolution rendering approach of large-scale process plant models based on programmable graphics pipeline［J］.Journal of Image and Graphics，2012，17（3）：426-434（in Chinese）.［周 剑，唐卫清，朱耀琴，等.基于可编程图形管线的大规模流程工厂模型多分辨率绘制方法［J］.中国图象图形学报，2012，17（3）：426-434.］

［12］ZHENG W，ZOU L，LIAN X，et al.Graph similarity search with edit distance constraint in large graph databases［C］／／Proceedings of the 22nd ACM International Conference on Information &Knowledge Management.New York，N.Y.，USA：ACM，2013：1595-1600.

［13］ZENG Z，TUNG A K H，WANG J，et al.Comparing stars：on approximating graph edit distance［J］.The Very Large Data Base Journal，2009，2（1）：25-36.

［14］RAYMOND J W，GARDINER E J，WILLETT P.Rascal：calculation of graph similarity using maximum common edge subgraphs［J］.The Computer Journal，2002，45（6）：631-644.

［15］KOUTRA D.Large graph mining and sense-making［D］.Cambridge，Mass.，USA：Microsoft Research，2014.