一种改进Boyer-Moore算法效率的预处理算法

• 作者: 宋恩民 金人超
• 来源期刊: 华中科技大学学报（自然科学版）
• 学科: 工学
• 关键词: DNA序列 字符串 图案匹配 Boyer-Moore算法
• 年，卷（期）: 2005,（z1）
• 所属期刊栏目: 数据库与信息检索
• 页码范围: 265-267
• 页数: 3页
• 分类号: Q751|TP391|TP399
• 字数: 3094字
• 语种: 中文
• DOI: 10.3321/j.issn:1671-4512.2005.z1.074

摘要

通过理论分析和测试发现,对大多数字符串而言,按某个方向搜索文本总是会比按另一个方向的搜索速度快.提出了新的预处理算法,在使用Boyer-Moore算法之前先确定一个较优的搜索方向,其时间复杂度和空间复杂度分别为O(σm)和O(σ+m),其中σ和m分别为字母表的大小和字符串图案的长度.采用真实的人类DNA序列测试,包括序列库中前1 000个长度超过1 000的完整序列作为文本,从中随机选出1 000个长度为20的序列片段作为图案,进行实验对比,证明可以将搜索时间平均缩短到原来的约90%.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	金人超	华中科技大学计算机科学与技术学院	13	117	6.0	10.0
2	宋恩民	华中科技大学计算机科学与技术学院	26	266	8.0	15.0