4

我有一个零和一的线性列表，我需要匹配多个简单模式并找到第一个匹配项。例如，我可能需要在长度为 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!
            }
        }
    }
}

编辑：顺便说一句，我已经按照上面的伪代码实现了这个程序，性能还可以，但没什么了不起的。我估计我在处理器的单个内核上每秒处理大约 600 万位。我用它来处理图像，它必须处理几千张 8 兆像素的图像，所以每一点都有帮助。

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

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

该算法预处理正在搜索的目标字符串（键），而不是正在搜索的字符串（与一些预处理要搜索的字符串然后可以通过重复搜索来分摊预处理费用的算法不同）。

这看起来很有趣，但它没有给出此类算法的任何示例。类似的东西也会有帮助吗？

4

7 回答 7

11

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

早在 1975 年，Aho 和 Corasick就发布了一种（线性时间）算法，该算法用于fgrep. 该算法随后被许多研究人员改进。例如，Commentz-Walter (1979)将 Aho&Corasick 与Boyer&Moore匹配结合起来。Baeza-Yates (1989)将 AC 与Boyer-Moore-Horspool变体相结合。Wu and Manber (1994)做了类似的工作。

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

我建议从阅读 Aho-Corasick 和 Rabin-Karp 维基百科页面开始，然后确定这对您的情况是否有意义。如果是这样，也许您的语言/运行时已经有一个可用的实现。

于 2009-08-09T02:57:47.707 回答
4

是的。

Boyer-Moore 字符串搜索算法

另请参阅：Knuth–Morris–Pratt 算法

于 2009-08-09T02:23:34.597 回答
2

您可以构建一个SuffixArray并搜索运行时是疯狂的：O（长度（模式））。但是..您必须构建该数组。只有当 Text 是 static 并且 pattern 是 dynamic 时才值得。

于 2009-08-09T02:24:44.377 回答
1

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

  1. 将模式存储在trie数据结构中
  2. 开始搜索列表
  3. 检查下一个pattern_length字符是否在 trie 中，成功时停止（ O(1) 操作）
  4. 第一步 char 并重复 #3

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

于 2009-08-09T03:24:03.703 回答
0

如果您的字符串需要灵活，我还建议根据 Mitch Wheat 修改“Boyer–Moore 字符串搜索算法”。如果您的字符串不需要灵活，您应该能够进一步折叠模式匹配。Boyer-Moore 模型对于搜索大量数据以查找要匹配的多个字符串之一非常有效。

雅各布

于 2009-08-09T02:43:15.737 回答
0

如果它只是交替 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 秒才能找到 1000 万个字符中三个目标的最早匹配项。当然，由于我使用的是随机文本，因此每次运行都会有所不同。

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

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

于 2009-08-09T02:59:14.227 回答
0

如果它是一个位数组，我想做一个滚动求和会是一个改进。如果 pattern 是 length n，则将第一位n相加，并查看它是否与模式的总和相匹配。始终存储总和的第一位。然后，对于每个下一位，从总和中减去第一位并添加下一位，看看总和是否与模式的总和相匹配。这将节省模式上的线性循环。

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

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

于 2009-08-09T03:49:06.273 回答