有穷自动机

摘要： 针对车间MDC系统和MES系统在获取制品信息时存在的数据缺失以及不准确、不及时的问题,提出了一种基于物联网的数控机床零件识别系统.通过建立机床加工程序库和零件标准程序库,运用正则表达式和有穷自动机对机床NC程序进行识别,从而间接实现加工零件识别.经验证,此系统具有准确性高、时效性强和维护成本低等特点.

摘要： 本文主要对词法分析器的自动生成进行了探讨和实践,介绍在有穷状态自动机、正则文法和正则表达式(RE)等形式化描述工具的基础理论和方法上,利用 Thompson 构造法、子集构造算法、分割法得到化简了的确定的有穷有自动机(DFA),以 DFA 状态图为输入,实现词法分析程序自动构造。

摘要： 深度检测在维护网络安全、保证服务质量等方面扮演着重要的角色.正则表达式匹配算法作为高性能深度检测的核心技术,具有重要的研究价值和实践意义.随着网络流量不断增长、规则数目持续增多以及网络结构日趋灵活和动态,现有的正则表达式匹配算法面临着匹配速度、内存占用和更新能力等多方面的挑战.介绍了正则表达式匹配算法的研究背景,从空间压缩、匹配加速、新型自动机设计以及规则拆分和分组四个角度入手,分类总结了学术界具有影响力的研究成果.通过基于真实网络流量的评测,比较了几种经典匹配算法在不同规则集上的匹配速度、内存占用和预处理时间等性能指标,并给出了不同需求场景下高效正则表达式匹配算法的选择建议,归纳了高性能正则表达式匹配算法的下一步发展方向.

摘要： 本文主要对词法分析器直接编程构造方法进行了分析与研究,分别通过正则表达式、状态图与有穷自动机对词法分析器进行了描述.然后运用实例对词法分析器构造流程进行分析与说明.进一步分析构造直接编程的词法分析器过程的性能,研究发现直接编程的词法分析器分析速度更快,优于其他类型的词法分析器.

摘要： Expert system is an important brunch of artificial intelligence.Knowledge representation and inference engine is an important part of the expert system.As an efficient pattern-matching algorithm,Rete algorithm can solve the ratiocination efficiency problem in expert system.However,there always exist the problems such as storage and efficiency in building and using Rete network.In this paper,we introduce the idea of finite automata,and the pattern sharing degree and node sharing degree model into Rete algorithm.We propose a Rete network construction and inference algorithm to reduce the complexity of Rete network and improve the speed of Rete network inference.Finally,experimental results show that it can reduce the complexity of the network greatly and raise the inference speed.%专家系统是人工智能领域的重要分支,其中知识表示和知识推理是专家系统的重要组成部分.Rete算法是一种高效的模式匹配算法,能够解决专家系统中推理效率的问题,但是Rete算法在构建Rete网络和推理过程中存在空间和性能方面问题.本文采取有穷自动机理论的思想,阐述了Rete算法中的模式共享度和节点共享度模型,提出了一种Rete网络构建和推理算法来降低Rete网络的复杂度,提升Rete网络推理的速度.最后实验结果表明,本算法能够降低网络复杂度,提升推理速度.

摘要： 多点触摸屏的应用程序开发是当前的研究热点.Linux multi-touch (MT)协议是Linux输入子系统的一个标准协议,定义了多点触摸设备驱动程序的数据传输规范,有着广泛的使用范围.识别和处理多点触摸屏驱动程序的数据是多点触摸屏应用最基本的功能.本文采用有穷自动机的思想,设计了一个可以识别符合Linux multi-touch协议规范数据的多点触摸屏中间件.中间件提供外部接口供应用程序使用,可以减少程序开发人员的重复工作,提高开发效率.

摘要： 在IETM领域中,装备名简称在数据模块文档中被广泛的使用,这在方便用户的同时也给IETM检索器中关键词匹配带来了难题.针对这种情况,提出一种装备名简称的生成方法.通过分析S1000D标准标签的语义特点、装备名称命名规则和简称生成特点,设计出装备名简称生成的有穷自动机,并根据装备名称中各部分的重要性设定权值输出简称.以美军联合电子装备命名规则为例,结果表明,该方法能够有效地输出装备名的简称集,覆盖用户的常用简称范围.

摘要： 提出了一种新颖的正则NFA引擎构造方法——PFA构造法.PFA构造法包括3个主要算法:预处理算法、解析树编码算法和基于编码树的NFA构造算法.采用PFA构造法能够构造出只含有一个开始状态和一个终止状态的规模更小的NFA,称其为NFAp.NFAp的规模与正则表达式组的长度线性相关,较Thompson自动机、后跟自动机、位置自动机以及部分派生自动机的规模都要小,是Thompson NFA的1/3,比已经接近最优的后跟自动机构造法所获得的NFA还要小.

摘要： 有穷自动机是一种关于系统状态变迁与时间关系的数学模型,20世纪40年代和50年代分别由McCulloch、Pitts和Moore等建立了自动机模型,经过半世纪多的发展,它已经成为一门完善的离散数学理论分支,广泛应用于形式语言、数字电路、计算机编译程序和操作系统等各个方面.自动机分为确定性(DFA)和非确定性两种(NFA),NFA可通过闭包算法转变为DFA,本文将探讨DFA在自动化控制方面的应用.

摘要： 针对入侵检测系统中数据匹配速度较慢的问题,提出了一种高效的模式匹配算法IBMHS-W.该算法基于确定型有穷自动机,通过在模式串移动过程中加入字符比较,不仅提高了模式串的右移距离,还消除了重复的字符比较.仿真实验表明,该算法比现有的BMHS算法和BMHS-W算法有更快的匹配速度.

摘要： 为了在软件开发早期阶段对UML2.0顺序图模型进行分析和验证,本文给出了UML2.0顺序图的一种有穷自动机模型.首先给出了顺序图在语法和语义上的形式化描述,然后提出了一种使有穷自动机来描述每个对象在顺序图描述的场景中所参与的事件序列的方法,并将该方法扩展到带有组合片段的UML2.0顺序图,最后分析了UML2.0顺序图中的时间建模机制,设计了从UML2.0顺序图中提取时间约束的算法。以上工作为使用模型检测工具UPPAAL对顺序图模型进行进一步的分析与验证奠定了基础.

摘要： 本文提出了一种新的有穷自动机理论，分析在电子商务的实际应用中交易协议是否满足支付过程中的公平性。文章证明了ISI支付协议不满足公平性并提出了具体的修改方法。

摘要： "不确定有穷自动机NFA(即Non-FiniteAutomat),先转化为确定有穷自动机FA(即FiniteAutomat),再转化为规范有穷自动机GFA(即GageFiniteAutomat)",是有穷自动机极小化的研究基础.HopcroftJE.等学者曾论及"NFA→FA→GFA"等价转换,但未见构造性算法.为此,本文将给出有穷自动机的规范化算法.

摘要： 本文把确定的有穷状态自动机理论和非确定的有穷状态自动机理论用于汉字信息输入处理的研究,引进了确定的汉字有穷自动机和非确定的汉字有穷自动机的概念.

摘要： 目前进行正则表达式匹配的典型工具DFA和NFA都存在匹配效率和内存需求之间不可调和的矛盾,无法胜任网络安全检测中大规模正则表达式的匹配.为了解决这个问题,文中从网络安全检测的行为特点出发,结合DFA、NFA模型各自的特性,提出了一种基于猜测-验证的匹配方法.首先使用DFA对正则表达式中的部分子特征进行搜索,完成特征存在性的猜测;当猜测到有可能匹配某个特征后,再使用NFA进行验证.文中方法既充分利用了DFA的高效性,减少了对相对较慢的验证过程的调用,又借助NFA避免了内存消耗过于巨大.结果表明,该方法可以在大大减少内存需求的情况下,实现正则表达式的高效匹配.

摘要： 目前进行正则表达式匹配的典型工具DFA和NFA都存在匹配效率和内存需求之间不可调和的矛盾,无法胜任网络安全检测中大规模正则表达式的匹配.为了解决这个问题,文中从网络安全检测的行为特点出发,结合DFA、NFA模型各自的特性,提出了一种基于猜测-验证的匹配方法.首先使用DFA对正则表达式中的部分子特征进行搜索,完成特征存在性的猜测;当猜测到有可能匹配某个特征后,再使用NFA进行验证.文中方法既充分利用了DFA的高效性,减少了对相对较慢的验证过程的调用,又借助NFA避免了内存消耗过于巨大.结果表明,该方法可以在大大减少内存需求的情况下,实现正则表达式的高效匹配.

摘要： 目前进行正则表达式匹配的典型工具DFA和NFA都存在匹配效率和内存需求之间不可调和的矛盾,无法胜任网络安全检测中大规模正则表达式的匹配.为了解决这个问题,文中从网络安全检测的行为特点出发,结合DFA、NFA模型各自的特性,提出了一种基于猜测-验证的匹配方法.首先使用DFA对正则表达式中的部分子特征进行搜索,完成特征存在性的猜测;当猜测到有可能匹配某个特征后,再使用NFA进行验证.文中方法既充分利用了DFA的高效性,减少了对相对较慢的验证过程的调用,又借助NFA避免了内存消耗过于巨大.结果表明,该方法可以在大大减少内存需求的情况下,实现正则表达式的高效匹配.

摘要： 目前进行正则表达式匹配的典型工具DFA和NFA都存在匹配效率和内存需求之间不可调和的矛盾,无法胜任网络安全检测中大规模正则表达式的匹配.为了解决这个问题,文中从网络安全检测的行为特点出发,结合DFA、NFA模型各自的特性,提出了一种基于猜测-验证的匹配方法.首先使用DFA对正则表达式中的部分子特征进行搜索,完成特征存在性的猜测;当猜测到有可能匹配某个特征后,再使用NFA进行验证.文中方法既充分利用了DFA的高效性,减少了对相对较慢的验证过程的调用,又借助NFA避免了内存消耗过于巨大.结果表明,该方法可以在大大减少内存需求的情况下,实现正则表达式的高效匹配.

摘要： 本发明涉及一种基于TCAM(ternary content addressable memory，三态内容寻址存储器)的DFA的匹配方法和装置。该方法主要包括：将DFA的每个状态用若干TCAM条目表示，每个TCAM条目由源状态域、输入字符域和目的状态域三个域组成，基于生成所述DFA的非确定性有穷状态自动机NFA中的链式结构，以及所述NFA和所述DFA之间的内在链式结构特征，识别出所述DFA中的链式结构；根据所述DFA中的链式结构对所述DFA的状态进行重新编号和编码，在TCAM中对所述DFA的状态转移边进行重新编码；以具体的所述源状态域和输入字符域的拼接作为搜索关键词，按照所述搜索关键字在所述DFA的所有TCAM条目中进行搜索，将搜索得到的目的状态域作为输出结果。本发明实施例通过在TCAM中通过对DFA的状态转移边进行编码和压缩，使得DFA中的副本链式结构在TCAM中能够被合并，以达到减少存储空间的目的。

摘要： 本发明涉及一种基于TCAM(ternary content addressable memory，三态内容寻址存储器)的DFA的匹配方法和装置。该方法主要包括：将DFA的每个状态用若干TCAM条目表示，每个TCAM条目由源状态域、输入字符域和目的状态域三个域组成，所述源状态域由模板ID域和私有ID域两个子域组成，所述目的状态域由模板ID域和私有ID域两个子域组成，以具体的所述源状态域和输入字符域的拼接作为搜索关键词，按照所述搜索关键字在所述DFA的所有TCAM条目中进行搜索，获取搜索得到的目的状态域，将所述目的状态域中的模板ID域的值与所述搜索关键字搜索关键词中的模板ID域的值进行异或，将所述异或结果作为所述目的状态域中的最终的模板ID域的值。本发明实施例可以在不牺牲匹配速度的前提下突破DFA状态数指数膨胀的问题，大大减少了DFA所需的存储空间。

摘要： 本发明涉及一种基于TCAM(ternary content addressable memory，三态内容寻址存储器)的DFA(deterministic finite automaton，确定性有穷状态自动机)的匹配方法和装置。该方法主要包括：将DFA的每个状态用若干三态内容寻址存储器TCAM条目表示，每个TCAM条目由出发状态、输入字符和到达状态三个域组成，表示同一状态的TCAM条目的出发状态相同；以具体的所述出发状态和输入字符的拼接作为搜索关键词，按照所述搜索关键字在所述DFA的所有TCAM条目中进行搜索，将搜索得到的到达状态作为输出结果。本发明实施例通过将DFA的每个状态用若干TCAM条目表示，利用单状态条目压缩算法、不同状态共享TCAM条目、共享状态转换的方法大大减少存储整个DFA所需的TCAM条目数量。

摘要： 本发明提出了一种基于确定性有穷状态自动机的数据匹配检测方法，包括以下步骤：A)捕获网络中的数据包；B)对所捕获的数据包进行全协议栈解析；C)将待匹配数据报文输入至确定性有限自动机DFA状态表中进行匹配；D)输出匹配成功结果。本发明通过对数据包进行全协议栈解析，大大提高了解码速度，满足实时解码要求，并减少了对服务器内存的需求；此外，本发明通过基于正则表达式的匹配方法，可以极大地减小状态迁移表所占用的储存空间，并提高匹配速度与匹配效率，通过上述高级隐遁技术实现了对高级逃逸入侵的有效防护。

摘要： 本发明涉及一种基于TCAM(ternary content addressable memory，三态内容寻址存储器)的DFA的匹配方法和装置。该方法主要包括：将DFA的每个状态用若干TCAM条目表示，每个TCAM条目由源状态域、输入字符域和目的状态域三个域组成，所述源状态域由模板ID域和私有ID域两个子域组成，所述目的状态域由模板ID域和私有ID域两个子域组成，以具体的所述源状态域和输入字符域的拼接作为搜索关键词，按照所述搜索关键字在所述DFA的所有TCAM条目中进行搜索，获取搜索得到的目的状态域，将所述目的状态域中的模板ID域的值与所述搜索关键字搜索关键词中的模板ID域的值进行异或，将所述异或结果作为所述目的状态域中的最终的模板ID域的值。本发明实施例可以在不牺牲匹配速度的前提下突破DFA状态数指数膨胀的问题，大大减少了DFA所需的存储空间。

摘要： 本发明涉及一种带通配符正则表达式的有穷自动机生成方法，其特征在于，按照如下步骤实现：S1：根据带通配符正则表达式生成抽象语法树，并对该抽象语法树的每个节点编号；S2：根据抽象语法树计算每个节点的nullable(n)和每个节点的三个位置集合；S3：将抽象语法树根节点的firstpos（n0）作为第一个状态，存储到到状态集合中；遍历状态集合，若在遍历过程中产生新的状态，则将新的状态加入到状态集合中，记录转换关系；在遍历每个状态时，计算该状态中的每个字符的跟随状态，并根据条件存放到状态集合中。本发明所提出的一种带通配符正则表达式的有穷自动机生成方法，有效的提高了编译的效率，降低了对内存的消耗。

摘要： 本发明涉及一种基于确定有穷自动机的长者护理等级评估方法以及系统，长者护理等级评估方法包括以下步骤：利用长者护理等级评估规则，编制完整的第一正则表达式，并根据该第一正则表达式来初始化有限状态机模型；对进行优化而得到优化后有限状态机模型；将优化后有限状态机模型转换为第二正则表达式；当对长者进行长者护理等级评估时，利用第二正则表达式，对本次评估中输入的评估选项数据进行匹配，从而得到该长者的评估等级结果。

摘要： 本申请公开了一种基于确定有穷自动机的敏感词检测方法和系统，所述方法包括：构建敏感词库树；匹配敏感词。与现有技术相比，本申请的技术方案采用对比正则检查方式，其时间效率随着待检文本长度和敏感词库的敏感词数量的增加而大大降低。通过使用确定有穷自动机减少了运算量，大大提高敏感词过滤的效率。

摘要： 本发明涉及一种基于有穷自动机的网络训练综合分析方法，利用网络态势综合分析模块接收网络入侵告警系统和主机入侵告警系统产生的多种入侵告警日志，基于有穷自动机建立了网络训练场景模型和分析算法，通过将这些日志按模型关联和融合，组织成网络训练事件，与所述网络态势综合分析模块中的规则库进行匹配，实时提交准确、直观的日志分析结果，重建训练情景。本发明是针对复杂网络环境提出了新的综合分析方法，基于有穷自动机建立了网络训练场景模型和分析算法，能适应多场景、多人员、多模式的训练需求，应用到网络训练系统综合分析评估中，提高了网络训练态势监控和评估的有效性，增强了网络训练系统的可靠性与实用性。

摘要： 本发明涉及一种带通配符正则表达式的有穷自动机生成方法，其特征在于，按照如下步骤实现：S1：根据带通配符正则表达式生成抽象语法树，并对该抽象语法树的每个节点编号；S2：根据抽象语法树计算每个节点的nullable(n)和每个节点的三个位置集合；S3：将抽象语法树根节点的firstpos（n0）作为第一个状态，存储到到状态集合中；遍历状态集合，若在遍历过程中产生新的状态，则将新的状态加入到状态集合中，记录转换关系；在遍历每个状态时，计算该状态中的每个字符的跟随状态，并根据条件存放到状态集合中。本发明所提出的一种带通配符正则表达式的有穷自动机生成方法，有效的提高了编译的效率，降低了对内存的消耗。