首页 / 算法 / 字符串与模式匹配算法（五）：BMH算法

字符串与模式匹配算法（五）：BMH算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了字符串与模式匹配算法（五）：BMH算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5161字，纯文字阅读大概需要8分钟。

内容图文

一、BMH算法介绍

　　在BM算法的实际应用中，坏字符偏移函数的应用次数要远远超过好后缀偏移函数的应用次数，坏字符偏移函数在匹配过程中起着移动指针的主导作用。在实际匹配过程，只是用坏字符偏移函数也非常有效。1980年，奈杰尔·豪斯普（Nigel Horspool）提出了改进的BM算法，也就是BMH算法。简化了BM算法，执行非常方便，效率也很可观。Boyer-Moore算法使用两种策略来确定不匹配模式的位移：坏字符策略和高端策略。 来自Horspool的想法是仅使用坏字符策略，而不使用导致不匹配的字符，而始终使用文本窗口的正确字符。

二、主要思想

　　Horspool建议仅使用窗口最右边字符的坏字符移位来计算Boyer-Moore算法中的移位。例如：

　　(a) Boyer-Moore

0123456789...
a b c a b d a a c b a
b c a a b            
  b c a a b          

　　(b) Horspool

0123456789...
a b c a b d a a c b a
b c a a b            
        b c a a b    

　　观察是上面两个不同算法的例子，后缀ab匹配，比较c-a表示不匹配。 Boyer-Moore算法（a）根据最后一次出现c的坏字符位置的策略确定滑动距离。 Horspool算法（b）根据最后一次出现的b来确定滑动距离，其中在模式的最后位置出现的b不计算在内。

　　同样在Horspool算法中，最有利的情况是，如果每次第一次比较都发现一个文本字符，而该字符根本不在模式中出现。 然后，该算法仅需要O（n / m）个比较。

　　坏字符策略所需的出现函数occ与Boyer-Moore算法中的计算略有不同。 对于每个字母字符a，occ（p，a）是它在p0 ... pm-2中最后一次出现的位置；如果根本不出现该字符，则为-1。 因此，不会考虑该模式的最后一个字符pm-1。

三、BMH算法代码

Horspool算法所用到的坏字符策略

 1     /**
 2      * 坏字符策略
 3      */
 4     private void horspoolInitocc() {
 5         int j;
 6         char a;
 7 
 8         for (a = 0; a < alphabetSize; a++)
 9             occ[a] = -1;
10 
11         for (j = 0; j < m - 1; j++) {
12             a = p[j];
13             occ[a] = j;
14         }
15     }

　　分析：预处理阶段为O(m + σ)时间复杂度和O（σ）空间复杂度。

Horspool算法的搜索函数

 1     /**
 2      * Horspool算法的搜索函数
 3      */
 4     private void horspoolSearch() {
 5         int i = 0, j;
 6         while (i <= n - m) {
 7             j = m - 1;
 8             while (j >= 0 && p[j] == t[i + j]) j--;
 9             if (j < 0) report(i);
10             i += m - 1;
11             i -= occ[t[i]];
12         }
13     }

　　搜索阶段具有二次最坏情况，但是可以证明，一个文本字符的平均比较数在1σ 和 2 /（σ+ 1）之间。

四、总结

　　BM算法中的坏字符策略对于σ比较小的来说不是很有效，但适合当σ与模式的长度相比比较大时。当ASCII表和在文本编辑器下进行的常规搜索一样BMH变得非常有用。在实践中，单独使用它会产生非常有效的算法。 Horspool建议仅使用窗口最右边字符的坏字符移位来计算Boyer-Moore算法中的移位。

源代码：

字符串与模式匹配算法（五）：BMH算法 - 文章图片字符串与模式匹配算法（五）：BMH算法 - 文章图片 
  1 package algorithm;
  2 
  3 public class Horspool {
  4     private static int alphabetSize = 256;
  5     private char[] p, t;        // 模式，文本
  6     private int m, n;           // 模式的长度，文本的长度
  7     private int[] occ;          // 记录文本字符在模式中的位置
  8     private String matches;     // 匹配位置
  9     private char[] showmatches; // 显示匹配的字符数组
 10 
 11     public Horspool() {
 12         occ = new int[alphabetSize];
 13     }
 14 
 15     public void search(String tt, String pp) {
 16         setText(tt);
 17         setPatten(pp);
 18         horspoolSearch();
 19     }
 20 
 21     /**
 22      * 设置文本
 23      *
 24      * @param tt
 25      */
 26     private void setText(String tt) {
 27         n = tt.length();
 28         t = tt.toCharArray();
 29         initMatches();
 30     }
 31 
 32     /**
 33      * 设置模式
 34      *
 35      * @param pp
 36      */
 37     private void setPatten(String pp) {
 38         m = pp.length();
 39         p = pp.toCharArray();
 40         horspoolInitocc();
 41     }
 42 
 43     /**
 44      * 坏字符策略
 45      */
 46     private void horspoolInitocc() {
 47         int j;
 48         char a;
 49 
 50         for (a = 0; a < alphabetSize; a++)
 51             occ[a] = -1;
 52 
 53         for (j = 0; j < m - 1; j++) {
 54             a = p[j];
 55             occ[a] = j;
 56         }
 57     }
 58 
 59     /**
 60      * Horspool算法的搜索函数
 61      */
 62     private void horspoolSearch() {
 63         int i = 0, j;
 64         while (i <= n - m) {
 65             j = m - 1;
 66             while (j >= 0 && p[j] == t[i + j]) j--;
 67             if (j < 0) report(i);
 68             i += m - 1;
 69             i -= occ[t[i]];
 70         }
 71     }
 72 
 73     /**
 74      * 初始化匹配位置该显示的数组
 75      */
 76     private void initMatches() {
 77         matches = "";
 78         showmatches = new char[n];
 79         for (int i = 0; i < n; i++) {
 80             showmatches[i] = ' ';
 81         }
 82     }
 83 
 84     /**
 85      * 匹配报告
 86      *
 87      * @param i
 88      */
 89     private void report(int i) {
 90         matches += i + " ";
 91         showmatches[i] = '^';
 92     }
 93 
 94     /**
 95      * 搜索后返回匹配位置
 96      *
 97      * @return
 98      */
 99     public String getMatches() {
100         return matches;
101     }
102 
103     /**
104      * BMH测试主函数
105      *
106      * @param args
107      */
108     public static void main(String[] args) {
109         Horspool horspool = new Horspool();
110         String tt, pp;
111         tt = "abcdabcd";
112         pp = "abc";
113         horspool.search(tt, pp);
114         System.out.println(pp);
115         System.out.println(tt);
116         System.out.println(horspool.showmatches);
117         System.out.println(horspool.getMatches());
118     }
119 }
View Code

内容总结

以上是互联网集市为您收集整理的字符串与模式匹配算法（五）：BMH算法全部内容，希望文章能够帮你解决字符串与模式匹配算法（五）：BMH算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/665274.html

来源：【匿名】