| 一种分布式后缀树构造与匹配算法 |
| |
| 引用本文： | 黄政林,张冰.一种分布式后缀树构造与匹配算法[J].华中科技大学学报(自然科学版),2012(Z1):219-224. |
| |
| 作者姓名： | 黄政林 张冰 |
| |
| 作者单位： | 深圳大学计算机与软件学院 |
| |
| 基金项目： | 深圳市科技研发资金基础研究基金资助项目(JC201005280459A) |
| |
| 摘 要： | 提出一种基于消息传递模式的分布式后缀树构造算法(DPSTG)及相应的并行匹配算法.DPSTG算法按不同的字符将原始字符串的后缀树分解成若干个子后缀树后由多个处理器并行构造.处理器间通过消息传递方式连接各个子后缀树,匹配时首先将要查找的字符串分割成若干不同首字符的子字符串,然后在构造相应首字符子后缀树的处理器上实现多个子字符串的并行匹配.理论分析表明DPSTG算法的时间复杂度要优于现有的大多数后缀树并行生成算法.模拟实验结果表明DPSTG算法的并行加速比随着待处理字符串的长度增加而提高.
|
| 关 键 词： | 后缀树 后缀树生成 字符串匹配 并行算法 高性能计算 |
A distributed suffix tree generation and matching algorithm |
| |
| Huang Zhenglin Zhang Bing.A distributed suffix tree generation and matching algorithm[J].JOURNAL OF HUAZHONG UNIVERSITY OF SCIENCE AND TECHNOLOGY.NATURE SCIENCE,2012(Z1):219-224. |
| |
| Authors: | Huang Zhenglin Zhang Bing |
| |
| Institution: | Huang Zhenglin Zhang Bing(College of Computer and Software,Shenzhen University,Shenzhen 518060,Guangdong China) |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 CNKI 等数据库收录！ |
