有限自动机在模式匹配中的应用与研究

有限自动机匹配算法是多模式匹配中的重要算法.反向有限自动机在一定的条件下能压缩自动机的规模,从而提高模式匹配的速度.将反向有限自动机算法与BM算法相结合,利用当前获取信息进一步增大匹配过程中的跳跃距离,可进一步提高模式匹配的速度.     

有限自动机在密码技术中的应用探讨

通过对流密码体制一般原理的分析,提出了一个基于DFA的流密码模型.依据该模型,可以构造一类初始密钥长度可变、加密/解密简单快捷、强度较高的流密码,以满足不同的应用需求.     

有限自动机在家用防火防盗报警器中的应用

从有限自动机理论出发,运用有限自动机理论对家用防火防盗报警器的原理设计进行了形式化的描述,通过分析家用报警器的功能模块,得到报警器整个系统的工作流程,并对各模块之间的工作流程进行了说明,使得家用报警器系统之间的设计更加清晰,也使得系统实现更加容易.     

高效率的模式匹配算法

给出高效率的模式匹配算法Boyer-moore算法的原理及其具体实现．     

有限自动机正则化方法研究

有限自动机正则化是编译中的重要技术,文章针对现有有限自动机正则化方法的不足,分析了有限自动机正则化的本质,提出了一个新的有限自动机正则化方法。这个新的方法具有通用的特点。     

有限自动机的半环方法

文章利用半环方法来讨论有限自动机.首先,利用线性代数基础给出半环上有限自动机的概念;然后,证明了半环上的有限自动机与不确定的有限状态自动机识别语言的一致性.从数学的角度看该方法使得有限自动机的讨论更加简洁.     

字符串的模式匹配算法——基于KMP算法的讨论

重点对基本的串匹配算法和KMP算法进行了探讨。通过对这两种算法的比较分析提出了一个新算法，此算法具有比基本的串匹配算法更优越的时间复杂性，并且相对KMP算法而言更简洁易懂。     

基于混合策略的单模式匹配算法

结合后缀有限自动机和正向有限自动机的优点,提出了两个单模式匹配算法.算法中,无论是后缀自动机还是正向有限自动机,只要扫描到的模式前缀长度R>0或者超过模式长度的1/2时,使用正向有限自动机继续向右进行扫描;否则都滑动m-R个字符,使用后缀自动机反向扫描模式串的前缀.两个算法的最差、最好时间复杂度分别为O(n)和O(n/m).结果表明,在短模式的情况下,两个算法的平均时间复杂度均好于RF和LDM,在小字符集长模式或大字符集短模式的情况下它们的平均性能好于BM.     

一种新的多模式快速匹配算法

提出了一种针对多模式的快速模式匹配算法。算法分为预处理阶段和匹配阶段两个部分，预处理阶段对所有待匹配的模式进行分析，构造一个关于这些模式的树型有限状态自动机，匹配阶段利用这个模式自动机．对文本串进行一次性的搜索，查找文本是否包含模式集中的模式。为了提高了匹配速度，算法利用已匹配的字符串信息实行跳跃式的比较，避免了文本扫描指针的回溯。     

线性有限自动机零状态的作用

通过零状态研究了线性有限自动机的一些性质,得到了线性有限自动机弱可逆的一些结果,并给出了最小线性子有限自动机的描述,最后给出了算法实现。     

确定有限自动机的矩阵形式

研究自动机的方法有状态转换函数、RTL、VHDL以及矩阵形式等方法.矩阵形式与其它方法相比能很好地完成对自动机状态转化过程的演算.自动机是描述集合之间某种关系,它的工作过程是一种逻辑推理过程.根据自动机的逻辑形式定义,结合矩阵方式,建立了自动机的矩阵逻辑运算方程;同时讨论了矩阵表示的有关性质.     

一种基于有限运行时间自动机的基因网络模型

阐述了最近几年来国外基因网络系统逻辑行为的研究新进展——基于有限状态自动机模型的方法,针对该方法的局限性,提出了一种基于有限运行时间自动机的基因网络模型,以描述网络行为的时间约束.     

概率有限自动机的交换性

提出了一类概率有限自动机并给出其交换的概念,得到了此类自动机交换的一些刻画,定义了两个概率有限自动机的和与积,并且得到了和自动机、积自动机交换的充要条件。     

一种面向中文的快速字串多模式匹配算法

针对中文字串匹配问题,提出一种快速模式匹配算法,算法采用新型组合状态自动机,将2个状态组合起来匹配一个双字符,从而解决了双字节符构建完全Hash表时带来的存储空间膨胀问题;同时考虑到待匹配模式串中的字符在大字符集中稀疏分布的特点,尝试将单模式QS匹配算法的思想与DFSA算法进行结合,应用于多模式匹配中,实验结果显示,本算法明显优于DFSA算法,平均所花费时间仅为DFSA算法的45．2％。     

基于粗糙集理论的有限自动机最小化方法改进

有限自动机放在粗糙集的范畴中来研究,它的各个状态对应粗糙集论域中的每个对象,每个输入符号为一个等价关系。从粗糙集的角度,利用对论域进行知识划分的方法,每次产生新的等价类,直到每个等价类都不能划分为止,从而得到最小化的有限自动机。与已有的研究方法不同,该方法以粗糙集理论为工具,为有限自动机最小化方法研究提供了新的思路。     

模式匹配算法在IDS中的应用

入侵检测作为一种主动防御技术越来越多得到应用.基于模式匹配的入侵检测系统成为主流,模式匹配效率的高低决定了入侵检测系统的性能.文章综述多种经典模式匹配算法,提出了模式匹配算法的发展方向.     

一种非确定型有穷自动机的极小化方法

自动机状态极小化是寻求状态数较少的自动机,使其与原自动机接受相同的语言．确定型有穷状态自动机（DFA）极小化问题在平方时间内可解,通过状态集上引入等价关系导出的商自动机即为接受相同正则语言的极小化自动机．而非确定型有穷状态自动机（NFA）极小化问题尚未找到有效算法．尽管NFA可以转化为DFA且接受的语言不变,但可能会出现状态数指数级增加．从语言B可以构造一个接受自己的子语言自动机,同态压缩映射子语言自动机为最终系统,从而为接受语言B的极小化自动机．