Optimizing of large-number-patterns string matching algorithms based on definite-state automata

来源 :哈尔滨工业大学学报(英文版) | 被引量 : 0次 | 上传用户:lustt005
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
Because the small CACHE size of computers, the scanning speed of DFA based multi-pattern stringmatching algorithms slows down rapidly especially when the number of patterns is very large. For solving such problems, we cut down the scanning time of those algorithms (i.e. DFA based) by rearranging the states table and shrinking the DFA alphabet size. Both the methods can decrease the probability of large-scale random memory accessing and increase the probability of continuously memory accessing. Then the hitting rate of the CACHE is increased and the searching time of on the DFA is reduced. Shrinking the alphabet size of the DFA also reduces the storage complication. The AC + + algorithm, by optimizing the Aho-Corasick ( i. e. AC) algorithm using such methods, proves the theoretical analysis. And the experimentation results show that the scanning time of AC + + and the storage occupied is better than that of AC in most cases and the result is much attractive when the number of patterns is very large. Because DFA is a widely used base algorithm in may string matching algorithms, such as DAWG, SBOM etc. , the optimizing method discussed is significant in practice.
其他文献
通过多年多点的高产攻关 ,对不同穗型高产冬小麦产量构成因素进行了研究。结果表明 :大穗型品种 ,栽培的主攻方向是穗重 ,但其分蘖成穗率低 ,应适当增加播种量 ,以获得理想穗
通过优化护理专业的人文教育课程,构建“一个核心、两个优化、三个结合”的人文课程体系,进一步强化和熏陶护生的人文精神和职业素养,效果显著。
本文根据教育部《大学英语课程教学要求》:“大学英语的教学目标是培养学生的英语综合应用能力,特别是听说能力。”分析了当前大学英语听说教学的特点和主要存在的问题,阐述
根据临床康复学的课程特点,在教学上采取“案例教学、合作学习”的教学方式,“角色扮演”的实践方式以及多元化的综合考核方式,能够提高课程的教学效果和学生的实用能力.
语文作为我国文化教育中的一个重要组成部分,它是我国文化的传承载体,是学好其他学科的基础,对于培养人们的阅读能力、思维能力等方面有着重大作用。本文就初中语文的学习方
计算机辅助语言学习始于于20世纪60年代的美国,经过几十年的发展,针对CALL的研究越来越深入,理论基础日渐完善.分析整理CALL最新研究成果不仅有助于对现阶段CALL技术有针对性
学生是有思想的、灵动的生命体,所以在课堂教学中,常会发生这样那样的意外。教师除了要完成既定的教学目标,还要处理课堂中的一些突发事件,对一些意外生成进行科学的引导,而
采用工业纯铁中间层,在非真空、无保护气氛条件下,进行1.6%C-UHCS/40Cr的超塑性焊接试验.试验结果表明,采用工业纯铁中间层能提高1.6%C-UHCS/40Cr超塑性焊接接头界面塑性变形能
Orthogonal frequency division multiplexing (OFDM) systems encounter performance degradations because of the time-varying (TV) channels common in wireless enviro
Detection coverage control is one of the most important topics in the intrusion detection problem of wireless sensor networks (WSN). However, its converse, i.e.