【2013-11-19】【转】字符串匹配的Boyer-Moore算法

[历史归档]本文原发布于 cstriker1407.info 个人博客内容为历史存档仅供参考。发布时间2013-11-19 标题【转】字符串匹配的Boyer-Moore算法分类编程 / 数据结构与算法 标签算法·Boyer-Moore算法【转】字符串匹配的Boyer-Moore算法文档信息本文转自http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html上一篇文章我介绍了KMP算法。但是它并不是效率最高的算法实际采用并不多。各种文本编辑器的查找功能CtrlF大多采用Boyer-Moore算法。Boyer-Moore算法不仅效率高而且构思巧妙容易理解。1977年德克萨斯大学的Robert S. Boyer教授和J Strother Moore教授发明了这种算法。下面我根据Moore教授自己的例子来解释这种算法。假定字符串为HERE IS A SIMPLE EXAMPLE搜索词为EXAMPLE。首先字符串与搜索词头部对齐从尾部开始比较。这是一个很聪明的想法因为如果尾部字符不匹配那么只要一次比较就可以知道前7个字符整体上肯定不是要找的结果。我们看到S与E不匹配。这时**“S就被称为坏字符”bad character即不匹配的字符。**我们还发现S不包含在搜索词EXAMPLE之中这意味着可以把搜索词直接移到S的后一位。依然从尾部开始比较发现P与E不匹配所以P是坏字符。但是P包含在搜索词EXAMPLE之中。所以将搜索词后移两位两个P对齐。我们由此总结出**“坏字符规则”**后移位数 坏字符的位置 - 搜索词中的上一次出现位置如果坏字符不包含在搜索词之中则上一次出现位置为 -1。以P为例它作为坏字符出现在搜索词的第6位从0开始编号在搜索词中的上一次出现位置为4所以后移 6 - 4 2位。再以前面第二步的S为例它出现在第6位上一次出现位置是 -1即未出现则整个搜索词后移 6 - (-1) 7位。依然从尾部开始比较E与E匹配。比较前面一位LE与LE匹配。比较前面一位PLE与PLE匹配。比较前面一位“MPLE与MPLE匹配。**我们把这种情况称为好后缀”good suffix即所有尾部匹配的字符串。**注意“MPLE”、“PLE”、“LE”、E都是好后缀。比较前一位发现I与A不匹配。所以“I是坏字符”。根据坏字符规则此时搜索词应该后移 2 - -1 3 位。问题是此时有没有更好的移法我们知道此时存在好后缀。所以可以采用**“好后缀规则”**后移位数 好后缀的位置 - 搜索词中的上一次出现位置举例来说如果字符串ABCDAB的后一个AB是好后缀。那么它的位置是5从0开始计算取最后的B的值在搜索词中的上一次出现位置是1第一个B的位置所以后移 5 - 1 4位前一个AB移到后一个AB的位置。再举一个例子如果字符串ABCDEF的EF是好后缀则EF的位置是5 上一次出现的位置是 -1即未出现所以后移 5 - (-1) 6位即整个字符串移到F的后一位。这个规则有三个注意点1好后缀的位置以最后一个字符为准。假定ABCDEF的EF是好后缀则它的位置以F为准即5从0开始计算。2如果好后缀在搜索词中只出现一次则它的上一次出现位置为 -1。比如EF在ABCDEF之中只出现一次则它的上一次出现位置为-1即未出现。3如果好后缀有多个则除了最长的那个好后缀其他好后缀的上一次出现位置必须在头部。比如假定BABCDAB的好后缀是DAB、“AB”、“B”请问这时好后缀的上一次出现位置是什么回答是此时采用的好后缀是B它的上一次出现位置是头部即第0位。这个规则也可以这样表达如果最长的那个好后缀只出现一次则可以把搜索词改写成如下形式进行位置计算(DA)BABCDAB即虚拟加入最前面的DA。回到上文的这个例子。此时所有的好后缀MPLE、PLE、LE、E之中只有E在EXAMPLE还出现在头部所以后移 6 - 0 6位。可以看到坏字符规则只能移3位好后缀规则可以移6位。所以Boyer-Moore算法的基本思想是每次后移这两个规则之中的较大值。更巧妙的是这两个规则的移动位数只与搜索词有关与原字符串无关。因此可以预先计算生成《坏字符规则表》和《好后缀规则表》。使用时只要查表比较一下就可以了。继续从尾部开始比较“P与E不匹配因此P是坏字符”。根据坏字符规则后移 6 - 4 2位。从尾部开始逐位比较发现全部匹配于是搜索结束。如果还要继续查找即找出全部匹配则根据好后缀规则后移 6 - 0 6位即头部的E移到尾部的E的位置。完文档信息版权声明自由转载-非商用-非衍生-保持署名 | Creative Commons BY-NC-ND 3.0原文网址http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html最后修改时间2013年11月 5日 10:21付费支持[](https://me.alipay.com/ruanyf) | [](https://www.paypal.com/cgi-bin/webscr?cmd_xclickbusinessyifeng.ruangmail.comcurrency_codeUSDamount0.99returnhttp://www.ruanyifeng.com/thank.htmlitem_nameRuan%20YiFeng’s%20Blogundefined_quantity1no_note0)