期刊文献+

基于Sunday算法的改良单模式匹配算法 被引量:3

Improved single pattern matching algorithm based on Sunday algorithm
下载PDF
导出
摘要 Unicode编码的中文环境下应用Sunday算法时,如直接使用中文字符生成失效跳转表,将造成空间膨胀,而将中文字符拆分为两个字节进行处理,虽可以降低空间消耗,但匹配的执行速度又会受影响。针对Sunday算法应用于Unicode编码的字符拆分环境时所产生的时间性能降低问题,结合Unicode中文单元的内部关联性,优化了原Sunday算法的辅助跳转表与匹配规则,从而在解决Unicode下算法空间膨胀问题的同时,提升了Sunday算法在此环境下的时间性能,并利用模拟实验对改良算法的时间与空间性能进行了实验证明。 When Sunday algorithm is applied into the Chinese version of Unicode, there are some problems. On one hand, it causes the expansion of space if using Chinese characters directly to generate a failed jump table. On the other hand, it can reduce the space consumption at the cost of matching speed when Chinese characters are split into two bytes. Concerning the degradation of time performance produced by applying Sunday algorithm to the character-splitting environment of Chinese version of Unicode, in combination with internal relevance of Chinese unit in Unicode, the improved algorithm in this paper optimized the auxiliary jump table and matching rules in original Sunday algorithm in the character-splitting environment. Consequently, the proposed algorithm not only solves the problem of space expansion, but also improves time performance of Sunday algorithm in this environment. Finally, the improved time and space performance of the algorithm gets proved via simulation.
出处 《计算机应用》 CSCD 北大核心 2014年第1期208-212,共5页 journal of Computer Applications
基金 科技部科技型中小企业技术创新基金资助项目(10C26215122841)
关键词 模式匹配 UNICODE编码 KMP算法 B—M算法 Sunday算法 pattern matching Unicode encoding Knuth-Morris-Pratt (KMP) algorithm Boyer-Moore (BM) algorithm Sunday algorithm
  • 相关文献

参考文献10

二级参考文献59

共引文献64

同被引文献26

  • 1张娜,侯整风.一种快速的BM模式匹配改进算法[J].合肥工业大学学报(自然科学版),2006,29(7):834-838. 被引量:9
  • 2Fisk M, Varghese G. An Analysis of Fast String Matching Applied to Content-based Forwarding and Intrusion Detection, CS2001-0670 [ R]. San Diego, USA : University of California,2002.
  • 3Antonatos S, Anagnostakis K G, Markatos E P. Generating Realistic Workloads for Network Intrusion Detection Systems [ C ]//Proceedings of ACM Workshop on Software and Performance. New York, USA: ACM Press ,2004:207-215.
  • 4Boyer R S, Moore J S. A Fast String Searching Algorithm [ J ]. Communications of the ACM, 1977, 20(10) :762-772.
  • 5Horspool N. Practical Fast Searching in Strings [ J]. Software Practice and Experience, 1980, 20 ( 10 ) : 501-506.
  • 6Sunday D M. A Very Fast Substring Search Algori- thm[J]. Communications of the ACM, 1990,33 (3) : 132-142.
  • 7万晓榆,杨波,樊自甫.改进的Sunday模式匹配算法[J].计算机工程,2009,35(7):125-126. 被引量:13
  • 8单懿慧,蒋玉明,田诗源.面向入侵检测的改进BMHS模式匹配算法[J].计算机工程,2009,35(24):170-173. 被引量:13
  • 9刘沛骞,冯晶晶.一种改进的BM模式匹配算法[J].计算机工程,2011,37(17):248-249. 被引量:10
  • 10杨子江,聂瑞华.一种快速的单模式匹配算法[J].华南师范大学学报(自然科学版),2013,45(5):31-35. 被引量:2

引证文献3

二级引证文献10

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部