使用按位运算符进行快速字符串搜索

Question

使用按位运算符在非常长的字符串中查找子字符串的最快(并行？)方法是什么？

例如,在人类基因组中查找"GCAGCTGAAAACA"序列的所有位置http://hgdownload.cse.ucsc.edu/goldenPath/hg18/bigZips/hg18.2bit(770MB)

*字母表由4个符号组成('G','C',T,'A'),用2位表示:'G':00,'A':01,'T':10,'C':11

*您可以假设查询字符串(较短的字符串)的长度是固定的,例如127个字符

*最快我的意思是不包括任何预处理/索引时间

*文件将在预处理后加载到内存中,基本上会在更大的字符串中搜索数十亿个短字符串,全部在内存中.

*按位,因为我正在寻找最简单,最快速的方法来搜索大型阵列中的位模式,并尽可能保持与硅的接近.

*由于字母表很小,KMP不会很好用

*C代码,x86机器代码都很有趣.

输入格式说明(.2bit):http://jcomeau.freeshell.org/www/genome/2bitformat.html

有关:

扫描位流中位模式的最快方法

算法帮助!使用其伙伴搜索字符串的快速算法

http://www.arstdesign.com/articles/fastsearch.html

http://en.wikipedia.org/wiki/Bitap_algorithm

Answer 1

如果您只是浏览一个文件,那么您几乎可以保证受到限制.使用大缓冲区(~16K),strstr()应该是您所需要的.如果文件是用ascii编码的,那么只搜索"gcagctgaaaaca".如果它实际上是以位编码的; 只是置换可能接受的字符串(应该有~8;丢掉第一个字节),并使用memmem()加上一个微小的重叠位检查.

我会在这里注意到glibc strstr并且memmem已经使用Knuth-Morris-Pratt来搜索线性时间,因此测试性能.它可能会让你大吃一惊