Boyer–Moore BM 后缀匹配算法 |
您所在的位置:网站首页 › bm算法字符串匹配题目 › Boyer–Moore BM 后缀匹配算法 |
前言
这几年一直在it行业里摸爬滚打,一路走来,不少总结了一些python行业里的高频面试,看到大部分初入行的新鲜血液,还在为各样的面试题答案或收录有各种困难问题 于是乎,我自己开发了一款面试宝典,希望能帮到大家,也希望有更多的Python新人真正加入从事到这个行业里,让python火不只是停留在广告上。 微信小程序搜索:Python面试宝典 或可关注原创个人博客:https://lienze.tech 也可关注微信公众号,不定时发送各类有趣猎奇的技术文章:Python编程学习 Boyer–MooreBoyer–Moore算法是一种在O(n)时间复杂度内的字符串匹配算法,简称BM算法,是一种后缀匹配算法,在你计算机使用中随处可见,比如你常使用的ctrl+f 这个算法的核心灵魂是,当每次匹配失败时,将尽可能多的向前位移,而不是逐个进行字符匹配判断,那样还是有点蠢的 在绝大多数场合的性能表现,Boyer–Moore算法比KMP算法还要出色,而KMP算法和BM算法,它们分别是前缀匹配和后缀匹配的经典算法 BM算法在移动模式串的时候是从左到右,而进行比较的时候是从右到左的 比如这样一段文本与一段匹配词 很明显,这是一次失败的匹配,虽然是从开头,一旦触发了失败的匹配,那么BM算法将遵循两种规则进行匹配词的位移判断,尽可能多的跳过不需要匹配的文本 这两种规则,就是人尽皆知的好后缀规则与坏后缀规则 坏后缀 坏后缀的理解非常简单,当匹配到的字符,不与当前位置的文本相符,那么这就是一个坏后缀,比如这里的话 又或者下面这样例子中的e a b c d e f a b c e好后缀 那么好后缀也是相当的简单去理解,当从末尾开始,当前位置的字符与文本相符,那么这就是一个好后缀 比如 a (b) {c d} e f w (y) {c d}那么c d就是一个好后缀,而y则是一个坏后缀 理解了好后缀与坏后缀之后,那么接下来欣赏一下BM算法在遇到好后缀与坏后缀时的处理规则 或者坏后缀与好后缀同时遇到时候的规则 坏后缀 如果遇到了一个坏后缀,那么会有如下两种情况 在整个匹配词中,坏后缀对应位置的匹配文本都没有出现,那么将直接跳过这一段匹配文本,从当前坏后缀的下一个位置开始进行重新匹配比如 a b c {d} e x x x x w y z {f}匹配文本w y z f的坏后缀f对应的d匹配字符,并没有出现在w y z f中,那么这将直接跳过a b c d 也就是将直接从e处继续进行匹配 a b c d e x x x x w y z f 如果坏后缀对应的匹配文本出现在了匹配词前面的位置,那么以该字符进行对齐按照最一开始的图示,当匹配虽然是一个坏后缀时 但是,我们发现,匹配对应的文本宝出现在了匹配词的第一个位置,那么将位移宝至文本中的宝进行对齐 坏后缀移动规则 稍微品一品坏后缀的两种移动方式,不难得出如下的移动规略 匹配词的移动位数 = 后缀索引 - 坏后缀对应文本在匹配词中出现的索引位置 如果坏后缀对应的文本并未出现在匹配词中,那么此时对应的位置为-1 回顾一下之前的匹配动作,比如 a b c {d} e x x x x w y z {f}那么发现d文本并未出现在匹配词中,那么匹配词将位移 3(坏后缀索引) - -1(未出现在匹配词中) = 4(最终位移结果数量) 再比如出现在匹配词中的情况 a b c {d} e x x x x w {d} z {f}那么发现d文本出现在了w d z f中,那么首先可以确定坏后缀对应文本在匹配词中的位置是1(索引从0开始) 得出位移结果 3(坏后缀索引) - 1 = 2, 此时w d z f将向后位移2 a b c {d} e x x x x w {d} z f好后缀 知道了坏后缀的处理规则,那么再来看一下好后缀的方式,和坏后缀类似,匹配到的好后缀文本是否出现在匹配词中,分为两种情况 当匹配到的文本未出现在之前的匹配词中比如 a b {c d} e x x x x w y {c d}此时文本中的c d与匹配词的末尾c d匹配,这称的上是一个好后缀,但是c d只在末尾出现,未出现在匹配词其余部位,那么,类似坏后缀的同样规则,这将直接向后跳过整段匹配文本 a b c d e x x x x w y c d 当匹配到的文本出现在了匹配词中 a b c d e x x x x d e c d ed e好后缀出现在了开头起点,那么此时将以这样的好后缀对齐 a b c d e x x x x d e c d e好后缀位移规则 再来稍微品一品好后缀的两种移动方式,不难得出如下的移动规略 匹配词的移动位数 = 后缀索引 - 坏后缀对应文本在匹配词中出现的索引位置 如果坏后缀对应的文本并未出现在匹配词中,那么此时对应的位置为-1 比如第一种,好后缀对应文本未出现在匹配词中,此时好后缀取最后的索引,也就是3 a b {c d} e x x x x w y {c d}此时,对应坏后缀文本c d未出现在匹配词中,那么将位移 3(好后缀最后索引) - -1(未出现在匹配词中) = 4 结果就是,直接向后移动4 a b c d e x x x x w y c d第二种,好后缀对应文本出现在了匹配词中 a (b) {c d e} x x x x d (e) {c d e}出现在匹配词中的索引位置为3,那么按照规则,将位移 3(好后缀索引) - 0(出现在匹配词的第一个) = 3 a b c d e x x x x d e c d e品一品,是不是非常的简单 同时具有好后缀,坏后缀 至此,明白了BM算法,那么还有一种情况需要我们考虑 a (b) {c d e} x d (e) {c d e}这里的好后缀为c d e、坏后缀为b 那么也可以按照好后缀,也可以按照坏后缀的方式进行移动,这又该如何抉择呢? 这就要遵循Boyer-Moore算法的基本思想:每次后移这两个规则之中的较大值 这里的好后缀d e,遵循出现在匹配词的规则 位移数量为3 3(后缀索引) - 0(出现在匹配词的第一个) = 3 a b c d e x d e c d e而坏后缀的文本b,遵循坏后缀中未出现在匹配词的规则 位移数量为 1(后缀索引) - -1(未出现在匹配词中) = 2 a b c d e x d e c d e结果已经显而易见 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |