首页 文章

线性模式匹配算法？

提问于
浏览 次
4

我有一个零和一的线性列表，我需要匹配多个简单的模式，并找到第一个出现 . 例如，我可能需要在长度为800万的列表中找到 0001101101 ， 01010100100 ，或 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!
            }
        }
    }
}

Edit: 顺便说一下，我已按照上面的伪代码实现了这个程序，性能还可以，但没什么了不起的 . 我用这个来进行图像处理，它必须要经过几千万像素的图像，所以每一点点都有帮助 .

Edit: 如果's not clear, I' m使用位数组，那么C中有's only two possibilities: ONE and ZERO. And it' s .

Edit: 感谢指向BM和KMP算法的指针 . 我注意到，在BM的维基百科页面上，它说

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

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

algorithm language-agnostic pattern-matching

7 回答

  • 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)

    在你提供的字符串的两倍长度上，找到1000万个字符中三个目标的最早匹配大约需要7秒钟 . 当然，由于我使用的是随机文本，因此每次运行都会有所不同 .

    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的编码时间会很长 .

    回复于
  • 1

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

    • 将模式存储在trie数据结构中

    • 开始搜索列表

    • 检查下一个 pattern_length 字符是否在trie中，停止成功（O（1）操作）

    • 步骤一个char并重复＃3

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

    回复于
  • 11

    如果它是一个阵列，我想做一个滚动的总和将是一个改进 . 如果pattern的长度为 n ，则将第一个 n 位求和，并查看它是否与模式's sum. Store the first bit of the sum always. Then, for every next bit, subtract the first bit from the sum and add the next bit, and see if the sum matches the pattern'的总和相匹配 . 这样可以在模式上保存线性循环 .

    看起来BM算法并不像它看起来那样令人敬畏，因为在这里我只有两个可能的值，零和一，所以第一个表并没有帮助很多 . 第二个表可能有所帮助，但这意味着BMH几乎毫无 Value .

    Edit: 在我睡眠不足的状态下，我不能单线程），而之前的17.3秒 .

    回复于
  • 0

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

    早在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维基百科页面，然后决定这是否适用于你的情况 . 如果是这样，也许已经存在可用于您的语言/运行时的实现 .

    回复于
  • 0

    你可以构建一个SuffixArray并搜索运行时是疯狂的：O（长度（模式）） . 但是......你必须构建那个数组 . 当Text是静态的并且模式是动态的时候，它是值得的 .

    回复于
  • 4
    回复于
  • 2

    如果您的字符串需要灵活，我还建议根据Mitch Wheat修改“The Boyer-Moore字符串搜索算法” . 如果您的字符串不需要灵活，您应该能够折叠您的模式匹配甚至更多 . Boyer-Moore的模型非常有效地搜索大量数据以匹配多个字符串中的一个 .

    雅各

    回复于

相关问题