共查询到20条相似文献,搜索用时 156 毫秒
1.
介绍了基于有限自动机的XML过滤技术的研究现状,依据自动机的特点进行分类,分析了其中几种典型算法,并对XML过滤算法的优缺点进行了深入讨论和比较. 相似文献
2.
3.
针对正则表达式匹配过程中吞吐率低及逻辑资源占用数多的问题,提出一种完全基于现场可编程门阵列(FPGA)逻辑电路的改进确定有限自动机(DFA)匹配算法。首先,该算法统计了DFA中每个状态的大多数转移边都会集中指向相同状态特征的结果,随后根据正则表达式的转移矩阵为DFA的每个状态设置一条默认的转移边,最后进行逻辑电路简化处理,并采用L7-filter规则集进行实测。实验结果表明,改进后的DFA方案与非确定有限自动机(NFA)方案相比,有10%~60%的规则获得了更高的吞吐率,62%~87%的规则占用了更少的逻辑资源。 相似文献
4.
5.
正则表达式匹配在网络安全应用中发挥着重要的作用.确定有限自动机(deterministic finite automaton,DFA)具有高速稳健的性能,因而更适合于在骨干网络环境下执行正则表达式匹配.然而,DFA存在状态膨胀的问题.很多研究工作基于状态关系来解决DFA的状态膨胀问题.然而目前对如何获得状态间的关系仍然缺少一种时空高效的解决办法.提出了一个通过有限自动机(finite automaton,FA)的活跃状态集来准确计算状态关系的算法,并给出了一个高效的获取所有活跃状态集的方法.实验结果证明,该方法不仅能准确地得到状态关系,而且其空间占用和时间消耗仅是已有方法的1?256和15%左右. 相似文献
6.
网络攻击的形式化建模探讨 总被引:2,自引:0,他引:2
随着网络入侵技术的不断发展,攻击行为表现出不确定性、复杂性和多样性的特点,攻击活动往大规模、协同化和多层次方向发展。网络攻击的日益复杂化迫切需要有一种新的描述方法对之进行有效的形式化建模,Z语言和确定有限自动机(DFA)是广泛使用的形式化工具,适合用来精确表示模型的语法和语义。文章建立了基于DFA的攻击模型,并在此基础上利用Z语言对之进行了有效的形式化描述。 相似文献
7.
8.
一组提高存储效率的深度包检测算法 总被引:2,自引:0,他引:2
随着深度包检测规则数目的剧烈增长,为了适应网络处理的需求,必须对表示正则表达式的DFA(deterministic finite automata,确定的有限自动机)进行高效的存储.一方面,对DFA的状态点数目进行压缩,提出了一种复合的FSM(有限自动机)的构造方法,通过对正则表达转化成DFA的状态点数目复杂度的分析,将不同复杂度的正则表达式采用不同的方式构建DFA,使得所有平方级和指数级复杂度的状态点数目降低到了线性级.另一方面,对DFA的状态转移数目进行压缩,给出了一种高效的压缩算法,即WD2FA(weighted delayed input DFA,带权延迟DFA)算法,对于任意复杂度的正则表达式都可以将状态转移数目压缩为原来的5%左右,相对于D2FA(delayed input DFA,延迟的DFA)有更好的压缩能力,并且使得D2FA是WD2FA在权值为0情况下的特例.实验结果表明,有限自动机的状态点数目能够控制在线性级,并且在状态点压缩的基础上将状态转移数目压缩为原来的7%. 相似文献
9.
正则表达式是数据验证技术中功能最为强大的输入控制技术。传统的基于NFA的正则表达式引擎的匹配速度低。通过正则表达式与自动机等价的原理,研究了通过最小化的确定的有限自动机(DFA)来等价实现.NET中正则表达式的数据验证的机制,以期提高正则表达式的匹配速度。 相似文献
10.
11.
本文提出了一种对XML 文本进行快速串匹配的算法- XMatch。在对于XML 文本的含路径信息的模式串匹配中,由于XML 文本的结构化特点,使得传统的串匹配算法不能直接有效的使用;而现有的大部分XML 内容筛选方法都是基于SAX 分析的事件驱动过程,效率普遍较低。XMatch 在对XML 文本的结构-schema 进行分析的同时,结合模式串的路径信息,建立一个扫描自动机的有限状态自动机;此外,算法还支持带循环引用路径信息的模式串匹配。XMatch 容易扩展,可以支持普通的结构化文本的串匹配。实验结果显示,本算法的效率比使用SAX事件驱动的方法有明显的提高。 相似文献
12.
13.
近年来,XM L数据流的查询处理引起了国内外学者的广泛兴趣。如何在XM L流中有效地查询大量XPath表达式是当今研究的一个热点问题。先将多个XPath式通过共享前缀处理,构造一个非确定的有穷自动机(NFA)模型,再将其转化为确定的有穷自动机(DFA),以实现状态转移的确定性,然后对DFA进行最小化,提出了一种普遍适用的改进的最小化算法,在执行效率和空间代价方面它都优于一般性算法。 相似文献
14.
基于扩展路径表达式的XML查询 总被引:4,自引:0,他引:4
XML查询问题是当前计算机界研究的热点问题之一,国内外学者提出了众多的模型与算法.其中,日本学者Makoto Murata等提出采用扩展路径表达式来表达查询,并利用hedge自动机和字符串自动机进行XML的查询计算.这种方法与采用路径表达式控制的XML查询相比,克服了后者不能充分利用XML文档有序性的缺点.另外,扩展路径表达式具有较强的表达能力,可以表达任何MSO(一元二阶逻辑)查询.因此,扩展路径表达式已作为XML查询问题研究的主要理论框架之一,但是扩展路径表达式的编写比较困难,表达式也比较复杂,导致算法时间复杂度的提高.在扩展路径表达式中引入通配符,使得扩展路径表达式更加简单灵活;同时在查询的计算过程中提出并应用带截止集的自动机提高计算的时间效率. 相似文献
15.
16.
《Information and Software Technology》2003,45(5):241-251
XML is data that has no fixed structure. So it is hard to design a schema for storing and querying an XML data. Instead of a fixed schema, graph-based data models are widely adopted for querying XML. Queries on XML are based on paths in a data graph.A meaningful query usually has several paths in it, but much of recent research is more concerned with optimizing a single path in a query. In this paper, we present an efficient technique for processing multiple path expressions in a query. We implemented our technique and present preliminary performance results. 相似文献
17.
XML access control models proposed in the literature enforce access restrictions directly on the structure and content of an XML document. Therefore access authorization rules (authorizations, for short), which specify access rights of users on information within an XML document, must be revised if they do not match with changed structure of the XML document. In this paper, we present two authorization translation problems. The first is a problem of translating instance-level authorizations for an XML document. The second is a problem of translating schema-level authorizations for a collection of XML documents conforming to a DTD. For the first problem, we propose an algorithm that translates instance-level authorizations of a source XML document into those for a transformed XML document by using instance-tree mapping from the transformed document instance to the source document instance. For the second problem, we propose an algorithm that translates value-independent schema-level authorizations of non-recursive source DTD into those for a non-recursive target DTD by using schema-tree mapping from the target DTD to the source DTD. The goal of authorization translation is to preserve authorization equivalence at instance node level of the source document. The XML access control models use path expressions of XPath to locate data in XML documents. We define property of the path expressions (called node-reducible path expressions) that we can transform schema-level authorizations of value-independent type by schema-tree mapping. To compute authorizations on instances of schema elements of the target DTD, we need to identify the schema elements whose instances are located by a node-reducible path expression of a value-independent schema-level authorization. We give an algorithm that carries out path fragment containment test to identify the schema elements whose instances are located by a node-reducible path expression. 相似文献
18.
XML函数依赖及其与键的关系 总被引:4,自引:0,他引:4
通过分析函数依赖的表现形式在XML文档和关系数据库中的不同之处,提出了基于DTD中的路径表达式的XML函数依赖的概念.并且给出了XML函数依赖的XML表示方法,研究了XML函数依赖和XML键的关系. 相似文献
19.
邓红辉 《电脑编程技巧与维护》2013,(8):73-74
通过对现有的路径表达式查询中几种优化技术的分析研究,提出了在XML语言查询中的一些重要问题,并根据其主要的技术特点提出了自己的观点,旨在提高对XML路径表达式查询技术的优化。 相似文献