如何优化非常长的字符串的子串查找？

Question

有一个实例：http://www.angio.net/pi/piquery
作用是在Pi的小数点后两亿位中查找某段数字开始出现的位置，
比如输入123456，他告诉我们123456出现在小数点后2458885位
一个很经典的字符串子串查找算法，一般用Boyer–Moore或者KMP毫无压力，难点应该在于数据量比较大，原来的父串特别长。
它已经实现了，就比较好奇它背后的原理，两亿位数字差不多800M，虽然放内存也可以，但是否可以运用数据库来辅助存储？现在pi已经算到了两万亿都不止了（10^13），能够运用数据库意味着数据库的集群化也可以使用了。。(当然也没有人会无聊到用这么大的集群放个这么小的功能吧)

Answer 1

人家对如何做的有说明的好不，http://www.angio.net/pi/how.html

Answer 2

首先两亿数字为啥会有800M呢，即使用比较蠢的19位数字一组用一个bigint表示，2亿数字也只有80M。

其次如果问题真的只是收束在大字符串的子串，那么数据库（尤其是关系型）肯定是不合适的。

至于怎么加速，我是个算法渣，连你说的B-M我的只知道丫是个算法而已，但这类问题的加速，重要的问题往往超越了算法的范畴。

优化必须合理，如果你的字符串不长，那么别优化。优化也是一步步来。我们前面提了2亿数字也才80M，但即使是80M的内存线型访问也是一件傻逼的事情，尤其是我们的问题压根就只有字符串查找。那么字典太厚，一页页翻太傻逼的时候我们怎么查单词呢？不外乎通过索引嘛。

现在我们来建索引： 1出现在位置1，2出现在位置多少，... 123456出现在位置2458885。因为2亿这个数字int装的下，一个索引4字节，假设我们就单台机器划1个G的空间来放索引，那么这种原始的没有任何优化的查表法可以支持到1~268435456的pi子串查找问题，如果实际需求的范围差不多到这里，那这就够了。

嗯，假设我们可以坏一点通过拉长pi的位数/输入子串位数，或者实际一点要求查找的数据不是性质良好的一串数字而是二进制的随机数据，那原始的索引很快也会碰到单台机器的内存瓶颈，这时候就需要进一步优化，比如试图压缩索引的尺寸，比如优化索引的结构，索引本身慢慢膨胀可能会需要通过多次查表，也就是给索引建索引……

优化一阵子以后，假设问题越来越坏，索引已经巧妙地压缩了体积，结构也已经优化到瓶颈，单机还是顶不住，这时候才应该考虑集群化

结论

• 查找问题的优化首先是优化数据结构（比如存pi千万别傻乎乎地存txt），也就是简化问题本身，降低问题本身的数据量
• 其次是索引，根据问题来建立合适的索引，并视需要优化
• 最后才是集群化

瞧，集群化之前就有那么多可以做的了，要集群化，那问题更多更多了，恕我没法简明易懂地全讲一遍

Answer 3

用后缀自动机。只要你有办法存下那么长的数，就可以用2倍的空间存下SAM。

Answer 4

用后缀数组这种数据结构预处理原串后，可以在 O(M+logN) 的时间内查找任意子串的位置，n 是原串的长度，m 是子串的长度。

Answer 5

最简单的方法就是把这两亿位分块（例如5位为一块）建立倒排索引，然后每次匹配一个块。剩余的一些位再暴力匹配就好。

Answer 6

如果要对一个长串进行多次的不同子串的查找，无疑对长串建立索引是最好的做法。基于字符的索引由好多，上面由同学提到的后缀数组就是不错的结构。但后缀数组的空间效率很低。在后缀数组的基础上做改进后的FM索引，压缩后缀数组索引都能实现和后缀数组一样的查询时间复杂度O(m+logn)，而空间可以做到很大的改善，并且，是自索引的，也就是说索引建立后就可以删除原文本了，用索引本身就能进行查询，也可以恢复出原串。FM索引有论文可以做到原文本0.4倍大小，压缩后缀数组可以做到0.7倍左右。但压缩后缀数组时间效率更高。

ps：你提出的问题的研究领域主要是生物信息学，该学科最基本的一个问题就是在超过2G的(人类)DNA序列上进行小子串(一般不会超过1000个字符)搜索，而且是大规模的搜索，一次测序可能产生数百万个断序列，并且，这种搜索还要支持模糊搜索，短序列有四五个变异太正常了。。