Boyer Moore 字符串搜索算法之 JavaScript 实现

最近碰到的一个需求需要借助字符串的快速搜索算法,于是看了一些有关字符串搜索的一些算法,最先看的是 KMP 算法,看完之后发现还有更优的算法,那就是 Boyer Moore 算法。编辑器的文本搜索、GNU 的 grep 都有使用 Boyer Moore 算法,那么效率应该是经过权威验证的。

虽然网上有不少介绍资料,但我还是从一个算法小白所理解的算法原理来尝试解析该算法,算法大神可绕道了。

从头至尾搜索一个字符串,看这个被搜索的字符串是否包含指定的子串,有则返回其位置,没有则返回 -1,相当于使用自己的算法来实现 JavaScript 中的 String.prototype.indexOf 的功能。

在接下来的讲解中使用 text 来代指被搜索的字符串,pattern 代指用于搜索的子串。

先来看第一个例子:

Boyer Moore 算法的匹配方式是从 pattern 的末尾开始的,如果 pattern 的末尾和 text 不匹配,那么就可以判定它们不匹配。

图一中 pattern 的字符「e」和 text 中的「s」不匹配,那么将 pattern 往右移,移多少位呢?上面说了 Boyer Moore 算法的匹配是从末尾匹配的,由于末尾起的第一个字符就不匹配,并且 text 对应的「s」也没有出现在 pattern 中,那么在「s」之前的所有字符串肯定都是不匹配的,此时将 pattern 往右移动到其开始位置刚好在 text 中的「s」之后。

在图二中 pattern 已经右移到了 text 中的「s」之后,此时仍然从末尾开始匹配,text 中的「p」与 pattern 中的「e」不匹配。但是 text 中的「p」有在 pattern 出现过,这是可能匹配的特征之一,那么此时将 pattern 继续往右移,这个时候从图中很直观的可以看出,pattern 应该尝试将自己包含的「p」与 text 中的刚刚进行匹配的「p」对齐,那么 pattern 应该向右移动 2 位才能确保「p」刚好对齐。

这种位移规则总结起来就是坏字符规则,坏字符是相对于 text 来说的,当从末尾开始匹配时发现 text 中的字符和 pattern 不匹配,那么 text 中不匹配的那个字符就是坏字符。匹配到坏字符时,要检查坏字符是否有在 pattern 中出现过,如果没有出现过,那么得将 pattern 位移到坏字符之后,如果出现过,那么位移的位数就是将 pattern 中出现的字符与 text 中的坏字符对齐。

那如果坏字符在 pattern 中出现过多次呢,该以哪个为准?因为匹配顺序是从末尾开始的,也可以说是从右往左,那么其出现的位置也应该从右往左开始查找,第一个(最右)的就是。这种查找规则就是 lastIndexOf 的查找规则。

坏字符移动位数的计算规则就是:

  • 移动位数 = pattern 匹配到坏字符的位置 - 坏字符在 pattern 中的位置

如果坏字符没有在 pattern 出现过,那么其位置就是 -1。根据以上的规则,图一中 pattern 匹配到坏字符的位置对应的字符是「e」,坏字符并未在 pattern 中出现过,那么移动位数就是「e」的位置 6 - (-1),为 7。
到了图二, pattern 匹配到坏字符的位置对应的字符仍然是「e」,坏字符出现的位置为 4,那么移动位数就是「e」的位置 6 - 4,为 2。

根据坏字符规则再来看另一个例子:

直接从第二步开始看,text 中的坏字符「b」与 pattern 最右边的「b」匹配上了,如果按照坏字符规则的计算,那么其计算结果为 1 - 2,为 -1,移动位置往左移动了一位,这不科学啊,不可能往左移,那么如果碰到这种往左移的情况就可以保守的将 pattern 往右移 1 位即可。

再回到第一个例子,此时应该往右移动 2 位。

继续从末尾开始匹配,发觉其中的「mple」都能正好匹配,而如果继续匹配的话,text 中的「i」和 pattern「a」是不匹配的。按照坏字符的计算,其移动位置应该是「a」的位置 2 - (-1),为 3,「i」并未在 pattern 中出现过。

因为上面有提到「mple」都能正好匹配,是否存在更好的位移规则呢。「mple」正好能匹配,那么称其为好后缀,好后缀是相对于 pattern 来说的,从图中可以隐隐的看出貌似有更好的位移规则。继续往下推导。

对于一个字符串来说,除了第一个字符以外,其后所有字符的组合都能称其为后缀。拿 example 来说,就会有后缀「xample」「ample」「mple」「ple」「le」「e」, pattern 和 text 从末尾开始匹配,匹配上的都称为好后缀。那么对于好后缀来说,该如何移动呢?

图五中,假如末尾了 4 个后缀,那么是否可以尝试将其移动 4 位呢?答案是肯定的,方式一就是位移结果,慢着好像还有更好的方法。「mple」在 pattern 整个后缀并没有再次出现过,而如果将 pattern 按照好后缀进行拆分后就成为了「exa」和「mple」,而「exa」和「mple」根本无法完全匹配,那么从图中直观的来看 pattern 和 text 并没有一个能相互对应上的位置。上面提到过「e」也是后缀,并且其包含在「mple」中,那么此时将左边的「e」移动到原来右边的「e」所在的位置,此时 pattern 和 text 有相互对应的关系,图五种的方式二比方式一可以多移 2 位,更优,并且这种位移方法也是切实可行的。

坏字符的位移比较容易看懂,而好后缀的位移规则可能要复杂些。对于好后缀「mple」来说,其可以再分解成 3 个「ple」「le」「e」,这样子分解后会发觉只有「e」在 pattern 有重复出现过,如果好后缀在这样分解后发觉某个好后缀有重复出现过,那么此时的位移就以重复出现过的好后缀为准。如果分解后的好后缀还没有在 pattern 种出现过,只能退而求其次,按照方式一来移动。

假如 pattern 为 bcabab 恰好其好后缀是「ab」,而「ab」还可以拆分成「b」,此时到底以哪个好后缀为准呢?其实这种情况下,不管是「ab」还是「b」为准,其位移的位数都是一样的。

那么来总结下好后缀的位移的计算规则:

  • 移动位数 = 好后缀在 pattern 中出现的位置 - 好后缀在 pattern 中的重复出现的位置

其重复出现的位置也和坏字符的位置规则一样从右往左开始找,第一个(最右)就是。

那么什么时候该使用好后缀,什么时候该用好后缀?这要看两种规则,哪种能移动更多的位数。

上面的例子继续往右移,这个时候根据坏后缀规则,仅移动 2 位就能完全匹配了。至此就找出了完全匹配的位置了。

好了,移动的规则都讲完了,那么该直接上代码了,下面是使用 JavaScript 实现该算法的代码:

var boyerMoore = function( content, pattern, fromIndex ){
        var cLen = content.length,
            pLen = pattern.length,
            i = pLen - 1,
            badCharMap = {},
            goodSuffixMap = {},
            index, item, suffix, pre, j;

        fromIndex = fromIndex || i;

        for( ; i > 0; i-- ){
            item = pattern[i];

            // 创建坏字符规则表
            if( badCharMap[item] === undefined ){
                badCharMap[ item ] = i;
            }

            // 创建好后缀规则表
            suffix = pattern.slice( i );
            pre = pattern.slice( 0, i );

            if( suffix.length <= pre.length ){
                for( j = pre.length - 1; j >= 0; j-- ){
                    item = pre.slice( j - suffix.length + 1, j + 1 );

                    if( suffix === item ){
                        if( goodSuffixMap[suffix] === undefined ){
                            goodSuffixMap[suffix] = j - suffix.length + 1;
                        }
                    }
                }
            }
        }

        var search = function( lastIndex ){
            var i = pLen - 1,   // 搜索字符串的索引标记
                j = lastIndex,  // 被搜索字符串的索引标记
                g = 0,  // 标记好后缀的长度
                badChar, goodSuffix, goodSuffixMove, badCharMove, badCharIndex, goodSuffixIndex;

            for( ; i > 0; i-- ){
                badChar = content[j];

                if( badChar === pattern[i] ){
                    g++;
                }
                else{
                    // 需要查找坏字符在搜索词上一次(lastIndexOf从右往左查找)的出现为止
                    badCharIndex = badCharMap[ badChar ];

                    if( badCharIndex === undefined ){
                        badCharIndex = -1;
                    }

                    badCharMove = i - badCharIndex;

                    if( badCharMove <= 0 ){
                        badCharMove = 1;
                    }

                    // 如果存在好后缀,则计算好后缀可以移动的位置
                    if( g ){
                        for( i = g; i > 0; i-- ){
                            goodSuffix = pattern.slice( 0 - i );

                            if( goodSuffix in goodSuffixMap ){
                                goodSuffixIndex = goodSuffixMap[ goodSuffix ];
                                goodSuffixMove = pLen - i - goodSuffixIndex;
                                break;
                            }
                        }

                        if( goodSuffixIndex === undefined ){
                            goodSuffixMove = pLen - g - 1;
                        }

                        // 取坏字符和好后缀规则中移动位数最大者
                        lastIndex += Math.max( goodSuffixMove, badCharMove );
                    }
                    else{
                        lastIndex += badCharMove;
                    }

                /* 测试代码 start
                    console.log( content );

                    for( var i = 0, space = '', len = lastIndex - pLen + 1; i < len; i++ ){
                        space += ' ';
                    }

                    console.log( space + pattern );
                    console.log( lastIndex );
                    console.log( '-----------------------------' );
                    测试代码 end */

                    break;
                }

                j--;
            }

            if( pLen - 1 !== g ){
                // 已到末尾
                if( lastIndex + 1 > cLen ){
                    index = -1;
                }
                // 没到末尾将继续搜索
                else{
                    search( lastIndex );
                }
            }
            // 完全匹配
            else{
                index = lastIndex + 1 - pLen;
            }
        };

        search( fromIndex );
        return index;
    };

    var content = 'here is a simple example';
    var query = 'example';

    var index = boyerMoore( content, query );

    console.log( 'boyerMoore : ' + index );
    console.log( 'indexOf : ' + content.indexOf(query) );

本文算是对 阮一峰 的 字符串匹配的Boyer-Moore算法 补充和具体实现,也是我对 阮一峰 的文章中的算法思想的个人理解。对于坏字符的规则这个容易搞懂,但是好后缀容易搞不明白,他在那篇文章中感觉就在好后缀的计算规则上说的还不够清楚。

扩展阅读:Boyer-Moore字符串搜索算法

Chrome 81 正式发布 !消灭混合内容最后一步~

Chrome 81 于前天正式发布了,这个版本其实最初是计划在 3 月 17 号 发布的,但由于冠状病毒(COVID-19)爆发而导致推迟到了现在。Chrome 81 的延迟也扰乱了 Google 正常的六周发布时间表。因此 Google 此前也宣布,下一个版本将直接跳过 Chrome 82 ,直接发布 Chrome 83。 下面我就来带大家看看 Chrome 81 有哪些重要的更新。

发布于:1月以前  |  121次阅读  |  详细内容 »

当浏览器全面禁用三方 Cookie

苹果公司前不久对 Safari 浏览器进行一次重大更新,这次更新完全禁用了第三方 Cookie,这意味着,默认情况下,各大广告商或网站将无法对你的个人隐私进行追踪。而微软和 Mozilla 等也纷纷采取了措施禁用第三方 Cookie,但是由于这些浏览器市场份额较小,并没有给市场带来巨大的冲击。

发布于:1月以前  |  105次阅读  |  详细内容 »

H5 直播的疯狂点赞动画是如何实现的?

直播有一个很重要的互动:点赞。 为了烘托直播间的氛围,直播相对于普通视频或者文本内容,点赞通常有两个特殊需求: 点赞动作无限次,引导用户疯狂点赞 直播间的所有疯狂点赞,都需要在所有用户界面都动画展现出来(广播用户使用websocket消息)

发布于:1月以前  |  101次阅读  |  详细内容 »

探索 Serverless 中的前端开发模式

最近关于 Serverless 的讨论越来越多。看似与前端关系不大的 Serverless,其实早已和前端有了渊源,并且将对前端开发模式产生变革性的影响。本文主要就根据个人理解和总结,从前端开发模式的演进、基于 Serverless 的前端开发案例以及 Serverless 开发最佳实践等方面,与大家探讨 Serverless 中的前端开发模式。本人也有幸在 QCon2019 分享了这一主题。

发布于:1月以前  |  132次阅读  |  详细内容 »

前端需要了解的9种设计模式

设计模式是对软件设计开发过程中反复出现的某类问题的通用解决方案。设计模式更多的是指导思想和方法论,而不是现成的代码,当然每种设计模式都有每种语言中的具体实现方式。学习设计模式更多的是理解各种模式的内在思想和解决的问题,毕竟这是前人无数经验总结成的最佳实践,而代码实现则是对加深理解的辅助。

发布于:1月以前  |  113次阅读  |  详细内容 »

为什么你的网页需要 CSP?

内容安全策略(CSP)是一个 HTTP Header,CSP 通过告诉浏览器一系列规则,严格规定页面中哪些资源允许有哪些来源, 不在指定范围内的统统拒绝。

发布于:1月以前  |  103次阅读  |  详细内容 »

10 种跨域解决方案(附终极方案)

嗯。又来了,又说到跨域了,这是一个老生常谈的话题,以前我觉得这种基础文章没有什么好写的,会想着你去了解底层啊,不是很简单吗。但是最近在开发一个 「vscode 插件」 发现,当你刚入门一样东西的时候,你不会想这么多,因为你对他不熟悉,当你遇到不会的东西,你就是想先找到解决方案,然后通过这个解决方案再去深入理解。

发布于:1月以前  |  166次阅读  |  详细内容 »

移动 Web 最佳实践(干货长文,建议收藏)

笔者在公司用 web 技术开发移动端应用已经有一年多的时间了,开始主要以 vue 技术栈配合 native 为主,目前演进成 vue + react native 技术架构,vue 主要负责开发 OA 业务,比如报销、出差、crm 等等,react native 主要负责即时通信部分,是在 mattermost-mobile的基础上修改的(mattermost 是一个开源的即时通讯方案)。

发布于:1月以前  |  119次阅读  |  详细内容 »

不可错过的实用前端工具

给大家整理了 25 个前端相关的学习网站和一些靠谱的小工具,包括一些小游戏、教程、社区网站和博客,以及一些资源网站,希望可以帮助到大家!

发布于:1月以前  |  110次阅读  |  详细内容 »

理解 WebView

我们通常使用 Chrome, Firefox, Safari, Internet Explorer 和 Edge 等浏览器来浏览网页。你也许正在使用其中一种浏览器阅读本文!虽然浏览器对于访问互联网内容的任务来说非常流行,它们还有一些我们从未过多关注过的竞争对手。这些竞争对手以 WebView 的形式被我们所熟知。这片文章将讲解 WebView 的神秘之处以及为什么它这么棒。

发布于:1月以前  |  116次阅读  |  详细内容 »

Facebook 前端技术栈重构分享

当我们考虑如何构建一个新的网络应用—一个为现代浏览器设计的、具有用户对Facebook(我们已知的)所有期望的功能,我们现有的技术栈无法支持我们所需要的类似于桌面应用的感觉和性能。

发布于:1月以前  |  112次阅读  |  详细内容 »

最多阅读

为Electron程序添加运行时日志 1年以前  |  4909次阅读
初探 React 组件 1年以前  |  2183次阅读
wordpress标签页的制作 1年以前  |  2071次阅读
Node.js下通过配置host访问URL 1年以前  |  2014次阅读
js动态创建类和实例化 1年以前  |  2000次阅读
500行PHP代码搞定富文本安全过滤 1年以前  |  1970次阅读
22个HTML5的初级技巧 1年以前  |  1921次阅读
使用 SRI 增强 localStorage 代码安全 1年以前  |  1912次阅读
浅谈浏览器的原生拖拽事件 1年以前  |  1882次阅读
第三版主题上线 1年以前  |  1881次阅读
CSS清除浮动 1年以前  |  1869次阅读
2014年度总结 1年以前  |  1819次阅读
【译】V8 团队眼中的 ES6、ES7及未来 1年以前  |  1811次阅读
利用服务器返回header来传输数据 1年以前  |  1803次阅读
获取元素的计算的样式 1年以前  |  1798次阅读