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

发表于 5年以前  | 总阅读数:4299 次

最近碰到的一个需求需要借助字符串的快速搜索算法,于是看了一些有关字符串搜索的一些算法,最先看的是 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字符串搜索算法

 相关推荐

刘强东夫妇:“移民美国”传言被驳斥

京东创始人刘强东和其妻子章泽天最近成为了互联网舆论关注的焦点。有关他们“移民美国”和在美国购买豪宅的传言在互联网上广泛传播。然而,京东官方通过微博发言人发布的消息澄清了这些传言,称这些言论纯属虚假信息和蓄意捏造。

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

博主曝三大运营商,将集体采购百万台华为Mate60系列

日前,据博主“@超能数码君老周”爆料,国内三大运营商中国移动、中国电信和中国联通预计将集体采购百万台规模的华为Mate60系列手机。

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

ASML CEO警告:出口管制不是可行做法,不要“逼迫中国大陆创新”

据报道,荷兰半导体设备公司ASML正看到美国对华遏制政策的负面影响。阿斯麦(ASML)CEO彼得·温宁克在一档电视节目中分享了他对中国大陆问题以及该公司面临的出口管制和保护主义的看法。彼得曾在多个场合表达了他对出口管制以及中荷经济关系的担忧。

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

抖音中长视频App青桃更名抖音精选,字节再发力对抗B站

今年早些时候,抖音悄然上线了一款名为“青桃”的 App,Slogan 为“看见你的热爱”,根据应用介绍可知,“青桃”是一个属于年轻人的兴趣知识视频平台,由抖音官方出品的中长视频关联版本,整体风格有些类似B站。

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

威马CDO:中国每百户家庭仅17户有车

日前,威马汽车首席数据官梅松林转发了一份“世界各国地区拥车率排行榜”,同时,他发文表示:中国汽车普及率低于非洲国家尼日利亚,每百户家庭仅17户有车。意大利世界排名第一,每十户中九户有车。

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

研究发现维生素 C 等抗氧化剂会刺激癌症生长和转移

近日,一项新的研究发现,维生素 C 和 E 等抗氧化剂会激活一种机制,刺激癌症肿瘤中新血管的生长,帮助它们生长和扩散。

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

苹果据称正引入3D打印技术,用以生产智能手表的钢质底盘

据媒体援引消息人士报道,苹果公司正在测试使用3D打印技术来生产其智能手表的钢质底盘。消息传出后,3D系统一度大涨超10%,不过截至周三收盘,该股涨幅回落至2%以内。

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

千万级抖音网红秀才账号被封禁

9月2日,坐拥千万粉丝的网红主播“秀才”账号被封禁,在社交媒体平台上引发热议。平台相关负责人表示,“秀才”账号违反平台相关规定,已封禁。据知情人士透露,秀才近期被举报存在违法行为,这可能是他被封禁的部分原因。据悉,“秀才”年龄39岁,是安徽省亳州市蒙城县人,抖音网红,粉丝数量超1200万。他曾被称为“中老年...

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

亚马逊股东起诉公司和贝索斯,称其在购买卫星发射服务时忽视了 SpaceX

9月3日消息,亚马逊的一些股东,包括持有该公司股票的一家养老基金,日前对亚马逊、其创始人贝索斯和其董事会提起诉讼,指控他们在为 Project Kuiper 卫星星座项目购买发射服务时“违反了信义义务”。

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

苹果上线AppsbyApple网站,以推广自家应用程序

据消息,为推广自家应用,苹果现推出了一个名为“Apps by Apple”的网站,展示了苹果为旗下产品(如 iPhone、iPad、Apple Watch、Mac 和 Apple TV)开发的各种应用程序。

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

特斯拉美国降价引发投资者不满:“这是短期麻醉剂”

特斯拉本周在美国大幅下调Model S和X售价,引发了该公司一些最坚定支持者的不满。知名特斯拉多头、未来基金(Future Fund)管理合伙人加里·布莱克发帖称,降价是一种“短期麻醉剂”,会让潜在客户等待进一步降价。

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

光刻机巨头阿斯麦:拿到许可,继续对华出口

据外媒9月2日报道,荷兰半导体设备制造商阿斯麦称,尽管荷兰政府颁布的半导体设备出口管制新规9月正式生效,但该公司已获得在2023年底以前向中国运送受限制芯片制造机器的许可。

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

马斯克与库克首次隔空合作:为苹果提供卫星服务

近日,根据美国证券交易委员会的文件显示,苹果卫星服务提供商 Globalstar 近期向马斯克旗下的 SpaceX 支付 6400 万美元(约 4.65 亿元人民币)。用于在 2023-2025 年期间,发射卫星,进一步扩展苹果 iPhone 系列的 SOS 卫星服务。

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

𝕏(推特)调整隐私政策,可拿用户发布的信息训练 AI 模型

据报道,马斯克旗下社交平台𝕏(推特)日前调整了隐私政策,允许 𝕏 使用用户发布的信息来训练其人工智能(AI)模型。新的隐私政策将于 9 月 29 日生效。新政策规定,𝕏可能会使用所收集到的平台信息和公开可用的信息,来帮助训练 𝕏 的机器学习或人工智能模型。

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

荣耀CEO谈华为手机回归:替老同事们高兴,对行业也是好事

9月2日,荣耀CEO赵明在采访中谈及华为手机回归时表示,替老同事们高兴,觉得手机行业,由于华为的回归,让竞争充满了更多的可能性和更多的魅力,对行业来说也是件好事。

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

AI操控无人机能力超越人类冠军

《自然》30日发表的一篇论文报道了一个名为Swift的人工智能(AI)系统,该系统驾驶无人机的能力可在真实世界中一对一冠军赛里战胜人类对手。

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

AI生成的蘑菇科普书存在可致命错误

近日,非营利组织纽约真菌学会(NYMS)发出警告,表示亚马逊为代表的电商平台上,充斥着各种AI生成的蘑菇觅食科普书籍,其中存在诸多错误。

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

社交媒体平台𝕏计划收集用户生物识别数据与工作教育经历

社交媒体平台𝕏(原推特)新隐私政策提到:“在您同意的情况下,我们可能出于安全、安保和身份识别目的收集和使用您的生物识别信息。”

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

国产扫地机器人热销欧洲,国产割草机器人抢占欧洲草坪

2023年德国柏林消费电子展上,各大企业都带来了最新的理念和产品,而高端化、本土化的中国产品正在不断吸引欧洲等国际市场的目光。

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

罗永浩吐槽iPhone15和14不会有区别,除了序列号变了

罗永浩日前在直播中吐槽苹果即将推出的 iPhone 新品,具体内容为:“以我对我‘子公司’的了解,我认为 iPhone 15 跟 iPhone 14 不会有什么区别的,除了序(列)号变了,这个‘不要脸’的东西,这个‘臭厨子’。

发布于:1年以前  |  398次阅读  |  详细内容 »
 相关文章
为Electron程序添加运行时日志 5年以前  |  20374次阅读
Node.js下通过配置host访问URL 5年以前  |  5895次阅读
用 esbuild 让你的构建压缩性能翻倍 4年以前  |  5794次阅读
 目录