基于树编辑距离的工作流距离度量方法

在工作流的发现和聚类等应用中,需要对两个工作流模型的距离进行度量。因此,提出一种计算两个不同结构化工作流的距离定量度量方法。首先介绍了结构化工作流,并将每一个结构化工作流转换为流程结构树;然后基于两个结构树之间的树编辑距离来计算工作流之间的距离及相应相似度。该距离度量方法满足距离度量的3个属性,即同实体不可区分性、对称性和三角不等式性质。这些属性使得该距离度量方法可以在工作流模型管理活动中作为定量分析工具。实验结果表明,基于树编辑距离的工作流度量方法是可行的。同时,与基于邻接矩阵的距离度量方法相比,该方法考虑了不同结构之间的语义距离,有效验证了此方法的合理性。

基于约束树编辑距离与导航树的信息采集

介绍基于网站和网页结构的信息采集算法,提出一种基于约束树编辑距离的导航树算法。该算法通过提取网页的HTML的重要标记生成网页结构的标签树,对网页进行结构分析,通过约束树编辑距离算法判断爬行到的网页与主题的相关性,并根据网站基于URL的拓扑结构,提出基于导航树的信息采集约束信息采集器的爬行路径,提高了目标页面采集的效率和准确率。

满足度量性质的归一化树编辑距离

利用树大小和树编辑距离的简单函数提出了一种归一化树编辑距离,在权重函数具有度量性质且所有插入和删除操作的权重都相等时,不仅能完全满足三角不等式,而且是一种取值在[0,1]的度量.这种距离可以由树编辑距离直接计算得到,其计算时间复杂度与树编辑距离相同.通过手写数字识别实验说明,AESA算法利用该距离获得的识别率为91.6%,比其他2种归一化树编辑距离分别高0.2%和0.8%.

Web信息抽取中基于结点权重的树编辑距离匹配法研究

提出一种改进的树匹配算法,通过考量HTML特性,对树编辑距离方法进行改进,根据不同HTML树结点在浏览器中所显示的相关数据的不同权重赋以不同的权重值。算法由HTML数据对象构造具有结点权重的HTML树,模式识别通过取得两棵构造树的最大映射值达成。通过基于商用网站的实验对算法有效性进行了证实。

基于树编辑距离的聚类算法数据记录抽取

本文研究了如何从列表页面中抽取数据记录.系统分为两个阶段:第一步采用三种启发式方法相结合的方法,识别主数据区域的根节点;第二步将数据记录分离,提出了一种新的基于树编辑距离的聚类算法,来减少候选分割方案的数量,然后根据公式计算相似度,找出最佳分割方案.本文通过对大量不同领域的网页进行测试,结果表明本文方法具有较高的准确率.

利用树编辑距离的等高线拓扑相似性度量方法

已有的拓扑相似性度量方法主要通过目标之间拓扑关系统计均值的差值,衡量目标之间的拓扑相似程度,在拓扑变化复杂区域由于拓扑关系的增减互补易产生度量误差。为此,提出一种顾及拓扑结构差异的等高线群拓扑相似性度量方法;引入Zhang-shasha算法将等高线群之间的拓扑变化转化为等高线树之间的转换编辑操作;构建基于树结构的拓扑差异表达;并利用动态规划方法求解等高线树之间的转换编辑距离;进而量化度量等高线群间的拓扑结构相似度。模拟数据实验和真实数据实验表明,该方法顾及了拓扑结构差异,能够有效度量多源多尺度等高线数据之间的拓扑相似程度,减少度量误差。

树编辑距离在Web信息抽取中的应用与实现

引入编辑距离的概念,探讨如何构造标签树,并利用标签树匹配算法来量化网页结构相似度。该算法被应用于Web信息抽取,通过URL相似度算法进行样本网页的粗聚类,进一步采用树的相似度匹配算法实现细聚类,从而获取模板网页。在模板网页的基础上,再次引入结构相似度算法并结合基于模板网页的抽取规则实现网页的自动化抽取。实验证明,该算法的引入能够有效提高包装器的抽取精度和半自动化能力。

基于编辑距离的Web数据挖掘

Div+CSS流行于Web页面的布局,在这种布局下,网页中很多数据记录以重复结构的形式聚集在一个层级。为了更好地从网页中挖掘数据,提出了一种新的Web数据挖掘算法,把树编辑距离转化为字符串编辑距离的计算,改进字符串编辑距离算法,利用字符串编辑距离评价树的相似度,进而找到网页中的重复模式,提取数据。通过针对不同重复模式特征的网页的实验说明,基于编辑距离的Web数据挖掘算法不仅能提取具有根节点及上面几层相同的网页的数据,对具有底层节点相同的网页也是有效的。

基于编辑距离相似度的文本校验技术研究与应用

树形结构的文本配置在分布式的测控数据处理软件中使用广泛,它的正确性对数据处理而言至关重要。为了实现树形结构的文本配置自动检查和纠错,通过引入LD(Levenshtein Distance)编辑距离算法,把字符串的编辑操作推广到多叉树之间。在此基础上定义了多叉树之间的编辑距离,建立了衡量多叉树之间相似度的方法,设计了基于模糊匹配的文本配置自动校对流程,解决了精确匹配时由字符的多义性导致的查全率失真和误判的问题。根据实验结果,查全率和查准率分别达到了87.5%和100%,有效提高了基于树形结构的文本配置自动校验时的可靠性。

基于局部标签树匹配的改进网页聚类算法

Web信息抽取中需要对目标网站的网页进行聚类分析,以检测并生成信息抽取所需的模板。传统的基于DOM树编辑距离的网页聚类算法不适合文档对象模型(DOM)树结构复杂的动态模板网页,提出了一种基于局部标签树匹配的改进网页聚类算法,利用标签树中模板节点和非模板节点的层次差异性,根据节点对布局影响的大小赋予节点不同的匹配权值,使用局部树匹配完成对网页结构相似性的有效计算。实验结果表明,改进的算法较传统的基于DOM树编辑距离的网页聚类算法,在对采用模板生成的动态网页进行聚类分析时具有更高的准确率,且时间复杂度低。

基于树模型算法的动态网页信息抽取研究和实现

动态网页是Internet上重要的网页类型,它们通常是由网站的后台数据库通过某种通用的模板构成。提出了一种新的基于树模型算法的动态网页信息抽取方法。它在已有算法和系统的基础上,进行了多方面的扩充。实验表明,这种基于树模型的抽取方法能够准确地定位和抽取动态网页信息。

有向标记根树之间的语义编辑距离

有向标记根树之间的编辑距离(TED)被广泛应用在文档的结构化相似度计算上.文中提出有向标记根树之间的语义编辑距离(TSED)的概念,并给出计算公式.组合TED和TSED形成距离测度,并应用在XML文档的结构聚类上.实验表明该距离模型在结构化聚类的准确率和召回率上明显优于单纯利用TED算法的聚类结果.该算法在时间复杂性上也等同于利用动态规划计算TED的最好算法.

XML数据的查询技术

XML规范已成为当前网络应用(包括数字图书馆、Web服务以及电子商务)中事实上的数据表达、交换的标准.针对XML数据的查询在当前XML数据管理研究中占有重要的地位,也是当前XML数据处理研究领域的热点方向,相关的研究文献有很多.根据查询模式描述的不同,将当前XML查询技术归入两大类:XML Query方式和XML IR方式.后者又进而可分以为3个子类:XML IR/keyword方式、XML IR/fragment和XMLIR/query方式,并从中挑选出3个研究者关注的问题进行了简述,它们是:Twig查询模式的处理、SLCA(smallest lowest common ancestor)节点的获取以及对所获取的XML片段相似性的度量.以方便普通用户使用为准则探讨了相关XML查询技术的优、缺点,将如下4个问题作为需要进一步关注的研究内容:结构化关键字查询及相应的结构相似性度量方法,如何消除XML Query查询处理模式(包含XML IR/query)和XML IR/keyword查询处理模式间数据冗余的问题,XML Query查询方式的理论探讨及其实现以及针对特定应用的XML数据的有效管理.

适用于配电网规划的可靠性指标改进显式估算算法

针对计及可靠性的配电网规划问题,提出一种可靠性指标的改进显式估算算法。以树编辑距离作为馈线拓扑结构间的差异性计量,对待评估区域内的配电馈线按拓扑结构层次聚类。将聚类中心作为区域典型拓扑,以它们取代传统估算方法中的简单辐射状结构,建立可靠性估算模型。模型基于各类拓扑结构的故障隔离能力与负荷转供能力,通过回归分析推导可靠性指标显式计算公式,并分析了不同停电方式与多种可靠性提升设备产生的影响。一个实际城市配电网的算例分析表明,算法在面对多样化网架结构时亦能保证较高的计算精度,且有助于提升配电网规划模型的求解质量与求解稳定性。

基于结构相似匹配的SQL程序自动评估模型研究

针对SQL语言编程能力评估的多因素影响、界限模糊特性造成的难度和偏差问题,本文提出了基于结构相似度匹配的评估模型(SQL-APAM)。结合静态评估与动态评估方法,给出了模型的整体框架;模型对提交的SQL语句进行规范化、分词处理后,将其转换成等价的单词序列对,进而构建对应的结构树S-tree;使用于代价模型、子结构贡献因子两方面上有所改进的树编辑距离算法计算与目标树的相似性值;最后利用正态分布思想将相似度值映射到成绩区间,并通过相似度阈值来调整影响因素所带来的偏差,给出SQL程序的定量评判结果。最后对模型作了基于数据的实验分析与验证,训练数据集进行参数调整,对模型进行优化。

基于ANTLR的SQL语法分析策略与实现

以SQL预编译的构建为目的,提出一种基于ANTLR(Another Tool for Language Recognition)的SQL预编译设计模型。模型从编译原理的角度出发,采用扩展的巴科斯范式EBNF(Extended Backus-Naur Form)定义SQL文法规则。在定义文法规则时,兼顾了SQL语言的特点和ANTLR识别器的工作原理,提出两层分析、嵌入Java语言的设计策略;在语法解析时,通过借鉴树编辑距离的相关研究成果,将目标代码和用户代码进行映射,实现了语法树异同点的检测。

一种利用动态控制流路径分析的隐藏恶意代码异常检测方法

提出了一种基于动态控制流路径分析的隐藏恶意代码检测方法.该方法首先有针对性地选取与恶意代码相关的敏感路径并动态记录其执行过程的控制流路径,然后采用基于调用层次树匹配的异常检测算法分析所获得的数据,从而检查出系统中隐藏型恶意代码.实验结果表明,该方法能有效检测出隐藏恶意代码,具有高检出率和低误报率的特点,适用于计算机操作系统内的隐藏型恶意代码的检测.

基于AST的存储过程自动评估模型研究

针对数据库机器学习过程中的存储过程评估问题,提出基于AST的存储过程自动评估模型。从静态评估的角度,给出了模型的整体框架;以构建存储过程的抽象语法树AST(Abstract Syntax Tree)为分析基础,通过改进的树编辑距离映射的代价模型,计算用户存储过程代码和目标程序之间的相似度;最后,利用学习样例说明了评估方法的有效性。

应用聚类技术分类提取Web页面

针对Web中数据密集型的动态页面,文本数据少,网页结构化程度高的特点,介绍了一种基于HTML结构的web信息提取方法。该方法先将去噪处理后的Web页面进行解析,然后根据树编辑距离计算页面之间的相似度,对页面进行聚类,再对每一类簇生成相应的提取规则,对Web页面进行数据提取。

一种节点加权的相似重复XML数据检测算法

XML类型的数据成为当前主流的数据形式,本文提出一种检测XML数据相似性的方法,即将XML文档转换成树结构的基础上,对树结构的节点加权,并结合树编辑距离算法。通过XML带权树各属性权值计算的相似度对数据进行粗略匹配与聚集,而在重新聚集的集合中使用树编辑距离算法更直接的进行相似性检测。由于XML数据集合范围的缩小,树编辑距离算法操作的次数减少,从而节省了一定的时间。