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

A pre-processing algorithm for improving efficiency of the Boyer-Moore algorithm

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

The original Boyer-Moore algorithm can be easily adjusted to match the pattern in the alternative direction.Theoretical analysis and experiments showed that for most string patterns,matching a pattern in one direction is always more efficient than in other direction for almost all texts.A pre-processing algorithm with time complexity O(σm) and space complexity O(σ+m) was proposed,where σ and m are the size of the alphabet and the length of the pattern respectively.The novel algorithm determines an optimal matching direction by examining the pattern only and then uses the Boyer-Moore algorithm in the optimal direction to match the pattern.In the experiments,1000 DNA sequences from a human gene database with each length being more than 1000 were chosen as the texts,then 1000 sequence segments with each length being 20 were randomly chosen from these sequences as the patterns.The results showed that the proposed algorithm can averagely reduce the time of pattern matching to 90?% of that of the original algorithm.