线性模式匹配算法？

Question

我有一个零和一个线性列表，我需要匹配多个简单模式并找到第一个匹配项。例如，我可能需要在长度为800万的列表中找到0001101101，01010100100或OR 10100100010。我只需要找到其中的第一个，然后返回它发生的索引。但是，在大型列表中进行循环和访问可能很昂贵，我宁愿不要这么做太多次。

难道还有比这样做

foreach (patterns) { 
    for (i=0; i < listLength; i++) 
     for(t=0; t < patternlength; t++) 
      if(list[i+t] != pattern[t]) { 
       break; 
      } 
      if(t == patternlength - 1) { 
       return i; // pattern found! 
      } 
     } 
    } 
} 

编辑更快的方法： BTW，我按照上面的伪代码已经实施了这一计划，并表现还算可以，但没有壮观。我估计我在处理器的单个内核上每秒处理约600万比特。我正在使用它进行图像处理，它将不得不经过几千个8百万像素的图像，所以每一点点都会有所帮助。

编辑：如果不清楚，我正在使用一个位数组，所以只有两种可能性：ONE和ZERO。它在C++中。

编辑：感谢指针BM和KMP算法。我注意到，对于BM维基百科页面上，它说

算法预处理正被搜索 目标 字符串（键），但不是在字符串中被搜索 （不像某些算法 预处理要搜索的字符串 ，然后可以通过重复搜索 来分摊预处理费用 ）。

这看起来很有趣，但它没有给出任何这样的算法的例子。这样的事情也会有帮助吗？

Answer 1

为谷歌搜索的关键是“多模式”的字符串匹配。

回到1975年，Aho and Corasick发表了一个（线性时间）算法，它在原始版本fgrep中使用。该算法随后被许多研究人员改进。例如，Commentz-Walter (1979)合并Aho & Corasick与Boyer&Moore匹配。 Baeza-Yates (1989)结合AC与Boyer-Moore-Horspool变体。 Wu and Manber (1994)做了类似的工作。

多模式匹配算法的AC线的替代方案是Rabin and Karp's算法。

我建议先阅读Aho-Corasick和Rabin-Karp维基百科页面，然后决定在你的情况下是否有意义。如果是这样，那么可能已经有可用的语言/运行时的实现。

Answer 2

是的。

The Boyer–Moore string search algorithm

参见：Knuth–Morris–Pratt algorithm

Answer 3

你可以建立一个SuffixArray和搜索的运行时间是疯了：O（长度（模式））。 但是..你必须建立这个数组。 当文本是静态的并且模式动态时，它是唯一值得的。

Answer 4

如果你的字符串需要灵活一些，我还会推荐一个修改后的“The Boyer-Moore string search algorithm”，按照Mitch Wheat。如果你的字符串不需要灵活，你应该可以折叠更多的模式匹配。 Boyer-Moore模型对于搜索大量数据以匹配多个字符串中的一个来说非常高效。

雅各

Answer 5

如果它只是交替0和1，那么将文本编码为运行。 n 0的运行是-n并且n 1的运行是n。然后编码你的搜索字符串。然后创建一个使用编码字符串的搜索功能。

的代码看起来是这样的：

try: 
    import psyco 
    psyco.full() 
except ImportError: 
    pass 

def encode(s): 
    def calc_count(count, c): 
     return count * (-1 if c == '0' else 1) 
    result = [] 
    c = s[0] 
    count = 1 
    for i in range(1, len(s)): 
     d = s[i] 
     if d == c: 
      count += 1 
     else: 
      result.append(calc_count(count, c)) 
      count = 1 
      c = d 
    result.append(calc_count(count, c)) 
    return result 

def search(encoded_source, targets): 
    def match(encoded_source, t, max_search_len, len_source): 
     x = len(t)-1 
     # Get the indexes of the longest segments and search them first 
     most_restrictive = [bb[0] for bb in sorted(((i, abs(t[i])) for i in range(1,x)), key=lambda x: x[1], reverse=True)] 
     # Align the signs of the source and target 
     index = (0 if encoded_source[0] * t[0] > 0 else 1) 
     unencoded_pos = sum(abs(c) for c in encoded_source[:index]) 
     start_t, end_t = abs(t[0]), abs(t[x]) 
     for i in range(index, len(encoded_source)-x, 2): 
      if all(t[j] == encoded_source[j+i] for j in most_restrictive): 
       encoded_start, encoded_end = abs(encoded_source[i]), abs(encoded_source[i+x]) 
       if start_t <= encoded_start and end_t <= encoded_end: 
        return unencoded_pos + (abs(encoded_source[i]) - start_t) 
      unencoded_pos += abs(encoded_source[i]) + abs(encoded_source[i+1]) 
      if unencoded_pos > max_search_len: 
       return len_source 
     return len_source 
    len_source = sum(abs(c) for c in encoded_source) 
    i, found, target_index = len_source, None, -1 
    for j, t in enumerate(targets): 
     x = match(encoded_source, t, i, len_source) 
     print "Match at: ", x 
     if x < i: 
      i, found, target_index = x, t, j 
    return (i, found, target_index) 


if __name__ == "__main__": 
    import datetime 
    def make_source_text(len): 
     from random import randint 
     item_len = 8 
     item_count = 2**item_len 
     table = ["".join("1" if (j & (1 << i)) else "0" for i in reversed(range(item_len))) for j in range(item_count)] 
     return "".join(table[randint(0,item_count-1)] for _ in range(len//item_len)) 
    targets = ['0001101101'*2, '01010100100'*2, '10100100010'*2] 
    encoded_targets = [encode(t) for t in targets] 
    data_len = 10*1000*1000 
    s = datetime.datetime.now() 
    source_text = make_source_text(data_len) 
    e = datetime.datetime.now() 
    print "Make source text(length %d): " % data_len, (e - s) 
    s = datetime.datetime.now() 
    encoded_source = encode(source_text) 
    e = datetime.datetime.now() 
    print "Encode source text: ", (e - s) 

    s = datetime.datetime.now() 
    (i, found, target_index) = search(encoded_source, encoded_targets) 
    print (i, found, target_index) 
    print "Target was: ", targets[target_index] 
    print "Source matched here: ", source_text[i:i+len(targets[target_index])] 
    e = datetime.datetime.now() 
    print "Search time: ", (e - s) 

在一根绳子上的两倍，只要你提供的，它需要大约7秒内找到的三个目标的最早的比赛，10万个字。当然，因为我使用随机文本，每次运行都会有所不同。

psyco是一个用于在运行时优化代码的python模块。使用它可以获得很好的性能，并且可以估计这是C/C++性能的上限。这是最近的表现：

Make source text(length 10000000): 0:00:02.277000 
Encode source text: 0:00:00.329000 
Match at: 2517905 
Match at: 494990 
Match at: 450986 
(450986, [1, -1, 1, -2, 1, -3, 1, -1, 1, -1, 1, -2, 1, -3, 1, -1], 2) 
Target was: 1010010001010100100010 
Source matched here: 1010010001010100100010 
Search time: 0:00:04.325000 

大约需要300毫秒来编码1000万个字符，大约4秒要搜索3个编码字符串。我不认为C/C++中的编码时间会很长。

Answer 6

一个解决方案，可能是有效的：

1. 存放在trie数据结构模式
2. 开始搜索列表
3. 检查，如果接下来的pattern_length字符是在特里，停止成功（O（1）操作）
4. 第1步char和repeat＃3

如果列表不可变，您可以存储匹配模式的偏移量以避免下次重复计算。

Answer 7

如果它是一个有点阵列，我想滚动总和会是一个改进。如果模式长度为n，则首先对第一个n位进行求和，并查看它是否与模式的和相匹配。总是保存总和的第一位。然后，对于每个下一位，从总和中减去第一位并添加下一位，并查看总和是否与模式的总和相符。这将节省模式上的线性循环。

看起来像BM算法并不像它看起来那么棒，因为在这里我只有两个可能的值，零和一，所以第一个表并没有帮助很多。第二张桌子可能会有所帮助，但这意味着BMH几乎毫无价值。

编辑：在我睡眠不足的状态下，我无法理解BM，所以我只是实现了这个滚动总和（这非常简单），它使我的搜索速度提高了3倍。感谢谁提到“滚动哈希”。现在，我可以在5.45秒内（这是单线程）搜索321,750,000位的两个30位模式，而之前是17.3秒。