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

Question

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

例如，在人类基因组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

Answer 1

如果你只是在浏览一个文件，你很有可能是受io约束的。使用大缓冲区(~16K)和strstr()应该就足够了。如果文件是用ascii编码的，只搜索"gcagctgaaaaca"。如果它实际上是以位编码的，只需置换可能接受的字符串(应该有~8个；去掉第一个字节)，并使用memmem()加上一个微小的重叠位检查。

在这里，我将注意到glibc strstr和memmem已经使用Knuth-Morris-Pratt在线性时间内进行搜索，因此测试其性能。这可能会让你大吃一惊。

Answer 2

如果您首先使用无损编码方法(例如Huffman、指数Golumb等)对DNA字符串进行编码/压缩然后，您将获得核苷酸的各种组合(例如，A、AA、CA等)的DNA令牌的排序概率表(“编码树”)。

这意味着，一旦你压缩了你的DNA：

1. 您可能会使用更少的位来存储GCAGCTGAAAACA和其他子序列，而不是始终使用每个基数两位的“未编码”方法。
2. 您可以遍历编码树或表来构建编码的搜索字符串，该字符串通常比未编码的搜索字符串更短。
3. 您可以应用相同系列的精确搜索算法(例如，博耶-摩尔)来定位这个较短的编码搜索字符串。

对于并行化方法，将编码的目标字符串拆分为N个块，并使用缩短的编码搜索字符串在每个块上运行搜索算法。通过跟踪每个块的位偏移量，您应该能够生成匹配位置。

总体而言，如果您计划对不会更改的序列数据执行数百万次搜索，这种压缩方法将非常有用。你会搜索更少的比特--总体上可能会少得多。

Answer 3

Boyer-More是一种用于在普通字符串中搜索子字符串的技术。基本思想是，如果您的子字符串有10个字符，您可以查看字符串中位置9的字符进行搜索。如果该字符不是搜索字符串的一部分，则只需在该字符之后开始搜索。(如果该字符确实在字符串中，则Boyer-More算法使用查找表跳过向前的最佳字符数。)

也许可以将这个想法重用于基因组字符串的打包表示。毕竟，只有256个不同的字节，所以您可以安全地预先计算跳表。