| 一种并行中英文混合多模式匹配算法 |
| |
| 引用本文： | 王震,李仁发,李彦彪,田峥.一种并行中英文混合多模式匹配算法[J].计算机工程,2014(4):318-320,F0003. |
| |
| 作者姓名： | 王震 李仁发 李彦彪 田峥 |
| |
| 作者单位： | 湖南大学嵌入式与网络计算湖南省重点实验室,长沙410082 |
| |
| 基金项目： | 基金项目：国家自然科学基金资助项目“以汽车为例的CPS若干问题研究”（61173036）. |
| |
| 摘 要： | 针对中英文混合文本的匹配准确性及大规模数据文本的匹配效率等问题,基于经典的线索化完全哈希特里树算法,提出一种并行化的中英文混合多模式文本匹配算法。采用拆分文本降低多模式匹配算法的串行度,进而在拆分出的小文本上并行地执行文本匹配。通过并行化预处理过程,设计新的存储结构。实验结果表明,该算法在保证结果正确的前提下,执行效率高于经典的串行匹配算法,当数据规模达到226个字符时,可以获得8倍以上的加速比。
|
| 关 键 词： | 多模式匹配 中英文混合 特里树 图形处理单元 并行计算 统一计算设备架构 |
A Parallel Multiple Pattern Matching Algorithm on Chinese/English Mixing |
| |
| WANG Zhen,LI Ren-fa,LI Yan-biao,TIAN Zheng.A Parallel Multiple Pattern Matching Algorithm on Chinese/English Mixing[J].Computer Engineering,2014(4):318-320,F0003. |
| |
| Authors: | WANG Zhen LI Ren-fa LI Yan-biao TIAN Zheng |
| |
| Affiliation: | (Key Laboratory for Embedded and Network Computing of Hunan Province, Hunan University, Changsha 410082, China) |
| |
| 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 ofpretreatment 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 2 26. |
| |
| Keywords: | multiple pattem matching Chinese/English mixing Tile tree Graphics Processing Unit（GPU） parallel computing ComputeUnified Device Architecture（CUDA） |
| 本文献已被 CNKI 维普 等数据库收录！ |
|
