线性模式匹配算法？

Question

我有一个0和1的线性列表,我需要匹配多个简单模式并找到第一个出现.例如,我可能需要寻找0001101101,01010100100,或10100100010长度800万的名单之内.我只需要找到第一个出现的,然后返回它发生的索引.但是,对大型列表进行循环和访问可能很昂贵,而且我宁愿不要这么做太多次.

有没有比做更快的方法

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万比特.我正在使用它进行图像处理,它必须经过几千万像素的图像,所以每一点都有帮助.

编辑:如果不清楚,我正在使用一个数组,所以只有两种可能:ONE和ZERO.它是在C++中.

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

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

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

Answer 1

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

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

交叉线多模式匹配算法的替代方案是Rabin和Karp算法.

我建议首先阅读Aho-Corasick和Rabin-Karp维基百科页面,然后决定这是否适用于你的情况.如果是这样,也许已经存在可用于您的语言/运行时的实现.

Answer 2

是的。

\n\n

Boyer\xe2\x80\x93Moore 字符串搜索算法

\n\n

另请参阅：Knuth\xe2\x80\x93Morris\xe2\x80\x93Pratt 算法

\n