计算机工程

• 开发研究与工程应用 • 上一篇    

一种并行中英文混合多模式匹配算法

王 震,李仁发,李彦彪,田 峥   

  1. (湖南大学嵌入式与网络计算湖南省重点实验室,长沙 410082)
  • 收稿日期:2013-03-27 出版日期:2014-04-15 发布日期:2014-04-14
  • 作者简介:王 震(1988-),男,硕士,主研方向:网络安全,并行计算,GPU通用计算;李仁发,教授、博士生导师;李彦彪、田 峥,博士。
  • 基金项目:
    国家自然科学基金资助项目“以汽车为例的CPS若干问题研究”(61173036)。

A Parallel Multiple Pattern Matching Algorithm on Chinese/English Mixing

WANG Zhen, LI Ren-fa, LI Yan-biao, TIAN Zheng   

  1. (Key Laboratory for Embedded and Network Computing of Hunan Province, Hunan University, Changsha 410082, China)
  • Received:2013-03-27 Online:2014-04-15 Published:2014-04-14

摘要: 针对中英文混合文本的匹配准确性及大规模数据文本的匹配效率等问题,基于经典的线索化完全哈希特里树算法,提出一种并行化的中英文混合多模式文本匹配算法。采用拆分文本降低多模式匹配算法的串行度,进而在拆分出的小文本上并行地执行文本匹配。通过并行化预处理过程,设计新的存储结构。实验结果表明,该算法在保证结果正确的前提下,执行效率高于经典的串行匹配算法,当数据规模达到226个字符时,可以获得8倍以上的加速比。

关键词: 多模式匹配, 中英文混合, 特里树, 图形处理单元, 并行计算, 统一计算设备架构

Abstract: Concerning the classical Threaded Hash Trie(THT) tree algorithm, a parallel multiple pattern matching on Chinese/English mixed texts algorithm is proposed for the accuracy of mixed Chinese and English text matching and the low efficiency of large-scale data text matching. The program splits the text into a number of small texts, and runs THT algorithm to match them. It is further accelerated by parallelization of pretreatment process and new storage structure. Experimental results indicate that the method is correct and more effective than classical algorithm, and can get more than 8 times speedup ratio when the data scale reaches 226.

Key words: multiple pattern matching, Chinese/English mixing, Trie tree, Graphics Processing Unit(GPU), parallel computing, Compute Unified Device Architecture(CUDA)

中图分类号: