【摘 要】
:
正则表达式具有灵活高效的特点,同时还有着强大的表达能力,在许多领域中被广泛应用。非确定性有限自动机是实现正则表达式应用的重要方法,Glushkov自动机是一种不同于Thompson自动机的非确定性有限自动机。Glushkov自动机有两大优点:第一,Glushkov自动机状态数目等于m+1(其中m为正则表达式非操作符长度);第二,Glushkov自动机每一个状态的所有输入都是同一个字符。Glushk
论文部分内容阅读
正则表达式具有灵活高效的特点,同时还有着强大的表达能力,在许多领域中被广泛应用。非确定性有限自动机是实现正则表达式应用的重要方法,Glushkov自动机是一种不同于Thompson自动机的非确定性有限自动机。Glushkov自动机有两大优点:第一,Glushkov自动机状态数目等于m+1(其中m为正则表达式非操作符长度);第二,Glushkov自动机每一个状态的所有输入都是同一个字符。Glushkov自动机和比特并行方法相结合是当前最常用的正则表达式匹配手段,例如Navarro-Raffinot方法(简称NR方法)和按自动机状态分类进行状态转换的方法(简称分类状态转换方法)。空间消耗是影响模式匹配方法性能的关键因素之一,上述方法在正则表达式长度增大时会引发空间消耗的急剧增大,从而影响模式匹配方法的时空性能,因此降低空间开销对于模式匹配方法来说至关重要。基于此背景,本文提出将Glushkov自动机等价状态进行合并,得到改进的Glushkov自动机,并将其应用于本文提出的异构状态转换方法中,主要贡献如下:基于左等价关系和粗右等价关系得到改进的Glushkov自动机,改进的Glushkov自动机通过合并Glushkov自动机中的等价状态,将状态数目从m+1降低至m1,将分支状态数(Glushkov自动机中分支状态数等于正则表达式子串数加1)由k+1降低至k1。本文首次证明了改进的Glushkov自动机应用于比特并行方法中的可行性,在改进的Glushkov自动机上应用NR方法将空间开销从NR 方法的0(m2m)bits 降低至O(m12m1)bits。基于改进的Glushkov自动机和分类状态转换方法,本文首次引入了 BMI2指令集中的新型指令PDEP和PEXT实现了改进Glushkov自动机的高性能处理,提出了基于改进的Glushkov自动机的异构状态转换方法(异构状态转换方法)。该方法将模式匹配过程中最坏情况下的空间开销从NR方法和分类状态转换方法的0(m2m)bits和O(m2k)bits降低至O(k2k1)bits,平均空间开销为k(1+1/σ)k1 bits。实验证明,本文提出的异构状态转换方法能够完全实现预期的匹配要求,空间开销降低至分类状态转换方法的9.3%-55.5%,匹配速度也因有效的规模压缩而得到了巨大的提升。这意味着本文所提出的异构状态转换方法解决了空间开销高的问题,为模式匹配方法提供了一条新思路。
其他文献
糖尿病前期是将来发生糖尿病的一个分水岭,经过有效的干预,可以将其逆转,降低向糖尿病的转化,从而缓解因此带来的社会经济压力。该病当属中医学“脾瘅”范畴,陈秋教授运用中医学理论体系解析糖尿病前期主要的病因病机,病证结合,标本同治,提出了“健脾行气、滋阴活血”为治疗大法的综合干预方案。笔者结合医案进行分析、总结,以期为中医临床提供一定的借鉴意义。
<正>互联网时代的到来,丰富了人们的生活方式,同时也衍生出多样化的社交方式。现如今,随着智能设备的普及,人们逐渐开始使用电子设备进行社交,以此满足自己的社交需求,这种社交方式没有随着时间的流逝而逐渐被人们所遗忘,反而随着社会的变迁发展,变得越来越常态化。为了进一步促进网络社交方式的发展,让人们逐渐适应这种新型社交方式,有关部门需要对年轻群体进行适当的引导,帮助其正确通过社交平台,从网络渠道与他人进
真菌次级代谢产物十分丰富,是天然药物的重要来源。我们的研究对象是本实验室自主分离获得的大团囊虫草菌(Tolypocladium ophioglossoides L2)。课题组在前期工作中对菌株进行了全基因组测序,经生物信息学分析,通过高表达bln簇内调控基因bln R,成功激活了该隐性基因簇并成功分离鉴定到balanol和其他新产物。Balanol是非选择性靶向蛋白激酶C(PKC)和c AMP依赖
目的 观察中医药综合干预对糖尿病前期(PD)患者糖脂代谢的影响。方法 选取2020年3月—2022年2月北京中医药大学房山医院月华分院综合内科门诊收治的184例PD患者作为研究对象,按照随机数字表法分为对照组92例和观察组92例。对照组患者采用二甲双胍+饮食控制干预,观察组患者在对照组基础上联合中医药综合干预。2组干预疗程均为3个月。比较2组干预前及干预1、2、3个月后的体质量,干预前、干预3个月
<正>糖尿病前期是发展为糖尿病的可逆过程[1-2],主要为糖耐量减低和/或空腹血糖受损。2020年我国2型糖尿病患者已经超过1亿[3-4]。为进一步减缓糖尿病前期向糖尿病转化,关键在于糖尿病前期把控和干预,这也符合我国慢性病的政策防控[5]。间歇性断食是指正常能量摄入和能量摄入受限交替进行的一种新的饮食模式[6],相较于传统的节食模式,带来更多的减重获益,同时能够维持β细胞稳态,改善葡萄糖耐受性,
目的 探讨饮食行为护理在糖尿病前期患者中的应用效果,分析对其饮食行为遵医情况、情绪状态、糖代谢指标等的影响。方法 选择2020年9月-2022年9月本院收治的糖尿病前期患者50例为对象。随机按照信封法原则将患者分为对照组、观察组,每组各25例。对照组饮食一般性护理,观察组实施饮食行为干预,比较两组饮食行为遵医情况变化,借助量表调查两组患者情绪状态、生活质量,检测其糖代谢指标并比较,调查护理满意度并
<正>2型糖尿病前期是介于血糖正常与2型糖尿病中间的一种状态,分为糖耐量受损,即空腹血糖<6.1毫摩尔/升、餐后2小时血糖为7.8~11.1毫摩尔/升;空腹血糖受损,即空腹血糖6.1~7.0毫摩尔/升、餐后2小时血糖<7.8毫摩尔/升。这两种情况都表明身体对血糖的调节能力出了问题。
随着互联网技术的不断深入发展,网络中传输的数据在数量和种类上都呈现快速上升的趋势。对网络中的数据进行监控和审查,以提升网络服务质量、加强监管、保障网络安全变得尤为重要。传统的基于中间人的加密数据检测算法使用接收数据包、解密数据、检测数据、再加密数据的方式实现。这种检测方式不仅会造成隐私泄露,而且解密数据包的行为违背了加密传输协议的设计初衷。因此,如何设计一种能够实现在保护通信双方隐私的前提下实现数
糖尿病视网膜病变(DR)和糖尿病黄斑水肿(DME)是长期危害糖尿病患者视力的眼部疾病,如果在患病早期及时发现并进行干预治疗可以有效预防视力损伤防止失明,因此高效准确的眼底疾病自动筛查方法尤为重要。近些年基于深度学习的DR或DME自动筛查方法达到了不错的分级精度,但大多数方法只关注于其中某一种特定疾病,缺乏通用性,并且往往模型参数过大导致不易于训练和临床应用。更重要的是大部分方法都没有去直面医疗数据
传统的推荐算法通过分析用户和物品之间的交互数据建模用户对物品的偏好。受限于交互数据的稀疏,这类模型可能无法从数据中学到足够多的信息来准确的建模用户偏好。为了应对这种情况,学者们将用户和物品相关的其他信息加入推荐算法中作为交互数据的补充,社交网络推荐就是通过增加用户在社交领域中的信息来缓解交互数据稀疏问题的一类方法。目前大多数利用用户社交信息的推荐算法都只是利用了社交数据中用户和用户的直接社交关系信