如何并行化一个长字符串的正则表达式搜索？

Question

我正在测试模拟的输出,看它是否在某个时刻进入循环,所以我需要知道输出是否重复.例如,可能有400个数字,然后是400000个数字周期.输出仅包含0-9的数字.我有以下正则函数,我用来匹配单个长字符串中的重复:

def repetitions(s):
    r = re.compile(r"(.+?)\1+")
    for match in r.finditer(s):
        if len(match.group(1)) > 1 and len(match.group(0))/len(match.group(1)) > 4:
            yield (match.group(1), len(match.group(0))/len(match.group(1)))

这个功能非常有效,但需要太长时间.我最近的测试是400万位,搜索需要4.5小时.它没有发现重复,所以我现在需要增加搜索空间.代码只关注自身重复次数超过4次的子序列,因为我正在考虑重复5次以给出一个可以手动检查的集合:模拟将生成将重复数百次的子序列.我正在四核机器上运行,要检查的数字是实时生成的.如何提高搜索速度？

Answer 1

根据 nhahtdh 在其他答案之一中提供的信息，一些事情已经浮出水面。

首先，您提出的问题称为寻找“串联重复”或“正方形”。

其次， http://csiflabs.cs.ucdavis.edu/~gusfield/lineartime.pdf中给出的算法在O ( n log n + z ) 时间内找到z串联重复，并且是“最佳”的，因为可以有这么多答案。您也许可以使用并行化串联搜索，但我首先会使用简单的方法进行计时，然后除以 4，看看是否在您期望的速度范围内。

此外，为了使用这种方法，您将需要O ( n ) 空间来存储该后缀树。因此，如果您有大约 400,000 个数字，那么您将需要大约 400,000 时间来构建并存储该后缀树，并需要 400,000 个字节。

我并不完全理解“实时”搜索的含义，我通常认为它是对操作可以花费多长时间的硬性限制。如果是这样的话，那么这里就不会发生这种情况。该算法需要读入整个输入字符串并在开始获取结果之前对其进行处理。从这个意义上说，它就是所谓的“离线”算法。

http://web.cs.ucdavis.edu/~gusfield/strmat.html有 C 代码可供下载。（在tar文件strmat.tar.gz中查找repeats_tandem.c和repeats_tandem.h）。

鉴于上述情况，如果该算法不够快或空间效率不够，我会寻找改变或缩小问题范围的方法。也许您只需要固定数量的答案（例如最多 5 个）？如果循环是程序中执行语句的结果，考虑到编程语言（汇编语言除外）没有任意的“goto”语句，则这可能会缩小可能发生的循环类型，并以某种方式使用该结构的研究可能会提供一种加快速度的方法。