正则表达式匹配引擎性能分析

正则表达式具有强大的描述能力,在计算机领域,正则表达式匹配技术应用十分广泛。目前,已经有多个正则表达式匹配引擎,在实际应用中,对于不同的匹配规则集和正则语法,不同的匹配引擎会有不同的性能表现。本文通过对PCRE、Greta、Boost、RE2四种常用正则表达式匹配引擎的性能测试,给出在不用的正则语法情况下的匹配速度,并深入分析不同坏境下适用的正则表达式匹配引擎。对实际系统设计中正则表达式库的选择有指导意义。     

正规文法与有限自动机的等价构造

在功能上,正规文法与有限自动机描述和识别语言是等价的,它们之间也存在等价构造算法,但这些构造算法有些复杂.对其算法进行了简化且给以了证明,并提出了一个从有限自动机构造等价左线性正规文法的算法,同时也进行了证明,最后给出了该算法的一个实例.     

一种适于XPath查询的自动机最小化算法

近年来,XM L数据流的查询处理引起了国内外学者的广泛兴趣。如何在XM L流中有效地查询大量XPath表达式是当今研究的一个热点问题。先将多个XPath式通过共享前缀处理,构造一个非确定的有穷自动机（NFA）模型,再将其转化为确定的有穷自动机（DFA）,以实现状态转移的确定性,然后对DFA进行最小化,提出了一种普遍适用的改进的最小化算法,在执行效率和空间代价方面它都优于一般性算法。     

Minimized Thompson NFA

The problem of converting a regular expression to nondeterministic finite automaton (NFA) is a fundamental problem that has been well studied. However, the two basic construction algorithms: (1) Thompson, (2) McNaughton–Yamada and Glushkov, both have disadvantages. In this article: first, a ‘smart’ parsing algorithm is developed which constructs a parse tree with at most (3l???1) nodes form a regular expression with l literals; second, we propose an algorithm that works on the resulting NFA from Thompson's construction, eliminating as many auxiliary states as possible while maintaining Thompson's properties. It is shown that the resulting NFA is minimized. This means that no auxiliary states can be eliminated without violating the defining properties of Thompson NFA. The time and space requirements for the above algorithms are linear with respect to the length of the regular expression.     

P2P网络中基于非确定有限自动机的XML数据流过滤

将自动机方法对XML数据的过滤延伸到P2P网络中,依据在本地XML系统YFilter中构造非确定有限自动机(NFA)的思想,采用Chord环建立起分布式的NFA对于peer节点中的XML数据的查询过滤系统,并基于递归法执行查询过滤,在不同的peer节点上得到满足查询条件的数据集合。通过实验验证了当查询的数量和网络大小发生变化时分布式NFA的方法的执行性能。结果表明:本文方法可在不同的过滤场景中处理百万数量级的XPath查询,具有良好的网络流量和过滤延迟。     

有限状态自动机的并行确定化及过程分析

本文通过对并行环境下非确定有限自动机和确定有限自动机的等价性和转换进行研究，详细分析了非确定有限自动机到确定有限自动机的并行转换方法及算法，并以实例给出了其间并行转化的过程。     

基于RFID及其路径约束的生产检查流程控制

针对生产检测流程控制中,产品可能会沿着多种工位流动,且工位的执行顺序是复杂的问题,文中提出了一种基于RFID及其路径约束的生产检测流程控制方法。该方法在产品上贴有RFID标签,在产品经过的生产检测工位上安装有阅读器;产品按固定的工位操作顺序进行生产检测,当贴有标签的产品经过每一个工位时就能被阅读器识别,从而判定产品经过的生产检测流程是否按照规定的顺序执行,将这一顺序称之为路径约束。使用NFA构造贴有RFID标签的产品在生产检测流程中所需要遵守的工位执行顺序(路径约束)。利用构造好的路径,按照设计好的算法先过滤RFID数据流,使用清洗后的数据流进行生产检测流程的控制。实验结果表明该算法能有效地控制生产检测的流程。     

Feedback supported isolation structure for blocking of minority leakage carriers in power integrated circuits

A combination of two conventional junction isolation structures is used to produce a device, which significantly improves the blocking of minority carriers injected into the substrate of a power IC due to switching of an inductive load. Simulation results show that the connection scheme employed greatly enhances the efficiency of the structures. A substrate current reduction of up to four orders of magnitude compared to conventional junction isolation structures is achieved. The significance of doping profiles in the p-sinker region is evaluated.     

On Straight Line Segment Detection

In this paper we propose a comprehensive method for detecting straight line segments in any digital image, accurately controlling both false positive and false negative detections. Based on Helmholtz principle, the proposed method is parameterless. At the core of the work lies a new way to interpret binary sequences in terms of unions of segments, for which a dynamic programming implementation is given. The proposed algorithm is extensively tested on synthetic and real images and compared with the state of the art.

在线-离线数据流上复杂事件检测

随着数据采集和处理技术的发展,在物联网对象跟踪、网络监控、金融预测、电信消费模式等领域中进行事件检测显得越发重要.事件检测在一次扫描数据流的假设下完成,数据流在被处理完后丢弃.事实上,很多应用场景中,历史数据流因含有丰富的信息而不能简单丢弃,且一些事件检测查询需要同时在实时和历史数据流上进行.鉴于已有复杂事件检测很少考虑同时在实时-历史数据流上进行模式匹配,作者研究了在线-离线数据流上复杂事件检测的关键问题.主要工作如下:(1)针对滑动窗口内产生的大量模式匹配中间结果,提出利用时态关系和时空关系管理中间结果的方法 TPM和STPM.STPM以中间结果的时态和状态信息为权值对中间结果进行管理,将最近的、最有可能更新状态的中间结果置于内存,极大地减少了中间结果的读取操作代价.(2)给出了基于选择度的在线-离线复杂事件检测优化算法;(3)给出了算法的复杂性分析和代价模型;(4)在基于时空关系的中间结果管理模型下,在一个在线-离线复杂事件检测原型系统中进行实验,对多个参数(子窗口大小,选择度,匹配率,命中率)进行了算法对比分析.实验结果充分验证了所提出的算法的可行性和高效性.