一种基于完整性约束的路径表达式的查询优化策略

利用路径表达式导航 XML 查询是 XML 查询语言的共同特点。目前对 XML 路径表达式的计算有两种方法:一种是基于树遍历的方法,一种是路径连接方法。在路径连接方法中路径表达式的计算效率很大程度上依赖于路径表达式的长度。在对 XML 模式反映的完整性约束研究的基础上,本文提出了排他性包含约束的概念;给出了利用排他性包含约束缩短路径表达式的策略和算法,从而降低了路径连接的代价。通过分析比较,这种路径缩短策略是有效可行的。     

XML结构完整性约束下的路径表达式的最小化

引入了一个XML结构完整性约束体系.这个体系描述了XML文档中节点或路径之间的5种结构关系,包括路径蕴涵、路径同现、路径互斥、必需性包含和排他性包含.给出了这些结构完整性约束的语法和语义定义,并研究了它们在XML查询优化中的作用.基于子路径的概念,提出了有结构完整性约束的路径表达式的最小化算法.该算法以路径蕴涵闭包为工具,不仅可以删除路径表达式的冗余,还可以识别无效路径表达式.实验结果表明了该算法的正确性和有效性.     

中缀及后缀算术表达式在运算中的应用研究

表达式求值是程序设计语言编译中的一个最基本问题。与人们习惯的中缀表示的表达式相比,后缀表达式不存在括号,没有优先级的差别,表达式中各个运算是按照运算符出现的顺序进行的。因此非常适合串行工作的计算机处理方式。该文首先对这两种表达式表示方法进行了分析比较,然后通过具体分析实现这两种表达式求值的算法来论证表达式后缀表示优于中缀表示。最后简要谈一下中缀表达式到后缀表达式的转换。     

一种基于表达式的疾病风险评估模型的表示方法

设计了一套可解析、简洁、统一的表达式,用于表示各类疾病风险评估模型中的规则与界面.对疾病风险评估模型中评估规则涉及的各类指标进行归纳和分类,为每一类指标和规则设计了表达式和界面样式.以Caprini评估模型为例,提出了一种适用于各类疾病风险评估模型的,基于表达式的模型表示方法,该方法支持指标解析、规则计算和界面渲染.基于表达式来表示疾病风险评估模型的评估规则和界面,能有效避免硬编码和重复开发工作.     

一种基于粗糙集的大规模语料库语言学知识发现模型

文中首先通过语言学特征表来对文本信息进行结构化处理，同时实现了对远距离约束的表示；然后借助于面向个体的数据泛化算法来去除语言学特征表中的冗余信息，并利用规则抽取算法过滤特征表中不一致的部分，从而为相应的自然语言处理任务建立了一个一致、高效的规则库。最后，本文研究了模型在汉语词义排歧以及音字转换中的应用，在采用了动态规则平滑算法后，分别获得了0．93和0．95的判别精度以及0．92和0．89的覆盖率，这一结果显示模型具有很高的实用性。     

自适应表压缩方法优化STR算法

表约束,也称为外延式约束,是约束编程领域最常见的约束形式,表压缩方法通过紧凑的表示元组集可以极大地缩减空间消耗,同时加速 GAC 算法。笛卡尔乘积表示和短支持是表约束中最常见的两种表压缩方法,两种表压缩方法在同一问题上的压缩率是影响它们优化效果的主要原因。基于 STR 算法提出一种自适应表压缩方法,在求解问题时自适应选择压缩率大的表压缩方法,将自适应表压缩方法应用到 STR2 上提出了 STR2 Adaptive 算法,可以同时覆盖两种表压缩方法的优势。实验结果表明,STR2 Adaptive 算法在绝大部分实例上都能自适应选择最佳的表压缩方法,有效地减少了STR2算法空间消耗和CPU运行时间。然后将自适应表压缩方法扩展到采用了高效的比特向量表示的 STRbit 算法上提出了 STRbit Adaptive 算法。实验结果表明,STRbit Adaptive 算法效率同样普遍优于 STRbit 算法。     

同一变量排序下的多OBDD合并算法

有序决策图（OBDD）是一种用于表示布尔表达式的数据结构,并在许多领域得到了广泛应用。在分布式或者动态环境下,利用已知布尔表达式的OBDD构造目标布尔表达式的OBDD是一个决定实际问题解决效率的关键问题。基于Shannon分解原理提出了一个同一变量排序下的OBDD合并算法。该算法首先建立目标布尔表达式的表存储模型,然后按照变量排序的逆序,依次处理各个变量,并且合并取值相同的行,直到所有变量处理完毕。     

表达式

这一节描述算术、字符、关系和逻辑表达式的形成、解释和求值规则。表达式是由操作数、运算符和括号形成的。 6.1 算术表达式算术表达式用来表示数值计算。算术表达式的求值产生一个数值。算术表达式的最简单形式是一个无符号的算术常数、算术变量引用、算术数组元素引     

负表约束的简单表缩减广泛弧相容算法

广泛弧相容算法（generalized arc consistency,简称GAC）,是求解约束满足问题的核心方法.表约束理论上可以表示所有约束关系,在过去10年中,有很多应用于表约束的广泛弧相容算法被提出来.在这些算法中,表缩减算法的效率非常高.但是目前的表缩减算法只能应用于正表约束,无法直接应用于负表约束.首先,提出一种表缩减算法STR-N,可以直接应用于负表约束;然后,给出了STR-N的两个改进版本STR-N2和STR-NIC.实验结果显示,STR-N算法在负表约束上的求解效率具有明显的优势.     

一种有效的模糊关联规则挖掘的形式化方法

模糊关联规则用于处理数据库中的不精确信息,并提供一个知识发现的良好表示。利用约束级别表示理论将GUHA模型泛化用于模糊关联规则,通过约束级别管理模糊规则,并给出一个扩展的验证度量过程。使用形式化方法的挖掘算法,在不同的约束级别上并行化挖掘过程,总结得到的结果。算法的复杂度分析以及实验结果表明该形式化方法是有效可行的,从而确立了模糊关联规则表示和评价的逻辑基础。     

正则表达式基础及C#下的简单应用

通过表格的形式将正则表达式的语法进行总结,同时给出一些常用的正则表达式,方便读者在相关方面的练习与应用。最后通过列举C#下正则表达式简单应用,将正则表达式的语法应用于C#编程实践中,更方便大家理解与应用。     

一种用于深度报文检测的DFA状态表压缩方法

基于正则表达式进行深度报文检测在IDS/IPS、应用层协议识别等网络应用中具有重要作用。然而,采用DFA实现正则表达式需要大量的存储空间,限制了它的实际应用。将DFA状态转换表拆分成3个表,使用run-length编码进行压缩,并对压缩方法进行了优化。采用l7-filter中几个常用应用程序的正则表达式进行测试,结果表明该方法压缩效果一般在90%以上。     

Obtaining shorter regular expressions from finite-state automata

We consider the use of state elimination to construct shorter regular expressions from finite-state automata (FAs). Although state elimination is an intuitive method for computing regular expressions from FAs, the resulting regular expressions are often very long and complicated. We examine the minimization of FAs to obtain shorter expressions first. Then, we introduce vertical chopping based on bridge states and horizontal chopping based on the structural properties of given FAs. We prove that we should not eliminate bridge states until we eliminate all non-bridge states to obtain shorter regular expressions. In addition, we suggest heuristics for state elimination that leads to shorter regular expressions based on vertical chopping and horizontal chopping.     

Extended Regular Expressions: Succinctness and Decidability

Most modern implementations of regular expression engines allow the use of variables (also called backreferences). The resulting extended regular expressions (which, in the literature, are also called practical regular expressions, rewbr, or regex) are able to express non-regular languages. The present paper demonstrates that extended regular-expressions cannot be minimized effectively (neither with respect to length, nor number of variables), and that the tradeoff in size between extended and “classical” regular expressions is not bounded by any recursive function. In addition to this, we prove the undecidability of several decision problems (universality, regularity, and cofiniteness) for extended regular expressions. Furthermore, we show that all these results hold even if the extended regular expressions contain only a single variable.     

基于食肉植物算法的状态序列搜索

从有限自动机中生成简短、可读性强的正则表达式是计算机理论研究中的一个重大课题.在经典的正则表达式生成算法中,状态序列是影响正则表达式质量的关键因素.为了能够快速高效地找到较优的状态序列,本文以食肉植物算法的理论为核心,并结合其他启发式算法的思想进行设计与优化,提出了一种基于食肉植物算法的状态序列搜索方法.通过实验将此方法与已有的一些使用启发式规则的搜索算法进行了对比,实验结果表明,基于食肉植物算法的状态序列搜索方法优于其他启发式算法,生成的正则表达式长度比起其他启发式算法明显缩短,如跟DM算法相比,长度的缩短幅度可以随着自动机阶数的增加达到20%以上,跟随机序列算法相比,可以把长度缩短多个数量级.     

Proof Pearl: Regular Expression Equivalence and Relation Algebra

We describe and verify an elegant equivalence checker for regular expressions. It works by constructing a bisimulation relation between (derivatives of) regular expressions. By mapping regular expressions to binary relations, an automatic and complete proof method for (in)equalities of binary relations over union, composition and (reflexive) transitive closure is obtained. The verification is carried out in the theorem prover Isabelle/HOL, yielding a practically useful decision procedure.     

Series Parallel Digraphs with Loops

In the conversion of finite automata to regular expressions, an exponential blowup in size can generally not be avoided. This is due to graph-structural properties of automata which cannot be directly encoded by regular expressions and cause the blowup combinatorially. In order to identify these structures, we generalize the class of arc-series-parallel digraphs beyond the acyclic case. The resulting digraphs are shown to be reversibly encoded by linear-sized regular expressions. Also, a characterization of this new class by a set of seven forbidden substructures is given. Automata that require expressions of superlinear size must contain some of these substructures.     

NIDS中正则表达式数量限定符的电路设计与实现

针对网络入侵检测系统(NIDS)中复杂正则表达式匹配的数量限定符进行了硬件设计和实现。经过对这3种限定符匹配原理的分析,改变了以往的直接复制多个重复单元的实现方法,设计了一套完整的优化的数量限定符FPGA实现电路。实验测试结果表明,本设计每个非元字符平均大约需要0.92个逻辑单元,系统可以达到1.2 Gb/s的吞吐能力。     

Algorithms for learning regular expressions from positive data

We describe algorithms that directly infer very simple forms of 1-unambiguous regular expressions from positive data. Thus, we characterize the regular language classes that can be learned this way, both in terms of regular expressions and in terms of (not necessarily minimal) deterministic finite automata.