使用位运算实现快速字符串搜索

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 相关： 在比特流中扫描位模式的最快方法 算法帮助！快速搜索具有其伙伴的字符串的算法

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

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

- alex

---

搜索 Boyer-Moore、KMP。 - Mitch Wheat

为什么要使用位运算符？位运算符可以在处理数字时执行一些高效的操作，例如掩码、位检查和位设置。此外，它们还可用于优化某些算法和数据结构。因此，在编写需要高效数字处理的程序时，使用位运算符可能是必要的。 - Michael Mior

数据是否使用每个字符2位进行记录？如果不是，那么观察到字母表仅由4个字符组成没有任何好处（或者至少我想不出任何好处）。 - Jonathan Leffler

嗯..如果这个文件被打包成2位元素，应该有一些方法可以优化搜索，以便使用32/64位比较来消除大部分搜索位置，只留下少数需要通过按位比较进一步检查的位置？对一个或两个文件进行一些预处理？不确定。 - Martin James

如何使用16位查找表，以搜索字符串中的16位值为索引，返回与扫描字符串的前16位匹配开始的位位置（如果有）。 如果返回0-15，则您知道要移位下一个16位以继续验证匹配。 - Martin James

Answer 1

如果您只是查看文件，那么您几乎可以保证会遇到io限制。使用大缓冲区（~16K）和strstr()即可满足需求。如果文件使用ascii编码，请仅搜索"gcagctgaaaaca"。如果实际上是使用位编码，则只需排列可能接受的字符串（应该有~8个；去掉第一个字节），并使用memmem()加上一个微小的重叠位检查。

我在这里指出glibc strstr和memmem已经使用Knuth-Morris-Pratt算法以线性时间搜索，因此请测试其性能。这可能会让您感到惊讶。

- Dave

Answer 2

如果您使用无损编码方法（如Huffman、指数Golumb等）对DNA字符串进行编码/压缩，那么您将得到一个DNA标记的排名概率表（"编码树"），其中包括各种核苷酸组合（例如A，AA，CA等）。

这意味着一旦您压缩了DNA，您将：

1. 存储GCAGCTGAAAACA和其他子序列所需的位数可能比每个碱基始终使用两个位数的“未编码”方法更少。 2. 您可以遍历编码树或表来构建一个已编码的搜索字符串，该字符串通常会比未编码的搜索字符串更短。 3. 您可以将相同类型的精确搜索算法（例如Boyer-Moore算法）应用于查找这个较短、已编码的搜索字符串。

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

总的来说，如果您计划对不会改变的序列数据进行数百万次搜索，这种压缩方法将非常有用。您将搜索更少的位数-在总体上可能少得多。

- Alex Reynolds

Answer 3

Boyer-More是一种用于在普通字符串中搜索子字符串的技术。其基本思想是，如果您的子字符串长度为10个字符，则可以查看要搜索的字符串中位置为9的字符。如果该字符不属于您的搜索字符串，则可以直接从该字符后面开始搜索。（如果该字符确实在您的字符串中，Boyer-More算法会使用查找表跳过最优数量的字符。）对于基因组字符串的压缩表示，重复利用此思想可能是可行的。毕竟，只有256个不同的字节，因此可以安全地预先计算跳过表。

- Lindydancer

Answer 4

将字母表编码为位域的好处在于紧凑性：一个字节可以容纳四个字符的等效信息。这类似于 Google 在搜索单词时执行的一些优化。

这表明有四个并行执行，每个执行都将（转换后的）搜索字符串偏移一个字符（两个位）。一个快速而简单的方法可能是只查找搜索字符串的第一个或第二个字节，然后在匹配其余字符串之前检查额外的字节，在必要时屏蔽掉末尾。第一个搜索可以方便地使用 x86 指令 scasb 完成。随后的字节匹配可以使用 cmpb 建立寄存器值。

- wallyk

Answer 5

你可以创建一个状态机。在这个主题中，从大量文本中提取成千上万个简单模式的快速算法，我使用 [f]lex 为我创建了状态机。使用 4 个字母（:= 两位）字母表需要一些技巧，但是可以使用与 [f]lex 生成的相同的表格来完成。 （您甚至可以创建自己的 fgetc() 函数，该函数从输入流中每次提取两个位，并保留连续调用的其他六个位。回推会更难，但不是不可能的）。

顺便说一句：我严重怀疑将数据压缩到每个核苷酸的两个位中是否有任何收益，但这是另一回事。

- wildplasser

Answer 6

好的，根据您的参数，这个问题并不难，只是不像传统的字符串搜索问题那样处理。它更像是一个数据库表连接问题，其中表比RAM大得多。

• 选择一个好的滚动哈希函数，也称为buzhash。如果您有数十亿个字符串，则需要使用具有64位值的哈希。

• 基于每个127元素搜索字符串创建哈希表。内存中的表只需要存储（哈希、字符串ID），而不是整个字符串。

• 扫描您非常大的目标字符串，计算滚动哈希并查找哈希表中的每个哈希值。每当有匹配时，将（字符串ID、目标偏移量）对写入流中，可能是文件。

• 重新读取目标字符串和对流，根据需要加载搜索字符串以在每个偏移量处与目标进行比较。

我假设一次性将所有模式字符串加载到内存中是禁止的。有一些方法可以将哈希表分段成比RAM大但不是传统的随机访问哈希文件的东西；如果您感兴趣，请搜索“混合哈希”和“grace哈希”，这在数据库世界中更为常见。

我不知道这是否值得你的努力，但是你的配对流提供了完美的预测输入来管理一组模式字符串的缓存 - Belady经典的虚拟内存页面置换算法。

- Mischa