| 一种改进Boyer-Moore算法效率的预处理算法 |
| |
| 引用本文： | 金人超,宋恩民. 一种改进Boyer-Moore算法效率的预处理算法[J]. 华中科技大学学报(自然科学版), 2005, 33(Z1): 265-267 |
| |
| 作者姓名： | 金人超 宋恩民 |
| |
| 作者单位： | 华中科技大学,计算机科学与技术学院,湖北,武汉,430074 |
| |
| 摘 要： | 通过理论分析和测试发现,对大多数字符串而言,按某个方向搜索文本总是会比按另一个方向的搜索速度快.提出了新的预处理算法,在使用Boyer-Moore算法之前先确定一个较优的搜索方向,其时间复杂度和空间复杂度分别为O(σm)和O(σ m),其中σ和m分别为字母表的大小和字符串图案的长度.采用真实的人类DNA序列测试,包括序列库中前1 000个长度超过1 000的完整序列作为文本,从中随机选出1 000个长度为20的序列片段作为图案,进行实验对比,证明可以将搜索时间平均缩短到原来的约90%.
|
| 关 键 词： | DNA序列 字符串 图案匹配 Boyer-Moore算法 |
| 文章编号： | 1671-4512(2005)S1-0265-03 |
| 修稿时间： | 2005-08-25 |
A pre-processing algorithm for improving efficiency of the Boyer-Moore algorithm |
| |
| Jin Renchao,Song Enmin. A pre-processing algorithm for improving efficiency of the Boyer-Moore algorithm[J]. JOURNAL OF HUAZHONG UNIVERSITY OF SCIENCE AND TECHNOLOGY.NATURE SCIENCE, 2005, 33(Z1): 265-267 |
| |
| Authors: | Jin Renchao Song Enmin |
| |
| Affiliation: | Jin Renchao Song Enmin Assoc.Prof.,College of Computer Sci.& Tech.,Huzhong Univ.of Sci.& Tech.,Wuahn 430074,China. |
| |
| Abstract: | |
| |
| Keywords: | DNA sequence string pattern matching Boyer-Moore algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
