浅谈数据结构-Boyer-Moore算法

时间:2023-02-01 04:04:24

上文讲解了KMP算法,这种算法在字符串匹配中应用比较少,在各种文本编辑器中的查找功能大多采用Boyer-Moore算法。1977年,德克萨斯大学的Robert S. Boyer教授和J Strother Moore教授发明了这种算法。

浅谈数据结构-Boyer-Moore算法

算法讲解

浅谈数据结构-Boyer-Moore算法

开始:假定字符串为"HERE IS A SIMPLE EXAMPLE",搜索词为"EXAMPLE"。

浅谈数据结构-Boyer-Moore算法

1、首先,"字符串"与"搜索词"头部对齐,从尾部开始比较。如果尾部字符不匹配,那么只要一次比较,就可以知道前7个字符(整体上)肯定不是要找的结果。

"S"与"E"不匹配。这时,"S"就被称为"坏字符"(bad character),即不匹配的字符。我们还发现,"S"不包含在搜索词"EXAMPLE"之中,这意味着可以把搜索词直接移到"S"的后一位。

浅谈数据结构-Boyer-Moore算法

2、依然从尾部开始比较,发现"P"与"E"不匹配,所以"P"是"坏字符"。但是,"P"包含在搜索词"EXAMPLE"之中。所以,将搜索词后移两位,两个"P"对齐。

浅谈数据结构-Boyer-Moore算法

3、由此总结出"坏字符规则"

后移位数 = 坏字符出现时搜索词的坐标值 - 坏字符在搜索词位置

以"P"为例,它作为"坏字符",出现在搜索词的第6位(从0开始编号)即开始时从尾部开始比较,就出现不匹配(E),“P”是坏字符在搜索词中的出现位置为4,所以后移 6 - 4 = 2位。再以前面第二步的"S"为例,它出现在第6位,上一次出现位置是 -1(即未出现),则整个搜索词后移 6 - (-1) = 7位。

浅谈数据结构-Boyer-Moore算法

4、从尾部开始比较,"E"与"E"匹配。

浅谈数据结构-Boyer-Moore算法

5、前面一位,"PLE"与"PLE"匹配

浅谈数据结构-Boyer-Moore算法/

6、比较前面一位,"MPLE"与"MPLE"匹配。我们把这种情况称为"好后缀"(good suffix),即所有尾部匹配的字符串。注意,"MPLE"、"PLE"、"LE"、"E"都是好后缀。

浅谈数据结构-Boyer-Moore算法

7、比较前一位,发现"I"与"A"不匹配。所以,"I"是"坏字符"。坏字符规则",此时搜索词应该后移 2 - (-1)= 3 位。

浅谈数据结构-Boyer-Moore算法

我们知道,此时存在"好后缀"。所以,可以采用"好后缀规则"

后移位数 = 好后缀的位置 - 搜索词中的上一次出现位置

举例来说,如果字符串"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位。

浅谈数据结构-Boyer-Moore算法

8/可以看到,"坏字符规则"只能移3位,"好后缀规则"可以移6位。所以,Boyer-Moore算法的基本思想是,每次后移这两个规则之中的较大值。

更巧妙的是,这两个规则的移动位数,只与搜索词有关,与原字符串无关。因此,可以预先计算生成《坏字符规则表》和《好后缀规则表》。使用时,只要查表比较一下就可以了。

浅谈数据结构-Boyer-Moore算法

继续从尾部开始比较,"P"与"E"不匹配,因此"P"是"坏字符"。根据"坏字符规则",后移 6 - 4 = 2位.

浅谈数据结构-Boyer-Moore算法

从尾部开始逐位比较,发现全部匹配,于是搜索结束。如果还要继续查找(即找出全部匹配),则根据"好后缀规则",后移 6 - 0 = 6位,即头部的"E"移到尾部的"E"的位置。

文档摘自:阮一峰的网络日志

浅谈数据结构-Boyer-Moore算法的更多相关文章

  1. [随机化算法] 听天由命?浅谈Simulate Anneal模拟退火算法

    Simulate Anneal模拟退火算法,是一种用于得到最优解的随机化算法. 如果可以打一手漂亮的随机化搜索,也许当你面对一筹莫展的神仙题时就有一把趁手的兵器了. 这篇题解将教你什么?SA的基本思路 ...

  2. Boyer Moore算法(字符串匹配)

    上一篇文章,我介绍了KMP算法. 但是,它并不是效率最高的算法,实际采用并不多.各种文本编辑器的"查找"功能(Ctrl+F),大多采用Boyer-Moore算法. Boyer-Mo ...

  3. Java学习笔记——浅谈数据结构与Java集合框架(第一篇、List)

    横看成岭侧成峰,远近高低各不同.不识庐山真面目,只缘身在此山中. --苏轼 这一块儿学的是云里雾里,咱们先从简单的入手.逐渐的拨开迷雾见太阳.本次先做List集合的三个实现类的学习笔记 List特点: ...

  4. 浅谈数据结构之KMP(串中的模式匹配算法)

    KMP算法是一种模式匹配算法的改进版,其通过减少匹配的次数以及使主串不回朔来减少字符串匹配的次数,从而较少算法的相应代价,但是,事件万物是普遍归中的,KMP算法的有效性也是有一定的局限的,我将在本文的 ...

  5. Java学习笔记——浅谈数据结构与Java集合框架(第二篇、Queue、Set)

    江南好,何处异京华. 香散翠帘多在水,绿残红叶胜于花.无事避风沙. --<纳兰词> 诗词再好,大图不能忘 上大图: 先说说栈和队列: 栈就好比手枪的弹匣,你往里面压入子弹,最先压入的子弹就 ...

  6. 浅谈数据结构vector

    vector: 又名 向量 1.C++中的一种数据结构. 2.是一个类. 3.相当于一个动态的数组,当程序员无法知道自己需要的数组的规模多大时,用其来解决问题可以达到最大节约空间的目的. A.使用时, ...

  7. 大数质因解:浅谈Miller-Rabin和Pollard-Rho算法

    2017-07-19 08:54 Amphetamine:能发一下代码吗? 应我那位谜一样好友的邀约,我打算好好看一看Miller-Rabin和Pollard-Rho算法.很奇怪,各种地方有很多代码描 ...

  8. Java学习笔记——浅谈数据结构与Java集合框架(第三篇、Map)

    桃李春风一杯酒,江湖夜雨十年灯 --寄黄几复 之前图上写错了,是Hashtable类.t是小写的,它是个很古老的类,以至于命名都没有那么规范.. HashMap HashMap就是存储key-valu ...

  9. 浅谈算法和数据结构&colon; 七 二叉查找树 八 平衡查找树之2-3树 九 平衡查找树之红黑树 十 平衡查找树之B树

    http://www.cnblogs.com/yangecnu/p/Introduce-Binary-Search-Tree.html 前文介绍了符号表的两种实现,无序链表和有序数组,无序链表在插入的 ...

随机推荐

  1. ubuntu 配置nginx&plus;php&plus;mysql 遇到的一些问题

    /* 公司内网打算配置一台ubuntu为主机的测试服务器.刚好手头有一个昂达的主机,装的windows 声音又大,还不如直接装ubuntu .声音又小,还占用资源少. */ 刚开始安装php5 结果提 ...

  2. Android课程---关于ListView列表视图的学习

    activity_ui3.xml <?xml version="1.0" encoding="utf-8"?> <ListView xmlns ...

  3. Xml Schema的用途

    Xml Schema的用途 1.  定义一个Xml文档中都有什么元素 2.  定义一个Xml文档中都会有什么属性 3.  定义某个节点的都有什么样的子节点,可以有多少个子节点,子节点出现的顺序 4.  ...

  4. HDU 3183 A Magic Lamp

    直接模拟   如果后一位比前一位小,那就一直 向前 pop()掉 维护他单调递增: #include<iostream> #include<cstring> #include& ...

  5. 【转载】php程序员:从1&period;5K到18K 一个程序员的5年成长之路

    昨天收到了心仪企业的口头offer, 回首当初什么都不会开始学编程, 到现在恰好五年. 整天在社区晃悠, 看了不少的总结, 在这个时间点, 我也写一份自己的总结吧. 我一直在社区分享, 所以, 这篇总 ...

  6. U盘安装Ubuntu kylin版

    初试U盘安装Ubuntu14.04 kylin版  等待Ubuntu14.04 kylin版出来后,一直想要尝试在物理机进行安装体验,恰巧碰到五一假期,因为咱是穷人,没钱出去玩,所以就有了时间实地进行 ...

  7. C&num; 4&period;0 的 Visual Studio 2010 示例

    C# 4.0 的 Visual Studio 2010 示例 我们将 C# 示例分为两种不同的类别: 语言示例 LINQ 示例 语言示例 语言示例帮助您熟悉各种 C# 语言功能.这些示例包含在 Lan ...

  8. 小妖精的完美游戏教室——人工智能,A&ast;算法,导航网络篇

    //================================================================//// Copyright (C) 2017 Team Saluk ...

  9. mongodb分组排序

    @Override public MessageDto getCheckInMembersByFlight(String fltDt, String fltNr, String channel,Str ...

  10. 在tomcat8&period;0&period;x和tomcat9&period;0&period;x之间么突然冒出个tomcat 8&period;5

    Apache Tomcat 8 (8.5.38) - Documentation Indexhttps://tomcat.apache.org/tomcat-8.5-doc/index.html to ...