使用按位运算符在很长的字符串中查找子字符串的最快(并行？)方法是什么？
例如在人类基因组 http://hgdownload.cse.ucsc.edu/goldenPath/hg18/bigZips/hg18.2bit (770MB) 中找到“GCAGCTGAAAACA”序列的所有位置
*字母表由 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
有关的:
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
最佳答案
如果您只是查看文件，则几乎可以保证您是 io 绑定(bind)的。使用大缓冲区(~16K)和 strstr() 应该是你所需要的。如果文件以 ascii 编码，则只搜索 "gcagctgaaaaca" 。如果它实际上是按位编码的；只需置换可能接受的字符串(应该有~8；去掉第一个字节)，并使用 memmem() 加上一个微小的重叠位检查。
我会在这里注意到 glibc strstr 和 memmem 已经使用 Knuth-Morris-Pratt 在线性时间内进行搜索，因此请测试该性能。可能会让你大吃一惊。
关于c - 使用按位运算符的快速字符串搜索，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8876026/