使用按位运算符进行快速字符串搜索
|
使用按位运算符在非常长的字符串中查找子字符串的最快(并行？)方法是什么？
例如在人类基因组中查找“GCAGCTGAAAACA”序列的所有位置http://hgdownload.cse.ucsc.edu/goldenPath/hg18/bigZips/hg18.2bit(770MB) *字母表由4个符号组成(‘G’,’C’,T,’A’),用2位表示： *您可以假设查询字符串(较短的字符串)的长度是固定的,例如127个字符 *最快我的意思是不包括任何预处理/索引时间 *文件将在预处理后加载到内存中,基本上会在更大的字符串中搜索数十亿个短字符串,全部在内存中. *按位,因为我正在寻找最简单,最快速的方法来搜索大型阵列中的位模式,并尽可能保持与硅的接近. *由于字母表很小,KMP不会很好用 * C代码,x86机器代码都很有趣. 输入格式说明(.2bit)：http://jcomeau.freeshell.org/www/genome/2bitformat.html 有关： Fastest way to scan for bit pattern in a stream of bits Algorithm help! Fast algorithm in searching for a string with its partner http://www.arstdesign.com/articles/fastsearch.html http://en.wikipedia.org/wiki/Bitap_algorithm 解决方法
如果您只是浏览一个文件,那么您几乎可以保证受到限制.应该使用大缓冲区(~16K)和strstr().如果文件以ascii编码,则只搜索“gcagctgaaaaca”.如果它实际上是以位编码的;只是置换可能接受的字符串(应该有~8;丢掉第一个字节),并使用memmem()加上一个微小的重叠位检查.
我会在这里注意到glibc strstr和memmem已经使用Knuth-Morris-Pratt来搜索线性时间,所以测试一下这个性能.它可能会让你大吃一惊 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |