摘要： 针对中英文混合文本的匹配准确性及大规模数据文本的匹配效率等问题，基于经典的线索化完全哈希特里树算法，提出一种并行化的中英文混合多模式文本匹配算法。采用拆分文本降低多模式匹配算法的串行度，进而在拆分出的小文本上并行地执行文本匹配。通过并行化预处理过程，设计新的存储结构。实验结果表明，该算法在保证结果正确的前提下，执行效率高于经典的串行匹配算法，当数据规模达到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)

中图分类号: 

• TP393.08